The cardinality of a set, roughly speaking, is the number of elements it has. For a set like the cardinality of (written as ) is or . This concept is fine until you consider an infinite set.
We cannot assign numbers to infinite quantities however we can describe their cardinalities it terms of size. They may all be infinite but some are more "infinite" than others!
For two sets to have the same cardinality there has to be a bijection (one-to-one and onto function) . This means that for every element of there is exactly one corresponding element of . We do not need to prove the map from to as the inverse of a bijective function is itself a bijection.
Example: and now if we find a bijection we have . The bijection is such a function.Therefore .
The power set of a set is the set of all possible subsets of . E.g. then the power set is
Clearly for all . Now using simple permutations we have the cardinality of a sets power set is as follows .
Back to cardinalities
Let's discuss infinite sets. There are a lot of infinities however we shall start from the smallest. Countable infinity or (pronounced aleph naught) is a type of infinity which is the cardinality of the natural numbers (). The name comes from the fact that for a set to have the same cardinality as there has to be a bijection as previously established. In a sense, each element in can be counted using a rule. Sets with the cardinality include and the set of even numbers. (Prove this! The case for is especially fun!).
Now using the idea of a power set we can construct sets with even larger cardinalities! For example . In fact without hurting your brain we can demonstrate at least countable amount of infinities
The next biggest infinity after is ... or is it? This is a fundamental question in set theory and has been proven to be impossible to prove! It is called the continuum hypothesis: There exists a cardinal number such that .
Moving on we have the cardinality of to consider. Is it countable () or uncountable (). We actually find that it is the latter! And we will prove this now! Firstly let us lay some lemmas down.
Lemma 1 The cardinality of the interval is the same as the cardinality of . Proof We need to demonstrate the existence of a bijection . The function suffices.
Lemma 2 We have this equality . Proof therefore .
OK! We are ready for the proof!
First we would like to show that every real number in between and can be shown to be equivalent to a subset of . This is easier to visualize in binary. We can construct a bijection such that and . Now represent where repersents the nth binary digit now we can define therefore for every binary number there is a corresponding subset of .
Example values for in the proof are
We have now proved that .
I hope this post on some set theoretic ideas has inspired and enlightened you!