$\pi$ is isomorphism from one Peano system $(N, S, e)$ to another $(N', S', e')$, then $\pi^{-1}$ is isomorphism from $(N', S', e')$ to $(N, S, e)$

144 Views Asked by At

This is an exercise from Cunningham's book "Set Theory: A First Course".

Theorem: Let $(N, S, e)$ and $(N', S', e')$ be Peano systems. Let $\pi$ be an isomorphism from $(N, S, e)$ onto $(N', S', e')$. Prove that $\pi^{-1}$ is thus an isomorphism from $(N', S', e')$ onto $(N, S, e)$.

Definition: Isomorphism $\pi$ is the following bijection $$ \pi = \begin{cases} \pi(e) = e' \\ (\forall x \in N)\pi(S(x)) = S'(\pi(x)) \end{cases} $$ Proof: Let $(N, S, e)$ and $(N', S', e')$ be Peano systems. Let $\pi$ be an isomorphism from $(N, S, e)$ onto $(N', S', e')$. $\pi$ is a bijection, so is $\pi^{-1}$. To prove that $\pi^{-1}\colon N'\to N$ is an isomorphism we have to show that: $$ \pi^{-1} = \begin{cases} \pi^{-1}(e') = e \\ (\forall x \in N')(\pi^{-1}(S'(x)) = S(\pi^{-1}(x))) \end{cases} $$

Since $\pi(e)=e'$ then $\pi^{-1}(e') = e$. Now we prove the second statement by induction. Consider a set $A = \{y \in N': \pi^{-1}(S'(y)) = S(\pi^{-1}(y)))\}$, prove that it is closed under $S'$. First show that $e'\in A$.

$$ \begin{align*} \pi(S(e)) &= S'(\pi(e)) &\text{def. of $\pi$} \\ \pi(e) &= e' \\ \pi^{-1}(e') &= e \\ \pi^{-1}(S'(e')) &= S(\pi^{-1}(e')) \\ e' &\in A \end{align*} $$ For induction hypothesis assume $y \in A$, therefore $\pi^{-1}(S'(y)) = S(\pi^{-1}(y))$. Show that $S'(y)$ is also in $A$ by proving that $\pi^{-1}(S'(S'(y))) = S(\pi^{-1}(S'(y)))$ holds. Since $y \in N'$ and $\pi^{-1}:N' \to N$ is bijection, then there exists unique $x \in N$ such that $x = \pi^{-1}(y)$ $$ \begin{align*} (\forall x \in N)(\pi(S(x)) &= S'(\pi(x))) &\text{def. of $\pi$}\\ S(x) &\in N \\ \pi(S(S(x)) &= S'(\pi(S(x)))) &\text{from def. of $\pi$} \\ \pi(S(x) &= S'(\pi(x))) &\text{from def. of $\pi$} \\ \pi(S(S(x)) &= S'(S'(\pi(x))) \\ \pi^{-1}(S'(S'(\pi(x)))) &= S(S(x)) \\ \pi^{-1}(S'(S'(\pi(\pi^{-1}(y))))) &= S(S(\pi^{-1}(y)))) &\text{replacing $x$ with $\pi^{-1}(y)$}\\ \pi^{-1}(S'(S'(y)))) &= S(S(\pi^{-1}(y))) \\ \pi^{-1}(S'(S'(y)))) &= S(\pi^{-1}(S'(y))) &\text{by Induction Hypothesis}\\ S'(y) &\in A \\ \text{The set $A$ is closed under $S'$, hence $A=N'$.} \\ (\forall x \in N')(\pi^{-1}(S'(x)) &= S(\pi^{-1}(x))) \end{align*} $$ Therefore $\pi^{-1}$ is an isomorphism from $(N', S', e')$ onto $(N, S, e).\qquad\square$

Even though the derivation above seems valid to me it feels too "straight forward", therefore my questions are: is the proof valid and whether more "elegant" solution exists. Cheers.

1

There are 1 best solutions below

2
On BEST ANSWER

Induction is not needed here.

For $x \in N'$, let $y = \pi^{-1}(x)$, so $x = \pi(y)$. Since $\pi$ is an isomorphism $$S'(x) = S'(\pi(y)) = \pi(S(y))$$ and $$\pi^{-1}(S'(x)) = S(y) = S (\pi^{-1}(x))$$ as required.

This is a simple theorem. One would expect its proof to be straight-forward.