8.20 Counting with natural numbers and recursive definitions
1.Inequalities
\(|X|\leq|Y|\), if \(\exists f:X\rightarrow Y\) injective
Equivalently, \(\exists f:Y\rightarrow X\) surjective
Note that since the inclusion function \(i:A\rightarrow B\) (\(i(a)=a.\))when \(A\subset B\) is always injective, we have that \(|A|\leq|B|\).
Example
- \(n<m,\left|N_{n}\right|\leq\left|N_{m}\right|\)
- \(\N\subseteq \Z\subseteq \mathbb{Q}\subseteq \R\subseteq \mathbb{C}\), \(|\N|\leq|\Z|\leq|\mathbb{Q}|\leq|\R|\leq|\mathbb{C}|\)
2.Denumerable and countable
- If \(\exists f:X\rightarrow \N\) bijective, \(X\) is denumerable
- If \(X\) is finite and denumerable, \(X\) is countable
Remark: Not all infinite sets are denumerable. For example, \(\N\) is denumerable(countably infinite), but \(\R\) is 'not denumerable'(uncountably infinite).
3.Proposition(Prove definition of infinity)
\(X~is~infinite\Leftrightarrow\exists f:\N\rightarrow X~~injective\)
\(\Rightarrow\)) We need to define \(f:\N\rightarrow X~~\text{injective}\)
Choose any \(x\in X\), \(f(1)\). Namely, define \(f(1)=x_1\)
To define \(f(2)\), pick something in \(X\setminus\{x_1\}\neq\emptyset\), \(f(2)=x_2\in X\setminus\{x_1\}\)
Now, inductively, suppose we have chosen
We can still choose \(x_{m+1}\in X\setminus\{x_{1},\cdots,x_{m}\}\) as \(f(m+1)=x_{m+1.}\)
This process defines \(f:\N\rightarrow X\) injective
\(\Leftarrow\)) We still show that there exist two sets \(B\subsetneq A\subseteq X\), such that\(B\)~\(A\)
Consider \(A=f(\N)\), where \(f\) is the injective function in the hypothesis.
Also consider \(B=f(2\N)\)
Check that:
\(B\subseteq A\) \(b\in B\Rightarrow b=f(2m)\Rightarrow b\in f(\N)=A\)
\(B\subsetneq A\) If not, any \(a\in A\) is also in \(B\).
\(a=f(m)\) and \(a=f(2k)\) for some \(m\in \N, k\in \N\)
Since \(f\) is injective\(\Rightarrow m=2k\Rightarrow\) \(m\) is even. Contradiction since \(m\) can be odd.
Consider the diagram:
\(f:\N\rightarrow X\) \(A=f(\N)=\{x\in X:x=f(n)~for~some~n\in\N\}=Ran(f)\)
So \(A=f(\N)\) is bijective
define \(h:A\rightarrow B\) bijective
\(h(a)=f(M(f^{-1}(a)))\)
\(h\) is bijection. So \(A\sim B\)
4.Uncountable sets
If \(X\) is not countable, We say that \(X\) is uncountable.
- \(X\nsim \N_{m}~~\forall m\in N\)
- \(X\nsim \N\)
Example
\(X=[0,1]=\{\text{All~real~numbers~between~0~and~}1\}\) is uncountable
Informal define of \([0,1]=\{All~decimal~expansions~of~the~form~0,a_1,a_2,a_3,a_4......0\leq a_i\leq 9\}\)
Suppose that \(X\sim \N\). That means that \(\exists f:\N\rightarrow X\) bijective
In particular \(f:\N\rightarrow X\) surjective\(\Rightarrow X=f(\N)\)
\(\begin{aligned} &f\left(1\right)=0.a_{11}a_{12}a_{13}a_{14}a_{15}a_{16}...... \\ &f(2)=0.a_{21}a_{22}a_{23}a_{24}a_{25}a_{26}...... \\ &f\left(3\right)=0.a_{31}a_{32}a_{33}a_{34}a_{35}a_{36}...... \\ &\text{......} \\ &f\left(n\right)=0.a_{n1}a_{n2}a_{n3}....a_{nn}a_{n(n+1)}...... \end{aligned}\)
This infinite list should be complete: \(b\in X\Rightarrow b=f(k),k\in \N.\)
Now consider \(b\in[0,1]\)
\(b=0.b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}......\)
choosing
\(b_{1}\neq a_{11}\Rightarrow b\neq f(1)\\b_{2}\neq a_{22}\Rightarrow b\neq f(2)\\b_{n}\neq a_{nn}\Rightarrow b\neq f(n)\)
\(\Rightarrow b\notin f(\N)\) Contradiction!
Conclusion: \(X=[0,1]\) is not countable
Self Study(Cantor's Diagonal Argument)
Explanation with an example
Lets highlight the digits in the main diagonal of the table
The highlighted digits are 037210...
Suppose that we add 1 to each of these digits, to get the number 048321...
Now, this number can't be in the table. Why not? Because
• it differs from \(f(1)\) in its first digit;
• it differs from \(f(2)\) in its second digit;
• \(\dots\)
• it differs from \(f(n)\) in its \(n\)th digit;
• \(\dots\)
So it can't equal \(f(n)\) for any \(n\) — that is, it can't appear in the table.
Precisely, the function f cannot possibly be surjective.
There will always be (infinitely many!) missing values.
Easily, we can know \([0,1]\) can be bijective to the \(\R\). Hence \(\R\) is uncountably infinite.
Furthermore, the sizes of infinite sets have infinitely many cardinalities
无穷集合的大小有无穷多个等级
Remark (related to Cantor's Diagonal Argument)
by using binary expansions, we also verify that \(Y=\{\)all possible sequences of zeros and ones\(\}\) is uncountable.
\(y=\{(a_{1}a_{2}a_{2}\cdots~\cdots a_{n}\cdots):a_{i}\in\{0,1\}\}\)
5.Property
Let \(A,B\) be sets. Consider the set \(A^{B}=\{f:B\rightarrow A,function\}\) 函数空间是一个函数的集合 而里面的函数是元素映射到元素的函数
Note that in the finite case \(|A^{B}|=|A|^{|B|}\)
Example
\(A=\{0,1\}\), \(B\) a finite set \(\{0,1\}^{B}=\{f:B\rightarrow\{0,1\}\}\)
obs: for any \(f:B\rightarrow\{0,1\}\) we may define the subset
-
- \(E\subseteq B:E=f^{-1}\left(1\right)=\left\{b\in B:f\left(b\right)=1\right\}.\)
* If \(b\in B\setminus E\Rightarrow f\left(b\right)=0\) (Given \(f\in\{0,1\}^{B}\), we associate a set \(E\subseteq B\), \(E=f^{-1}(1)\))
-
Given \(E\subseteq B\), define \(f:B\rightarrow\{0,1\}\) as
\(f\left(b\right)=\left\{\begin{matrix}1&if~b\in E\\0&if~b\notin E\end{matrix}\right.~~~~~~~f\in\left\{0,1\right\}^{B}\)
Conclusion: Given \(B\) a set, \(\wp(B)\sim\{0,1\}^{B}\)
In particular, If \(B\) is finite: \(|\wp(B)|=|\{0,1\}^{B}|=|\{0,1\}|^{|B|}=2^{|B|}.\)
e.g.: \(B=\{b_1,b_2,b_3\}~~~~~\{0,1\}^B=\{f_1(x),f_2(x),...,f_8(x)\}\)
- \(f_1(b_1)=0,f_1(b_2)=0,f_1(b_3)=0\)
- \(f_2(b_1) = 1, f_2(b_2) = 0, f_2(b_3) = 0\)
- \(f_3(b_1) = 0, f_3(b_2) = 1, f_3(b_3) = 0\)
- \(f_4(b_1) = 0, f_4(b_2) = 0, f_4(b_3) = 1\)
- \(f_5(b_1) = 1, f_5(b_2) = 1, f_5(b_3) = 0\)
- \(f_6(b_1) = 1, f_6(b_2) = 0, f_6(b_3) = 1\)
- \(f_7(b_1) = 0, f_7(b_2) = 1, f_7(b_3) = 1\)
- \(f_8(b_1) = 1, f_8(b_2) = 1, f_8(b_3) = 1\)
One infinite example: \(X=\{0,1\}^{\N}\) is equivalent to \(\{f:\N \rightarrow \{0,1\}\}\sim\{\)All possible infinite sequences of zeros and ones\(\}\) or \(\wp(\N)\)
uncountable
More detailed explanation
- 函数空间的定义:
函数空间 \(\{0, 1\}^{\mathbb{N}}\) 表示从自然数集合 \(\mathbb{N}\) 到 \(\{0, 1\}\) 的所有可能的函数的集合。
这意味着：
- 这个空间中的每个元素是一个函数 \(f\)，其定义域是自然数集合 \(\mathbb{N}\)，而值域是 \(\{0, 1\}\)。
- 每个 \(f\) 把每个自然数 \(n \in \mathbb{N}\) 映射到集合 \(\{0, 1\}\) 中的一个元素。
例如，函数 \(f\) 的映射可能是:
即对于自然数 \(1, 2, 3, 4, \dots\)，函数 \(f\) 依次输出 \(0, 1, 0, 1, \dots\)。
- 为什么 \(\{0, 1\}^{\mathbb{N}}\) 等价于所有可能的无限 0 和 1 序列:
每个人从 \(\mathbb{N}\) 到 \(\{0, 1\}\) 的函数 \(f\) 定义了一个由 0 和 1 组成的无限序列。这是因为对于每个 \(n \in \mathbb{N}\)，函数 \(f(n)\) 可以取 \(0\) 或 \(1\)。因此，每个函数对应于一个由 0 和 1 组成的序列。
举例:
- 一个函数 \(f\) 可能是 \(f(1) = 0, \ f(2) = 0, \ f(3) = 0, \dots\)，这对应于序列:
- 另一个函数 \(f\) 可能是 \(f(1) = 1, \ f(2) = 0, \ f(3) = 1, \ f(4) = 0, \dots\)，这对应于序列:
- 还有一个函数 \(f\) 可能是 \(f(1) = 1, \ f(2) = 1, \ f(3) = 1, \ f(4) = 1, \dots\)，这对应于序列:
因此，每个函数 \(f \in \{0, 1\}^{\mathbb{N}}\) 就对应一个无限的 0 和 1 序列，而 \(\{0, 1\}^{\mathbb{N}}\) 的所有函数表示所有可能的无限序列。这就是为什么我们说函数空间 \(\{0, 1\}^{\mathbb{N}}\) 等价于所有可能的无限 0 和 1 序列。
- 无限序列与函数的关系:
对于集合 \(\{0, 1\}^{\mathbb{N}}\):
- 每个函数 \(f : \mathbb{N} \to \{0, 1\}\) 其实就是一个规则，它决定了对每个 \(n \in \mathbb{N}\)，对应的 \(f(n)\) 是 \(0\) 还是 \(1\)。
- 换句话说，这个规则定义了一个无限的 0 和 1 序列，因为对于每个自然数 \(n\)，都有对应的 \(f(n)\)，而 \(f(n)\) 只能是 0 或 1。
因此，一个函数可以看作是一个序列生成器，它生成了一个由 0 和 1 组成的无限序列。
更抽象地:
- 自然数 \(\mathbb{N}\) 是一个索引集合。每个函数 \(f : \mathbb{N} \to \{0, 1\}\) 根据自然数索引的顺序生成序列。序列的第 \(n\) 项是 \(f(n)\)，而这个序列的每一项只能是 \(0\) 或 \(1\)。
6.Cantor Theorem
\(X\) set. Then \(\wp(X)\nsim X\), prove \(\left|X\right|\leq\left|\wp\left(X\right)\right|\)
Strategy: Cantor's idea
Trick: discuss \(b\) belonging
Consider the injective function \(f:X\rightarrow \wp(X)\), \(f(x)=\{x\}\)
Now, we show that \(|\wp(X)|\leq |X|\) is false
Suppose it is true (to get a contradiction): \(|\wp(X)|\leq |X|\)
This means that \(\exists f:X\rightarrow\wp(X)\) surjective
Note that, for every \(x\in X\), \(f(x)\in \wp(X)\)(equivalently: \(f(x)\subseteq X\)) Trick: \(\subseteq\) is more useful than \(\in\)
It makes sense to consider the set \(B=\left\{x\in X:x\notin f(x)\right\}.\)
Since \(B\subseteq X\), \(f\) is surjective \(\Rightarrow \exists b\in X:f(b)=B\)
Question: does \(b\) belong to \(B\)?
Suppose \(b\in B\Rightarrow b\notin f(b)=B\) contradiction!
\(b\notin B\Rightarrow b\in f\left(b\right)=B\) contradiction
then \(\nexists f:X\to \wp(X)\) surjective \(\Rightarrow\)\(\left|\wp\left(X\right)\right|>\left|X\right|\)
Remark: Power set of N is uncountable infinite but N is countable infinite.
As a consequence of this result, the sequence of infinite sets
\(\mathbb{N}, \ \mathcal{P}(\mathbb{N}), \ \mathcal{P}(\mathcal{P}(\mathbb{N})), \ \mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N}))), \ \dots\)must keep increasing in cardinality.
That is, there are infinitely many different sizes of infinity!
7.Sequences
We will consider elements of the form(\(a_{1},a_{2},a_{3},\cdots a_{m},\cdots\)) where \(a_j\in\R\) for any \(j\in \N\)
An infinite string of real numbers
Example
\(a_{n}=\frac{1}{n}\) defines the sequence \((1,\frac{1}{2},\frac{1}{3},\frac{1}{4}\cdots,\frac{1}{n},\cdots)\)
Natation:\(\{a_{n}\}_{n\in \N}\)
Remark
We may think that \(\{a_{n}\}_{n\in \N}\) is the image of \(f:\N\rightarrow \R\)
Example
\(b_{m}=2^{m}~~~\{b_{m}\}_{m\in \N}=\{2,4,8,4,32,\cdots\}\)
8.Recursive sequences
Let \(a_m\) be a sequence defined as follows: \(\begin{aligned}a_{1}=1\\\forall n\in N,a_{n+1}=n~· a_{n}\end{aligned}\)
Explicitly:
\(a_1=1,a_2=2,a_3=6,a_4=24,...,a_n=n(n-1)(n-2)...2·1\)
\(a_n=n!\)
9.Recursive
The sequences is defined in terms of the previous values
Exercise
Prove that given any \(n\geq 1\), there exists an odd integer \(m\) and integer \(k\geq 0\) such that \(n=2^k*m\)(using the well ordering axiom)
Proof
Let S the set of positive integers that cannot be represent as a product of a power of 2 and an odd integer
Suppose that \(S\neq\emptyset\) then by W.O.A, S has a first element \(n_0\). If \(n_0\) is odd then \(n_0=2^0\times n_0\) which is a contradiction.
Therefore \(n_0\) is even, that is, \(n_0=2l\) for some positive integer \(l\).
Since \(l\geq 1\) and \(n_0>l\) then \(l\notin S\)(Otherwise \(l\) contradict that \(n_0\) is the first element)
Hence \(l=2^km\) which \(m\) is odd and \(k\geq 0\), and so \(n_0=2l=2(2^km)=2^{k+1}m\) which is a contradiction.
Therefore \(S=\emptyset\)