Finite>Infinite

**ThePerfectHacker** · February 18th 2006, 03:42 PM

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".

**topsquark** · February 18th 2006, 04:19 PM

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

**ThePerfectHacker** · February 18th 2006, 04:24 PM

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.

**CaptainBlack** · February 18th 2006, 11:42 PM

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

**ThePerfectHacker** · February 19th 2006, 10:03 AM

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|$ .

**CaptainBlack** · February 19th 2006, 10:26 AM

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

**CaptainBlack** · February 19th 2006, 11:06 AM

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

**ThePerfectHacker** · February 19th 2006, 02:47 PM

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.

**CaptainBlack** · February 19th 2006, 08:53 PM

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

**ThePerfectHacker** · February 20th 2006, 11:37 AM

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.

Thread: Finite>Infinite

LinkBack

Thread Tools

Display

Finite>Infinite

Similar Math Help Forum Discussions

Finite and infinite sets

finite or infinite?

Finite and Infinite order

finite and infinite sets...denumerable

infinite/finite limits

Search Tags