38
$\begingroup$

Mathematician Edward Nelson is known for his extreme views on the foundations of mathematics, variously described as "ultrafintism" or "strict finitism" (Nelson's preferred term), which came into the split light recently because of his claim, quickly recanted, of proving $PA$ inconsistent (but he's still working on it). He believes in Robinson Arithmetic, but not the induction schema of Peano Arithmetic (although he does accept weak forms of induction interpretable in Robinson's $Q$, like induction for bounded formulas; see his book Predicative Arithmetic). He even believes that exponentiation is not total! Here is a quote explaining his viewpoint:

“The intuition that the set of all subsets of a finite set is finite—or more generally, that if $A$ and $B$ are finite sets, then so is the set $B^A$ of all functions from $A$ to $B$—is a questionable intuition. Let $A$ be the set of some $5000$ spaces for symbols on a blank sheet of typewriter paper, and let $B$ be the set of some $80$ symbols of a typewriter; then perhaps $B^A$ is infinite. Perhaps it is even incorrect to think of $B^A$ as being a set. To do so is to postulate an entity, the set of all possible typewritten pages, and then to ascribe some kind of reality to this entity—for example, by asserting that one can in principle survey each possible typewritten page. But perhaps it is simply not so. Perhaps there is no such number as $80^{5000}$; perhaps it is always possible to write a new and different page.”

He believes that finite numbers are closed under addition and multiplication, but not exponentiation: he thinks you can have two numbers, like $80$ and $5000$, which are both finite, but where $80^{5000}$ in infinitely large!

My question is, can we illustrate this view using a nonstandard model of arithmetic? Specifically, how would we construct a nonstandard model of $Q$, containing an initial segment closed under successor, addition, and multiplication, but not exponentiation? Preferably, I'd like a computable nonstandard model.

Any help would be greatly appreciated.

Thank You in Advance.

EDIT: As @JoelDavidHamkins pointed out, exponentiation need not be total in a model of $Q$, so such a model wouldn't illustrate the phenomenon Edward Nelson believes is possible, of the exponentiation of finite numbers being infinite. So let me clarify: I'm looking for a computable nonstandard model of $Q$ + "exponentiation is total", such that the model has an initial segment closed under successor, addition, and multiplication, but not exponentiation.

EDIT 2: @EmilJeřábek has pointed out that different formulations of "exponentiation is total" in the language of arithmetic aren't provably equivalent in $Q$. How you formalize this assertion doesn't really concern me, so rather than talk about models of $Q$ + "exponentiation is total", let me talk about models $M$ of $Q$ equipped with a binary operation on $M$ that satisfies the basic properties of exponentiation: $a^{b+c} = a^b a^c$, $(a^b)^c = a^{bc}$, $a^1 = a$, $a^{0} = 1$, and $0^b = 0$. I also want addition and multiplication to be commutative and associative, multiplication to distribute over addition, and addition to obey the cancellation property that $a + c = b + c$ implies $a = b$. An example of a computable nonstandard model of $Q$ that satisfies at least these properties of addition and multiplication is the set of polynomials $\{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] , a_n > 0 \}$, together with $0$, with polynomial addition and multiplication, and the successor just involving adding $1$.

Improve this question
$\endgroup$
5
  • $\begingroup$ Not an answer to your question, but in this article: web.math.princeton.edu/~nelson/papers/warn.pdf Nelson gives a mathematical argument in favor of his view. $\endgroup$
    – Michael Bächtold
    Commented Sep 20, 2013 at 16:44
  • $\begingroup$ Yes, I've read this, and most other papers by Nelson on the subject. $\endgroup$
    – Keshav Srinivasan
    Commented Sep 20, 2013 at 19:09
  • $\begingroup$ Regarding your latest edit, see the comment I posted on my answer. $\endgroup$
    – Joel David Hamkins
    Commented Sep 21, 2013 at 17:04
  • $\begingroup$ What is exponentiation? There are various reasonable ways of defining (the graph of) exponentiation in sufficiently strong theories such as $I\Delta_0$, but they are going to be neither mutually equivalent nor well-behaved in $Q$ (or in the kind of theories that have computable nonstandard models). You need to state exactly what you want. $\endgroup$
    – Emil Jeřábek
    Commented Sep 30, 2013 at 10:25
  • 2
    $\begingroup$ @EmilJeřábek I want a nonstandard model of $Q$ along with a binary operation ^ that satisfies the usual properties of exponentiation: $a^{b+c} = a^b a^c$, $(a^b)^c = a^{bc}$, $a^1 = a$, $a^0 = 1$, and $0^b = 0$. And I want addition and multiplication to satisfy the usual properties of associativity, commutativity, distributivity, and the cancellation law. $\endgroup$
    – Keshav Srinivasan
    Commented Sep 30, 2013 at 23:03

