Question

Suppose that A is a countable set. Show that the set B is also countable if there is an onto function f from A to B.

Short answer

B is countable.

Step-by-step solution

Step 1:

DEFINITIONS:

The function f is onto if and only if for every element $\mathrm{b}\in \mathrm{B}$there exist an element data-custom-editor="chemistry" $\mathrm{a}\in \mathrm{A}$such that f (a) = b .

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.

f is a one-to-one correspondence if and only if f is one-to-one and onto.

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.

Composition of f and g: .

Definition (1): $\left|A\right|=\left|B\right|$if and only if there is a one-to-one correspondence from A to B.

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

Result exercise : A is countable if and only if $\left|A\right|\le \left|Z^{+}\right|$.

Step 2:

Given: A is countable and there is an onto function f from A to B.

To proof: B is countable.

PROOF:

If A is countable, then A is either finite or countably infinite.

FIRST CASE- A is finite.

Since f is a function from A to B:

$f\left(A\right)\subseteq B$

Since f is also onto, we then know that these two subsets have to be the same (since for every , there exists an element such that ).

|f (A)| = |B|

Since the two sets are the same, they have the same cardinality:

A is finite, thus let us assume that A contains n elements, which we name: $a_1,a_2,\dots a_n$. Then $f\left(A\right)=\left\{f\left(a_i\right)\mid a_i\in A\right\}$contains at most n elements and thus is finite.

Since f (A) and B have the same cardinality and since f (A) is finite, B then has to be finite as well and thus B is countable.

Step 3:

SECOND CASE- A is countably infinite.

$\left|A\right|=\left|Z^{+}\right|$

By definition (1): There exists a one-to-one correspondence g from A to $Z^{+}$ .

Since f is a function from A to B:

$f\left(A\right)\subseteq B$

Since, f is also onto, we then know that these two subsets have to be the same (since, for every , there exists an element such that ).

$\left|f\right(A\left)\right|=\left|B\right|$

Since, g is a one-to-one correspondence, the inverse of g exists and the inverse is also a one-to-one correspondence.

$\left|f\left(g^{-1}\left(Z^{+}\right)\right)\right|=\left|B\right|$

Since, is countably infinite, $f\left(g^{-1}\left(Z^{+}\right)\right)$is finite or countably infinite. Then B has to be finite or countably infinite as well (since $\left|f\left(g^{-1}\left(Z^{+}\right)\right)\right|=\left|B\right|$and thus, B is countable.