1. ## Infinte Sets

Some notations:
$\displaystyle J_n = \{x|x \in N, 1\leq x \leq n\}$
For any two sets A,B; $\displaystyle 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 $\displaystyle S \cong J_n$ for some $\displaystyle 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 $\displaystyle 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 $\displaystyle S \cong S' \Rightarrow$ there exists no $\displaystyle n \in N$ such that $\displaystyle S \cong J_n$

Outline of my attempt
1. Let $\displaystyle S \cong J_n$ for some $\displaystyle n \in N$
2. Prove $\displaystyle S' \cong J_m$ where $\displaystyle m<n$
3. Assume $\displaystyle S \cong S'$
4. Now we have $\displaystyle 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 $\displaystyle n \in N$ such that $\displaystyle S \cong J_n \Rightarrow$ there exists a proper subset of S, S', where $\displaystyle 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?

2. Hello aman_cc
Originally Posted by aman_cc
...
2. Prove $\displaystyle S' \cong J_m$ where $\displaystyle 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 $\displaystyle f : S\mapsto J_n$ and $\displaystyle f:S'\mapsto J_m$ where $\displaystyle m \le n$. We must prove $\displaystyle m < n$.

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

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

Further
$\displaystyle \forall r \in S'$

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

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

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

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

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

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

Further
$\displaystyle \forall r \in S'$

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

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

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

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

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

4. Originally Posted by aman_cc
Some notations:
$\displaystyle J_n = \{x|x \in N, 1\leq x \leq n\}$
For any two sets A,B; $\displaystyle 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 $\displaystyle S \cong J_n$ for some $\displaystyle 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 $\displaystyle 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 $\displaystyle S$ is a finite set and $\displaystyle J_n=\{1,2,\cdots,n\}$ then:
1) if there is an injection $\displaystyle f:S\mapsto J_n$ then $\displaystyle |S|\le n$.
1) if there is a surjection $\displaystyle g:J_n\mapsto S$ then $\displaystyle |S|\le n$.

There also a powerful theorem that applies to all sets:
There is an injection $\displaystyle f:A\mapsto B$ if and only if there is a surjection $\displaystyle 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 $\displaystyle J=\mathbb{Z}^+$ then $\displaystyle \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.

5. 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 $\displaystyle S$ is a finite set and $\displaystyle J_n=\{1,2,\cdots,n\}$ then:
1) if there is an injection $\displaystyle f:S\mapsto J_n$ then $\displaystyle |S|\le n$.
1) if there is a surjection $\displaystyle g:J_n\mapsto S$ then $\displaystyle |S|\ge n$.

There also a powerful theorem that applies to all sets:
There is an injection $\displaystyle f:A\mapsto B$ if and only if there is a surjection $\displaystyle 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 $\displaystyle J=\mathbb{Z}^+$ then $\displaystyle \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 $\displaystyle g:J_n\mapsto S$ then $\displaystyle |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 $\displaystyle f:S\mapsto J_n$ then $\displaystyle |S|\le n$.
1) if there is a surjection $\displaystyle g:J_n\mapsto S$ then $\displaystyle |S|\le n$.

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