SUNY Geneseo Department of Mathematics
Monday, April 12
Math 239 03
Spring 2021
Prof. Doug Baldwin
(No.)
Problem set 9, focusing on set theory and related proofs, is now “officially” assigned. See the handout for details.
Finish it by next Monday, and grade by April 28 (1 1/2 weeks from the “complete by” date, to allow for a rejuvenation day on the 22nd).
Based on section 5.4 of our textbook and this Cartesian product discussion.
A Cartesian product is a set of ordered pairs. Specifically, A × B is the set of all pairs you can make with their first element taken from A and their second from B.
For example, what is {1,2,3} × {-1,-2}? { (1,-1), (1,-2), (2,-1), (2,-2), (3,-1), (3,-2) }
How would you prove part 3 of the book’s Theorem 5.25 (that (A ∩ B) × C = (A × C) ∩ (B × C))?
The book’s examples involve breaking down elements of products. For example, we might start by letting (x,y) be an element of (A ∩ B) × C. So then x is in A ∩ B and y is in C, i.e., x is in A and x is in B. Continuing on in this way eventually leads to a complete proof (hopefully).
Basically, the strategy here is element chasing.
We worked out the complete proof and wrote it up using LaTeX. The source file and PDF output are available from Canvas.
The central idea in the proof is that, since we want to show that two sets are equal, we show that each is a subset of the other. Element chasing does this by showing that a generic element of the first set must also be in the second set, and then that a generic element of the second set must also be in the first.
For clarity, we did each direction of this argument in a separate paragraph. We also included an opening paragraph that restates what will be proved and summarizes how, and a closing paragraph that again summarizes the result and how we got it.
This may be the first time you’ve seen the \times command in LaTeX, which produces a cross multiplication sign.
Another example: what, if anything can you say about the cardinality of A × B compared to the cardinalities of A and B?
We looked at the opening example, where the Cartesian product of a 3-element set with a 2-element set had 6 elements. Then we considered what would happen if we added a 4th element to the 3-element set: it would pair with each element of the 2-element set, adding 2 more pairs to the product. From these examples and the related thinking, we conjectured that |A × B| =|A||B|.
Can you prove it?
We didn’t do a full proof, but there’s a nice induction proof, using induction on the cardinality of one of the sets.
The basis step is a cardinality of 0, i.e., the empty set. From a careful reading of the definition of Cartesian product, we realized that ∅ × A = ∅, which has cardinality 0.
For the induction step, you would assume that if |A| = k then |A × B| is k|B|, and then imagining adding another element to A, to increase its cardinality to k+1. That extra element could pair with each element of B, adding another |B| to the total cardinality of the product.
Indexed families of sets — one way of talking about and working with sets of sets.
Please read section 5.5 in the textbook.
Please also do this discussion of indexed families of sets.