Skip to main content
deleted 18 characters in body
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The easiest way to construct a model $M$ of PRA where the Ackermann function is not total is to take a nonstandard model $M_0$ of, say, PA PRA, fix a nonstandard element $a\in M_0$, and definelet $M$ asbe the cut onin $M_0$ consisting of all elements bounded by the value of some primitive recursive function at $a$ (with no further parameters).defined as $$\{x\in M_0:\exists f\text{ primitive recursive s.t. }M_0\models x\le f(a)\}.$$

In this specific case, one can alsoeven take just the model consistingclosure of the values themselves$a$ under all primitive recursive functions, without closing it downwards, but constructions using cuts tend to work for more theories of interest.

The indicator theory, of which the above mentioned Avigad–Sommer paper is an offshoot, is essentially a generalization of the same idea to theories higher in the hierarchy whose existential quantifiers are not so easy to witness directly.

The easiest way to construct a model $M$ of PRA where the Ackermann function is not total is to take a nonstandard model $M_0$ of, say, PA, fix a nonstandard element $a\in M_0$, and define $M$ as the cut on $M_0$ consisting of all elements bounded by the value of some primitive recursive function at $a$ (with no further parameters).

In this specific case, one can also take the model consisting of the values themselves without closing it downwards, but constructions using cuts tend to work for more theories of interest.

The indicator theory, of which the above mentioned Avigad–Sommer paper is an offshoot, is essentially a generalization of the same idea to theories higher in the hierarchy whose existential quantifiers are not so easy to witness directly.

The easiest way to construct a model $M$ of PRA where the Ackermann function is not total is to take a nonstandard model $M_0$ of PRA, fix a nonstandard element $a\in M_0$, and let $M$ be the cut in $M_0$ defined as $$\{x\in M_0:\exists f\text{ primitive recursive s.t. }M_0\models x\le f(a)\}.$$

In this specific case, one can even take just the closure of $a$ under all primitive recursive functions, without closing it downwards, but constructions using cuts tend to work for more theories of interest.

The indicator theory, of which the above mentioned Avigad–Sommer paper is an offshoot, is essentially a generalization of the same idea to theories higher in the hierarchy whose existential quantifiers are not so easy to witness directly.

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The easiest way to construct a model $M$ of PRA where the Ackermann function is not total is to take a nonstandard model $M_0$ of, say, PA, fix a nonstandard element $a\in M_0$, and define $M$ as the cut on $M_0$ consisting of all elements bounded by the value of some primitive recursive function at $a$ (with no further parameters).

In this specific case, one can also take the model consisting of the values themselves without closing it downwards, but constructions using cuts tend to work for more theories of interest.

The indicator theory, of which the above mentioned Avigad–Sommer paper is an offshoot, is essentially a generalization of the same idea to theories higher in the hierarchy whose existential quantifiers are not so easy to witness directly.