Set theory basics exam

197 Views Asked by At

I have a question about this, we had this on our exam.

Let be $f:A \to B$ a function. Prove next statements or give an example against it.

(i): if $A$ is countable, then $f(A)$ is also countable.

I gave a counter example: sequences. f: natural numbers into real numbers.

But I got zero points.

(ii): if $B$ is countable,then $f^{-1}(B)$ is also countable.

I tried to prove with claiming that $f^{-1}(B)$ is a subset of $B$ and so it would mean it's countable. But I am not sure,can anyone help me with it?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $A$ and $B$ be sets and let $f\colon A\rightarrow B$ be a function. Then you can co-restrict $f$ to its codomain, i.e. consider the function $f^{\vert f(A)}\colon A\rightarrow f(A)$ sending $a\in A$ to $f(a)\in B$. Now, by definition, this map is onto, hence the cardinality of $f(A)$ is at most the cardinality of $A$. In particular, if $A$ is countable to start with, then $f(A)$ has either finite cardinality or is in bijection with the natural numbers (this may exactly mean that $f(A)$ is countable, according to the definition of being countable that you have, that is, according to whether a countable set can be finite or not in your definition).

As for the second question, given again any function $f\colon A\rightarrow B$ between two sets, by definition of function and of inverse image, $f^{-1}(B)=A$. Thus, in general there is no hope that $f^{-1}(B)$ is countable if $B$ is such to start with. Take, for example, the function $f\colon\mathbb{R}\rightarrow \mathbb{N}$ sending every $x\in\mathbb{R}$ to $0\in\mathbb{N}$.

2
On

Some ideas for you to develop:

(i) Here, define $\;h:A\to f(A)\;$ by $\;h(a):=f(a)\;,\;\;a\in A\;$ . Show that $\;h\;$ is surjective (onto), which means $\;\text{card}(A)\ge\text{card}(f(A))\;$

(ii) What about $\;f:\Bbb R\to\Bbb N\;,\;\;f(x)=0\;\;\;\forall\,x\in\Bbb R\; $ ?