Question about Function and Equivalence Relations

Question

Problem 1: Give examples of functions $f$ and $g$ such that $f \circ g$ is onto, but $g$ is not onto.

Problem 2: Let $R$ be the relation defined on the set of eight-bit strings by $s_1 \;R\; s_2$ provided that $s_1$ and $s_2$ have the same number of zeros.

(a) Show that $R$ is an equivalence relation.

(b) How many equivalence classes are there?

(c) List one member of each equivalence class.

Solution to Problem 2): (a) R is reflexive because any eight-bit string has the same number of zeroes as itself. R is symmetric because, if s_1 and s_2 have the same number of zeros, then s_2 and s_1 have the same number of zeros. To see that R is transitive, suppose that s_1 and s_2 have the same number of zeros and that s_2 and s_3 have the same number of zeroes. Then s_1 and s_3 have the same number of zeros. Therefore, R is an equivalence relation. Is my prove right? (b) I think there are nine equivalence classes, but I not sure.... (c) ....

Please explain in detail. I really need to understand the solution of these tasks... Thank you very much in advance!!!!

Answer 1

You are right, there are $9$ equivalence classes-the class of strings with no zeros, the class of strings with $1$ zero, the class of strings with $2$ zeros and so on. The number of zeros can be $0,1,2,...,8$ so we have $9$ equivalence classes in general. As for listing a member for each equivalence class, well it's easy:

$11111111$ is the only member of the class with no zeros.

$11111110$ is a member of the class with $1$ zero.

$11111100$ is a member of the class with $2$ zeros.

And continue this way.

Now about problem $1$. Define $f:\{0,1\}\to\{0\}$ by $f(0)=f(1)=0$, and $g:\{0\}\to\{0,1\}$ by $g(0)=0$. $g$ is not onto because it never returns the value $1$ which is in its range, but $f\circ g$ is onto.

Answer 2

1) we need $g: A\to B$ and $f: B \to C$.

$g$ is not onto so there must be a $b \in B$ so that there isn't any $a \in A$ so that $g(a) = b$.

In other words $g(A) \subsetneq B$ because $b \not \in g(A)$ because we can't have $g(a) = b$.

Yet that can't stop $f\circ g: A \to C$ so that every $c \in C$ will have an $a \in A$ so that $f(g(a)) = c$.

So we must still have $f(g(A)) = C$ even though $g(A)\ne B$. In other words the $b\in B$ so that is not mapped to doesn't matter and $f(B -\{b\})$ is still $C$. This means $f(b)$ can't matter. And that means there must be a different $\beta\in B$ so that $f(\beta) = f(b)=c$ and there is an $a\in A$ so that $g(a) = \beta$ even though there is no $a$ so that $g(a) = b$.

The simplest way to do that is let $A=\{a\}; B=\{b,\beta\}; C= \{c\}$ and $g(a) = \beta; f(b)=c; f(\beta) = c$.

Or if that seems too abstract then consider: $g: \mathbb R \to \mathbb R$ with $g(x) = x^2$. That is not onto as $g(x) = -5$ is impossible. Let $f(x) = \ln |x|$ if $x \ne 0$ and $f(0) = 0$. Then $f\circ g(x) = \ln x^2$ if $ \ne 0$ and $f\circ g(0) = 0$. That is onto.

It doesn't matter that $g$ doesn't map anything to the negative numbers because $f$ "makes do" by mapping just the positive numbers to everything any way. So the negative numbers (which $g$ doesn't map to) are not necessary to get $f$ to map everything that $g$ does map to, to map to everything.

....

Maybe even easier: Let $g: \mathbb Z \to \mathbb R$ be $g(n) = n$. This is not onto as it only maps to the integers. It doesn't map to anything else. Let $f: \mathbb R \to \mathbb Z$ be $f(x) = \lfloor x\rfloor$ where $\lfloor x\rfloor$ is the floor function (i.e. the largest integer equal or less than $x$).

$f\circ g(n) = n$ and that does map every integer to every integer. It "misses" all the non-integers that also map to the integers but that doesn't matter. $g(\mathbb Z) = \mathbb Z \subsetneq \mathbb R$ but $f(\mathbb Z) = \mathbb Z$ so we don't need to consider what $f(\mathbb R \setminus \mathbb Z)$ do. They are superflous.