Show that $F: P(\mathbb{N} \times \mathbb{N}) \rightarrow P(\mathbb{N} \times \mathbb{N})$ defined as $F(r) = r \circ r$ is not surjection I have to show that $$F: P(\mathbb{N} \times \mathbb{N}) \rightarrow P(\mathbb{N} \times \mathbb{N})\\
F(r) = r \circ r$$ is not surjection
where $r \circ r$ is composition of two (same) relations.

So I found counter example for this:
$s = \mathbb{N} \times \mathbb{N} - \{\langle x, x \rangle \mid x \in \mathbb{N}\}$
But I do not know how to show that there is not such $r$ that $r \circ r = s$.
I thought that a little bit easier is to show that for every $n \geq 1$ set $A_{n}=\{x \mid x \leq n\}$ also have this counter example (just change $\mathbb{N}$ to $A_{n}$) so it implies that it must but true (to have similar counter example) for $\mathbb{N}$.
But anyway I could not find any formal proof for that.
 A: Let us take $r \in P(\mathbb{N}, \mathbb{N})$, and suppose that we have $s  \in P(\mathbb{N}, \mathbb{N})$ such that $r = s^2$.
Let us say there is some $(a,b) \in r$, then there must be $c \in \mathbb N$ such that $(a,c)$ and $(c,b)$ are in $s$. Let us then suppose that there is also $(a,c) \in r$, then there is $(a,c')$ and $(c', c)$ in $s$, for some $c'$. Then we necessarily have $(c',b) \in r$. 


*

*$a \rightarrow_s c \rightarrow_s b \in r$

*$a  \rightarrow_s c' \rightarrow_s c \in r$

*Then $c' \rightarrow_s c \rightarrow_s b \in r$


This looks like something we can use to build $r$ in such a way it will not be atteignable by $F$. The problem is, we cannot use $c$ to build $r$, because, because $c$ depends on $s$, which does not depend on $r$ (a priori).
To circumvent this, we will generalise things a bit.


*

*say $r = s^2$ for some $s$

*say, for some $a \not = b \in N$ :


*

*$\forall x \not = a, (a,x) \in r$ (we exclude $a$ to lead to a contradiction, see end of proof)

*$(x,b) \in r \Rightarrow x = a$ 


*Then there is some $c$ such that $ a \rightarrow_s c \rightarrow_s b \in r$. 


*

*If $c = a$, then $(a,a) \in s$, and $a \rightarrow_s a \rightarrow_s a \in r$, which is a contradiction. 

*If $c \not = a$, then there is some $c'$ such that $a \rightarrow_s c' \rightarrow_s c \in r$. Then $c' \rightarrow_s c \rightarrow_s b \in r$, so that $\mathbf{ c' = a}$, and again $(a,a) \in s$, a contradiction.


