cardianlity

**lllll** · October 11th 2008, 09:54 PM

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.

**CaptainBlack** · October 11th 2008, 11:49 PM

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 :

$<br /> f_{rn}\circ f_b \circ f<br />$

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

**Moo** · October 11th 2008, 11:51 PM

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

**Jhevon** · October 11th 2008, 11:55 PM

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.

**lllll** · October 11th 2008, 11:58 PM

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.

**Moo** · October 11th 2008, 11:59 PM

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

Do you have examples of infinite sets for which there are injections into $\mathbb{N}$ ?

Oh okay, there are the ones that are in bijection with $\mathbb{N}$ ...

Then we can say "g is injective, but not surjective"

**Jhevon** · October 12th 2008, 12:00 AM

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

**Jhevon** · October 12th 2008, 12:03 AM

Originally Posted by Moo

Well, this is what my teacher said

maybe you weren't paying attention again.

we talked about this before. listen to your professors!

Do you have examples of infinite sets for which there are injections into $\mathbb{N}$ ?

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!!!

**Moo** · October 12th 2008, 01:04 AM

Originally Posted by Jhevon

maybe you weren't paying attention again.

we talked about this before. listen to your professors!

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

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"

congrats on the 35

th post!!!

urgh ! I forgot it again !

**Jhevon** · October 12th 2008, 12:45 PM

Originally Posted by Moo

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

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.

Thread: cardianlity

LinkBack

Thread Tools

Display

cardianlity

Search Tags