MHB Question for Intermediate Analysis ()

[AutGuy98]

Hey guys,

Got what seems like a simple problem at first, but has been giving me difficulty in trying to prove. Please help me with it and show me what to do because I have no clue really. Here is what it asks:

Prove that if A is a countable set and the function f:A\impliesB is onto, then B is either countable or finite.

Thanks in advance to whomever helps me out with this. The assistance is greatly appreciated.

 

[Evgeny.Makarov]

For each $b\in B$ choose a single $a_b\in A$ such that $f(a_b)=b$. Then consider the restriction of $f$ to $A'=\{a_b\mid b\in B\}$. Show that this is a bijection from $A'$ to $B$. As a subset of $A$, the set $A'$ is either countable or finite, and so is $B$.

 

[soloenergy]

Hi there,

Sure, I can help you with this proof! First, let's define some terms to make sure we're on the same page. A countable set is a set that has the same cardinality (number of elements) as the set of natural numbers, denoted by |N|. A finite set is a set that has a finite number of elements, denoted by |F|.

Now, let's start the proof. Since A is countable, we can list all the elements of A as a sequence: a1, a2, a3, ..., an, ... where n is any natural number. Since the function f is onto, every element in B must have a preimage in A. In other words, for every b in B, there exists an element in A, say an, such that f(an) = b.

Now, let's consider two cases:

1. B is countable: In this case, we can list all the elements of B as a sequence: b1, b2, b3, ..., bn, ... where n is any natural number. Since f is onto, for every bn in B, there exists an an in A such that f(an) = bn. This means that we can create a one-to-one correspondence between the elements of B and the elements of A. Therefore, B has the same cardinality as A, which is countable.

2. B is finite: In this case, we can list all the elements of B as a sequence: b1, b2, b3, ..., bn. Since f is onto, for every bn in B, there exists an an in A such that f(an) = bn. However, since B has a finite number of elements, there must be a finite number of elements in A that map to these elements in B. This means that A is finite as well, and therefore B is also finite.

Therefore, we have proven that if A is a countable set and the function f is onto, then B is either countable or finite.

I hope this helps! Let me know if you have any further questions.