Skip to content

9

999027873 Shi Yue

Basic_concepts__Copy_.pdf

Exercise 1. In each case, give an example of denumerable sets \(A\) and \(B\), neither of which is a subset of the other, such that:

(a) \(A \cap B\) is denumerable.

Let \(A=\N\cup \{-1\}\) and \(B=\mathbb{N}\cup\{-2\}\), then \(A\cap B=\N\) which is denumerable

(b) \(A \cap B\) is finite.

Let \(A=\N\cup\{0\}\) and \(B=\Z-\N\), then \(A\cap B=\{0\}\) which is finite

(c) \(A - B\) is denumerable.

Let \(A=\mathbb{Z}-\{0\}\) and \(B=\mathbb{N}\cup\left\lbrace0\right\rbrace\), then \(A-B=\mathbb{Z}^{-}\) which is denumerable

(d) \(A - B\) is finite and nonempty.

Let \(A=\mathbb{N}\) and \(B=\mathbb{Z}-\left\lbrace1\right\rbrace\), then \(A-B=\left\lbrace1\right\rbrace\) which is finite and nonempty

Exercise 2. Let \(\mathbb{Q}[x]\) be the set of polynomials \(a_n x^n + \cdots + a_1 x + a_0\) with rational coefficients \(a_n, \ldots, a_0\). Prove that \(\mathbb{Q}[x]\) is denumerable.

Consider the degree of polynomial is \(k\), then \(\mathbb{Q}[x]_{k}=a_{k}x^{k}+\cdots+a_1x+a_0\) (fix \(k\))

Since \(a_i\in \mathbb{Q},i\in[0,k]\), then \(\{a_0x^0\},\{a_1x^1\},...,\{a_kx^k\}\) are all denumerable

Then \(\mathbb{Q}[x]_k\) is also denumerable since \(\mathbb{Q}[x]_{k}=\bigcup_{i\in\left\lbrack1,k\right\rbrack}\left\lbrace a_{i}x^{i}\right\rbrace\) is also denumerable by theorem

Then \(\mathbb{Q}[x]=\bigcup_{k\in\left\lbrack0,+\infty\right)}\mathbb{Q}[x]_{k}\) is also denumerable

Exercise 3.
(a) Write a bijection between \([0, 1)\) and \((0, 1)\).

For \(n\geq 2\), consider \(f:\left\lbrack0,1\right)\to(0,1)\) where \(\frac{1}{n}\mapsto1/(n+1)\)

\(g:\left\lbrack0,1\right)\to(0,1)\) where \(0\mapsto \frac12\)

To construct the bijection, consider \(h:\left\lbrack0,1\right)\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}\)

(b) Write a bijection between \(\mathbb{R}\sim(\mathbb{R}-\mathbb{Z})\).

Define \(f:\mathbb{R}\to\mathbb{R}-\mathbb{Z}\) where \(n\to n+\frac12\left(n\in\mathbb{Z}\right)\)

\(g:\mathbb{R}\to\mathbb{R}-\mathbb{Z}\) where \(n+\frac{1}{a}\to n+\frac{1}{a+1}\left(n\in\mathbb{Z},a\in\mathbb{N}-\{1\}\right)\)​

Then define \(h:\mathbb{R}\to\mathbb{R}-\mathbb{Z}\) where \(h=\begin{cases}f,\text{ if }x=n,\quad\quad\quad\quad n\in\mathbb{Z}\\ g,\text{ if }x=n+\frac{1}{a},\quad\quad n\in\mathbb{Z},a\in\mathbb{N}-\{1\}\\ id_{x},\text{ if }x\neq n,n+\frac{1}{a},~n\in\mathbb{Z},a\in\mathbb{N}-\{1\}\end{cases}\)​

Exercise 4.
(a) Prove that every infinite set \(X\) contains a denumerable subset.

Since \(X\) is infinite, then we first choose \(x_0\in X\).

Then since \(X-\{x_0\}\) is still infinite, then choose \(x_1\in X-\{x_0\}\)

.....

Then since \(X-\{x_0,x_1,\ldots,x_{n}\}\) is still infinite, then choose \(x_{n+1}\in X-\{x_0,x_1,\ldots,x_{n}\}\)

.....

Thus we get a subset \(S=\left\lbrace x_0,x_1,x_2,...\}\right.\) which all the elements are distinct.

Then there is a bijection \(f:S\to\mathbb{N}\) where \(x_i\mapsto i\)​

Thus \(S\) is a subset and is denumerable

(b) Prove that if \(B\) is denumerable and \(A \subset B\) is a subset such that \(B - A\) is infinite, then \(B \sim (B - A)\).

Since \(B\) is denumerable and \(A\subset B\)\, then \(B-A\subset B\) and \(B-A\) is countable

Since \(B-A\) is infinite, then \(B-A\) has to be denumerable

Since \(B\) and \(B-A\) are all denumerable, then there is a bijection

(c) Prove that if \(X\) is uncountable and \(A \subset X\) is a denumerable subset, then \(X \sim (X - A)\).

First, we need to prove \(X-A\) has a denumerable subset.

Then it's enough to prove \(X-A\) is infinite and use exercise 4a

Suppose \(X-A\) is finite, then \(X-A\) and \(A\) are all countable, then \((X-A)\cup A\) is countable

Then \(X\) is countable, contradiction. Thus \(X^{\prime}\subset X-A\) is denumerable.

Let \(A\) and \(X^{\prime}\) are all denumerable where \(X'\subseteq X-A\)

Then \(A\cup X'\) is also denumerable, then \(f_1:A\to \N\) and \(f_2:X'\to \N\) are bijections

And \(f_3:A\cup X'\to\N\) is bijective, then define \(f:A\cup X^{\prime}\to X^{\prime}\) is also bijective since \(f=f_2^{-1}\circ f_3\)​

Then define \(g:X\to X-A\) where \(g=\begin{cases}f,\text{ if }x\in A\cup X^{\prime}\\ id,\text{ if }x\notin A\cup X^{\prime}\end{cases}\) which bijective.

‍