# uncountable

• Jul 3rd 2008, 11:33 AM
particlejohn
uncountable
Prove that if a set $S$ is countably or uncountably infinite, then there is a proper subset $T \subset S$ and a bijection $f: S \to T$.

Consider the case in which the set is countably infinite. Then $\text{card}(S) = \aleph_0$. Then there is a set $T$ such that $\text{card}(T) < \text{card}(S)$. And so there is an injective function $f: T \to S$. Then $f: S \to T$ is an injection and also a surjection which implies that it is a bijection.

Consider case in which $S$ is uncountably infinite. Then $\text{card}(S) > \aleph_{0}$. Suppose that $T$ is a set such that $\text{card}(S) > \text{card}(T) > \aleph_{0}$.

Now how do I proceed?
• Jul 3rd 2008, 11:42 AM
CaptainBlack
Quote:

Originally Posted by particlejohn
Prove that if a set $S$ is countably or uncountably infinite, then there is a proper subset $T \subset S$ and a bijection $f: S \to T$.

Consider the case in which the set is countably infinite. Then $\text{card}(S) = \aleph_0$. Then there is a set $T$ such that $\text{card}(T) < \text{card}(S)$. And so there is an injective function $f: T \to S$. Then $f: S \to T$ is an injection and also a surjection which implies that it is a bijection.

Consider case in which $S$ is uncountably infinite. Then $\text{card}(S) > \aleph_{0}$. Suppose that $T$ is a set such that $\text{card}(S) > \text{card}(T) > \aleph_{0}$.

Now how do I proceed?

What definition are you using for an infite set?

It looks to me as though what you are trying to prove is the Dedekind's definition of an infinite set.

RonL
• Jul 3rd 2008, 12:03 PM
particlejohn
Quote:

Originally Posted by CaptainBlack
What definition are you using for an infite set?

It looks to me as though what you are trying to prove is the Dedekind's definition of an infinite set.

RonL

A set $S$ is said to be uncountably infinite if $\aleph_{0} < \text{card}(S)$.
• Jul 3rd 2008, 12:06 PM
ThePerfectHacker
Quote:

Originally Posted by particlejohn
Prove that if a set $S$ is countably or uncountably infinite, then there is a proper subset $T \subset S$ and a bijection $f: S \to T$.

A set is finite if it is equiponent to a natural number. A set is infinite if it is not finite (Rofl) (no seriously, that is how we define it). If $A$ is finite then there is no proper subset $B$ with $|A| = |B|$. Thus, if $A$ has a proper subset equiponent to it then it means $A$ is infinite. We may wonder if $A$ is a set such that it is has a proper subset equiponent to it, then is it infinite (this property is Dedekind infinite)? Phrased more differently are infinite sets equivalent to Dedekind infinite sets? With the Axiom of Choice this is true. Let $A$ be an infinite set. And let $a\in A$. Then since $|A| > |\{ a\}|$ it means $|A - \{ a\}| = |A|$. Thus, $B = A - \{ a\}\subset A$ is equipotent to $A$.
• Jul 3rd 2008, 01:58 PM
awkward
Quote:

Originally Posted by particlejohn
Prove that if a set $S$ is countably or uncountably infinite, then there is a proper subset $T \subset S$ and a bijection $f: S \to T$.

Here is one way to proceed.

Since $S$ is infinite, it contains a countable subset $E$. Define $f$ on $E$ by $f(e_i) = e_{i+1} \text{ and } f(x) = x$ elsewhere. Then $f$ is one-to-one but $e_1$ is not in its range.
• Jul 10th 2008, 12:37 PM
ThePerfectHacker
Quote:

Originally Posted by awkward
Since $S$ is infinite, it contains a countable subset $E$.

By the way, in case you are interested this uses the Axiom of Choice. (Happy)