1. ## 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?

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

3. 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)$.

4. 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 (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$.

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

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