Set Theory Lecture 3 Flashcards
What is a partial order?
A relation that is reflexive, transitive, and anti-symmetric.
What are the three properties of a partial order?
- Reflexivity: x R x 2. Transitivity: x R y ∧ y R z → x R z 3. Anti-symmetry: x R y ∧ y R x → x = y.
Is ≤ a partial order on natural numbers?
Yes, because it satisfies reflexivity, transitivity, and anti-symmetry.
What is the power set of {1,2}?
P({1,2}) = {∅, {1}, {2}, {1,2}}.
Is ⊆ a partial order on P(V)?
Yes, because subset inclusion is reflexive, transitive, and anti-symmetric.
What is a linear (or total) order?
A partial order where every pair of elements is comparable.
Is ≤ on natural numbers a total order?
Yes, because for all m, n, either m ≤ n or n ≤ m.
Is ⊆ on P({1,2}) a total order?
No, because {1} and {2} are not comparable.
What is a strict partial order?
A relation that is transitive, anti-symmetric, and irreflexive.
How is a strict partial order related to a partial order?
It is derived by removing all reflexive pairs from the partial order.
What does a Hasse diagram represent?
A simplified graph representation of a partial order.
What is omitted in a Hasse diagram?
Reflexive and transitive edges.
How do elements appear in a Hasse diagram?
Higher elements are greater, and lower elements are smaller.
What is the Cartesian order?
A × B is ordered as ⟨a1,b1⟩ ≤ ⟨a2,b2⟩ iff a1 ≤ a2 and b1 ≤ b2.
What is the lexicographic order?
⟨a1,b1⟩ ≤ ⟨a2,b2⟩ iff (a1 < a2) or (a1 = a2 and b1 ≤ b2).
Is Cartesian order always a total order?
No, it is only a partial order.
Is lexicographic order always a total order?
Yes, if the original orders are total.
Which order is used in dictionaries?
Lexicographic order.
What is a minimal element in a partially ordered set?
An element m such that no element is strictly smaller than m.
What is a maximal element in a partially ordered set?
An element m such that no element is strictly greater than m.
What is the difference between minimal and smallest elements?
A minimal element has no smaller elements, but there can be multiple. The smallest element is unique.
What is the difference between maximal and largest elements?
A maximal element has no larger elements, but there can be multiple. The largest element is unique.
What is Theorem 1 about maximal elements?
Every maximum of a set is a maximal element.
What is Theorem 2 about maximal elements?
If a set has a maximum, it is the only maximal element.
What is an example of a largest element?
In the power set P({a,b,c}), the largest element is {a,b,c}.
What is an example of a smallest element?
In the power set P({a,b,c}), the smallest element is ∅.
What is an example of minimal elements?
In P({a,b,c}) \ {∅, {c}}, the minimal elements are {a} and {b}.
What is an example of maximal elements?
In P({a,b,c}) \ {∅, {c}}, the maximal element is {a,b,c}.
