Yes or No? Injection into the Naturals finite?

[mpitluk]

For any set S, the natural numbers N and function f, if f : S → N is injective but not surjective, is S finite?

 

[DonAntonio]

For any set S, the natural numbers N and function f, if f : S → N is injective but not surjective, is S finite?

$$S:=\{1,3,5,7,...\}\,\,,\,\,f:S\to\mathbb{N}\,,\,\,f(2n-1):=2n-1$$

DonAntonio

 

[mpitluk]

Sorry, I'm not sure what that tells me. I have VERY little mathematics training, but ended up taking a math-logic course heavy on notation and dependent on higher-math knowledge.

It seems to me what you are saying, though I am probably dead wrong, is that the set of odd naturals is in a bijection with the naturals. And thus, they have the same cardinality. But, I'm asking about a case in which S is not surjective.

 

[SteveL27]

Sorry, I'm not sure what that tells me. I have VERY little mathematics training, but ended up taking a math-logic course heavy on notation and dependent on higher-math knowledge.

It seems to me what you are saying, though I am probably dead wrong, is that the set of odd naturals is in a bijection with the naturals. And thus, they have the same cardinality. But, I'm asking about a case in which S is not surjective.

You map each odd number in the set of odd numbers, to the same number in the set of natural numbers. So 1 goes to 1, 3 goes to 3, 5 goes to 5, etc.

This is an injection, right?

But it's not a surjection, because (for example) 6 doesn't get hit.

So this is an example of an injection into N that's not a surjection, but the domain is not finite.

 

[mpitluk]

Wow. I see where I went wrong. What I meant to ask, while trying to get the notation down, was: if you have a set A that doesn't have a bijection with a set S such that |S| = |N|, then is A finite? It seems to me it would be (by definition, really).

 

[mpitluk]

*A doesn't have a bijection with S because f : A → S is not surjective, while it is injective.

 

[DonAntonio]

Wow. I see where I went wrong. What I meant to ask, while trying to get the notation down, was: if you have a set A that doesn't have a bijection with a set S such that |S| = |N|, then is A finite? It seems to me it would be (by definition, really).

No. S could be, say the set of all real numbers, which cannot mapped bijectively with the naturals...

And "by definition" of what?

DonAntonio

 

[mpitluk]

And "by definition" of what?
DonAntonio

I was referring to the following definition: for a set S and the set of naturals N, if |S| < |N|, then is S finite. I see where I went wrong. I am just trying to define a finite set using the terms "bijection," "surjection," and "injection."

No. S could be, say the set of all real numbers, which cannot mapped bijectively with the naturals...
DonAntonio

Might this be right: if for every mapping f between S and N, f : S → N is not surjective, then S is finite.

 

[DonAntonio]

I was referring to the following definition: for a set S and the set of naturals N, if |S| < |N|, then is S finite. I see where I went wrong. I am just trying to define a finite set using the terms "bijection," "surjection," and "injection."



Might this be right: if for every mapping f between S and N, f : S → N is not surjective, then S is finite.

I guess that could work, but why do you seem to enjoy making things messy? Go to the following definition:

"A set S is finite iff EVERY proper subset of S has a cardinality strictly smaller than that of S".

Voila

DonAntonio

 

[mpitluk]

I guess that could work, but why do you seem to enjoy making things messy? Go to the following definition:

"A set S is finite iff EVERY proper subset of S has a cardinality strictly smaller than that of S".

Voila

DonAntonio

Haha...I'm just trying to make connections. This "mess" has helped me understand the definition of cardinality better: sets A, B have the same cardinality iff a bijection exists between A, B. I had no previous knowledge of bijection, injection, and surjection, so I was just trying to get to know the terms. I appreciate the patience.