Power sets and Cardinalities.


The cardinality of a set, roughly speaking, is the number of elements it has. For a set like \(A=\{1, 2, 3\}\) the cardinality of \(A\) (written as \(|A|\)) is \(3\) or \(|A|=3\). 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 A=B|A|=|B| there has to be a bijection (one-to-one and onto function) f:ABf:A\to B. This means that for every element of AA there is exactly one corresponding element of BB. We do not need to prove the map from BB to AA as the inverse of a bijective function is itself a bijection.

Example: A={1,2,3}A=\{1,2,3\} and B={2,4,6}B=\{2, 4, 6\} now if we find a bijection we have A=B|A|=|B|. The bijection f:x2xf:x\mapsto 2x is such a function.Therefore A=B|A|=|B|.

Power sets

The power set of a set AA is the set of all possible subsets of AA. E.g. A={1,2,3}A=\{1, 2, 3\} then the power set is P(A)={{1,2,3},{1,2},{2,3},{3,1},{1},{2},{3},}\mathscr{P}(A)=\{\{1, 2, 3\}, \{1, 2\}, \{2, 3\}, \{3, 1\}, \{1\},\{2\}, \{3\}, \varnothing\}

Clearly AP(A)A\in \mathscr P(A) for all AA. Now using simple permutations we have the cardinality of a sets power set is as follows P(A)=2A|\mathscr P(A)|=2^{|A|}.

Back to cardinalities

Let's discuss infinite sets. There are a lot of infinities however we shall start from the smallest. Countable infinity or 0\aleph_0 (pronounced aleph naught) is a type of infinity which is the cardinality of the natural numbers (N\Bbb N). The name comes from the fact that for a set AAto have the same cardinality as N\Bbb N there has to be a bijection f:NAf:\Bbb N \to A as previously established. In a sense, each element in AA can be counted using a rule. Sets with the cardinality 0\aleph_0 include Z,Q\Bbb{Z, Q} and the set of even numbers. (Prove this! The case for Q\Bbb Q is especially fun!).

Now using the idea of a power set we can construct sets with even larger cardinalities! For example P(N)=20=1|\mathscr P(\Bbb N)|=2^{\aleph_0}=\aleph_1. In fact without hurting your brain we can demonstrate at least countable amount of infinities P(N)=20=1<P(P(N))=21=2<P(P(P(N)))=22=3|\mathscr P(\Bbb N)|=2^{\aleph_0}=\aleph_1<|\mathscr P(\mathscr P(\Bbb N))|=2^{\aleph_1}=\aleph_2\\<|\mathscr P(\mathscr P(\mathscr P(\Bbb N)))|=2^{\aleph_2}=\aleph_3\cdots

The next biggest infinity after 0\aleph_0 is 1\aleph_1... 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 c\mathfrak c such that 0<c<1\aleph_0<\mathfrak c< \aleph_1.

Moving on we have the cardinality of R\Bbb R to consider. Is it countable (0\aleph_0) or uncountable (1\aleph_1). 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 (0,1)(0, 1) is the same as the cardinality of R\Bbb R. Proof We need to demonstrate the existence of a bijection f:(0,1)Rf:(0,1)\to\Bbb R. The function f:xcot(πx)f:x\mapsto\cot(\pi x) suffices.

Lemma 2 We have this equality (0,1)=[0,1]|(0, 1)|=|[0, 1]|. Proof (0,1)[0,1]R(0,1)\subset[0, 1]\subseteq\Bbb R therefore (0,1)=[0,1]|(0, 1)|=|[0, 1]|.

OK! We are ready for the proof!

First we would like to show that every real number in between 00 and 11 can be shown to be equivalent to a subset of N\Bbb N. This is easier to visualize in binary. We can construct a bijection φ:[0,1]P(N)\varphi:[0,1]\to\mathscr P(\Bbb N) such that φ(0)=\varphi(0)=\varnothing and φ(1 (or) 0.1111)=N\varphi(1\text{ (or) }0.1111\cdots)=\Bbb N. Now represent [0,1]x=n=1bn2n\displaystyle [0,1]\ni x=\sum^\infty_{n=1}\frac{b_n}{2^n} where bnb_n repersents the nth binary digit now we can define φ:0.b1b2b3{nN:bn=1}\varphi:0.b_1b_2b_3\cdots\mapsto\{n\in\Bbb N : b_n=1\} therefore for every binary number there is a corresponding subset of N\Bbb N. \square

Example values for φ\varphi in the proof are φ(0.010101)={2,4,6}\varphi(0.010101\cdots)=\{2, 4, 6\cdots\}

We have now proved that R=P(N)|R|=|\mathscr P(\Bbb N)|.

I hope this post on some set theoretic ideas has inspired and enlightened you!

Note by A Former Brilliant Member
7 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

You should add the proof that a set and its power set do not have the same cardinality. It's a beautiful argument and includes echoes of Cantor's diagonal proof and Russell's paradox. (It also helps with the clarity of this post, since some of your remarks seem to assume it implicitly.)

Patrick Corn - 7 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...