# cardianlity

• Oct 11th 2008, 10:54 PM
lllll
cardianlity
Let f be a 1-1 function from A into B with B finite. Show that A is finite.

I was thinking along the lines of since $A \stackrel{1-1}{\mapsto} B$ and since $B=\{b_1, \ b_2,\ ..., \ b_n\}$, then A can have the same number of element as B, or slightly less, given that it's 1-1. Now since we can arrange all the elements of B, we should be able to do the same for A... but I'm not too sure on how to show this.
• Oct 12th 2008, 12:49 AM
CaptainBlack
Quote:

Originally Posted by lllll
Let f be a 1-1 function from A into B with B finite. Show that A is finite.

What definition of finite are you using?

Is it that a set $S$ is finite iff there is a bijection defined on it to a set of consecutive naturals with a largest element.

If so let $f_b$ be a bijection from $B$ to $\{1, 2, .., n\}$ then $f_b \circ f$ is a bijection from $A$ to $f_b(f(A))$ . Now we just need to introduce a renumbering function on $f_b(f(A))$ so these are consecutive integers.

Consider:

$f_{rn}(x)=\sum_{z \in f_b(f(A))} \chi_{\{y \in f_b(f(A)),\ y\le x\}}(z)$

Where $\chi_U$ is the indicator or charateristic function of $U$ (that is it is $1$ for any element of $U$ and zero otherwise).

Then :

$
f_{rn}\circ f_b \circ f
$

is a bijection of $A$ to a set of consecutive integers with a largest element(you will have to fill in the detailed justification of this).

CB
• Oct 12th 2008, 12:51 AM
Moo
Hello,

B is finite means that there exists an injection from B into $\mathbb{N}$

So $A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} \mathbb{N}$

Where f is a bijection (1-1) and g is an injection.
Show that $g \circ f$ is an injection and you'll prove that there exists an injection from A into $\mathbb{N}$ and hence A is finite.

______________________________________________
You can also do it by cardinalities :
$\text{B is finite } \Leftrightarrow \text{ Card}(B) < \text{Card}(\mathbb{N})$

If there is a bijection between A and B, then $\text{Card}(A)=\text{Card}(B)$

Hence $\text{Card}(A)< \text{Card}(\mathbb{N}) \implies \text{ A is finite}$

But this requires to know the theorems relating cardinality to bijections, injections and surjections..
• Oct 12th 2008, 12:55 AM
Jhevon
Quote:

Originally Posted by Moo
Hello,

B is finite means that there exists an injection from B into $\mathbb{N}$

So $A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} \mathbb{N}$

Where f is a bijection (1-1) and g is an injection.
Show that $g \circ f$ is an injection and you'll prove that there exists an injection from A into $\mathbb{N}$ and hence A is finite.

i don't think that is specific enough. we can have infinite sets for which there are injections into $\mathbb{N}$. we can do it for any countable set in fact. i think the Captain's definition is more on the ball here.
• Oct 12th 2008, 12:58 AM
lllll
Quote:

Originally Posted by CaptainBlack
What definition of finite are you using?

CB

A set $A$ is finite if either $A$ is the empty set, or there is a $n \ \in \ \mathbb{N}$ such that $A \sim \{ 1,2,..., n\}$.

That's the definition from the book.
• Oct 12th 2008, 12:59 AM
Moo
Quote:

Originally Posted by Jhevon
i don't think that is specific enough. we can have infinite sets for which there are injections into $\mathbb{N}$. we can do it for any countable set in fact. i think the Captain's definition is more on the ball here.

Well, this is what my teacher said (Thinking)
Do you have examples of infinite sets for which there are injections into $\mathbb{N}$ ? (Surprised)
Oh okay, there are the ones that are in bijection with $\mathbb{N}$...

Then we can say "g is injective, but not surjective" :p
• Oct 12th 2008, 01:00 AM
Jhevon
Quote:

Originally Posted by lllll
A set $A$ is finite if either $A$ is the empty set, or there is a $n \ \in \ \mathbb{N}$ such that $A \sim \{ 1,2,..., n\}$.

That's the definition from the book.

that is the definition CaptainBlack used. the case where the set is empty does not come into play here. since we would not have any function existing in the first place were that the case
• Oct 12th 2008, 01:03 AM
Jhevon
Quote:

Originally Posted by Moo
Well, this is what my teacher said (Thinking)

Quote:

Do you have examples of infinite sets for which there are injections into $\mathbb{N}$ ? (Surprised)
how about the positive even numbers with the identity function. it is an injection "into" the natural numbers since it skips all the odd integers in the naturals

congrats on the 35:):)th post!!!
• Oct 12th 2008, 02:04 AM
Moo
Quote:

Originally Posted by Jhevon

No, it was by email, so I am sure he said it (Worried)

Quote:

how about the positive even numbers with the identity function. it is an injection "into" the natural numbers since it skips all the odd integers in the naturals
Actually, there exists a bijection from the set of even numbers into the natural numbers.
I guess it's even what you call "identity function" :
f : 2N -> N
2n -> n
It may sound weird, but this is a bijection :
- f(n)=f(m) <=> 2m=2n <=> m=n. This is an injection.
- n in N => there exists m in 2N such that f(n)=m, namely m=2n. This is a surjection.

Hence f is a bijection.

This is why I added "injection but not surjection"

Quote:

congrats on the 35:):)th post!!!
urgh ! I forgot it again !
• Oct 12th 2008, 01:45 PM
Jhevon
Quote:

Originally Posted by Moo
No, it was by email, so I am sure he said it (Worried)

Actually, there exists a bijection from the set of even numbers into the natural numbers.
I guess it's even what you call "identity function" :
f : 2N -> N
2n -> n
It may sound weird, but this is a bijection :
- f(n)=f(m) <=> 2m=2n <=> m=n. This is an injection.
- n in N => there exists m in 2N such that f(n)=m, namely m=2n. This is a surjection.

Hence f is a bijection.

This is why I added "injection but not surjection"

urgh ! I forgot it again !

the identity function on the even naturals to the naturals is not a surjection. since we only map to even numbers, we miss all the odd ones. so that definition does not work. maybe your professor was talking about something else. in fact, i think you are mixing up the definition for infinite sets with finite ones. a set is infinite if there exists an injection that is not onto from the set into itself.