1.2

Workshop 12.pdf

Are the following sets countable?
1. \(A=\{2^{n};n\geq0\}\)
  
  Yes, \(f:\mathbb{N}\to A,f(n)=2^{n}\) is bijective 2. \(\mathbb{N} \times \mathbb{R}\)
  
  no 3. \(\mathbb{Q}[\sqrt{2}] = \{a + b\sqrt{2}; a, b \in \mathbb{Q}\}\)
  
  Yes, First \(f:\mathbb{Q}[\sqrt2]\to\mathbb{Q}\times\mathbb{Q}\) where \((a+b\sqrt{2})\mapsto (a,b)\) is bijective
  
  Since \(\mathbb{Q}\approx\mathbb{N}\), then \(\mathbb{Q}\times\mathbb{Q}\approx\mathbb{N}\times\mathbb{N}\), then \(g:\mathbb{Q}\times\mathbb{Q}\to\mathbb{N}\times\mathbb{N}\) is bijective
  
  Since we know \(h:\N\times \N\to \N\) is bijective, then \(h\circ g\circ f:\mathbb{Q}[\sqrt2]\to\mathbb{N}\) is bijective 4. the set of prime numbers
  
  Yes, injective to \(\N\) 5. the set of functions from \(\mathbb{R}\) into \(\mathbb{R}\)
  
  Since we know \(\mathbb{N}^{\mathbb{N}}\subseteq\mathbb{R}^{\mathbb{R}}\) and \(\N^{\N}\) is uncountable, then \(\mathbb{R}^{\mathbb{R}}\) is also uncountable
Let \((f_n)\) be a sequence of applications of \(\mathbb{N}\) into \(\mathbb{N}\). Let \(g:\mathbb{N}\to\mathbb{N}\) be defined by: for all \(n \in \mathbb{N}\), \(g(n)=f_{n}(n)+1\). Show that for any integer \(p\), we have \(f_{p}\neq g\).

Since \(g(p)=f_p(p)+1\), then \(g(p)\neq f_p(p)\), then \(g\neq f_p\)

Deduce that the set of applications of \(\mathbb{N}\) into \(\mathbb{N}\) is not countable.

Thus \(g\) is a new function from \(\N\) to \(\N\) that is not in the sequence, then similar to cantor's theorem

It is not countable
1. Show that \((0, 1)\) and \((0, 1]\) are in bijection (we can use a bijection from \((0, 1]\) to \((0, 1)\) which associates \(1/(n+1)\) with \(1/n\)).
  
  For \(n\geq 1\), consider \(f:(0,1]\to (0,1)\) where \(\frac{1}{n}\mapsto1/(n+1)\)
  
  To construct the bijection, consider \(g:(0,1]\to(0,1)\) where \(g=\begin{cases}f,\text{ if }x=\frac{1}{n}\\id_{x},\text{ if }x\neq\frac{1}{n}\end{cases}\) 2. Show that \(\left(0,1\right)\) and \([0, 1]\) are in bijection.
  
  For \(n\geq 1\), consider \(f:(0,1]\to (0,1)\) where \(\frac{1}{n}\mapsto1/(n+2)\)
  
  \(g:\{0\}\to\{\frac12\}\) where \(0\mapsto \frac12\)
  
  To construct the bijection, consider \(h:\left\lbrack0,1\right\rbrack\to(0,1)\) where \(h=\begin{cases}f,\text{ if }x=\frac{1}{n}\\ g,\text{ if }x=0\\ id_{x},\text{ if }x\neq\frac{1}{n},0\end{cases}\)
Let \((I_\alpha)_{\alpha \in A}\) be a family of pairwise disjoint non-empty open intervals. Show that \(A\) is necessarily at most countable.

Proof

Consider \(f:(I_{\alpha})_{\alpha\in A}\to\mathbb{Q}\) where \(I_{\alpha}\to q_{\alpha}\) and \(q_{\alpha}\in\mathbb{Q}\cap I_{\alpha}\)

Claim: \(f\) is injective

Take \(q_\alpha=q_\beta\), then since \(I_\alpha \cap I_\beta= \empty\), then \(I_\alpha=I_\beta\)

