Krdytkyu

Prop: Suppose $A$ is a nonempty finite set, this means that there is a Bijection $f : C_n → A$ where $n$ is an element of the set of Natural Numbers. Now let $g : ℕ → A$ be any function. Show that $g$ is not injective.

I really want to get a good understanding of functions within discrete mathematics so allow me to explain what I know so I don't waste anyone's time and get direct, helpful, and explained feedback.

What I know and how I am processing this question:

We know that $A$ is a non-empty finite set so let's say $A = {1, 2, 3, 4}$. If there is a Bijection between $C_n → A$ that means every element from $C_n$ maps to one and only one of $A$'s elements, and if we reverse this mapping it will yield the same results. However, lets say $n = 2$, this means $C_n = {1, 2}$ and that cannot possibly yield a bijection with $A$ if $A$ is equal to our example above, or can it?

I have drawn out examples of the two functions and get stuck trying to see the bijection, meaning I have yet to add the function $g$ into the equation.

I am quite lost with writing a proof for this so my first step would be to fully understand the question. All help is much appreciated and detailed explanations would be best!

Thank you.

"there is a bijection between $C_n$ and $A$ where $n$ is some natural number", is a true statement if $A$ is finite, because of the word some. For example, for $A = {1,2,3,4}$, we see that $n = 4$ works i.e. $C_4$ and $A$ are bijective. However, $C_2$ and $A$ are not bijective. Similarly, $C_6$ and $A$ are not bijective. However, the word some prevents us from checking cases of non-bijectivity, since we have already located that "some" $n$ with which we can work.

Also, since an explicit description of $C_n$ has not been provided, one cannot write down the description of the bijection above. All one can therefore say is that this map is injective and surjective, and has an inverse map which is also injective and surjective.

The question is this : you have a finite set $A$, and you want to show that there is no injective map from $mathbb N$ to $A$. First, we compare $A$ with $C_n$ for some $n$ which works. This $n$ will be different for different $A$, but will always exist because of finiteness.

What should be your idea? The idea is to use the finiteness of $C_n$!

So let $phi : mathbb N to A$ be an injective map, and let $psi : A to C_n$ be a bijection (for some $n$ which works). Then, by composing these maps, $psi circ phi : mathbb N to mathbb C_n$ is a composition of two injective maps, hence is injective. However, we will now contradict this, using the "pigeonhole principle".

Think of the $n$ elements in $C_n$ as numbered holes, and the elements of $mathbb N$ as pigeons. Then, a function from $mathbb N to mathbb C_n$ is like placing pigeons in numbered holes. However, the principle (or just common sense) tells you that if you have $n+1$ pigeons to place in $n$ holes, then at least one hole will have more than two pigeons. Go back to what the pigeons and holes were, and I leave you to see why this implies that $psi circ phi$ cannot be injective.

I leave a formal proof here :

Let $xi = psi circ phi$. Treat $xi(1),...,xi(n+1)$ as pigeons. The point is, that since we have only $n$ possibilities for these elements (the elements $xi(i)$ have to belong to $C_n$ which has only $n$ elements), there exists $i neq j$ from amongst $1,...,n+1$ such that $xi(i) = xi(j)$. However, this shows that $xi$ is not one-one.