/Solutions

1. Transitivity

Recall von Neumann's definition of the NaturalNumbers in terms of sets: 0 = ∅ = {}, 1 = 0 ∪ { 0 } = ∅ ∪ { ∅ } = { ∅ } = { { } }, 2 = 1 ∪ { 1 } = { ∅ } ∪ { { ∅ } } = { ∅, { ∅ } } = { { }, { { } } }, etc., with the general rule that the successor Sx of each natural number x is defined by Sx = x ∪ { x }.

One useful property of the natural numbers is that if z<y, and y<x, then z<x. We'd like the von Neumann naturals to have this property (called transitivity) when we interpret ∈ as <.

A set x is transitive if, whenever y∈x and z∈y, then z∈x (formally, x is transitive if and only if ∀y∀z z∈y ∧ y∈x ⇒ z∈x).

1. Show that ∅ is transitive.
2. Show that if x is transitive, so is x ∪ { x }.
3. Show that if x is transitive, then ∪x ⊆ x. (Recall that ∪x is defined to be the union of all the elements of x, i.e. { z | ∃y y∈x ∧ z∈y }.)
4. Show that there exists a transitive set x where ∪x ≠ x.
5. Show that there exists a transitive set x where ∪x = x.

2. Pairs and products

Recall the definition of an ordered pair (a,b) = { {a}, {a,b} } and the Cartesian product A×B = { (a,b) | a∈A, b∈B }.

1. Show that if (a,b) = (c,d), then a = c and b = d.
2. Show that if A×B = B×A, then either A = B or at least one of A and B is the empty set.

3. Closure

A set of sets S is closed under union if A∈S and B∈S implies A∪B ∈ S. Similarly, it is closed under intersection if A∈S and B∈S implies A∩B ∈ S. Which of the following sets are closed under union and/or intersection? Justify your answers.

1. The power set ℘(A) of A, where A is any set.

2. The set I = { [a,b] | a,b ∈ ℕ, a≤b }, where [a,b] is defined to be { x∈ℕ | a≤x≤b }. (These sets [a,b] are called closed intervals.)

3. The set H = { [a,∞) | a ∈ ℕ }, where [a,∞) is defined to be { x∈ℕ | a≤x }. (These sets [a,∞) are called half-open intervals.)