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

Question

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.

Answer 1

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.