# Infinte Sets

• Nov 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
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, 08: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, 09: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, 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.
• Nov 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?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 84, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.999830424785614, "perplexity": 4411.250977232881}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-44/segments/1476988720468.71/warc/CC-MAIN-20161020183840-00376-ip-10-171-6-4.ec2.internal.warc.gz"}