1

Let $S=\{a_1,a_2,a_3,\cdots,a_n\}$.

The number of functions from $S$ to $\{0,1\}$ is just $2^n$, since each input of the $a_i$ can have 2 choice of output.

Recall that the number of subsets of a finite set with cardinal number $n$ is just $2^n$. Hence the power set $\mathcal{P}(S)$ of a set $S$ is of cardinality equals to the set of all functions from $S$ to $\{0,1\}$.

Therefore, there is a one-to-one correspondence between the power set $\mathcal{P}(S)$ of a set $S$ and the set of all functions from $S$ to $\{0,1\}$.

Yet I can’t understand why this result implies the theorem 0.14. Can anyone help?enter image description here

鈴木悠真
  • 387
  • 1
  • 8

2 Answers2

1

The main idea here is that if $A$ is a finite set and there's a bijection $A\to B$ then $B$ is also a finite set and $|A|=|B|$. In this case, if we previously know that the set of functions $S\to \{0, 1\}$ is finite of size $2^{|S|}$ then power set of $S$ will also be finite of size $2^{|S|}$ because there's a bijection between them.

For the second statement, the theorem you can use here is that if $B$ is a finite set and there is an injective function $A\to B$ which is not surjective then $A$ is also finite and $|A|<|B|$. There is a very natural injective function $S\to \mathcal{P}(S)$, mapping element to the subset which contains only that element. This funnction is not surjective (take any subset with two elements in it) so $|S| < 2^{|S|}$.

David Dinh
  • 626
1
  1. If $|S|=\kappa$ (i.e. the cardinality of set $S$ is $\kappa$) then $|P(S)|=2^{\kappa} $ (i.e. cardinality of the power set on $S$ is $2^{\kappa} $).
  1. Since $S\in P(S)\implies|S|<|P(S)|\implies \kappa<2^{\kappa}$
Nitin Uniyal
  • 7,946
  • Thank you for your reply. I see how the second one is proved, but why the first one is also true for infinite sets? – 鈴木悠真 Aug 26 '22 at 08:50
  • The cardinality of infinite sets follows the hierarchy $\aleph_0<2^{\aleph_0}=c<2^c<2^{2^c}<....$ (where $\aleph_0$, the cardinal number of set $\mathbb N$ is the smallest infinity among the family). – Nitin Uniyal Aug 26 '22 at 08:56
  • Oh I think I get what you mean. Since $|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$, it works in the infinite set too. – 鈴木悠真 Aug 26 '22 at 11:54