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.

1.1. Solution

1. If x = ∅, then y∈x is never true, so neither is z∈y ∧ y∈x. It follows that z∈y ∧ y∈x ⇒ z∈x holds vacuously for all y and z.
2. Let y be an element of x ∪ { x } and let z∈y. Case 1: y∈x. Then y∈x and z∈y implies z∈x by transitivity of x, which implies z ∈ x ∪ { x }. Case 2: y = x. Then z∈y directly implies z∈x and thus again z ∈ x ∪ { x }.
3. Let z be any element of ∪x; then there exists some y∈x such that z∈y. From the transitivity of x it follows that z∈x. So z ∈ ∪x ⇒ z ∈ x, or equivalently z ⊆ x.
4. The simplest example may be 1 = { ∅ } = { { } }, where ∪1 = ∅ ≠ 1.
5. There are two obvious choices here. The easy one is to observe that ∅ is transitive (all of the nonexistent elements of its nonexistent elements are also elements) and satisfies ∪∅ = ∅. We could also use ℕ; this is also transitive when each natural number is defined von-Neumann as the set of all smaller natural numbers; if x∈y∈ℕ, then x∈ℕ. It also has the property that ∪ℕ = ℕ. This is a little trickier to prove, but the essential idea is that we already know ∪ℕ ⊆ ℕ, so we just need to show that ℕ ⊆ ∪ℕ. To do so we show that for any x∈ℕ, there is some y∈ℕ that contains x (e.g. let y = Sx = x ∪ { x }). But then x∈y∈ℕ implies x ∈ ∪ℕ by the definition of union.

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.

2.1. Solution

1. Suppose (a,b) = (c,d). Then ∩(a,b) = {a} ∩ {a,b} = {a} = ∩(c,d) = {c} ∩ {c,d} = {c} and we have a = c. But if we instead take unions we get ∪(a,b) = {a} ∪ {a,b} = {a,b} = ∪(c,d) = {c,d}. Since b ∈ {a,b} = {c,d} we have that b = d or b = c. In the former case we are done. In the latter case, we have b = c = a, so {c,d} = {a,b} = {a} and d ∈ {b} implies d = b.
2. The easiest proof is probably by contraposition: suppose that A and B are both nonempty and A≠B. Since A≠B there is either some element in A\B or some element in B\A; let's suppose the second case holds (the first case is symmetric). Let x be some element of A and let y be some element of B\A. Then (x,y) ∈ A×B but (x,y) ∉ B×A (since y ∉ A), implying A×B ≠ B×A.

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,b ∈ ℕ }, where [a,∞) is defined to be { x∈ℕ | a≤x }. (These sets [a,∞] are called half-open intervals.)

3.1. Solution

1. For any set A, ℘(A) is closed under both union and intersection. Proof: Let X,Y ∈ ℘(A), i.e., let X,Y ⊆ A. Then both X∪Y and X∩Y are subsets of A, and those contained in ℘(A).
2. The set I is closed under neither intersection nor union. Observe first that each interval [a,b] contains at least the point a (since a≤a≤b), but the intersection between, say, [1,1] and [2,2] is empty. For union, observe that if [a,b] contains two points x≤y (so a≤x≤y≤b), then any point z with x≤z≤y is also in [a,b] (since a≤x≤z≤y≤b). But the union of [1,1] and [3,3] is the set {1,3}, which contains 1 and 3 but not 2.
3. The set H is closed under both intersection and union. For intersection, consider two sets [a,∞) and [b,∞). Then x ∈ [a,∞) ∩ [b,∞) if and only if a≤x and b≤x. If a≤b, this means x is in the intersection only if b≤x (because this implies a≤x as well); we thus have [a,∞) ∩ [b,∞) = [b,∞) in this case. The case b≤a is symmetric; in either case the intersection is [max(a,b),∞) ∈ H. A similar argument shows [a,∞) ∪ [b,∞) = [min(a,b),∞), also in H.