We say that two sets have the same cardinality if , and we write . This allows us to inter-relate cardinality and function relations via a special theorem.
Theorem 3.0.1 (Schröder-Berstein Theorem). If and then .
The Schröder-Berstein theorem provides some immediate results for allowing explicit bijections.
Proposition 3.0.1 (Cardinality of to any power). Using Schröder-Berstein we can create explicit bijections given by
Proposition 3.0.2 (). We create the explicit bijection via . It follows then that permits a similar bijection.
Proof of Prop. 3.1.2. Notice that any natural number can be written as where is odd, i.e., . A bijection is automatically created here with , and the additional at the end of the statement is there to shift the entire bijection down one. So instead of we get .∎
Proposition 3.0.3 (Countable vs uncountable infinites)..
Proof by Cantor. Given by Cantor’s diagonal argument, no map be surjective, because:
then let where for each . Now look at the digit, , so can’t be surjective. ∎
Proposition 3.0.4 (Cardinality of mappings).
Proof by Cantor’s diagonal used for mappings. We can use the fact that in addition to Cantor’s diagonal argument as a decimal expansion——with as an integer between and . So now to show , we create some and construct the bijection via:
We say that is made up of all that are odd; is made up of all which are odd such that ; is made up of all which are odd such that , and so on (the general form being ). Therefore there exists a bijection between .∎
Proposition 3.0.5 (There does not exist a largest cardinality). Let be the standard powerset. It follows then that and for any .
Proof of non-existence of largest cardinality. Recall that . There must exist a bijection since and . Now to show we use proof by contradiction: suppose and let defined by , now for for some we notice that means that , but to say , thus we have a contradiction. ∎
Another option for this proof, though less formal, can be found by showing that and that subsets of have such that ; let then
𝟙
Note that if is finite then and . This naturally leads us into our next theorem regarding the infinitude of the cardinality of in relation to .