Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

2014-06-17 11:57