Bijection - Countability

**aman_cc** · October 20th 2009, 03:18 AM

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?

**Defunkt** · October 20th 2009, 03:55 AM

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.

**aman_cc** · October 20th 2009, 04:03 AM

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

**Plato** · October 20th 2009, 08:02 AM

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.

**aman_cc** · October 20th 2009, 08:42 AM

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.

Thread: Bijection - Countability

LinkBack

Thread Tools

Display

Bijection - Countability

Similar Math Help Forum Discussions

countability of a set

Countability

Countability

Countability

Countability

Search Tags