0

Let $X$ be a set then $X$ is infinite if and only if there is a $1-1$ map $X\to X$ which is not onto.

I don't know how to prove this? I read that,

A set $X$ is infinite if and only if it may be put into one-one correspondence with a proper subset of itself

but I got a bit confused because when they say it can put into a bijection of its proper subset does that mean the proper subset is also infinite? So the map is a bijection of an infinite set to am infinite set?

Tom
  • 1,079

3 Answers3

1

I assume you mean "$X$ is infinite if and only if there is a one-to-one map $X\to X$ which is not onto" (since otherwise every set is infinite, as the inclusion map $\Bbb N\to\Bbb R$ is an example of a map that is one-to-one but not onto). This is almost immediately equivalent to the characterization of an infinite set as one that may be put into one-to-one correspondence with a proper subset of itself. (Try writing out the definitions of one-to-one map, one-to-one correspondence, and proper subset to see how.)

In answer to your other questions, yes, the proper subset will be infinite, and that map will be a bijection of an infinite set to an infinite set. Neither of these is particularly relevant to the proof, though.

Cameron Buie
  • 102,994
  • I think my confusion is where it states " ... if and only if there is a one-to-one map X→X which is not onto" and then states, " ... infinite set as one that may be put into one-to-one correspondence with a proper subset of itself". A bijection is one-one and onto but the first statement says it is one-one but not onto. – Tom Aug 28 '13 at 04:31
  • Saying that $X$ may be put into one-to-one correspondence with a proper subset of itself means that there is a proper subset $Y$ of $X$ such that there is a one-to-one correspondence $f:X\to Y$. What if we think of $f$ as a function from $X$ to $X$? Is it one-to-one? Is it onto? – Cameron Buie Aug 28 '13 at 05:01
  • So lets say $X \to Y$ where the set $Y$ is distinct from $X$. Does that statement still follow? Or it only applies to maps of itself $X\to X$? – Tom Aug 28 '13 at 05:11
  • It only applies to maps of itself. If it were not so, then we could show that any singleton was infinite by exhibiting a one-to-one mapping from the singleton that was not onto (an easy task). – Cameron Buie Aug 28 '13 at 09:41
  • It's worth noting that in order to determine if a function is onto, we must have a domain and codomain specified. I discuss this further in my answer here (skip down to "*IMPORTANT POINTS*"). – Cameron Buie Aug 28 '13 at 18:04
  • 1
    You're very welcome! – Cameron Buie Aug 28 '13 at 19:49
1

Yes, the bijection will be between two infinite sets. For a specific example, let us take $X=\Bbb N$ which will include $0$. Now the map $n \to n+1$ is one-to-one because each element in the range is the image of only element of the domain. It is not onto because $0$ is not the image of any element of the domain. This is a specific case of your definition. You have probably seen many bijections between the naturals and other sets, some "larger" than the naturals (like the rationals) and some "smaller" (like the even numbers, squares, primes, etc.).

Ross Millikan
  • 374,822
  • We haven't properly learned rationals, reals, naturals, etc. yet. Maybe we should have been taught those before jumping into infinity? – Tom Aug 28 '13 at 04:32
  • Instead of rationals, maybe pairs of integers? Or at least the integers? – Ross Millikan Aug 28 '13 at 05:00
  • Nope, not even integers yet. We have discussed only one-one, onto, bijection and unions and intersects. – Tom Aug 28 '13 at 05:13
  • The point is that for finite sets, one-to-one functions are surjections are bijections. This is not true for infinite sets. Take the map over the naturals that takes $n$ to $n+1$. It is one-to-one but not onto because nothing goes to zero. This is a bijection with a proper subset. Going the other way, take the map that takes $0$ to $0$, and otherwise $n$ to $n-1$. It is surjective but not one-to-one. For the pairs, there is a bijection between $n$ and $(p,q)$ that you will see. You could look at http://en.wikipedia.org/wiki/Pairing_function for a preview. – Ross Millikan Aug 28 '13 at 15:13
1

The point in this definition is that we have a function $f\colon X\to X$ which is injective, but not surjective. On the other hand, every function is onto its range, so if we restrict the codomain we have that $f$ is a bijection with a proper subset of $X$.

To answer your question we need to know how you define an infinite set, and what set theoretic assumptions you are allowed to make, in particular the assumption of the axiom of choice, which may be needed for the proof (depending on your definition of infinite).

Asaf Karagila
  • 393,674
  • 1
    From the title, I would say that infinite proofs don't count. – Will Jagy Aug 28 '13 at 05:05
  • Well, zero is the empty set. – Asaf Karagila Aug 28 '13 at 05:08
  • Good thinking. There are fairly regular requests, on MSE, for bijective proofs. I don't know, some kind of religious thing. – Will Jagy Aug 28 '13 at 05:12
  • Is any map that maps a set into itself, like $X\to X$, $Y\to Y$ always not onto? – Tom Aug 28 '13 at 05:14
  • @WillJagy is there something wrong with my title? – Tom Aug 28 '13 at 05:16
  • @Tom: I don't understand your concern in the comment. As for the title, the hyphen is inside the LaTeX so it becomes a minus sign. – Asaf Karagila Aug 28 '13 at 05:19
  • 1
    @Tom, it is incorrect and rather humorous. Asaf is an expert, and i guess he is awake. Perhaps he will be able to explain in detail. Meanwhile, in English, your title implies that the proof is infinite, not any of the sets involved. A proof cannot be infinite, it is something written by a human being. – Will Jagy Aug 28 '13 at 05:20
  • @WillJagy Lol I never meant to be that. It is a bit silly. I was just trying to keep the title short. – Tom Aug 28 '13 at 05:22
  • @Will: Not only awake, but also barely hungover! – Asaf Karagila Aug 28 '13 at 05:30
  • @Tom: No. Maps from a set to itself can certainly be onto, such as the identity map. And they need not be one-to-one, as any constant map from a set with more than one element into itself shows us. – Cameron Buie Aug 28 '13 at 09:49