- #1

- 86

- 0

So, the task is to prove: Every infinite set has a infinite countable subset.

2. A set [tex]X[/tex] is countable if there exists a bijection [tex]\phi: \mathbb{N}\rightarrow X[/tex]

3. So here's what I have:

Let [tex]A[/tex] be an infinite set, and pick some [tex]a_{1}\in A[/tex]. Define [tex]S_{n}=\left\{a_{i} [/tex], [tex]i\in \mathbb{N} \left| 1\leq i \leq n \right\} [/tex].

Pick [tex]a_{n}\in (A - S_{n-1})[/tex] for each [tex]n \in \mathbb{N}[/tex], [tex]n>1[/tex].

Let [tex]X=\left\{a_{n}|n \in \mathbb{N}\right\}[/tex], and let [tex]\phi: \mathbb{N}\rightarrow X[/tex] by [tex]\phi(x)=a_{x}[/tex].

Then I can show that [tex]\phi[/tex] is a bijection, and thus I am done. Is this good? I'm sure there has to be a better way to do this.

2. A set [tex]X[/tex] is countable if there exists a bijection [tex]\phi: \mathbb{N}\rightarrow X[/tex]

3. So here's what I have:

Let [tex]A[/tex] be an infinite set, and pick some [tex]a_{1}\in A[/tex]. Define [tex]S_{n}=\left\{a_{i} [/tex], [tex]i\in \mathbb{N} \left| 1\leq i \leq n \right\} [/tex].

Pick [tex]a_{n}\in (A - S_{n-1})[/tex] for each [tex]n \in \mathbb{N}[/tex], [tex]n>1[/tex].

Let [tex]X=\left\{a_{n}|n \in \mathbb{N}\right\}[/tex], and let [tex]\phi: \mathbb{N}\rightarrow X[/tex] by [tex]\phi(x)=a_{x}[/tex].

Then I can show that [tex]\phi[/tex] is a bijection, and thus I am done. Is this good? I'm sure there has to be a better way to do this.

Last edited: