Definitions and Propositions pdf
Part A: Order Theory 1
Partially ordered sets (posets) are the central notion of order theory.
A binary relation ≤ on a set A is called a partial order, if for all x, y, z ∈ A the following conditions hold:
| (Reflexivity) | x ≤ x |
| (Antisymmetry) | x ≤ y and y ≤ x ⇒ x = y |
| (Transitivity) | x ≤ y and y ≤ z ⇒ x ≤ z |
A = (A, ≤) is called a "partially ordered set", in short, a poset.
P = (P, ≤) is a poset. Define x ≤' y as y ≤ x. Then P' = (P, ≤') is also a poset. It is the dual poset to (P, ≤).
Definition A.3 - Extreme Elements, Covers (Neighbors)
A = (A, ≤) is a poset, B ⊆ A a subset of A. A maximal element of B is an element b ∈ B where b < a ⇒ a ∉ B for all a ∈ A. The maximum of B is an element b ∈ B with b' ≤ b for all b' ∈ B.
A minimal element of B is an element b ∈ B where a < b ⇒ a ∉ B for all a ∈ A. The minimum of B is an element b ∈ B with b ≤ b' for all b' ∈ B.
b is called upper cover (neighbor) (or lower cover of b), if a ≤ b and if there is no x ≠ a, b where a ≤ x ≤ b.
Posets A = (A, ≤) can be visualised with the help of so called Hasse diagrams. Elements of A are represented by points or small circles. The line segments between the points reflect the order relation. b is drawn above a and is connected to a by a line segment if and only if b is the upper cover of a. A Hasse diagram stores all information of a poset. Hasse diagrams are not unambiguously defined, i.e. a poset possesses several possible Hasse diagrams (cf. figure A).
Figure A: Two Hasse diagrams of the same posets
Remark A.4 - Interpretation of Partial Order ≤
In the definitions, propositions, and examples used on this site we will henceforth use the standard interpretation of the order relation ≤ and all its related relations, such as <, ≥, >,...
In a poset not all elements need to be ordered. This means that it is possible that the set A contains two elements which cannot be ordered, cannot be compared.
In the following, this fact and other fundamental notions concerning posets will be shown in a slightly more mathematical fashion.
Definition A.5 - Comparable Elements
A = (A, ≤) is a poset. Two elements a, b ∈ A are called comparable, if a ≤ b or b ≤ a. Else they are called incomparable.
Definition A.6 - Chain, Antichain
A chain is a poset in which any two elements are comparable. The poset Cn := (C, ≤) is called an n-chain, if C contains n elements and all of them form a chain under ≤.
An antichain is a subset of pairwise incomparable elements.
Definition A.7 - Subposet, Order-Homomorphism, Order-Embedding, Order-Isomorphism
A poset (B, ≤B) is a subposet of the poset (A, ≤A) if B ⊆ A and ≤B ⊆ ≤A, i.e. for all x, y ∈ B x≤By if and only if x≤Ay.
If (A, ≤A) and (B, ≤B) are posets, then a map f : A → B is called order-preserving or an order-homomorphism if x ≤A y implies f(x) ≤B f(y) for all x, y ∈ A.
If additionally f is injective and f(x) ≤B f(y) implies x ≤A y for all x, y ∈ A, then f is called an order-embedding.
Surjective order-embeddings are called order-isomorphisms.