3Posets and Zorn's lemma
II Logic and Set Theory
3.1 Partial orders
Definition (Partial ordering (poset)). A partially ordered set or poset is a pair
(X, ≤), where X is a set and ≤ is a relation on X that satisfies
(i) x ≤ x for all x ∈ X (reflexivity)
(ii) x ≤ y and y ≤ z ⇒ x ≤ z (transitivity)
(iii) x ≤ y and y ≤ x ⇒ x = y (antisymmetry)
We write
x < y
to mean
x ≤ y
and
x
=
y
. We can also define posets in terms
of <:
(i) x < x for all x ∈ X (irreflexive)
(ii) x < y and y < z ⇒ x < z (transitive)
Example.
(i) Any total order is (trivially) a partial order.
(ii) N with “x ≤ y” if x | y is a partial order.
(iii) P(S) with ⊆ for any set S is a partial order.
(iv) Any subset of P(S) with inclusion is a partial order.
(v) We can use a diagram
a
b
c
d
e
Where “above” means “greater”. So
a ≤ b ≤ c
,
a ≤ d ≤ e
, and what
follows by transitivity. This is a Hasse diagram.
Definition (Hasse diagram). A Hasse diagram for a poset
X
consists of
a drawing of the points of
X
in the plane with an upwards line from
x
to
y if y covers x:
Definition (Cover). In a poset,
y
covers
x
if
y > x
and no
z
has
y > z > x
.
Hasse diagrams can be useful — e.g. N, or useless, e.g. Q.
(vi)
The following example shows that we cannot assign “heights” or “ranks”
to posets:
a
d
b
e
c
(vii) We can also have complicated structures:
a
b
c
d
e
(viii)
Or the empty poset (let
X
be any set and nothing is less than anything
else).
While there are many examples of posets, all we care about are actually
power sets and their subsets only.
Often, we want to study subsets of posets. For example, we might want to
know if a subset has a least element. All subsets are equal, but some subsets are
more equal than others. A particular interesting class of subsets is a chain.
Definition (Chain and antichain). In a poset, a subset
S
is a chain if it is
totally ordered, i.e. for all
x
,
y
,
x ≤ y
or
y ≤ x
. An antichain is a subset in
which no two things are related.
Example. In (N, |), 1, 2, 4, 8, 16, ··· is a chain.
In (v), {a, b, c} or {a, c} are chains.
R is a chain in R.
Definition (Upper bound and supremum). For
S ⊂ X
, an upper bound for
S
is
an x ∈ X such that ∀y ∈ S : x ≥ y.
x ∈ X
is a least upper bound, supremum or join of
S
, written
x
=
sup S
or
x
=
W
S
, if
x
is an upper bound for
S
, and for all
y ∈ X
, if
y
is an upper bound,
then y ≥ x.
Example.
(i) In R, {x : x <
√
2} has an upper bound 7, and has a supremum
√
2.
(ii)
In (v) above, consider
{a, b}
. Upper bounds are
b
and
c
. So
sup
=
b
.
However, {b, d} has no upper bound!
(iii) In (vii), {a, b} has upper bounds c, d, e, but has no least upper bound.
Definition (Complete poset). A poset
X
is complete if every
S ⊆ X
has a
supremum. In particular, it has a greatest element (i.e.
x
such that
∀y
:
x ≥ y
),
namely sup X, and least element (i.e. x such that ∀y : x ≤ y), namely sup ∅.
It is very important to remember that this definition does not require that
the subset
S
is bounded above or non-empty. This is different from the definition
of metric space completeness.
Example.
– R is not complete because R itself has no supremum.
–
[0
,
1] is complete because every subset is bounded above, and so has a least
upper bound. Also, ∅ has a supremum of 0.
– (0, 1) is not complete because (0, 1) has no upper bound.
– P
(
S
) for any
S
is always complete, because given any
{A
i
:
i ∈ A}
, where
each A
i
⊆ S,
S
A
i
is its supremum.
Now we are going to derive fixed-point theorems for complete posets. We
start with a few definitions:
Definition (Fixed point). A fixed point of a function
f
:
X → X
is an
x
such
that f(x) = x.
Definition (Order-preserving function). For a poset
X
,
f
:
X → X
is order-
preserving of x ≤ y ⇒ f(x) ≤ f(y).
Example.
– On N, x 7→ x + 1 is order-preserving
– On Z, x 7→ x − 1 is order-preserving
–
On (0
,
1),
x 7→
1+x
2
is order-preserving (this function halves the distance
from x to 1).
– On P(S), let some fixed i ∈ S. Then A 7→ A ∪ {i} is order-preserving.
Not every order-preserving
f
has a fixed point (e.g. first two above). However,
we have
Theorem (Knaster-Tarski fixed point theorem). Let
X
be a complete poset,
and f : X → X be a order-preserving function. Then f has a fixed point.
Proof.
To show that
f
(
x
) =
x
, we need
f
(
x
)
≤ x
and
f
(
x
)
≥ x
. Let’s not be
too greedy and just want half of it:
Let
E
=
{x
:
x ≤ f
(
x
)
}
. Let
s
=
sup E
. We claim that this is a fixed point,
by showing f(s) ≤ s and s ≤ f(s).
To show
s ≤ f
(
s
), we use the fact that
s
is the least upper bound. So if
we can show that
f
(
s
) is also an upper bound, then
s ≤ f
(
s
). Now let
x ∈ E
.
So
x ≤ s
. Therefore
f
(
x
)
≤ f
(
s
) by order-preservingness. Since
x ≤ f
(
x
) (by
definition of E) x ≤ f(x) ≤ f(s). So f(s) is an upper bound.
To show
f
(
s
)
≤ s
, we simply have to show
f
(
s
)
∈ E
, since
s
is an upper
bound. But we already know
s ≤ f
(
s
). By order-preservingness,
f
(
s
)
≤ f
(
f
(
s
)).
So f(s) ∈ E by definition.
While this proof looks rather straightforward, we need to first establish that
s ≤ f
(
s
), then use this fact to show
f
(
s
)
≤ s
. If we decided to show
f
(
s
)
≤ s
first, then we would fail!
The very typical application of Knaster-Tarski is the quick, magic proof of
Cantor-Shr¨oder-Bernstein theorem.
Corollary (Cantor-Schr¨oder-Bernstein theorem). Let
A, B
be sets. Let
f
:
A →
B and g : B → A be injections. Then there is a bijection h : A → B.
Proof.
We try to partition
A
into
P
and
Q
, and
B
into
R
and
S
, such that
f(P ) = R and g(S) = Q. Then we let h = f on R and g
−1
on Q.
Q
P
S
R
f
g
Since S = B \ R and Q = A \ P , so we want
P = A \g(B \f(P ))
Since the function
P 7→ A \ g
(
B \ f
(
P
)) from
P
(
A
) to
P
(
A
) is order-preserving
(and P(a) is complete), the result follows.
The next result we have is Zorn’s lemma. The main focus of Zorn’s lemma is
on maximal elements.
Definition (Maximal element). In a poset
X
,
x ∈ X
is maximal if no
y ∈ X
has y > x.
Caution! Under no circumstances confuse a maximal element with a maximum
element, except under confusing circumstances! A maximum element is defined
as an
x
such that all
y ∈ X
satisfies
y ≤ x
. These two notions are the same in
totally ordered sets, but are very different in posets.
Example. In the poset
a
b
c
d
e
c and e are maximal.
Not every poset has a maximal element, e.g.
N, Q, R
. In each of these, not
only are they incomplete. They have chains that are not bounded above.
Theorem (Zorn’s lemma). Assuming Axiom of Choice, let
X
be a (non-empty)
poset in which every chain has an upper bound. Then it has a maximal element.
Note that “non-empty” is not a strictly necessary condition, because if
X
is
an empty poset, then the empty chain has no upper bound. So the conditions
can never be satisfied.
The actual proof of Zorn’s lemma is rather simple, given what we’ve had so
far. We “hunt” for the maximal element. We start with
x
0
. If it is maximal,
done. If not, we find a bigger
x
1
. If
x
1
is maximal, done. Otherwise, keep go on.
If we never meet a maximal element, then we have an infinite chain. This
has an upper bound
x
ω
. If this is maximal, done. If not, find
x
ω+1
> x
ω
. Keep
going on.
We have not yet reached a contradiction. But suppose we never meet a
maximal element. If
X
is countable, and we can reach
x
ω
1
, then we have found
uncountably many elements in a countable set, which is clearly nonsense!
Since the ordinals can be arbitrarily large (Hartogs’ lemma), if we never
reach a maximal element, then we can get find more elements that X has.
Proof.
Suppose not. So for each
x ∈ X
, we have
x
′
∈ X
with
x
′
> x
. We denote
the-element-larger-than-x by x
′
.
We know that each chain C has an upper bound, say u(C).
Let γ = γ(X), the ordinal-larger-than-X by Hartogs’ lemma.
We pick x ∈ X, and define x
α
for α < γ recursively by
– x
0
= x
– x
α
+
= x
′
α
– x
λ
= u({x
α
: α < λ})
′
for non-zero limit λ
Of course, we have to show that
{x
α
:
α < λ}
is a chain. This is trivial by
induction.
Then α 7→ x
α
is an injection from γ → X. Contradiction.
Note that we could as well have defined
x
λ
=
u
(
{x
α
:
α < λ}
), and we can
easily prove it is still an injection. However, we are lazy and put the “prime”
just to save a few lines of proof.
This proof was rather easy. However, this is only because we are given
ordinals, definition by recursion, and Hartogs’ lemma. Without these tools, it is
rather difficult to prove Zorn’s lemma.
A typical application of Zorn’s lemma is: Does every vector space have a
basis? Recall that a basis of
V
is a subset of
V
that is linearly independent (no
finite linear combination = 0) and spanning (ie every
x ∈ V
is a finite linear
combination from it).
Example.
– Let V be the space of all real polynomials. A basis is {1, x, x
2
, x
3
, ···}.
–
Let
V
be the space of all real sequences. Let e
i
be the sequence with all
0 except 1 in the
i
th place. However,
{
e
i
}
is not a basis, since 1
,
1
, ···
cannot be written as a finite linear combination of them. In fact, there is
no countable basis (easy exercise). It turns out that there is no “explicit”
basis.
–
Take
R
as a vector space over
Q
. A basis here, if exists, is called a Hamel
basis.
Using Zorn’s lemma, we can prove that the answer is positive.
Theorem. Every vector space V has a basis.
Proof. We go for a maximal linearly independent subset.
Let
X
be the set of all linearly independent subsets of
V
, ordered by inclusion.
We want to find a maximal
B ∈ X
. Then
B
is a basis. Otherwise, if
B
does
not span
V
, choose
x ∈ span B
. Then
B ∪ {x}
is independent, contradicting
maximality.
So we have to find such a maximal
B
. By Zorn’s lemma, we simply have to
show that every chain has an upper bound.
Given a chain
{A
i
:
i ∈ I}
in
X
, a reasonable guess is to try the union. Let
A
=
S
A
i
. Then
A ⊆ A
i
for all
i
, by definition. So it is enough to check that
A ∈ X, i.e. is linearly independent.
Suppose not. Say
λ
1
x
1
+
···
+
λ
n
x
n
= 0 for some
λ
1
···λ
n
scalars (not all
0). Suppose
x
1
∈ A
i
1
, ···x
n
∈ A
i
n
for some
i
1
, ···i
n
∈ I
. Then there is some
A
i
m
that contains all
A
i
k
, since they form a finite chain. So
A
i
m
contains all
x
i
.
This contradicts the independence of A
i
m
.
Hence by Zorn’s lemma, X has a maximal element. Done.
Another application is the completeness theorem for propositional logic when
P , the primitives, can be uncountable.
Theorem (Model existence theorem (uncountable case)). Let
S ⊆ L
(
P
) for any
set of primitive propositions P . Then if S is consistent, S has a model.
Proof.
We need a consistent
¯
S ⊆ S
such that
∀t ∈ L
,
t ∈
¯
S
or
¬t ∈
¯
S
. Then we
have a valuation
v
(
t
) =
(
1 t ∈
¯
S
0 t ∈
¯
S
, as in our original proof for the countable
case.
So we seek a maximal consistent
¯
S ⊇ S
. If
¯
S
is maximal, then if
t ∈
¯
S
, then
we must have
¯
S ∪ {t}
inconsistent, i.e.
¯
S ∪ {t} ⊢ ⊥
. By deduction theorem, this
means that
¯
S ⊢ ¬t
. By maximality, we must have
¬t ∈
¯
S
. So either
t
or
¬t
is in
¯
S.
Now we show that there is such a maximal
¯
S
. Let
X
=
{T ⊆ L
:
T is consistent , T ⊇ S}
. Then
X
=
∅
since
S ∈ X
. We show that any
non-empty chain has an upper bound. An obvious choice is, again the union.
Let
{T
i
:
i ∈ I}
be a non-empty chain. Let
T
=
S
T
i
. Then
T ⊇ T
i
for all
i
.
So to show that T is an upper bound, we have to show T ∈ X.
Certainly,
T ⊇ S
, as any
T
i
contains
S
(and the chain is non-empty). So we
want to show
T
is consistent. Suppose
T ⊢ ⊥
. So we have
t
1
, ··· , t
n
∈ T
with
{t
1
, ··· , t
n
} ⊢ ⊥
, since proofs are finite. Then some
T
k
contains all
t
i
since
T
i
are nested. So
T
k
is inconsistent. This is a contradiction. Therefore
T
must be
consistent.
Hence by Zorn’s lemma, there is a maximal element of X.
This proof is basically the same proof that every vector space has a basis! In
fact, most proofs involving Zorn’s lemma are similar.