Order Theory#
Contents#
PARTIAL ORDER
A partial order on a set \(S\) is an arrangement s.t. certain pairs of elements are orderable.
TOTAL ORDER
A total order (or linear order) is a partial order in which any two elements are orderable. In other words, a total order is a binary relation \(\le\) on a set \(S\) which satisfies the following properties for all \(a, b, c \in S\).
Reflexivity
\(a \le a\)
Transitivity
If \(a \le b\) and \(b \le c\) then \(a \le c\)
Antisymmetry
If \(a \le b\) and \(b \le a\) then \(a = b\)
Totality, or strong connectedness
\(a \le b\) or \(b \le a\)
STRICT TOTAL ORDER
A strict total order is a strict partial order in which any two distinct elements are orderable. In other words, a total order is a binary relation \(\lt\) on a set \(S\) which satisfies the following properties for all \(a, b, c \in S\).
Irreflexivity
\(a \not\lt a\)
Transitivity
If \(a \lt b\) and \(b \lt c\) then \(a \lt c\)
Asymmetry
If \(a \lt b\) then \(b \not\lt a\)
Connectedness
If \(a \ne b\) then \(a \lt b\) or \(b \lt a\)
WELL-ORDER
A well-order on a set \(S\) is a total ordering on \(S\) with the property that every non-empty subset of \(S\) has a least element in this ordering.
WELL ORDERING PRINCIPLE
Every non-empty subset \(S\) of positive integers contains a least element: there is some integer \(a \in S\) s.t. \(a \le b\) for all \(b \in S\).
In other words, the set of positive integers does not contain any infinite strictly decreasing sequences.
The well-ordering principle holds for both the set of positive integers \(\mathbb{N}^{+}\) and the set of nonnegative integers \(\mathbb{N}\).
THEOREM
There are no positive integers strictly between \(0\) and \(1\).
Proof by contradiction
Let \(S\) be the set of integers \(x\) s.t. \(0 \lt x \lt 1\).
Suppose that \(S\) is non-empty and that \(n\) is its least element.
\(n \lt 1 \implies n^2 \lt n\)
The square of a positive integer is a positive integer, so \(n^2\) is an integer s.t. \(0 \lt n^2 \lt n \lt 1\).
This is a contradiction of the minimality of \(n\).
Therefore \(S\) is empty.
\(\blacksquare\)
THEOREM
For every positive integer \(n\), the number \(n^2 + n + 1\) is odd.
Proof by contradiction
Let \(S\) be the subset of positive integers \(n\) for which \(n^2 + n + 1\) is even.
Suppose that \(S\) is non-empty and that \(m\) is its least element.
Then \(m - 1 \not\in S\) and so \((m - 1)^2 + (m - 1) + 1\) is odd.
\( \begin{aligned} (m - 1)^2 + (m - 1) + 1 &= m^2 - 2m + 1 + m - 1 + 1 \\ &= m^2 + m + 1 - 2m \\ 2m + (m - 1)^2 + (m - 1) + 1 &= m^2 + m + 1 \\ \end {aligned} \)
\(2m\) is even and \((m - 1)^2 + (m - 1) + 1\) is odd, so their sum \(m^2 + m + 1\) is odd. Contradiction!
Therefore \(S\) is empty.
\(\blacksquare\)
THEOREM
Every positive integer greater than one has a prime divisor.
Proof by contradiction
Let \(S\) be the set of positive integers greater than one with no prime divisor.
Suppose that \(S\) is non-empty and that \(n\) is its least element.
\(n\) cannot be prime since \(n \mid n\) and if \(n\) were prime then \(n\) would be its own prime divisor; therefore \(n\) is composite.
\(n\) must have a divisor \(d\) with \(1 \lt d \lt n\), but then \(d\) must have a prime divisor by the minimality of \(n\). Call it \(p\).
Then \(p \mid d\) but \(d \mid n\), so \(p \mid n\). Contradiction.
Therefore \(S\) is empty.
\(\blacksquare\)
THEOREM
Every positive integer greater than one can be written as the product of one or more primes.
Proof by contradiction
Let \(S\) be the set of positive integers greater than one that cannot be written as the product of primes.
Suppose that \(S\) is non-empty and that \(n\) is its least element.
\(n\) cannot be prime since \(n = n\) and if \(n\) were prime then \(n\) would be its own prime factorization; therefore \(n\) is composite.
\(n = de\) with \(1 \lt d, e \lt n\), but then \(d, e\) must have prime factorizations by the minimality of \(n\).
So \(n\) is a product of product of primes, so a product of primes. Contradiction.
Therefore \(S\) is empty.
\(\blacksquare\)
WELL-ORDERING THEOREM
Every set can be well-ordered.
Resources#
Terms#
[ w ] Antisymmetric Relation
[ w ] Asymmetric Relation
[ w ] Binary Relation
[ w ] Connected Relation
[ w ] Converse Relation
[ w ] Duality
[ w ] Equipollence
[ w ] Equivalence Relation
[ w ] Finitary Relation
[ w ] Greatest Element
[ w ] Hasse Diagram
[ w ] Homogeneous Relation
[ w ] Least Element
[ w ] Linear Relation
[ w ] Order Theory
[ w ] Order Type
[ w ] Partial Order
[ w ] Pre Order
[ w ] Reflexive Relation
[ w ] Relation
[ w ] Serial Relation
[ w ] Symmetric Relation
[ w ] Total Order
[ w ] Total Relation
[ w ] Transitive Closure
[ w ] Transitive Relation
[ w ] Well-Order
[ w ] Well-Ordering Principle
[ w ] Well-Ordering Theorem