Thread: a set is infinite iff there is a bijection between it and a proper subset

I've been trying to prove that a set S is infinite if any only if there is a proper subset S' and a bijection .

Assuming the bijection exists, it's pretty clear that S cannot be finite, and it was easy to prove this. But I'm not having much luck going the other direction:

Assuming S is not finite, prove there exists with a bijection .

Any tips?

How does your textbook define infinite set ?

The textbook's definition is as follows:

A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.

... so essentially we have infinite defined as not finite.

Originally Posted by pswoo

The textbook's definition is as follows:
A set S is finite if it is empty or if there is a natural number n such that {1, 2, ..., n} and S have the same cardinality. A set that is not finite is said to be infinite.
... so essentially we have infinite defined as not finite.

That is a definition that I do not use in my presentations of this material.
Therefore, sad to say, I do not see a good way to do this.
Maybe someone else here knows this approach.

Here is my solution.

We'll prove that if is infinite, then is in bijection with a proper subset of itself.

This is obvious if is countable, as if we remove one element, we still have a countable set, so we'll assume is uncountable.

It is true that any infinite set has a countable subset .

Define the bijection as follows:

Then define the bijection as follows:

If then .
Otherwise, , where .

Then is a bijection from to .

I'll illustrate an example with the real numbers.

has a countable subset, .

Then will map 1 to 2, 2 to 3, etc .. and everything else will remain fixed.

We thus have a bijection from to .