5Set theory
II Logic and Set Theory
5.2 Properties of ZF
Now, what does V look like? We start with the following definition:
Definition (Transitive set). A set
x
is transitive if every member of a member
of x is a member of x:
(∀y)((∃z)(y ∈ z ∧ z ∈ x) ⇒ y ∈ x).
This can be more concisely written as
S
x ⊆ x
, but is very confusing and
impossible to understand!
This notion seems absurd — and it is. It is only of importance in the context
of set theory and understanding what
V
looks like. It is an utterly useless notion
in, say, group theory.
Example.
{∅, {∅}}
is transitive. In general, for any
n ∈ ω
,
n
is transitive.
ω
is
also transitive.
Lemma. Every x is contained in a transitive set.
Note that this is a theorem of
ZF
, i.e. it officially means: let (
V, ∈
) be a
model of ZF. Then in V , <stuff above>. Equivalently, ZF ⊢ <stuff above>.
We know that any intersection of transitive sets is transitive. So this lemma
will tell us that
x
is contained in a least transitive set, called the transitive
closure of x, or T C(x).
Proof.
We’d like to form “
x ∪
(
S
x
)
∪
(
SS
x
)
∪
(
SSS
x
)
∪ ···
”. If this makes
sense, then we are done, since the final product is clearly transitive. This will be
a set by the union axiom applied to
{x,
S
x,
SS
x, ···}
, which itself is a set by
replacement applied to
ω
, for the function-class 0
7→ x
, 1
7→
S
x
, 2
7→
SS
x
etc.
Of course we have to show that the above is a function class, i.e. can be
expressed as a first order relation. We might want to write the sentence as:
p(s, t) is (s = 0 ∧ t = x) ∨ (∃u)(∃v)(s = u + 1 ∧ t =
S
v ∧ p(u, v)),
but this is complete nonsense! We are defining p in terms of itself!
The solution would be to use attempts, as we did previously for recursion. We
define “
f
is an attempt” to mean “
f
is a function and
dom f ∈ ω
and
dom f
=
∅
and
f
(0) =
x
and (
∀n
)(
n ∈ ω ∧ n ∈ dom f
)
⇒ f
(
n
) =
S
f
(
n −
1), i.e.
f
is
defined for some natural numbers and meet our requirements when it is defined.
Then it is easy to show that two attempts
f
and
f
′
agree whenever both are
defined. Also,
∀n ∈ ω
, there is an attempt
f
defined for
n
(both by
ω
-induction).
Note that the definition of an attempt is a first-order formula. So our function
class is
p(s, t) is (∃f)(f is an attempt ∧ y ∈ dom f ∧ f(y) = z).
This is a good use of replacement, unlike our example above.
We previously said that Foundation captures the notion “every set is built
out of simpler sets”. What does that exactly mean? If this is true, we should be
able to do induction on it: if p(y) for all y ∈ x, then p(x).
If this sounds weird, think about the natural numbers: everything is built
from 0 using +1. So we can do induction on ω.
Theorem (Principle of
∈
-induction). For each formula
p
, with free variables
t
1
, ··· , t
n
, x,
(∀t
1
) ···(∀t
n
)
[(∀x)((∀y)(y ∈ x ⇒ p(y))) ⇒ p(x)] ⇒ (∀x)(p(x))
Note that officially, p(y) means p[y/x] and p(x) is simply x.
Proof.
Given
t
1
, ··· , t
n
, suppose
¬
(
∀x
)
p
(
x
). So we have some
x
with
¬p
(
x
).
Similar to how we proved regular induction on naturals from the well-ordering
principle (in IA Numbers and Sets), we find a minimal
x
such that
p
(
x
) does
not hold.
While foundation allows us to take the minimal element of a set,
{y
:
¬p
(
y
)
}
need not be a set — e.g. if p(y) is y = y.
Instead, we pick a single
x
such that
¬p
(
x
). Let
u
=
T C
(
{x}
). Then
{y ∈ u
:
¬p
(
y
)
}
=
∅
, since
x ∈ u
. So it has an
∈
-minimal element, say
y
, by
Foundation. Then each
z ∈ y
has
z ∈ u
since
u
is transitive. Hence
p
(
z
) by
minimality of y. But this implies p(y). Contradiction.
Note that here we used the transitive closure to reduce from reasoning about
the whole scary V , to an actual set T C(x). This technique is rather useful.
We have now used Foundation to prove
∈
-induction. It turns out that the
two are in fact equivalent.
Proposition. ∈-induction ⇒ Foundation.
Proof.
To deduce foundation from
∈
-induction, the obvious
p
(
x
) —
x
has an
∈-minimal member, doesn’t work.
Instead, consider p(x) given by
(∀y) x ∈ y ⇒ y has an ∈ -minimal member.
If
p
(
x
) is true, we say
x
is regular. To show that (
∀x
)
p
(
x
), it is enough to show
that: if every y ∈ x is regular, then x is regular.
Given any
z
with
x ∈ z
, we want to show that
z
has an
∈
-minimal member.
If
x
is itself minimal in
z
, then done. Otherwise, then
y ∈ z
for some
y ∈ x
.
But since y ∈ x, y is regular. So z has a minimal element.
Hence all
x
is regular. Since all non-empty sets contain at least one element
(by definition), all sets have ∈-minimal member.
This looked rather simple to prove. However, it is because we had the clever
idea of regularity. If we didn’t we would be stuck for a long time!
Now what about recursion? Can we define f(x) using f(y) for all y ∈ x?
Theorem (
∈
-recursion theorem). Let
G
be a function-class, everywhere defined.
Then there is a function-class
F
such that
F
(
x
) =
G
(
F |
x
) for all
x
. Moreover,
F is unique (cf. definition of recursion on well-orderings).
Note that F |
x
= {(y, F (y)) : y ∈ x} is a set, by replacement.
Proof.
We first show existence. Again, we prove this with attempts. Define “
f
is an attempt” to mean “
f
is a function and
dom f
is transitive and (
∀x
)(
x ∈
dom f ⇒ f(x) = G(f|
x
))”.
Then by simple ∈-induction, we have
(∀x)(∀f
′
)[(f an attempt defined at x∧
f
′
an attempt defined at x) ⇒ f(x) = f
′
(x)].
Also, (
∀x
)(
∃f
)(
f an attempt defined at x
), again by
∈
-induction: suppose for
each
y ∈ x
, there exists an attempt defined at
y
. So there exists a unique attempt
f
y
with domain
T C
(
{y}
). Set
f
=
S
y∈x
f
y
, and let
f
′
=
f
S
{
(
x, G
(
f|
x
)
}
. Then
this is an attempt defined at x.
So we take q(x, y) to be
(∃f)(f is an attempt defined at x with f (x) = y).
Uniqueness follows form ∈-induction.
Note that this is exactly the same as the proof of recursion on well-orderings.
It is just that we have some extra mumbling about transitive closures.
So we proved recursion and induction for
∈
. What property of the relation-
class
∈
(with
p
(
x, y
) defined as
x ∈ y
) did we use? We most importantly used
the Axiom of foundation, which says that
(i) p is well-founded: every set has a p-minimal element.
(ii) p
is local: ie,
{x
:
p
(
x, y
)
}
is a set for each
y
. We needed this to form the
transitive closure.
Definition (Well-founded relation). A relation-class
R
is well-founded if every
set has a R-minimal element.
Definition (Local relation). A relation-class
R
is local if
{x
:
p
(
x, y
)
}
is a set
for each y.
So we will have
Proposition.
p
-induction and
p
-recursion are well-defined and valid for any
p(x, y) that is well-founded and local.
Proof. Same as above.
Note that if
r
is a relation on a set
a
, then
r
is trivially local. So we just
need r to be well-founded. In particular, our induction and recursion theorems
for well-orderings are special cases of this.
We have almost replicated everything we proved for well-orderings, except
for subset collapse. We will now do that.
This is motivated by the following question: can we model a given relation
on a set by ∈?
For example, let
a
=
{b, c, d}
, with
b r c
and
c r d
. Can we find a set
{b
′
, c
′
, d
′
}
such that
b
′
∈ c
′
and
c
′
∈ d
′
? Yes. We can put
b
′
=
∅
,
c
′
=
{∅}
,
d
′
=
{{∅}}
.
Moreover, a
′
= {b
′
, c
′
, d
′
} is transitive.
Definition (Extensional relation). We say a relation
r
on set
a
is extensional if
(∀x ∈ a)(∀y ∈ a)((∀z ∈ a)(z r x ⇔ z r y) ⇒ x = y).
i.e. it obeys the axiom of extension.
Theorem (Mostowski collapse theorem). Let
r
be a relation on a set
a
that is
well-founded and extensional. Then there exists a transitive
b
and a bijection
f
:
a → b
such that (
∀x, y ∈ a
)(
x r y ⇔ f
(
x
)
∈ f
(
y
)). Moreover,
b
and
f
are
unique.
Note that the two conditions “well-founded” and “extensional” are trivially
necessary, since ∈ is both well-founded and extensional.
Proof.
Existence: define
f
on
a
the obvious way —
f
(
x
) =
{f
(
y
) :
y r x}
. This
is well-defined by
r
-recursion, and is a genuine function, not just of a function
class by replacement — it is an image of a.
Let
b
=
{f
(
x
) :
x ∈ a}
(this is a set by replacement). We need to show that
it is transitive and bijective.
By definition of
f
,
b
is transitive, and
f
is surjective as
b
is defined to be the
image of f. So we have to show that f is injective.
We’ll show that (
∀x ∈ a
)(
f
(
y
) =
f
(
x
)
⇒ y
=
x
) for each
x ∈ a
, by
r
-
induction. Given
y ∈ a
, with
f
(
y
) =
f
(
x
), we have
{f
(
t
) :
t r y}
=
{f
(
s
) :
s r y}
by definition of
f
. So
{t
:
t r y}
=
{s
:
s r x}
by the induction hypothesis. Hence
x = y since r is extensional.
So we have constructed such an
b
and
f
. Now we show it is unique: for any
suitable f, f
′
, we have f(x) = f
′
(x) for all x ∈ a by r-induction.
Recall that we defined the ordinals to be the “equivalence class” of all well-
orderings. But this is not a good definition since the ordinals won’t be sets.
Hence we define them (formally) as follows:
Definition (Ordinal). An ordinal is a transitive set, totally ordered by ∈.
This is automatically well-ordered by ∈, by foundation.
Example.
∅
,
{∅}
,
{∅, {∅}}
are ordinals. Any
n ∈ ω
as
n
=
{
0
,
1
, ··· , n −
1
}
, as
well as ω itself, are ordinals.
Why is this a good definition? Mostowski says that each well-ordering is
order-isomorphic to a unique ordinal (using our definition of ordinal above)
— this is its order-type. So here, instead of saying that the ordinals is the
equivalence class of well-orderings, we simply choose one representative of each
equivalence class (given by Mostowski collapse), and call that the ordinal.
For any ordinal
α
,
I
α
=
{β
:
β < α}
is a well-ordering of order-type
α
.
Applying Mostowski collapse, we get α = {β : β < α}. So β < α iff β ∈ α.
So, for example,
α
+
=
α ∪ {α}
, and
sup{α
k
:
k ∈ I}
=
S
{α
i
:
i ∈ I}
,
Set theorists are often write suprema as unions, but this is a totally unhelpful
notation!