I was taking a casual look over the exercises at the end of some section in Endertons's logic book and stumbled upon this one. Again,
Does the set of sentences $\Sigma=\{\exists xPx, \neg Pa_{0}, \neg Pa_{1}, \neg Pa_{2},\dots\}$ have a model?
[I am not sure if the exercise was exactly this, as I only caught a glimpse of it, but in any case, it got me wondering about what I am going to ask here]
Well, it trivially does: take any $\mathfrak{A}$ where the $x$ of the universe such that $x \in P^{\mathfrak{A}}$ is not denoted by any constant symbol nor definable representable by any formula in the language — the idea is that the system has to "construct" it somehow.
For instance, a structure $(\mathbb{N}; 1, <, \mathbf{S})$ with $Px$ being $\forall y(x<y)$.
Now, I always had a hard time grasping $\omega$-inconsistency, nonstandard models of arithmetics and the like: a system proving $Pk$ for every $k$ but not proving $\forall xPx$ sounded unintuitive—it is just that the "for every $k$" quantifies over all definable elements, while the one inside the formal sentence in turn quantifies over all elements.
Thus, is it merely the case that, for example, the model of $PA+\neg Con(PA)$ has its element $x$ of the universe such that $x$, say, is the Gödel number of a proof of a contradiction from the axioms of $PA$, not definable? Is this essentially what $\omega$-inconsistency is all about?
For instance, take the language containing parameter $\mathbf{S}$, $<$ and some constant symbol. Then, is the set of sentences of this language
- $\forall x,y(x=y\leftrightarrow\mathbf{S}x=\mathbf{S}y)$, (successor is unique);
- $\forall x,y(\mathbf{S}x=y \to (x<y\wedge\forall z\neg(x<z\wedge z<y)))$, (successor is immediately "to the right");
- $\forall x,y,z(x<y \wedge y<z \to x<z)$, (ordering is transitive);
- $\forall x,y(x<y\oplus y<x \oplus x=y)$, (trichotomy);
- $\exists x \forall y (x<y)$.
(plus any others I might have forgot, you get the idea of what I'm trying to do I guess)
$\omega$-inconsistent?
No. Remember that $PA$ includes induction, so if $M\models PA$ then any definable nonempty subset $D$ of $M$ has a least element. This least element is, in turn, definable: it is the unique element $x$ satisfying $$\varphi(x)\wedge\forall y(y<x\implies \neg\varphi(y)),$$ where $\varphi$ is the formula defining $D$.
So what? Well, in any $M\models PA$, the set of (codes of) $PA$-proofs of $0=1$ is a definable set! Moreover, if $M$ thinks $PA$ is inconsistent, this set is nonempty; so in such an $M$ there is a definable element of $M$ coding (what $M$ thinks is) a $PA$-proof of $0=1$.
So it is wrong to conflate the definable elements of a nonstandard model $M\models PA$ with the standard elements: although every standard element is definable, the converse may fail.
In fact, we can generalize the above fact (with some work) to prove the following:
Proof sketch: suppose $M\not\models TA$. We'll find a definable element of $M$ which is nonstandard; specifically, we'll look at the "simplest" difference between the theory of $M$ and true arithmetic, and show that the least witness to this difference must be a definable nonstandard element of $M$.
Let $n$ be the least (standard) natural number such that, for some $\varphi\in TA\cap(\Sigma_n\cup\Pi_n)$, $M\not\models\varphi$ (so $n$ is the first level of the arithmetic hierarchy where we see that $M$ and $\mathbb{N}$ have different theories); and pick such a $\varphi$.
First, I claim that $\varphi$ can't be $\Sigma_n$. Why? Well, suppose it were. Write $\varphi$ as $\exists x\psi(x)$ for some $\Pi_{n-1}$ formula $\psi$. (I'm implicitly assuming $n>0$ here, but it's easy to show that $PA$ is in fact $\Sigma_0$-complete, so in fact we'll always have $n>0$.) Since $\varphi\in TA$, there is some $n\in\mathbb{N}$ such that $\mathbb{N}\models\psi(n)$. But $n$ is definable, being standard; so we can write this as $\mathbb{N}\models \chi$ for a parameter-free sentence $\chi$ (namely, $\chi\equiv\psi(\underline{n})$, where $\underline{n}$ is the numeral for $n$). Well, $\chi$ is $\Pi_{n-1}$, so by assumption on $n$ we have $M\models\chi$. But then $M\models\exists x\psi(x)$, since $x=n$ satisfies $\psi$ in $M$.
So $\varphi$ must be $\Pi_n$. Write $\varphi$ as $\forall x\theta(x)$ for some $\Sigma_{n-1}$ formula $\theta$, and let $$D=\{m\in M: M\models \theta(m)\}.$$ This set is nonempty (since we're assuming $M\not\models\varphi$) and definable, so it has a least element $d\in M$. This $d$ is definable. But $d$ must be nonstandard, since the statement "$\neg\theta(m)$" for every standard natural $m$ is $\Pi_{n-1}$ and true in $\mathbb{N}$, so (by assumption on $n$) true in $M$. So we are done.
Re: the example you give, first a couple comments:
I don't recommend using "$\oplus$" for "xor"; since we use "$\oplus$" frequently to denote a binary function symbol or direct sum of structures, it would become dangerously overloaded.
I think you also want axioms asserting "$c>SSSS...S(0)$" for every finite string of $S$s (where $c$ is your new constant symbol).
That said - assuming my second bullet is correct - yes, this is an example of a consistent, $\omega$-inconsistent theory: it proves "$c>\underline{k}$" for every natural number $k$ (where $\underline{k}$ is the numeral for $k$: $SSSSS...S(0)$, with $k$-many $S$s), but disproves "$\forall x(c>x)$".