# Infinte Sets

• Nov 21st 2009, 07:12 AM
aman_cc
Infinte Sets
Some notations:
$J_n = \{x|x \in N, 1\leq x \leq n\}$
For any two sets A,B; $A \cong B \Rightarrow$ there exists a bijection between A and B

I have read following two definitions of infinite sets:

1. Set S, is finite if $S \cong J_n$ for some $n \in N$. If a set is not finite, it is infinite.

2. Set is infinite if there exits a proper subset of S, say S' such that $S \cong S'$

Problem: I want to prove the equivalence of these two definitions.
My Attempt: I have to demonstrate both Part 1 and Part 2 below -

Part 1: To prove, if $S \cong S' \Rightarrow$ there exists no $n \in N$ such that $S \cong J_n$

Outline of my attempt
1. Let $S \cong J_n$ for some $n \in N$
2. Prove $S' \cong J_m$ where $m
3. Assume $S \cong S'$
4. Now we have $J_n \cong S \cong S' \cong J_m \Rightarrow J_n \cong J_m, m. This leads to a contradiction if you apply pigeon-hole principle. Hence assumption in step 3 is not valid and we are done.

Problem I am facing: Step 2 above. How do I prove it formally. I know it sounds so much true from intuition but how do I show it in the language of formal mathematics.

Part 2: To prove, if there doens't exist any $n \in N$ such that $S \cong J_n \Rightarrow$ there exists a proper subset of S, S', where $S \cong S'$
Problem I am facing: Don't even know how to start with this one?

Also is my approach to this question correct, or there are other ways to do it?
• Nov 21st 2009, 09:47 AM
Hello aman_cc
Quote:

Originally Posted by aman_cc
...
2. Prove $S' \cong J_m$ where $m
...

Problem I am facing: Step 2 above. How do I prove it formally. I know it sounds so much true from intuition but how do I show it in the language of formal mathematics.

I'm not sure about Part 2, but can't you say something like this for Part 1, Step 2?

Suppose that $f : S\mapsto J_n$ and $f:S'\mapsto J_m$ where $m \le n$. We must prove $m < n$.

$S'$ is a proper subset of $S \Rightarrow \exists p \in S$ for which $p \notin S'$

Then $f(p)\notin f(S')$, for otherwise $f^{-1}\Big(f(p)\Big) \in S'$.

Further
$\forall r \in S'$

$S' \subset S \Rightarrow r \in S$

$\Rightarrow f(S')\subseteq f(S)$
But we have now found a $f(p) \in f(S)$ for which $f(p) \notin f(S')$. Hence $f(S') = J_m$ is a proper subset of $f(S)=J_n \Rightarrow m < n$.

• Nov 21st 2009, 10:23 AM
aman_cc
Quote:

Hello aman_ccI'm not sure about Part 2, but can't you say something like this for Part 1, Step 2?

Suppose that $f : S\mapsto J_n$ and $f:S'\mapsto J_m$ where $m \le n$. We must prove $m < n$.

$S'$ is a proper subset of $S \Rightarrow \exists p \in S$ for which $p \notin S'$

Then $f(p)\notin f(S')$, for otherwise $f^{-1}\Big(f(p)\Big) \in S'$.

Further
$\forall r \in S'$

$S' \subset S \Rightarrow r \in S$

$\Rightarrow f(S')\subseteq f(S)$
But we have now found a $f(p) \in f(S)$ for which $f(p) \notin f(S')$. Hence $f(S') = J_m$ is a proper subset of $f(S)=J_n \Rightarrow m < n$.

I am going to list them
1. $f:S'\mapsto J_m$. Why should that be?

2. $m \le n$. Again why can't m>n?

3. "Hence http://www.mathhelpforum.com/math-he...b6d76348-1.gif is a"
We never showed f(S') = Jm

I know all the above are trivial, but problem I am having is to put them formally. Apologies, but with my limited understanding, I think we still have some holes to plug, though I fully follow the idea you are proposing.
• Nov 21st 2009, 10:38 AM
Plato
Quote:

Originally Posted by aman_cc
Some notations:
$J_n = \{x|x \in N, 1\leq x \leq n\}$
For any two sets A,B; $A \cong B \Rightarrow$ there exists a bijection between A and B

I have read following two definitions of infinite sets:
1. Set S, is finite if $S \cong J_n$ for some $n \in N$. If a set is not finite, it is infinite.

2. Set is infinite if there exits a proper subset of S, say S' such that $S \cong S'$

It is really difficult to ‘jump in’ the middle of any development of finite/infinite sets.
We do not know what theorems you have at hand.
Generally, we would know these for finite sets.
If $S$ is a finite set and $J_n=\{1,2,\cdots,n\}$ then:
1) if there is an injection $f:S\mapsto J_n$ then $|S|\le n$.
1) if there is a surjection $g:J_n\mapsto S$ then $|S|\le n$.

There also a powerful theorem that applies to all sets:
There is an injection $f:A\mapsto B$ if and only if there is a surjection $g:B\mapsto A$.
With those we show that no finite set bijects with a proper subset of itself.

The second definition is known as Dedekind Infinite.
If $J=\mathbb{Z}^+$ then $\left( {\forall n} \right)\left[ {J\backslash J_n } \right]$ is also infinite.
Do you see how you might use this to show equivalence with the first definition.
• Nov 21st 2009, 07:59 PM
aman_cc
Quote:

Originally Posted by Plato
It is really difficult to ‘jump in’ the middle of any development of finite/infinite sets.
We do not know what theorems you have at hand.
Generally, we would know these for finite sets.
If $S$ is a finite set and $J_n=\{1,2,\cdots,n\}$ then:
1) if there is an injection $f:S\mapsto J_n$ then $|S|\le n$.
1) if there is a surjection $g:J_n\mapsto S$ then $|S|\ge n$.

There also a powerful theorem that applies to all sets:
There is an injection $f:A\mapsto B$ if and only if there is a surjection $g:B\mapsto A$.
With those we show that no finite set bijects with a proper subset of itself.

The second definition is known as Dedekind Infinite.
If $J=\mathbb{Z}^+$ then $\left( {\forall n} \right)\left[ {J\backslash J_n } \right]$ is also infinite.
Do you see how you might use this to show equivalence with the first definition.

Thanks Plato.
I think you meant -
if there is a surjection $g:J_n\mapsto S$ then $|S|\le n$.

Well I guess I need to be comfortable with all the concepts you mentioned before I go any further.

So, if I may ask one question - the two theorems you said

1) if there is an injection $f:S\mapsto J_n$ then $|S|\le n$.
1) if there is a surjection $g:J_n\mapsto S$ then $|S|\le n$.

I trust both of them follow directly from pigeon-hole principle. Or, there is something more basic required?