How does your textbook define infinite set ?
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?
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.
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 .