Question

Explain why the set Ais countable if and only if $\left|\mathbf{A}\right|\le \left|{\mathit{Z}}^{+}\right|$.

Short answer

is a countable if and only if $\left|\mathbf{A}\right|\le \left|{\mathit{Z}}^{+}\right|$

Step-by-step solution

Definition

A set is countable if it is finite or countably infinite.

A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).

A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

The function f is one-to-one if and only if f = (a) f (b) implies that a = b for all a and b in the domain.

X is a subset of Y if every element of X is also an element of Y. Notation: $X\subseteq Y$

Definition (2): There is a one-to-one function from A to B if and only if $\left|A\right|\le \left|B\right|$.

Proof for the first case

To proof: is countable if and only if $\left|A\right|\le \left|Z^{+}\right|$

IN FIRST CASE

Let A be countable, then A is either finite or countably infinite.

Let us first assume that A is finite. Then contains elements with

. We can then list the elements of a as $a_1,a_2,\dots \dots a_n$.

Let us then define the function:

$f:A\to Z^{+},f\left(a_i\right)=i$

is one-to-one, because if $f\left(a_i\right)=f\left(a_j\right)$then this implies i = j by the definition of and thus also implies

By definition , we then obtain $\left|A\right|\le \left|Z^{+}\right|$

Proof for the second case

IN SECOND CASE

Let $\left|A\right|\le \left|Z^{+}\right|$

By Definition (2) , we then know that there is a one-to-one function from A to$\left|Z^{+}\right|$ .

Then A has the same cardinality as a subset to$\left|Z^{+}\right|$ .

We will proof that the subset of a countable set is also countable. Thus has the same cardinality as a countable set$\left|Z^{+}\right|$ (which is the subset of the countable set ) and thus is countable as well.

We have then proved that if$\left|A\right|\le \left|Z^{+}\right|$, then A is countable.