uncountable

**particlejohn** · July 3rd 2008, 11:33 AM

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?

**CaptainBlack** · July 3rd 2008, 11:42 AM

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

**particlejohn** · July 3rd 2008, 12:03 PM

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

**ThePerfectHacker** · July 3rd 2008, 12:06 PM

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

**awkward** · July 3rd 2008, 01:58 PM

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.

**ThePerfectHacker** · July 10th 2008, 12:37 PM

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.

Thread: uncountable

LinkBack

Thread Tools

Display

uncountable

Similar Math Help Forum Discussions

cantor set is uncountable

uncountable set

[SOLVED] uncountable subset is itself uncountable

[SOLVED] Uncountable: A is a countable subset of an uncountable set X, prove X \ A un

N^N is uncountable

Search Tags