Infinte Sets

Printable View

November 21st 2009, 06: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<n$
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<n$ . 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?
November 21st 2009, 08:47 AM
Grandad

Hello aman_cc

Quote:

Originally Posted by aman_cc

...
2. Prove $S' \cong J_m$ where $m<n$
...

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

Grandad
November 21st 2009, 09:23 AM
aman_cc

Quote:

Originally Posted by Grandad

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

Grandad

Hi Grandad - Thanks. I have not been able to follow some of your conclusions.
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.
November 21st 2009, 09: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.
November 21st 2009, 06: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?