Thread: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

For set S, the set of naturals N, and a function f, if f : S → N is injective, but NOT surjective, is S finite?

Not necessarily, for example if S is the set of natural numbers and f(n)=2n.

Thanks for the response. I meant to ask: for some set S and any countable set A, if f : S → A is injective but not surjective, is S finite? I see that B = {1, 3, 5, 7,...} can inject into the naturals, but it is not surjective as 6 is unmapped. However, B is infinite. Is this right? Thanks, again.

I can see that is wrong as well for the same reason. I am just trying to say that S is finite using the terms "bijective" "injective" and/or "surjective," so far, to no avail. I'm taking a grad-level math-logic class as a mere philosophy undergrad (in order to apply for departmental honors) and so, I'm just trying to make connections between the terms.

Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?

Originally Posted by mpitluk

Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?

No that does not work.
One way to define infinite is called Dedekind infinite
A set is infinite if there is a non-surjective injection mapping .
So is finte if every injection is also an surjection.

Plato, can you clarify a little? I understand a set S to be Dedekind infinite iff some proper subset of S has the same cardinality as S, i.e., there is some f : A ⊂ S → S such that f is bijective. Maybe what you're saying is the same...?

Originally Posted by mpitluk

I understand a set S to be Dedekind infinite iff some proper subset of S has the same cardinality as S, i.e., there is some f : A ⊂ S → S such that f is bijective. Maybe what you're saying is the same...?

Yes, this is the same. Plato says that S is infinite iff there exists an f : S -> S such that f is an injection and f is not a surjection. Let A be the image of f; then A ⊂ S and f is a bijection between S and A.

Originally Posted by mpitluk

Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?

The natural interpretation of this statement is

∀S ∀f: S -> N. (f is not surjective => S is finite).

This is false. However, the following statement:

∀S. (∀f : S -> N. f is not surjective) => S is finite

is true. It can be expressed in English as: "For every S, if every function f: S -> N is not surjective, then S is finite. Note that "if" is located before "every" implying that the universal quantifier over f is in the assumption.