Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that a set $X$ is infinite if and only if $X$ is equivalent to a proper subset of itself.

If $X$ is finite, then suppose $|X|=n$. Any proper subset $Y$ of $X$ has size $m<n$, and so there cannot be any bijective mapping between $Y$ and $X$.

If $X$ is countably infinite, then suppose $X=\{x_1,x_2,\ldots\}$. We can map $X$ to $Y=\{x_2,x_3,\ldots\}$ by using the map $f(x_i)=x_{i+1}$.

But what if $X$ is uncountably infinite? How can we specify the mapping?

share|improve this question
1  
What does uncountably infinite mean for you? That there is an injection $\mathbb N \to X$, but no bijection? –  martini Jun 8 '13 at 22:01
1  
Which definition of inifinite do you use? –  Hagen von Eitzen Jun 8 '13 at 22:01

2 Answers 2

up vote 5 down vote accepted

The solution was in the previous title: if $X$ is infinite, then it contains a countable infinite subset, say $X_0$. Then you gave a bijection $X_0\to X_0\setminus\{x_1\}$, that extends to a bijection $X\to X\setminus\{x_1\}$, that acts as identity on $X\setminus X_0$.

share|improve this answer
1  
Actually, you need AC to get a countable infinite subset of an uncountable set. See on MO. –  vadim123 Jun 8 '13 at 22:43

The answer is no if you do not assume the axiom of choice or a weaker version such as countable choice. If $X$ is an amorphous set, then it is Dedekind-finite, which is the negation of the property in the question.

share|improve this answer
    
Actually, countable choice suffices. It's okay, so long as we have just enough choice so that $\aleph_0$ is comparable to every cardinality. –  Cameron Buie Jun 8 '13 at 22:54
    
Thanks, I'll elaborate. –  vadim123 Jun 8 '13 at 22:56
    
Mentioning amorphous sets seems a bit of a distraction. Any infinite Dedekind-finite set is a counterexample (by definition), regardless of whether it is amorphous or not. The thing to point out is that the existence of such sets is (relatively) consistent with the other axioms of set theory, excluding choice. –  Andres Caicedo Jun 8 '13 at 23:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.