1
$\begingroup$

I would like some predicates in the language of first order Peano arithemetic (PA) that are true for the standard natural numbers and false for other types of numbers like negative numbers, fractions, irrational numbers, etc. An example would be Lagrange's four square theorem.

$P(x) = \exists a \exists b \exists c \exists d(x=a\cdot a + b\cdot b + c \cdot c + d \cdot d)$

This predicate is true for non-negative integers but false for negative integers.

I actually want to work in Modular arithmetic (MA). MA has the same axioms as PA except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. MA has the same language as PA, $(0, S, +, \cdot)$. Order, $\leq$, is not defined in MA so I don't what predicates that use it.

These predicates can be used to prove certain sets are not models of MA. The four square theorem can be used to prove $\mathbb{Z}$ is not a model of MA. We can prove $\forall x (P(x))$ using induction which is clearly false for $\mathbb{Z}$. I am looking for other theorems like the four square theorem. Maybe something based on the binomial theorem. Some of the rings thought to be models of MA include $\mathbb{Z} /n \mathbb{Z}$, any algebraically closed field, and $Z_2$.


Response to Asaf Karagila

I am working in the first order theory Modular arithmetic (MA). I think of MA as an alternate definition of the natural numbers. I am interested in MA as a tool for proving PA is inconsistent. It is well suited for this task. MA has finite models so it is hard to argue it is inconsistent. MA has the same signature as PA and almost all of the same axioms. MA is $\omega$-inconsistent and every infinite model has non-standard elements. MA is not well ordered or well founded.

MA is basically commutative ring theory with first order induction. Induction is valid in surprisingly few commutative rings. Induction fails in $\mathbb{Z}, \mathbb{Q}$, and the Gaussian integers.

I would be interested in a predicate that identified $\mathbb{Z}$ inside $Z_2$. I could combine such a predicate with the four square theorem to indentify the non-negative integers. Such a combined predicate would prove $Z_2$ is not a model of MA.

Because MA has finite models, I only need a predicate that allows me to prove the model is not finite. For example, if $P(x)$ is only true if $x$ is a particular irrational number, I could use $P(x)$ to prove $\mathbb{C}$ is not a finite model of MA.


This is another example of what I am looking for. This statement can only be true in an infinite model of MA:

$\forall x \exists y(S0 \neq 0 \land SS0 \neq 0 \land x = y \cdot y)$.

I have to eliminate the trivial ring and $\mathbb{Z} /2 \mathbb{Z}$. Any statement which is true in only a finite number of finite rings but true in an algebraically closed field or $Z_2$ would be acceptable.

$\endgroup$
5
  • $\begingroup$ Julia Robinson gave a predicate $J(x)$ (quantifiers range over the rationals) which is true precisely when $x$ is a natural number. $\endgroup$ Nov 9, 2013 at 4:47
  • $\begingroup$ Thanks. This is exactly the sort of thing I am looking for. $\endgroup$ Nov 9, 2013 at 6:22
  • $\begingroup$ There are definitions of the integers available for certain function rings. Much of it is very specialized, since it is done in connection with extending results the Hilbert 1oth problem, so people look for existential definitions. If universal quantifiers are also allowed, one has much more freedom. Of course the integers cannot be defined in an algebraically closed (or real-closed) field. $\endgroup$ Nov 9, 2013 at 8:06
  • $\begingroup$ Your question doesn't make much sense. $\sf PA$ is the theory of "finite non-negative integers", in the first-order theory we cannot define standard integers, because there are non-standard models. If we move to a stronger logic (than first-order logic) which can actually characterize finiteness, then we only need to take the predicate $x=x$ for characterizing standard natural numbers. If you want to talk about negative numbers, rational numbers, real numbers, ordinal numbers, non-standard numbers, and so on, you need to either specify the language and theory; or [...] $\endgroup$
    – Asaf Karagila
    Nov 9, 2013 at 8:10
  • $\begingroup$ [...] decide that you want to focus on one particular model of one particular language. For example, the rational numbers in the language of ordered rings. $\endgroup$
    – Asaf Karagila
    Nov 9, 2013 at 8:11

0

You must log in to answer this question.

Browse other questions tagged .