SUNY Geneseo Department of Mathematics
Friday, April 26
Math 239 01
Spring 2019
Prof. Doug Baldwin
SOFIs have started!
Please fill them out. I do read them and apply the feedback where possible to future classes (like the mid-semester feedback).
Section 9.1.
Show that for any natural number n, A = {k ∈ ℕ | k ≤ n} ≈ B = {-k | k ∈ ℕ and k ≤ n}.
Equivalence vs cardinality: having the same cardinality is defined via equivalence, but the direct definition of equivalence is that there is a bijection between two sets.
Consider f : A → B by f(k) = -k
Check that this is an injection: f(k) = f(m) implies -k = -m which implies k = m
Check that this is a surjection: for any m in B , its preimage in A is -m.
Therefore f is a bijection from A to B, so A and B are equivalent.
Prove that if A and B are finite sets, then A ∪ B is finite.
Maybe do this via cardinality, i.e., card(A ∪ B) ≤ card(A) + card(B), and since A and B are both finite, card(A) and card(B) are both natural numbers and so anything less than their sum is finite. But this overlooks the possibility that A or B might be empty and so have cardinality 0, which isn’t a natural number, and, more seriously, assumes that everything less than or equal to a natural number is finite. This is intuitively perfectly plausible, but not something we’ve proven yet, and even if it’s true of numbers, we don’t know for sure that there couldn’t be infinite cardinalities that under some definition of “less than or equal” turn out to be less than or equal to certain natural numbers.
So let’s try a different approach: go back to the definition of “finite” as meaning equivalent to a subset of the natural numbers, and thus see if we can find a bijection between A ∪ B and a suitable subset.
A first idea for such a bijection would be to define it piecewise from the bijections we know exist for A and B (since they’re finite). So suppose bijection f : A → ℕk for some k and bijection g : B → ℕj for some j, and (naively) try to construct bijection h : (A ∪ B) → ℕm for some m as
This general idea of defining a new bijection piecewise from others is common in equivalence proofs about combinations of sets, but this particular piecewise function doesn’t work because x might be in both A and B. But we can fix that by being more careful about when to use f(x) and when g(x):
But now if we try to show that h is a bijection we run into another problem: we can’t show that it’s an injection, because nothing says g(x) can’t equal f(y) for distinct x and y.
This too is fixable. Think about ways to fix it between now and Monday, and we’ll finish the proof then.
The definition of “equivalence” as the existence of a bijection between two sets.
Prove equivalence by finding a bijection (any bijection will do, you aren’t looking for any particular one).
Finish the proof about the union of finite sets.
Then start looking at infinite sets, specifically the countable ones.
Read section 9.2.