For set S, the set of naturals N, and a function f, if f : S → N is injective, but NOT surjective, is S finite?
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?
No that does not work.
One way to define infinite is called Dedekind infinite
A set $\displaystyle S$ is infinite if there is a non-surjective injection mapping $\displaystyle S\to S$.
So $\displaystyle S$ is finte if every injection $\displaystyle S\to S$ 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...?
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.
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.