Is Induction Independent of the Other Axioms of PA? 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 2x2 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}$.
 A: 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. 
A: A structure that satisfies the axioms of Peano arithmetic except for induction is $\mathbb N[x]$, the set of all polynomials with natural number coefficients, setting the successor $S(p) = p + 1x^0$ and zero being $0x^0$.
It has a zero, successor is closed under the set, it is injective.  If you think of the Peano axioms as constraints on a directed graph, this is the natural structure to arrive at:


*

*$0 \in \mathbb N \land \lnot \exists x \in \mathbb N~:~ S(x) = 0$ - there is a source

*$x \in \mathbb N \implies S(x) \in \mathbb N$ - there are no sinks

*$S$ is an injective function - there are no forks in the graph


All that remains is to establish that the graph is connected, which induction does.
So you can have multiple zeros, like $\mathbb N[x]$.
Or you can have a disconnected graph, such as using $\mathbb N \cup \mathbb Z \cup \mathbb Z' \cup \mathbb Z'' \dots$ (treating each pair of the previous sets as pairwise disjoint, but otherwise maintaining their usual properties).
Or some combination of both of the above.
A: If you drop the induction principle it will become easy to find a model so that the other axioms are fulfilled. Consider the set $\mathbb N\cup \{\infty\}$ where $\sigma(\infty) = \infty$ and $\sigma$ is defined as normal for $\mathbb N$. Then the other axioms are fulfilled, but the induction principle doesn't work. Consider for example the statement $\phi(x): x\in\mathbb N$. If $\phi(n)$ we clearly have $\phi(\sigma(n))$ and we have $\phi(0)$, but still $\phi(k)$ is not valid over the entire set since $\neg\phi(\infty)$ (that is the induction principle doesn't work for this set).
A: [Note, I'm using your definition, Peano minus induction. Carl pointed me to the wikipedia page, where $PA^-$ is defined as something quite different. There, it is Peano minus induction plus a lot of the basic theorems we normally prove by induction.]
With induction, we can prove that every natural number is either zero, or the successor of a natural number. Indeed, this is the easiest usage of induction possible. (It's my favorite induction proof, because $P(0)$ is clearly true, and $P(Sn)$ is true, whether $P(n)$ is true or not.)
There are some simple examples where the other axioms hold but this most basic induction theorem is not true.
A: I think a simple example of PA negating induction would be the set $\mathbb N \cup C$ where $C$ is some (any) cycle in the sense that some symbol $c \in C$, and for every $x \in C$, $Sx \in C$, and $SSSSSSSx = x$.
A: This is not a first-order approach, but you may be able to adapt it to PA.
If we grant the existence of at least one Dedeknd-infinite set $X$, the principle of mathematical induction can be shown to be independent of the other Peano Axioms (the set-theoretic version). 
Since $X$ is Dedekind-infinite, there exists a function $f: X\to X$ such that $f$ is injective and not surjective.
Since $f$ is not surjective, we have $x_0 \in X$ such that $\forall x\in X:f(x)\neq x_0$
We can construct subset $n\subset X$ such that $n=\{x_0, f(x_0), f(f(x_0)), \cdots \}$ and $(n,f,x_0)$ satisfies all the Peano axioms (PA1-5): 
We can also construct a successor function $g:n\to n$ such that $(n,g,f(x_0))$ satisfies axioms PA1-4, but not induction.
$$g(x) =
\begin{cases}
x_0,  & \text{if $x=x_0$} \\
f(x), & \text{otherwise}
\end{cases}$$
See detailed formal proof. 