4 Answers 4

Reset to default
37
$\begingroup$

Thanks to Timothy Chow for informing me of this discussion.

To avoid vagueness, let Q* be Q with the usual relativization schemata adjoined. Construct a formal system F by adjoining an unary predicate symbol $\psi$, the axiom $\psi(0)$, and the rule of inference: from $\rm\psi(a)$ infer $\rm\psi(Sa)$ (for any term a). I think this is an adequate formalization of the concept of an "actual number". Is $\psi(80^{5000})$ a theorem of F? I see no reason to believe so. Of course, one can arithmetize F in various theories, even Q*, and prove a formula $\exists p[p \hbox{ is an arithmetized proof in F of } `\psi(80^{5000})\hbox{'}]$, but to conclude from this that there is a proof in F itself of $\psi(80^{5000})$ appears to me to be unjustified.

Contrast F with the theory T obtained by adjoining to Q* a unary predicate symbol $\phi$ and the two axioms $\phi(0)$ and $\phi(0)\;\&\;\forall x'[\phi(x')\to\phi({\rm S}x')]\to\phi(x)$. Then one can easily prove in T $\phi(80^{5000})$ or even $\phi(80^{5000...^{5000}})$. The ellipsis means that the iterated exponential term is actually written down.

Improve this answer
$\endgroup$
19
  • 7
    $\begingroup$ To be clear, you also see no reason to believe that $\psi(80\cdot80\cdots80)$ (where we actually write down five thousand 80's) is a theorem of F, right? $\endgroup$
    – Timothy Chow
    Commented Oct 31, 2013 at 23:37
  • 3
    $\begingroup$ @Timothy Chow. Yes. $\endgroup$
    – Edward Nelson
    Commented Nov 1, 2013 at 13:43
  • 4
    $\begingroup$ @abo. You seem to be arguing in ordinary language that $\exists p[p \text{ is an arithmetized proof in F of } \psi(80^{5000})]$. No dispute about that. But the reasoning cannot be expressed in F. I fear this is getting way off topic for MathOverflow. $\endgroup$
    – Edward Nelson
    Commented Nov 2, 2013 at 16:05
  • 4
    $\begingroup$ @Keshav Srinivasan If I believed that, then, applying that reasoning a billion times, I would believe that $\psi(2^{2^{1000000000}})$ is a theorem, but I don't. Abstract arguments about a formal system are really arguments about its arithmetization. $\endgroup$
    – Edward Nelson
    Commented Nov 7, 2013 at 20:42
  • 3
    $\begingroup$ I think Edward Nelson has tried to formalize the "marks on paper" problem. Just because we can define Ackermann(1000,1000) with a few symbols does not mean we can really put Ackermann(1000,1000) marks on a piece of paper. $\endgroup$
    – Russell Easterly
    Commented Nov 17, 2013 at 22:05
28
$\begingroup$

If you are really satisfied with a model only of the theory $Q$, then you should be prepared for a bad situation, for this is an extremely weak theory. In fact one can make a computable model simply by adding a single new point at infinity, forming the structure $\mathbb{N}\cup\{\infty\}$ with the usual arithmetic on the finite part, and defining $n+\infty=\infty=\infty+n$ for any finite $n$, and $n\cdot\infty=\infty=\infty\cdot n$ for any finite nonzero $n$. This silly model, unfortunately, satisfies $Q$, which goes to show you how weak $Q$ is as far as determining the usual theory of arithmetic: it doesn't even prove $\forall x\ x+1\neq x$. Similar models can be constructed by adding two points at infinity, where multiplication is not commutative and other unusual arithmetic situations arise. So $Q$ is a very weak theory having computable nonstandard models.

As you strengthen the theory that you want, you will run into the Tennenbaum phenomenon, which asserts that there is no computable nonstandard model of PA. Indeed, if $\langle N,+,\cdot\rangle$ is a nonstandard model of PA, then neither $+$ nor $\cdot$ is computable. I noticed that there has been some work on The limits of the Tennenbaum phenomenon for weak theories, and I'm not sure where the boundary lies.

Meanwhile, it is easy to find cuts in any nonstandard model of PA, which are closed under addition and multiplication, but not exponentiation. Every nonstandard model of PA has unboundedly many such proper initial segments like this. For example, if $\cal{N}$ is a nonstandard model of PA, let $m$ be any nonstandard element, and let $I$ be the collection of numbers $n$ in the model $\cal{N}$ below $m^k$ for some standard $k$. This collection is closed under addition and multiplication in $\cal{N}$, but not exponentiation, essentially because $m^k\cdot m^s=m^{k+s}$. So the model $\langle I,+,\cdot,0,1,\lt\rangle$ thinks exponentiation is not total, although its addition and multiplication properties are very nice, since it is an initial segment of a model of PA. I'm not sure whether one can find a computable such model; the question is whether the Tennenbaum phenomenon applies, and I think it likely does.

Improve this answer
$\endgroup$
15
  • 6
    $\begingroup$ There are various “Tennenbaum phenomena” (there are no nonstandard recursive models, every nonstandard model has a nonstandard cut satisfying PA, the additive reduct of the model is recursively saturated, the real closure of the model is recursively saturated) whose boundaries may somewhat differ, but if we stick to the basic property of having nonstandard recursive models, the strongest theory known to have such models is IOpen + Bézout property + there are infinitely many primes lc08.iam.unibe.ch/program/mohsenipour.pdf , while on the other hand, there are no nonstandard recursive $\endgroup$
    – Emil Jeřábek
    Commented Sep 20, 2013 at 13:57
  • 4
    $\begingroup$ models of $IE_1$, or of just about any fragment of bounded arithmetic in Buss’s framework with some form of sharply bounded induction (say, $\mathit{BASIC}+\Sigma^b_0\text-\mathit{LIND}$). $\endgroup$
    – Emil Jeřábek
    Commented Sep 20, 2013 at 14:00
  • 2
    $\begingroup$ Editing suggestion: I found the order of quantifiers confusing in the definition of $I$ (specifically, that $k$ could depend on $n$.) You mean $\{ n : \exists k \ \mbox{such that} \ k\ \mbox{is standard and}\ n<m^k \}$, right? $\endgroup$
    – David E Speyer
    Commented Sep 20, 2013 at 14:18
  • 1
    $\begingroup$ There are plenty of non-pathological non-standard models of $Q$. For instance, $\{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] , a_n > 0 \}$ with polynomial addition and multiplication, and the successor just involving adding 1, is a computable nonstandard model of $Q$. $\endgroup$
    – Keshav Srinivasan
    Commented Sep 20, 2013 at 15:25
  • 2
    $\begingroup$ It seems one can do that as follows: the model is $\mathbb{N}\cup\{\infty_1,\infty_2\}$, with a "small" infinity $\infty_1$ and "large" infinity $\infty_2$, so $n+\infty_1=n\cdot\infty_1=\infty_1$ and $n+\infty_2=n\cdot\infty_2=\infty_2$, but $\infty_1+\infty_2=\infty_1\cdot\infty_2=\infty_2$ etc. Now define exponentation as norml, but have $x^{\infty_1}=\infty_2$ for any $x>1$. I believe this satisfies $Q$ plus the basic recursive definition of exponentiation. $\endgroup$
    – Joel David Hamkins
    Commented Sep 21, 2013 at 17:01
22
$\begingroup$

Other people have answered your question as stated, but let me address what I think is your real underlying question, which is whether one can construct a conventional mathematical structure that has all the properties that Nelson wants to attribute to the natural numbers. I think that this is fundamentally impossible, because conventional mathematics isn't capable of being vague in the requisite manner. No infinite set can properly represent what Nelson believes in since he doesn't believe in infinite sets. But no finite set can either, because finite sets have sharp boundaries. There isn't any specific integer $n$ that Nelson will absolutely affirm such that he will absolutely deny $n+1$.

In my opinion the most promising avenue is not to try to model Nelson's integers directly, but instead to model Nelson himself, or more precisely the kinds of statements that Nelson is willing to affirm. In doing so, we're free to use infinite sets or anything else that we believe in. As a first crude approximation, I can imagine defining a probability distribution $P$ on sentences of first-order arithmetic where $P(S)$ represents the probability that Nelson will affirm $S$. I could also imagine coming up with rules about how $P(S)$ and $P(S')$ are related where $S$ and $S'$ are (for example) statements such that $S'$ follows from $S$ by applying a rule of inference. Of course $P(S)$ should also depend on the length of $S$, falling off to zero as $S$ gets too large.

I haven't seen anyone try to carry out such a program in full detail; if you're interested then I think it would make for an interesting project. There has been some work done by logicians on formalizing vagueness that might be relevant.

Improve this answer
$\endgroup$
22
  • 12
    $\begingroup$ Perhaps computational cost is a better model here than probability, with some calculus on assertions such as "I can affirm $S$ after $N$ units of computation", and impredicative induction having an infinite computational cost. $\endgroup$
    – Terry Tao
    Commented Sep 20, 2013 at 21:42
  • 5
    $\begingroup$ @Keshav: The vagueness I'm referring to is the vagueness of what the largest integer is. When you say that he doesn't believe that there are only finitely many natural numbers...well, look at what you quoted: He says that perhaps there is no such number as 80^5000. Not that 80^5000 is infinitely large. He only says that we can't say for sure that 80^5000 is finite. The source of Nelson's skepticism is the physical infeasibility of arbitrarily large integers, and physical infeasibility is a vague concept. That's what I mean by vagueness; I don't mean Nelson is unclear about what he believes. $\endgroup$
    – Timothy Chow
    Commented Sep 21, 2013 at 1:18
  • 4
    $\begingroup$ Also when you say that he'll accept whatever can be proven in $Q$, I agree that he'll accept statements whose proofs in $Q$ can be exhibited, but most mathematicians will say that there are theorems of Q that are 80^5000 characters long, but I don't think Nelson will agree. When Nelson says he accepts that the successor of a natural number is a natural number, we have to be careful not to assume that he means exactly what we mean by that. He's willing to assert any explicitly exhibited theorem of $Q$, but that's not the same as what most people mean by accepting $Q$. $\endgroup$
    – Timothy Chow
    Commented Sep 21, 2013 at 1:22
  • 2
    $\begingroup$ @TimothyChow It's easy to misunderstand Nelson's views, because they're so extreme, but he definitely doesn't believe in a largest integer. He believes that the sequence 1, 1+1, 1+1+1, ... goes on for all eternity. But he believes that there are some numbers $a$ and $b$ in this sequence such that $a^b$ never occurs in the sequence, even though if $a$ and $b$ occur in the sequence, $a + b$ and $ab$ must occur in the sequence. Now you or I may think this is impossible, because if $2^x$ is infinite, then there must be a least number $n$ such that $2^n$ is infinite, but that assumes induction. $\endgroup$
    – Keshav Srinivasan
    Commented Sep 21, 2013 at 2:09
  • 4
    $\begingroup$ @Keshav: Though I'm not sure I agree with your interpretation of Nelson, let me set that aside for a moment. In what sense does a nonstandard model illustrate Nelson's point of view? Nelson doesn't believe in the completed totality of the natural numbers, so he wouldn't believe in your nonstandard model either. Are you just looking for something that illustrates a small subset of Nelson's beliefs, namely those surrounding his beliefs about the totality (or otherwise) of exponentiation? $\endgroup$
    – Timothy Chow
    Commented Sep 21, 2013 at 17:08
8
$\begingroup$

One way would be to consider the theory consisting of the axioms of arithmetic plus a new symbol $x$ and the axioms $x>1$ and $x^n<2^x$ for each standard natural number $n$. This is consistent, because each finite subset of its axioms is satisfiable. Take a model, and take the initial segment of all numbers less than $x^n$ for some $n$. This is clearly closed under addition and multiplication, but not exponentiation.

I'm not sure how to make a computable model of this theory.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .