Question

Show that if A is an infinite set, then it contains a countably infinite subset.

Short answer

A is a countably infinite set.

Step-by-step solution

Step 1:

DEFINITIONS:

• 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.

• A set is uncountable if the set is not finite or countably infinite.

Step 2:

SOLUTION

Given: A is an infinite set

To proof: A contains a countably infinite set

PROOF

Let us select some element $a_1$from A (such an element needs to exist as A is an infinite set and thus A is not empty).

Next, we select another element from A (which again needs to exist as A is an infinite set).

Let us continue selecting other elements $a_3,a_4,\dots$from A.

We then obtain some listing of all elements in A while $f:\mathrm{A}\to Z^{\ast },a_n\to n$is a one-to-one corresponding with the positive integers and thus A is then countable infinite.