note-math

Binary relation := Propositional function $𝑝 : 𝐴 \times 𝐵 \to {0, 1}$ or a subset of $𝐴 \times 𝐵$

when $𝐴 \times 𝐵$ it's called $𝐴, 𝐵$ is independent

$𝑛$ -ary relation is similar

order_(tag)

Propositional function $< : 𝐴^{2} \to {0, 1}$ is an order := $\forall 𝑎, 𝑏, 𝑐 \in 𝐴$

Transitive: $(𝑎 < 𝑏) \land (𝑏 < 𝑐) ⟹ 𝑎 < 𝑐$
Acyclic: $\neg ((𝑎 < 𝑏) \land (𝑏 < 𝑎))$

Can also use the equivalent $\leq$ version

Example

Subset inclusion $\subset$ or inclusion and not equal to $⊊$ is an order

image modified from wiki media about partial order
$<, \leq$ of $ℕ, ℤ, ℚ, ℝ$
Tree diagram

order-comparable_(tag) $𝑎, 𝑎^{'} \in 𝐴$ comparable := $(𝑎 \leq 𝑎^{'}) \lor (𝑎^{'} \leq 𝑎)$

comparable-component_(tag) $𝐴_{𝑖} \subset 𝐴$ is comparable-component := $\forall 𝑎 \in 𝐴, (\exists 𝑎_{𝑖} \in 𝐴_{𝑖}, comparable (𝑎, 𝑎_{𝑖}) ⟹ 𝑎 \in 𝐴_{𝑖})$

Partial order can be decomposed into comparable-components that are not comparable to each other. Imagine two tree diagrams that have no relation

linear-order_(tag) $𝐴$ linear order

$\forall 𝑎, 𝑎^{'} \in 𝐴, comparable (𝑎, 𝑎^{'})$

Intuitively, a linear order has no branches, also called a "chain"

maximal-linear-order_(tag) Maximal linear order chain

let $𝐵 \subset 𝐴$ with $<$ linear order. $𝐵$ is maximal-linear-order := the following definitions are equivalent

$\forall 𝑎 \in 𝐴, (\forall 𝑏 \in 𝐵, comparable (𝑎, 𝑏) ⟹ 𝑎 \in 𝐵)$
$\forall linear-order 𝐶 \subset 𝐴, (𝐵 \subset 𝐶 ⟹ 𝐵 = 𝐶)$

It cannot be used to decompose partial orders. Two maximal linear order chains can have intersecting parts

maximal-linear-order-exists_(tag) maximal-linear-order chain alaways exists

related to #link(<axiom-of-choice>)[]?