[FrontPage] [TitleIndex] [WordIndex

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.

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.

2014-06-17 11:57