20 2. Background Notice that in the direction we used two cases that could over- lap, and did not worry whether we were in the overlap or not. In the direction, we could only assert x B and x C if we knew x / A (although it is certainly possible for x to be in all three sets), so forbidding the first case was part of the second case. Exercise 2.2.8. Using any of the three options listed above, as long as it is applicable, do the following. (i) Prove intersection distributes over union (i.e., for all A, B, C, A (B C) = (A B) (A C)). (ii) Prove de Morgan’s Laws. (iii) Prove that A B = (A B) (B A) (A B) for any sets A and B. Our final topic in the realm of sets is cardinality. The cardinality of a finite set is the number of elements in it. For example, the cardi- nality of the set of positive integer divisors of 6 is 4: |{1, 2, 3, 6}| = 4. When we get to infinite sets, cardinality separates them by “how infi- nite” they are. We’ll get to its genuine definition in §2.3, but it is fine now and later to think of cardinality as a synonym for size. The way to tell whether set A is bigger than set B is to look for a one-to-one function from A into B. If no such function exists, then A is bigger than B, and we write |B| |A|. The most important result is that |A| |P(A)| for any set A (see §A.3). If we know there is a one-to-one function from A into B but we don’t know about the reverse direction, we write |A| |B|. If we have injections both ways, |A| = |B|. It is a significant theorem of set theory that having injections from A to B and from B to A is equivalent to having a bijection between A and B the fact that this requires work is a demonstration of the fact that things get weird when you work in the infinite world. Another key fact (for set theorists not so much for us) is trichotomy: for any two sets A and B, exactly one of |A| |B|, |A| |B|, or |A| = |B| is true. For us, infinite cardinalities are divided into two categories. A set is countably infinite if it has the same cardinality as the natural numbers. The integers and the rational numbers are important ex- amples of countably infinite sets. The term countable is used by some
Previous Page Next Page