Bijection between two Peano triples.

Question

Let $(P_1, \sigma_1, s_1)$ and $(P_2, \sigma_2, s_2)$ be two Peano triples. Can we show that there exists a bijection $g:P_1 \to P_2$ such that $g(\sigma_1) = \sigma_2$ and $g \circ s_1 = s_2 \circ g$. If yes, how to prove it?

My answer is no, as cardinality of $P_1$ and $P_2$ may not be same. Is my reasoning correct?

A Peano triple is a triple $(N,1,\sigma)$ where $N$ is a set, $1 \in N$, and $\sigma : N \to N$ is a map such that

1. $\sigma$ is injective;
2. $\sigma(N) = N \setminus \{1\}$;
3. for any subset $S \subset N$ if $1 \in S$ and $\sigma(S) \subset S$ then $S = N$.

Answer 1

You've claimed that there are Peano triples of different cardinalities; while this would indeed imply that the statement you're analyzing is false, your claim is not correct. In fact, the statement you're analyzing is true: any two Peano triples are isomorphic.

REMARK (ignore this if you're not familiar with model theory): In light of the existence of nonstandard models of arithmetic this might seem like a contradiction, but it's not. The existence of nonstandard models relies on the theory in question being first order, and you're looking at the second-order version of Peano arithmetic - the quantifier over all sets (axiom (3)) is not first-order.

---

Here's a sketch of the proof:

You already know of one Peano triple - namely, $(\mathbb{N},1,succ)$. Now suppose $(P,\sigma,s)$ is another Peano triple; you want to show that $(P,\sigma,s)$ is "the same as" (in the appropriate sense) the Peano triple $(\mathbb{N},1,succ)$.

• There is a natural function $f:\mathbb{N}\rightarrow P$ given by "counting" the elements of $P$. For example, $f(1)$ should be $\sigma$, and $f(2)$ should be $s(\sigma)$. Do you see how to define $f$ in general?

• Can you prove that $f$ is in fact an injection?

• Now you would be done with the problem if you could show that $f$ is a bijection (why?). So suppose it's not. Let $S=P\setminus range(f)$. Can you show that $S$ has a weird property that means that $(P,\sigma,s)$ is in fact not a Peano triple?

The focus on the specific triple $(\mathbb{N},1,succ)$ above is unnecessary - we could develop a similar argument for showing that two arbitrary Peano triples are isomorphic, directly - but I think the approach above makes things more concrete.