# Finite>Infinite

Printable View

• Feb 18th 2006, 04:42 PM
ThePerfectHacker
Finite>Infinite
Proof that if $S$ is any finite set and $T$ is any infinite set then $|S|<|T|$. In mathematical words prove that there exists a surjection $\phi:S\to T$ which is not one-to-one.

What I am trying to get to is perhaps there exists a set that cannot be placed with ono-to-one correspondence with a proper subset and is greater then an infinite set! I doubt that but I am trying to connect this to my other post on "the set of all finite sets".
• Feb 18th 2006, 05:19 PM
topsquark
Quote:

Originally Posted by ThePerfectHacker
Proof that if $S$ is any finite set and $T$ is any infinite set then $|S|<|T|$. In mathematical words prove that there exists a surjection $\phi:S\to T$ which is not one-to-one.

What I am trying to get to is perhaps there exists a set that cannot be placed with ono-to-one correspondence with a proper subset and is greater then an infinite set! I doubt that but I am trying to connect this to my other post on "the set of all finite sets".

You can't. In order to have a surjection between the sets S and T, the cardinality of T must be less than or equal to the cardinality of S. Otherwise you wind up having at least one point of S being defined to have more than one value in T, which means your "function" violates one of the definitions of a function: No function can have multiple values on an element of the domain.

-Dan
• Feb 18th 2006, 05:24 PM
ThePerfectHacker
Quote:

Originally Posted by topsquark
You can't. In order to have a surjection between the sets S and T, the cardinality of T must be less than or equal to the cardinality of S. Otherwise you wind up having at least one point of S being defined to have more than one value in T, which means your "function" violates one of the definitions of a function: No function can have multiple values on an element of the domain.

-Dan

Can you proof it? I understand what you are saying but you are using the intuitive meaning of finity and infinity.
• Feb 19th 2006, 12:42 AM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
Can you proof it? I understand what you are saying but you are using the intuitive meaning of finity and infinity.

I didn't see any reference to finite or infinite in topsquarks post, only to
equality or inequality of cardinality. This uses an implied reference to the
usual definition of infinite as applied to sets. This fully subsumes the normal
dichotomy of finite/infinite.

RonL
• Feb 19th 2006, 11:03 AM
ThePerfectHacker
If a set $S$ has property:
$|S|\not =|S'|,\forall S'\subset S$.
And another set $T$ has property:
$|T|=|T'|,\exists T'\subset T$.

Prove that,
$|S|<|T|$.
• Feb 19th 2006, 11:26 AM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
If a set $S$ has property:
$|S|\not =|S'|,\forall S'\subset S$.
And another set $T$ has property:
$|T|=|T'|,\exists T'\subset T$.

Prove that,
$|S|<|T|$.

I think you want to say:

If a set $S$ has property:
$
\forall S'\subset S,\ |S|\not =|S'|
$
.

And another set $T$ has property:
$
\exists T'\subset T,\ |T|=|T'|
$
.

Prove that,
$|S|<|T|$

RonL
• Feb 19th 2006, 12:06 PM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
I think you want to say:

If a set $S$ has property:
$
\forall S'\subset S,\ |S|\not =|S'|
$
.

And another set $T$ has property:
$
\exists T'\subset T,\ |T|=|T'|
$
.

Prove that,
$|S|<|T|$

RonL

To do this I think we will need more machinery than I suspect Mr Hacker
has available, so it would be advantageous to show:

If $S$ is a set such that

$
\forall S'\subset S,\ |S|\not =|S'|
$
.

then $\forall P\subset S$

$
\forall P'\subset P,\ |P|\not =|P'|
$
.

RonL
• Feb 19th 2006, 03:47 PM
ThePerfectHacker
Perhaps, we can do this, (please check for errors).
If $\phi :S\to T$ is bijective.
Then $\exists T'\subset T\mbox { with }|T'|=|T|$
Thus,
$\phi^{-1}[T']\subset S$ with,
$|\phi^{-1}[T']|=|S|$
but that is impossible, thus,
$|S|\not =|T|$.
Now it remains to complete that,
$|S|<|T|$ by assuming $|S|>|T|$
and then using trichtonomy.
• Feb 19th 2006, 09:53 PM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
Perhaps, we can do this, (please check for errors).
If $\phi :S\to T$ is bijective.

We say $|S| \ge |T|$ if there exists a one to one map from $S$ into $T$

We say $|S|=|T|$ iff $|S| \ge |T|$ and $|T| \ge |S|$.

You will now need to prove the existance of the bijection.

RonL
• Feb 20th 2006, 12:37 PM
ThePerfectHacker
Quote:

Originally Posted by CaptainBlack
We say $|S| \ge |T|$ if there exists a one to one map from $S$ into $T$

We say $|S|=|T|$ iff $|S| \ge |T|$ and $|T| \ge |S|$.

You will now need to prove the existance of the bijection.

RonL

No, I do not. I should have said this in the proof but I forgot, that I assumed that they had the same cardinality thus by definition there exists a bijective map, which leads to a contradiction.