$\begingroup$

I always thought, that when creating a theory (set of formulas of predicate logic of first order in some language) and when you want to have only infinite models, you must use infinite number of axioms. That's how Peano arithmetic or ZF are made.

But when I look at Robinson arithmetic, it is finite. Am I missing something? Does Robinson arithmetic have finite models, or I was wrong - you can "enforce" only infinite models by finite theory?

$\endgroup$ 1

2 Answers

$\begingroup$

A theory with a finite number of axioms can easily have only infinite models. One of the simplest examples is the theory of densely ordered sets. The language (over te predicate calculus with equality) has a single binary predicate symbol $R$. For the sake of familiarity we write $X\lt y$ instead of $R(x,y)$.

The axioms say that $\lt$ is a total order, which is dense. The total order axioms say that for all $x$ and $y$, exactly one of $x\lt y$, $y\lt x$, and $x=y$ holds, and that $x\lt y$ and $y\lt z$ implies $x\lt z$. In addition to the usual axioms for total order, we ask that there is more than one element, and that for any $x$ and $y$ there is a $z$ such that $x\lt z$ and $z\lt y$. This theory only has infinite models.

Or else we can use the basic theory of the successor function. Beside the usual symbols of first-order logic with equality, the language has a constant symbol $0$, and a unary function symbol $S$. The axioms say that for all $x$, $Sx\ne x$, that $0$ is not the successor of anything, and that every $x$ except $0$ has a unique predecessor. This is far simpler than Robinson Arithmetic, but only has infinite models.

There are much more complicated examples. For instance, the von Neumann- Gödel-Bernays set theory (NBG) is finitely axiomatized.

$\endgroup$ 2 $\begingroup$

Here is another example that may be of interest, especially to any who are algebraically minded.

Choose an odd prime $p$. To the first-order theory of fields (i.e., the field axioms) add

1. $\underbrace{1+1+\cdots+1}_{p \text{ times}}=0$
2. $\forall x \exists y (x = y^2)$

Now you have the first-order theory of characteristic $p$ fields that are quadratically closed. The algebraically closed field of characteristic $p$ is an infinite model, but there can be no finite models, since the squaring map is not injective, and hence not surjective.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy