Zermelo–Fraenkel Axiomatic Set Theory

Question 1

The first order language we will be working with is as simple as they get: just one binary relation, written as…
In addition,of course we will have the equality relation.

Answer 1

∈, We write x ∈ y instead of (x,y)∈∈!

Question 2

Axiom 1

Answer 2

Extension. If two sets have the same members, they are equal:

Question 3

Axiom 2

Answer 3

Empty Set. There exists a set Ø with no elements:

Question 4

Axiom 3

Answer 4

Pairs. For any sets x, y, there is a set {x, y} whose elements are precisely x and y:

Question 5

Axiom 4

Answer 5

Union. For any set x, there is a set ∪x whose elements are precisely members of members of x:

Question 6

Axiom 5

Answer 6

Power Set. For any sets x, there is a set Px whose elements are precisely the subsets of x:

Question 7

Axiom 6

Answer 7

Infinity. There exists a set which contains Ø, and for each of its elements y it also contains its ‘successor’ y ⋃ {y}:

Question 8

Axiom7

Answer 8

Selection. Let φ = φ(x, p1, . . . , pn) be a first order formula with free variables x,p1,…,pn, and let y be a set. Then, for any fixed p1,…,pn, there exists a set which consists precisely of all x ∈ y such that the formula
φ(x, p1, . . . , pn) holds:

Question 9

Axiom 8

Answer 9

Foundation. Any non-empty set has a member disjoint from it.

Question 10

Axioms 9+10 are to do with functions.
Axiom 9

Answer 10

Replacement. For a first order formula φ = φ(x, y, p) with free variables x, y and p = (p1, . . . , pn), if φ is function-like, then the set of all images of elements of a set z under this function is a set:

Question 11

Axiom 10

Answer 11

Choice. For any function f defined on a set I, and having the property that f(i) is a non-empty set for all i ∈ I there is a function g defined on I with the property that g(i) ∈ f(i) for all i ∈ I:

Question 12

Axiom 1 formula (Extension: if two sets have the same members, they are equal)

Answer 12

^ ∨ ⇒ ∀ ∃ ¬ ∈ ∉ ⇔
(∀x)(∀y)((∀z)(z∈x⇔z∈y)⇒x=y)

Question 13

Axiom 2 formula (Empty Set. There exists a set Ø with no elements)

Answer 13

(∃x)(∀y)(y∉x)

Question 14

Axiom 3 formula (Pairs. For any sets x, y, there is a set {x, y} whose elements are precisely x and y)

Answer 14

(∀x)(∀y)(∃z)(∀t)(t∈z⇔(t=x∨t=y))
There is no assumption that x and y are distinct here. When x = y wewrite just {x}.

Question 15

Axiom 4 formula (Union. For any set x, there is a set ∪x whose elements are precisely members of members of x)

Answer 15

(∀x)(∃y)(∀z)(z∈y⇔(∃t)(t∈x^z∈t))

Question 16

Axiom 5 formula (Power Set. For any sets x, there is a set Px whose elements are precisely the subsets of x)

Answer 16

(∀x)(∃y)(∀z)(z∈y⇔(∀t)(t∈z⇒t∈x))
If we introduce the abbreviation z ⊆ x to mean (∀t)(t∈z⇒t∈x) the axiom then simplifies to (∀x)(∃y)(∀z)(z∈y⇔z ⊆ x)

Question 17

Axiom 6 formula (Infinity. There exists a set which contains Ø, and for each of its elements y it also contains its ‘successor’ y ⋃ {y})

Answer 17

(∃x)(Ø∈x ^ (∀y)(y∈x⇒y∪{y} ∈x)
We cannot say that such a set should be unique by the Extension Axiom, as x may contain further elements.

Question 18

Axiom 7 formula (Selection. Let φ = φ(x, p1, . . . , pn) be a first order formula with free variables x,p1,…,pn, and let y be a set. Then, for any fixed p1,…,pn, there exists a set which consists precisely of all x ∈ y such that the formula φ(x, p1, . . . , pn) holds)

Answer 18

(∀p1)…(∀pn)(∀y)(∃z)(∀x)(x ∈ z ⇔ x ∈ y ^φ(x, p1, . . . , pn)

Unlike the previous axioms, this is not a single formula, but an infinite collection (schema) of formulas. The variables p1, . . . , pn can be regarded as parameters.

Question 19

Axiom 8 formula (Foundation. Any non-empty set has a member disjoint from it.)

Answer 19

(∀x)(x≠Ø⇒((∃y)

Question 20

Axiom 9 formula (Replacement. For a first order formula φ = φ(x, y, p) with free variables x, y and p = (p1, . . . , pn), if φ is function-like, then the set of all images of elements of a set z under this function is a set)

Question 21

Axiom 10 formula (Choice. For any function f defined on a set I, and having the property that f(i) is a non-empty set for all i ∈ I there is a function g defined on I with the property that g(i) ∈ f(i) for all i ∈ I)

Question 22

About the replacement axiom (axiom 9)

Answer 22

Replacement Axiom, intuitively asserts that the image of a set under a function will again be a set. The functions in question will be those defined by a formula. Such a formula would have two free variables, say φ = φ(x, y), and would need to satisfy the property that for every x there exists at most one y such that φpx, yq holds. (Thus we are in fact talking about partial functions