Review

Return to Course Outline

Previous Lecture

Things you wanted to talk about...

Sample Exam Question 4

Pairwise intersecting sets in a family of at least 3; prove that the intersection of all the sets in the family is empty.

The heart of the proof is to assume that the intersection is non-empty, from which it follows that some value x is in all sets, and particularly in sets a₁, a₂, and a₃. But that contradicts the part of the definition that says no two sets with non-consecutive index numbers have any elements in common.

Sample Exam Question 2

Why is function f a surjection onto the Math 239 numbers?

Because it essentially is the definition of the Math 239 numbers: if there were a Math 239 number that weren’t the image of some n under f then that number would, by definition, not be a Math 239 number. So all Math 239 numbers are images of something under f.

Sample Exam Question 5

How does the induction step work?

It needs to show that if f(k) = 1, then f(k+1) also equals 1. So it starts by assuming that for some non-negative integer k, f(k) = 1. Then it figures out what f(k+1) would be, using the definition of f. Since k is a non-negative integer, k ≥ 0 and so k+1 > 0, which means the second part of the definition of f applies, and f(k+1) = f(k)⁵. This is 1, since f(k) = 1.

Cardinality of Cartesian Products

Question 1 from problem set 9.

I’d do the proof by induction, somewhat like this:

Theorem: If A and B are subsets of some universal set, then card(A × B ) = card(A) × card(B).

Proof: We prove by induction on card(A) that if A and B are subsets of some universal set, then card(A × B ) = card(A) × card(B).

For the basis step, let card(A) = 0, i.e., A be the empty set. We showed in class that ∅ × B = ∅ for all sets B, so card(A × B) = 0 = card(A) × card(B).

For the induction step, we need to show that if card(A) = k for some non-negative integer k implies that card(A × B) = k card(B), then card(A) = k+1 implies that card(A × B ) = (k+1) card(B). So suppose A = { a₁, a₂, ..., a_k, a_k+1 } which can be rewritten as { a₁, a₂, ..., a_k } ∪ { a_k+1 }. Then, because Cartesian product distributes over union,

We can now use three observations to calculate card(A × B ): First, card {a₁, a₂, ..., a_k} × B = k card(B) by the induction hypothesis. Second, because {a_k+1} × B pairs a_k+1 with each element of B, card( {a_k+1} × B ) = card(B). Finally, the cardinality of a union of two sets is the sum of those sets’ cardinalities, as long as the sets have no elements in common; that’s the case here because every pair in {a₁, a₂, ..., a_k} × B has a different first coordinate from every pair in {a_k+1} × B. Based on these observations,

Having now established a basis step and an induction step, it follows by the principle of mathematical induction that if A and B are subsets of some universal set, then card(A × B) = card(A) × card(B). QED.

Indexed Families of Sets

Notation

The main piece is the family of sets. This is really a set of sets, and you can think of it that way if it’s easier than “family.”

Each set in the family is identified by a label. This is often a natural number, but doesn’t have to be, for instance if the family isn’t countable, or something besides a natural number is more convenient in a particular context.

So to define exactly what the labels can be for a particular family, there is also an “indexing set,” Λ, that lists them.

A Typical Proof

Proof techniques that work with other sets also work with indexed families, e.g., element chasing.

For example, consider the book’s proof that the intersection of all sets in a family is a subset of each individual member.

That proof uses element chasing, and so starts by assuming that x is a generic member of the intersection. That in turn means that x is a member of every member of the family, and in particular of generic member A_β. Thus everything that’s in the intersection is also in each member, so the intersection is a subset of each member.

Countably Infinite Sets

Some examples of proofs that sets are countably infinite.

First Example

The set of reciprocals of the natural numbers is countably infinite. Call that set R, defined formally as

To prove that a set is countably infinite, show a bijection between it and the set of natural numbers.

In this case, try f(n) = 1/n as that bijection.

If 1/n = 1/m then n = m, so f is an injection.

Further for each reciprocal, say 1/x where x is a natural, 1/(1/x)) = x should be a pre-image for 1/x. And indeed f(x) = 1/x, so every reciprocal is the image of something under f, i.e., f is a surjection.

Thus f is a bijection from ℕ to R.

Second Example

Now consider

I claim this set is also countably infinite. This is a more interesting claim, because the existence of the countably infinite S_k sets means that any reciprocal has an infinite number of smaller reciprocals, or, colloquially, no matter how small a reciprocal you make, you’re still infinitely far from 0.

Once again, to prove that S_k is countably infinite, find a bijection between it and ℕ.

Suggestion: f(n) = 1/(n+k)

To see that this is a surjection, let x be any member of S_k. i.e., x = 1/(k+y) for some natural y. We want to make sure that x has a pre-image under f, i.e., that for some natural number n, f(n) = x. So since f(n) = 1/(n+k) and we want this to equal 1/(k+y), it seems that n = y should be y’s pre-image. And indeed we can check by calculating f(y) = 1/(y+k) = x. Therefore f is a surjection.

It’s easy to show that f is an injection also.

Thus, because we have found a bijection between S_k and ℕ, we have shown that S_k is countably infinite.

(No Next Lecture)