1. ## 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 $\displaystyle A \stackrel{1-1}{\mapsto} B$ and since $\displaystyle 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.

2. 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 $\displaystyle S$ is finite iff there is a bijection defined on it to a set of consecutive naturals with a largest element.

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

Consider:

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

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

Then :

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

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

CB

3. Hello,

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

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

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

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

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

Hence $\displaystyle \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..

4. Originally Posted by Moo
Hello,

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

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

Where f is a bijection (1-1) and g is an injection.
Show that $\displaystyle g \circ f$ is an injection and you'll prove that there exists an injection from A into $\displaystyle \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 $\displaystyle \mathbb{N}$. we can do it for any countable set in fact. i think the Captain's definition is more on the ball here.

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

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

That's the definition from the book.

6. Originally Posted by Jhevon
i don't think that is specific enough. we can have infinite sets for which there are injections into $\displaystyle \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 $\displaystyle \mathbb{N}$ ?
Oh okay, there are the ones that are in bijection with $\displaystyle \mathbb{N}$...

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

7. Originally Posted by lllll
A set $\displaystyle A$ is finite if either $\displaystyle A$ is the empty set, or there is a $\displaystyle n \ \in \ \mathbb{N}$ such that $\displaystyle 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

8. Originally Posted by Moo
Well, this is what my teacher said

Do you have examples of infinite sets for which there are injections into $\displaystyle \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 35th post!!!

9. Originally Posted by Jhevon
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 35th post!!!
urgh ! I forgot it again !

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