If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

Question

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. Let $T$ be a theory in the language of arithmetic extending $Q$.

Show that:

If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

If $T$ proves any incorrect $\exists$-rudimentary sentence, then $T$ is $\omega$-inconsistent.

It seems like I'm having a lot of trouble with terminology here. If someone could clarify some things for me I would be very appreciative. First of all, what does it mean for $\exists x F(x)$ to be a "theorem" of $T$? Does this just mean that $\exists x F(x)$ is a sentence/equation within the set $T$? Are there practical examples that will help me see what we mean by $\omega$-inconsistency in the context of this problem ("...then so is $\neg F(n)$ for each natural number n")? Also, if $\neg F(n)$ holds for each natural number $n$, then how can we have $\exists x F(x)$? Does this just imply that $x$ is not a natural number?

Additionally, what does it mean to prove some "incorrect" $\forall$/$\exists$-rudimentary sentence (as opposed to proving a "correct" one)?

Answer 1

You have to start from the definition of $\forall$-rudimentary :

By a rudimentary formula of the language of arithmetic we mean a formula built up from atomic formulas using only negation, conjunction, disjunction, and bounded quantifications $∀x < t$ and $∃x < t$, where $t$ may be any term of the language (not involving $x$). (Conditionals and biconditionals are allowed, too, since these officially are just abbreviations for certain constructions involving negation, conjunction, and disjunction. [...] ). By an $∃$-rudimentary formula we mean a formula of form $∃xF$ where $F$ is rudimentary, and similarly for an $∀$-rudimentary formula.

In the system $Q$ of minimal arithmetic, the atomic formulas are basically of the form :

$x = 0$, $x < 1$, and so on.

Thus an example of $\forall$-rudimentary sentence [i.e.closed formula] that is incorrect can be :

$\forall x(x = 1)$.

It is clearly incorrect [i.e.not true in the standard interpretation] because we know that not all numbers are equal to $1$.

Assume that :

$T \vdash \forall x(x = 1)$

i.e. that $T$ (which extend $Q$) proves the incorrect ∀-rudimentary sentence above.

By the rules of f-o logic, we can derive in $T$ all instances of it, like : $0 = 1$.

But see (page 208) the proof of Theorem 16.13 :

All of $0 \ne 1, 0 \ne 2, 0 \ne 3$, . . . , are provable [in $Q$, and thus in $T$].

In conclusion, we have that $T$ proves $0 = 1$ and also $\lnot 0 = 1$, and this is a contradiction; thus $T$ will be inconsistent.

You have to argument in this way also for the second part of your problem; consider an $\exists$-rudimentary sentence like :

$\exists x(x < 0)$.

It is clearly incorrect. Now, exploiting the fact [see page 208] :

that $\lnot 1 < 1, \lnot 2 < 1$, . . . are provable [in $Q$]

we conlcude that $∃xF(x)$ is a theorem of $T$, but so is $\lnot F(n)$ for each natural number $n$, i.e. $T$ is $\omega$-inconsistent.

Answer 2

The key point is that $Q$ (and therefore $T$) proves every correct $\Sigma^0_1$ (i.e. $\Sigma$-rudimentary) sentence in the language of arithmetic. Here a "correct" sentence is one that holds in the standard model of arithmetic.

The problem follows from the key point almost immediately using simpler facts about negations of formulas and the definitions of consistency and $\omega$-consistency.