# 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).

- Show that ∅ is transitive.
- Show that if x is transitive, so is x ∪ { x }.
- 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 }.)
- Show that there exists a transitive set x where ∪x ≠ x.
- 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 }.

- Show that if (a,b) = (c,d), then a = c and b = d.
- 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.

- The power set ℘(A) of A, where A is any set.
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*.)The set H = { [a,∞) | a ∈ ℕ }, where [a,∞) is defined to be { x∈ℕ | a≤x }. (These sets [a,∞) are called

*half-open intervals*.)