13 - Properties of Countability

Properties of Sets

1. Subset of a finite set is finite
2. Non-empty finite subset of $\mathbb{R}$ is bounded above
3. $\mathbb{N}$ is not bounded above (by the Archimedean property)

Countable Property of Sets

Let $A$ be a set

1. $A$ is countable if and only if $A$ is countably infinite or finite
2. If there is an injection $f:A\to B$ and an injection $g:B\to A$ then
   there exists bijection $h:A\to B$

Examples of countably infinite sets

1. $\mathbb{N}$

2. $\mathbb{N}\cap \{0\}$

3. $\{2k-1:k\in N\}$

4. $\mathbb{Z}$

5. $\mathbb{N}\times \mathbb{N}$

Proof - $(1)$

Clear…

Proof - $(2)$

Define $f:\mathbb{N}\cup \{0\}\to \mathbb{N}$ by $f(n)=n+1$
With $f$ being a bijection

Proof - $(3)$

Define $f:\mathbb{N}\to \{2k-1:k\in \mathbb{N}\}$ by $f(n)=2n-1$

Proof - $(4)$

Define $f:\mathbb{Z}\to \mathbb{N}$ by

$$f(k)=\{\begin{array}{ll}2k& \text{ if }k\ge 1\\ 1-2k& \text{ if }k\le 0\end{array}$$

which is also a bijection

Proof - $(5)$

Define $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ by

$$f((m,n))=2^{m-1}(2n-1)$$

Need to prove it is bijective

1. Injective
   If $f((m_1,n_1))=f((m_2,n_2))$ then

$$2^{m_1-1}(2n_1-1)=2^{m_2-1}(2n_2-1)$$

So by uniqueness of prime factorisation in $\mathbb{N}$ then

$$2^{m_1-1}=2^{m_2-1}\text{ and }2n_1-1=2n_2-2$$

Hence

$$m_1=m_2\text{ and }{n}_1=n_2$$

2. Surjective
   Take $k\in \mathbb{N}$
   Then $k=2^r(2s+1)$ for some $r,s\ge 0$
   (consider the set $T=\left\{t\in {\mathbb{Z}}^{\ge 0}:\frac{k}{2^t}\in \mathbb{N}\right\}$),
   which is non-empty and bounded above so it has maximum
   Then

$$k=f(r+1,s+1)$$

^63ae95

Countable Sets of Unions and Products

Let $A,B$ be countable sets

1. If $A$ and $B$ are disjoint, then $A\cup B$ is countable

2. $A\times B$ is countable

Proof

1. Since $A,B$ are countable then there are injections

$$f:A\to \mathbb{N}\text{ and }g:B\to \mathbb{N}$$

Define $h:A\cup B\to \mathbb{N}$ by

$$h(x)=\{\begin{array}{ll}2f(x)-1& \text{ if }x\in A\\ 2g(x)& \text{ if }x\in B\end{array}$$

Naturally this is an injection as both $f$ and $g$ are
2) Define

$$h:A\times B\to \mathbb{N}\text{by}h((a,b))=2^{f(a)}{3}^{g(b)}$$

By the uniqueness of prime factorisation in $\mathbb{N}$, it is an injection

Countability of $\mathbb{Q}$

$$\mathbb{Q}\text{ is countable}$$

Proof $\mathbb{Q}={\mathbb{Q}}^{>0}\cup \{0\}\cup {\mathbb{Q}}^{<0}$ This is a disjoint union so as ${\mathbb{Q}}^{>0}$ is countable and then so is ${\mathbb{Q}}^{<0}$ with $\{0\}$ being finite hence it is countable Therefore by countability of disjoint sets, $\mathbb{Q}$ is coutable

We can write