# Math Help - Bijection - Countability

1. ## Bijection - Countability

I want to establish the following:
"There exists a bijection from $N$ to any 'infinite subset of $N$'."

Definitions -
1. If there exists a bijection from $J_n$ -> $S$. Then S is finite AND countable. Else S is infinite (and maybe countable)
2. If there exists a bijection from $N$ -> $S$. Then S is infinite AND countable.

J_n = {1,2,3,....,n}
N = {1,2,3,....,n,....}

(I need this to prove subset of any countable set is countable. And I want to work out a rigorous proof for the same.)

Any pointers plz?

2. Originally Posted by aman_cc
I want to establish the following:
"There exists a bijection from $N$ to any 'infinite subset of $N$'."

Definitions -
1. If there exists a bijection from $J_n$ -> $S$. Then S is finite AND countable. Else S is infinite (and maybe countable)
2. If there exists a bijection from $N$ -> $S$. Then S is infinite AND countable.

J_n = {1,2,3,....,n}
N = {1,2,3,....,n,....}

(I need this to prove subset of any countable set is countable. And I want to work out a rigorous proof for the same.)

Any pointers plz?
If we're working in the context of proving that the subset of any countable set is countable itself, would it not suffice to prove that there is an injection from any infinite subset of $\mathbb{N}$ to $\mathbb{N}$ itself?

This would give us the result that the subset itself is countable, however not that it's cardinality is the same as that of $\mathbb{N}$. A proper injection from $A \subset N$ to $\mathbb{N}$ would be: $f:A \to \mathbb{N} : f(n) = n$ therefore $|A| \leq |\mathbb{N} |$...

Are you allowed to make the assumption that $\aleph_0 = |\mathbb{N}|$ is the smallest infinite cardinal number? If so, this would also give us the result that $|A| = |\mathbb{N}|$, otherwise, I would need to think of another way to prove equivalence.

3. Originally Posted by Defunkt
If we're working in the context of proving that the subset of any countable set is countable itself, would it not suffice to prove that there is an injection from any infinite subset of $\mathbb{N}$ to $\mathbb{N}$ itself?

This would give us the result that the subset itself is countable, however not that it's cardinality is the same as that of $\mathbb{N}$. A proper injection from $A \subset N$ to $\mathbb{N}$ would be: $f:A \to \mathbb{N} : f(n) = n$ therefore $|A| \leq |\mathbb{N} |$...

Are you allowed to make the assumption that $\aleph_0 = |\mathbb{N}|$ is the smallest infinite cardinal number? If so, this would also give us the result that $|A| = |\mathbb{N}|$, otherwise, I would need to think of another way to prove equivalence.
Thanks yes I would agree to you.

You seem to use that if there is an injection from S into N, S is countable,

I want to prove this.

I am referring Rudin. Definitions he has given is that S is countable IFF there is a bi-jection between S and N.

About assuming cardinality of N - I guess these are much stronger statements which are not needed in this context. We should be able to do whatever definitions we have at our disposal.

Please excuse me if I am off the track. I am reading all this on my own - so might not really know the established methods.

Thanks

4. Originally Posted by aman_cc
I want to establish the following:
"There exists a bijection from $N$ to any 'infinite subset of $N$ '."
Originally Posted by aman_cc
I am referring Rudin. Definitions he has given is that S is countable IFF there is a bi-jection between S and N.
You say that you are reading Rudin. Well notice the statement posted in the first quote is found as theorem 2.10 in Rudin. His proof depends upon $\mathbb{J}$, the symbol he uses for $\mathbb{Z}^+$, being well ordered (every non-empty subset having a first term).

Although Rudin does not use this, many other authors do.
Is $S = \bigcup\limits_n {E_n }$ is the countable union of countable sets then $S = \bigcup\limits_n {F_n }$ where $n \ne m\, \Rightarrow \,F_n \cap F_m = \emptyset$.
In other words, $S$ is the countable union of pairwise disjoint sets, each of which is at most countable.
So $x\in S\, \Rightarrow \, x=f¬_{n,j}\in F_n$ define $\phi :S \mapsto J$ as $\phi(x)=2^n\cdot 3^j$.
It is easy to show that $\phi(x)$ is an injection. So use 2.10 to conclude that $S$ is at most countable.

5. Originally Posted by Plato
You say that you are reading Rudin. Well notice the statement posted in the first quote is found as theorem 2.10 in Rudin. His proof depends upon $\mathbb{J}$, the symbol he uses for $\mathbb{Z}^+$, being well ordered (every non-empty subset having a first term).

Although Rudin does not use this, many other authors do.
Is $S = \bigcup\limits_n {E_n }$ is the countable union of countable sets then $S = \bigcup\limits_n {F_n }$ where $n \ne m\, \Rightarrow \,F_n \cap F_m = \emptyset$.
In other words, $S$ is the countable union of pairwise disjoint sets, each of which is at most countable.
So $x\in S\, \Rightarrow \, x=f¬_{n,j}\in F_n$ define $\phi :S \mapsto J$ as $\phi(x)=2^n\cdot 3^j$.
It is easy to show that $\phi(x)$ is an injection. So use 2.10 to conclude that $S$ is at most countable.

Thanks Defunkt and Plato. It's beginning to make sense. Let me please read your arguments more carefully. Thanks again.