I am given two inductively defined sets as follows:
Let $S \subseteq \Bbb N\times \Bbb N$ defined with the following rules:
I. If $n \in \Bbb N$, then $\langle n,n\rangle \in S$
II. If $\langle n,m\rangle \in S$, then $\langle n,m+1\rangle \in S$
Let $Q \subseteq \Bbb N\times \Bbb N$ defined with following rules:
I. If $n\in \Bbb N$,then $\langle 0,n\rangle \in Q$
II. If $\langle n,m\rangle \in Q$, then $\langle n+1,m+1\rangle\in Q$.
I am asked to prove that $S=Q$, by showing that $S=T$ and $Q=T$, where $T$ is: $$\begin{align}T&=\{\,\langle n,m\rangle\mid\langle n,m\rangle \in \Bbb N\times\Bbb N, n\leq m\}\\&=\{\,\langle n,n+m\rangle \mid n,m \in \Bbb N\,\}.\end{align}$$
To prove each of the two equalities, I'm proving the double inclusion. I got to prove $S \subseteq T$ but I don't know how to prove that $T \subseteq S$.
It's clear that when $n=m$, $\langle n,m\rangle$ belongs to $T$ and $S$ because of the first rule of $S$ and $T$. But what happens when $n<m$? How can I prove that each element of the form $\langle n,n+m\rangle$ can be built using the rules of $S$?
Thank you
You already have this part: Let $x\in S$. Then either $x=\langle n,n\rangle$ for some $n\in\Bbb N$, or $x=\langle n,m+1\rangle$ where $\langle n,m\rangle \in S$. In the first case, $n\le n$ implies $x\in T$, as desired. In the second case, we may assume $\langle n,m\rangle\in T$, i.e., $n\le m$ by induction hypothesis. Then also $n\le m+1$ and so $x\in T$. Therefore $S\subseteq T$.
Here's the other direction: We prove that $$\tag {$\Phi_m$} \forall n\in\Bbb N\colon \langle n,n+m\rangle\in S$$ holds for all $m\in \Bbb N$. From rule I, we see immediately that $\Phi_0$ holds. Next, assume $\Phi_m$ holds. Let $n\in\Bbb N$ be arbitrary. Then by $\Phi_m$, $\langle n,m\rangle\in S$. Then by rule II, $\langle n,m+1\rangle\in S$. As $n$ was arbitrary, we have $\Phi_{m+1}$. So $\Phi_m\to \Phi_{m+1}$ holds for all $m\in\Bbb N$. So by induction, $\forall m\in\Bbb N\colon \Phi_m$. In other words, $T\subseteq S$.