I am trying to come up with a model of first order Peano Arithmetic (PA) where induction fails. Let $PA^{-IND}$ have the same axioms as PA except the first order induction axiom schema is replaced with its negation. I need to show there exists a predicate, $P$, that makes first order induction false. $P$ must satisfy $P(0) \land \forall x(P(x) \rightarrow P(Sx))$, yet $\forall x(P(x))$ is false. We can prove multiplication is commutative using double induction on $P(x,y)= (xy=yx)$. Why Does Induction Prove Multiplication is Commutative?
Consider the 2×2 matrices $M_2(N)$ with the standard definitions for matrix addition and multiplication. Let the zero matrix be $0$ and the identity matrix be $S0$. $\forall x(Sx=x+S0)$ is a theorem of $PA^{-IND}$. Matrix multiplication is not commutative, yet we can prove multiplication is commutative for all the successors of $0$. Would $M_2(N)$ be a model of $PA^{-IND}$?
The negation of first order induction says there exists a predicate:
$P(0) \land \forall x(P(x) \rightarrow P(Sx)) \land Ex( Not(Px))$
This looks like quantification over predicates but it isn't. The induction schema requires us to add an infinite number of axioms to the language. The negation of induction only requires the addition of a single axiom. Unlike PA, $PA^{-IND}$ has a finite number of axioms. I have simply added a new predicate to the language.
I am using the axioms of PA given by Wikipedia for First Order Arithmetic. These axioms use induction to prove commutativity. Without induction, these axioms are very weak. They don't even require addition to be commutative. I would be interested in any model of $PA^{-IND}$.
Best Answer
You have to be careful about what you mean by $\text{PA}^-$. The convention I expect is that $\text{PA}^-$ is the finite set of axioms for a discretely ordered semiring - which includes the axiom that multiplication is commutative. This set of axioms is typical when we want to look at systems of arithmetic with limited induction. For example, it is the set of axioms in Kaye's book The Structure of Models of Peano Arithmetic.
The original five axioms proposed by Peano, which only mention the successor operation, but not addition, multiplication, or order, are not sufficient for first-order Peano Arithmetic, because they are not sufficient to define addition or multiplication in first-order semantics.
On the other hand, some authors use an abbreviated set of axioms for Peano arithmetic. For example, Mendelson's logic text uses a smaller set of axioms that do not mention the order relation. These work because he only considers them in conjunction with the induction scheme. It seems to me that $M_2(\mathbb{N})$ is a model of this smaller set of axioms, but I would not call them $\text{PA}^-$.
Even when we look at the full set of axioms for $\text{PA}^-$, we can give an example of a model that does not satisfy induction. Tennenbaum's theorem shows that no nonstandard model of Peano arithmetic is computable. But the set of polynomials over $\mathbb{Z}$ with positive leading coefficient are a computable nonstandard model of $\text{PA}^-$, so induction must fail in that model, although I am not sure which instance of the schema fails. I believe the proof only relies on a finite number of instances of induction, so that would give a short list of candidates.