]>
Suppose that is a non-empty collection of sets. We define a relation on by if and only if there exists a one-to-one function from onto (sometimes called a bijection). That is, and are in one-to-one correspondence.
Show that is an equivalence relation on .
Two sets that are in one-to-one correspondence are said to have the same cardinality. Thus, the equivalence classes under this equivalence relation capture the notion of having the same number of elements.
For , let . Technically, a set is finite if for some , in which case is the cardinality of , and we write . Think of as a reference set with elements; any other set with elements must be equivalent to this one. Appropriately enough, a set is infinite if it's not finite. We will study the cardinality of finite sets in the next two sections on Counting Measure and Combinatorial Structures. In this section, we will concentrate primarily on infinite sets.
Let be a set. Recall that denotes the power set of (the set of all subsets of ), and denotes the set of functions from into . Show that . The mapping that takes a set into its indcator function is a bijection.
A set that is equivalent to the set of natural numbers is said to be countably infinite. A set that is either finite or countably infinite is said to be countable. Countable sets play a very important role in probability theory, as in many other branches of mathematics. Appropriately enough, a set that is not countable is said to be uncountable. We will soon see that there are such sets.
Show that the set of even natural numbers is countable infinite, and the set of integers is countable infinite.
Suppose that is a set with at least two elements, and let , the set of all functions from into . Thus, the elements of are infinite sequences indexed by and taking values in . Show that is uncountable. The proof is by contradiction, and uses a nice trick known as the diagonalization method:
Surely a set must be as least as large as any of its subsets, in terms of cardinality. On the other hand, it might also seem that the set of even natural numbers is only half the size of the set of all natural numbers, and that the set of integers is twice the size of the set of natural numbers. However, by a Exercise 3, the three sets have exactly the same size, in terms of cardinality. In this subsection, we will explore some interesting and somewhat paradoxical results that relate to subsets of infinite sets. Along the way, we will see that the countable infinity is the smallest
of the infinities.
Suppose that is an infinite set. Show that has a countable infinite subset.
Show that a set is infinite if and only if is equivalent to a proper subset of
pigeonhole principle
When was infinite in the previous exercise, not only did we map one-to-one onto a proper subset, we actually threw away a countably infinite subset and still maintained equivalence. Similarly, we can add a countably infinite set to an infinite set without changing the cardinality .
Show that if is an infinite set and is a countable set, then
In particular, if is uncountable and is countable then and have the same cardinality as , and in particular are uncountable.
In terms of the dichotomies finite-infinite and countable-uncountable, a set is indeed at least as large as a subset. First we need a preliminary result.
Show that if is countably infinite and is an infinite subset of , then is countably infinite.
Suppose that . Prove the following results.
Hint: Note that (b) is the contrapositive of (a), and (d) is the contrapositive of (c).
We will look deeper at the general question of when one set is at least as big
than another, in the sense of cardinality. Not surprisingly, this will eventually lead to a partial order on the cardinality equivalence classes
First note that if there exists a function that maps a set one-to-one into a set , then, in a sense, there is a copy of contained in . Hence should be at least as large as .
Suppose that is one-to-one. Show that
Hint: Note that maps one-to-one onto , and . Now use the Exercise 9.
On the other hand, if there exists a function that maps a set onto a set , then, in a sense, there is a copy of contained in . Hence should be at least as large as .
Suppose that is onto. Show that
Hint: For each , select a specific with (if you are persnickety, you may need to invoke the axiom of choice). Let be the set of chosen points. Argue that maps one-to-one onto , and . Now use the Exercise 10.
The previous exercise also could be proved from the one before, since if there exists a function mapping onto , then there exists a function mapping one-to-one into . This duality is proven in the discussion of the axiom of choice. A simple and useful corollary of the previous two theorems is that if is a given countably infinite set, then a set is countable if and only if there exists a one-to-one function from into , if and only if there exists a function from onto .
Show that if is a countable set for each in a countable index set , then is countable.
Show that if and are countable then is countable.
The last result could also be proven from the one before, by noting that
Both proofs work because the set is essentially a copy of , embedded inside of . The last theorem generalizes to the statement that a finite product of countable sets is still countable. But, from Exercise 4, a product of infinitely many sets (with at least 2 elements each) will be uncountable.
Show that the set of rational numbers is countably infinite.
A real number is algebraic if it is the root of a polynomial function (of degree 1 or more) with integer coefficients. Rational numbers are algebraic, as are rational roots of rational numbers (when defined). Moreover, the algebraic numbers are closed under addition, multiplication, and division. A real number is transcendental if it's not algebraic. The numbers and are transcendental, but we don't know very many other transcendental numbers by name. However, as we will see, most (in the sense of cardinality) real numbers are transcendental.
Show that the set of algebraic numbers is countably infinite.
Now let's look at some uncountable sets.
Show that the interval is uncountable.
Show that the following sets have the same cardinality, and in particular all are uncountable:
Hints: You can find a linear function that maps an interval one-to-one onto another interval, as long as the two intervals are of the same type--that is, both bounded or unbounded, and both with the same type of closure. A closed (or half-closed) interval differs from its open counterpart by two (or one) points. The natural log function maps the interval one-to-one onto . The tangent function maps the interval one-to-one onto . The irrational numbers can be obtained from the real numbers by removing the rational numbers (a countably infinite set), and similarly, the transcendental numbers can be obtained from the real numbers by removing the algebraic numbers (again a countably infinite set).
Suppose that is a nonempty collection of sets. We define the relation on by if and only if there exists a one-to-one function from into , if and only if there exists a function from onto . In light of the previous subsection, should capture the notion that is at least as big as , in the sense of cardinality.
Show that is reflexive and transitive.
Thus, we can use the construction in the section on on Equivalence Relations to first define an equivalence relation on , and then extend to a true partial order on the collection of equivalence classes. The only question that remains is whether the equivalence relation we obtain in this way is the same as the one that we have been using in our study of cardinality. Rephrased, the question is this: If there exists a one-to-one function from into and a one-to-one function from into , does there necessarily exist a one-to-one function from onto ? Fortunately, the answer is yes; the result is known as the Schröder-Bernstein Theorem, named for Ernst Schröder and Sergi Bernstein.
Show that if and then .
We will write if , but and are not equivalent. That is, there exists a one-to-one function from into , but there does not exist a function from onto . Note that would have its usual meaning if applied to the equivalence classes. That is, if and only if but . Intuitively, of course, means that is strictly larger than , in the sense of cardinality.
Show that in each of the following cases:
We close our discussion with the observation that for any set, there is always a larger set.
Let be a set. Show that .
The proof that a set cannot be mapped onto its power set is similar to the Russell paradox, named for Bertrand Russell.
The continuum hypothesis is the statement that there is no set of real numbers whose cardinality is between between that of and . The continuum hypothesis actually started out as the continuum conjecture, until it was shown to be consistent with the usual axioms of the real number system (by Kurt Gödel in 1940), and independet of those axioms (by Paul Cohen in 1963).