Then since \(g:\mathbb{Q}\to\mathbb{N}\) is bijective, then \(g\circ f\) is also injective, thus by definition it is countable
A sequence of integers \((n_k)\) is said to be stationary if there exists an integer \(p \in \mathbb{N}\) such that, for all \(k \geq p\), \(n_k = n_p\). Prove that the set of sequences of almost zero integers and that the set of sequences of stationary integers are countable.

Since the sequence is almost zero integers, then \(\exists p:\forall k\geq p,n_k=0\), then the sequence is \((n_1,n_2,...,n_p,0,...)\).

Thus the set of such sequence of fixed \(p\) is \(\underbrace{\mathbb{Z}\times\mathbb{Z}\times...\times\mathbb{Z}}_{\text{p times}}\times\mathbb{Z}\times.....=A_{p}\)

But there is a bijection from \(A\) to \(\underbrace{\mathbb{Z}\times\mathbb{Z}\times...\times\mathbb{Z}}_{\text{p times}}=\mathbb{Z}^{p}\) since the terms behind p-th are all zero.

And \(\mathbb{Z}^p\) is countable, then \(A_p\) is countable. Then we can consider \(\bigcup_{p\in\mathbb{N}}A^{p}\) is also countable by theorem

Another is similar
1. Compute \(\sum_{n\geq0}\frac{1}{2^{n+1}}=\frac{\frac12}{1-\frac12}=1\)
2. Let \((u_n)\) be a sequence of \([0, 1]\). Show that, for all \(n \geq 1\), there exists an element \(x_n\) in \([0, 1] \setminus \bigcup_{k=0}^{n} \left[u_k - \frac{1}{2^{k+2}}, u_k + \frac{1}{2^{k+2}}\right]\).
  
  The length of union of interval must be less than \(1\) 3. Why can we extract from the sequence \((x_n)\) a subsequence convergent to \(\ell \in [0, 1]\)?
  
  Because when \(n\) grows, the union of intervals will grows, then the scope of \(x_n\) become smaller.
  
  Eventually, it's will convergent
  
  Bolzano-Weierstrass 4. Prove that \([0, 1]\) is not countable.
  
  Suppose it is surjective from \(\N\) to \([0,1]\)
  
  Then \(=(u_1,u_2,...)\)
  
  ‍
  
  ‍
  
  ‍
  
  Since \(f:(u_n)\to \N\) where \(u_k\mapsto k\) is bijective, then suppose \([0,1]\) is also countable, then there exists \(g:[0,1]\to \N\) is injective, then \(g^{-1}\circ f\) is surjective where \((u_n)\mapsto [0,1]\)
  
  And we know there exists \(x_{n}\in[0,1]\setminus\bigcup_{k=0}^{n}\left[u_{k}-\frac{1}{2^{k+2}},u_{k}+\frac{1}{2^{k+2}}\right]\) which is contradiction to surjective.
We say that a real number \(x\) is an algebraic number if there exist \(d \in \mathbb{N}^*\) and relative integers \(a_0, \dots, a_d\) with \(a_d \neq 0\) such that \(a_dx^d + \cdots + a_1x + a_0 = 0\). The smallest integer \(d\) verifying this property is then the degree of \(x\).
1. What are the algebraic numbers of degree 1? \(x=\frac{-a_0}{a_1}\)
2. Prove that the set of algebraic numbers of degree \(d\) is at most countable.
  
  Since the polynomial has at most \(d\) roots, which means there are at most \(d\) \(x\)
  
  Thus for the fixed \(d\), the set of algebraic numbers (\(A_d\)) is countable since it is finite
  
  Then \(\bigcup_{d\in\mathbb{N}^{*}}A_{d}\) is also countable by theorem 3. Prove that the set of algebraic numbers is countable.
  
  See above
For this exercise, we recall that every infinite set contains a countable infinite set. Let \(X\) be an infinite set and \(D\) a set that is at most countable. Show that \(X \cup D\) is in bijection with \(X\).

Since \(X\) is infinite set, then let \(A\) be a countable infinite set inside \(X\).

Since \(D\) is at most countable, then there are two cases
- \(D\) is denumerable
- \(D\) is finite

‍