# Homework Help: Proof about infinite subsets

1. Jan 6, 2013

### cragar

1. The problem statement, all variables and given/known data
Let X be a set and let f be a one-to-one mapping of X into itself such that
$f[X] \subset X$ Then X is infinite.
3. The attempt at a solution
Lets assume for the sake of contradiction that X is finite and there is an f such that it maps all of the elements of X to a proper subset of X called Y. And this function also preserves the 1-to-1 mapping. If Y is a proper subset then |Y|<|X| and if X is finite then
Y is also finite, but there is a problem with the one to one mapping, if Y has less elements then X then there is no 1-to-1 mapping. So this is a contradiction of our original assumption therefore X is infinite.

2. Jan 6, 2013

### voko

The reasoning is correct in general, but perhaps somewhat informal. Formally, you could recall that a one-to-one mapping of two sets implies that the two sets have equal cardinality. And for finite sets, cardinality is simply the number of their elements.

3. Jan 6, 2013

### clamtrox

I think you are thinking of mappings that are both one-to-one and onto. If the mapping is only one to one, then the cardinalities don't need to be equal -- there for example certainly is a one to one mapping from N to R, f(x) = x.

4. Jan 6, 2013

### voko

No, what I mean is that the cardinality of the image of X (where f is onto) must be equal to that of X. Invoking the finiteness of X completes the proof.

5. Jan 6, 2013

### HallsofIvy

"
But nothing is said about f being "onto".

6. Jan 6, 2013

### voko

Any map is "onto" its image.