equivalence and ordering

≼

means "is a subset of or equal (in the form of a hierarchy where lower elements come before) to" can also be used to denote an ordered relation

ordering

an ordering on a set A is a relation ≼ : A ↔ A that is reflexive, anti-symmetric and transitive

strict ordering

a relation that is irreflexive, anti-symmetric and transitive ≺

identity relations and ordering

if ≼ : A ↔ A is an ordering, then ≼ \ IA is a strict ordering

if ≺ : A ↔ A is a strict ordering then ≺ ∪ IA is an ordering

(the difference between an ordering and a strict ordering is the identity matrix)

hasse diagram

a digraph showing an ordering leaves out some details for simplicity: -no reflexive self-loops -no transitive direct edges if there exists a longer path -no arrows, elements are ordered from bottom to top (so instead of an arrow from A to B, it's a line pointing up to B from A) INC DIAGRAM

comparable and incompatable

for any ordering ≼ on a set A: elements a1, a2 ∈ A are comparable if a1 ≼ a2 ∨ a2 ≼ a1 (they are either the exact same element or they are connected by ordering in the hierarchy, where one branches up to another) otherwise they're incomparable

total/linear ordering

an ordering where every pair of elements is comparable

partial ordering

a non-total ordering can also be used to refer to orderings in general to emphasize they are not necessarily total

equivalence relation

the relation R≡ : A ↔ A is an equivalence if it is reflexive, symmetric and transitive

equivalence class

for equivalence relation R≡ : A ↔ A, for each a ∈ A, the equivalence class is the subset: [a]R≡ = {a1 | aR≡a1} (the set of all elements a is equivalent to)

equivalence classes and relations

if a1∈[a]R≡ , a2∈[a]R≡ then a1R≡a2 (they're connected)

inequality and joint classes

unequal R≡ classes are disjoint this is because an element cannot belong to two equivalence classes at the same time

equivalence classes and partitions

if R≡ : A ↔ A is an equivalence, its equivalence classes form a partition of A