A similar question was asked in comments elsewhere.

A paper by Roberto Di Cosmo and Thomas Dufour ("The Equational Theory of 〈ℕ, 0, 1, + , ×, ↑〉 Is Decidable, but Not Finitely Axiomatisable") asserts in footnote 2 (p.3) that it has been shown "that there are no nontrivial equations for $⟨\mathbb{N}, \mathrm{Ack}(n, \_, \_)⟩$ if $n > 2.$" References make it clear that $\mathrm{Ack}(n,x,y)=H_{n+1}(x,y)$ in the hyperoperation sequence, so the assertion is as follows:

$\text{There are no nontrivial equations for the binary function }(\_\uparrow^y\_)\text{ if }y>1\\ \text{ (i.e., for hyperoperations above exponentiation)}\tag{*}.$

(For this, the above paper cites Charles F. Martin, "Axiomatic bases for equational theories of natural numbers", Notices of the Am. Math. Soc., 19(7):778, 1972, which I have not found online.)

Q.1: What, precisely, is meant by a "nontrivial equation" here?

(The defining recursion $$x\uparrow^{y+1}(z+1)=x\uparrow^y (x\uparrow^{y+1}z),$$ which certainly holds for $y>1$, is evidently considered trivial.)

Q.2: Is the following a valid proof based on assertion $(*)$? ...

Claim:

If $x,y,z$ are integers $\gt 1$, then the value of $\ x\uparrow^y z\ $ uniquely determines $x,y,z$; i.e., $$x\uparrow^y z = x'\uparrow^{y'} z' \quad\implies\quad x=x',\ y=y',\ z=z'.\quad \tag{1}$$

(The purpose of restricting the domain to integers $>1$ is to remove obvious counterexamples that arise from equations like $x\uparrow (a\cdot z) = (x\uparrow a)\uparrow z\ \ $ or $\ \ 2\uparrow^y 2=4\uparrow^{y'} 1\ \ $ or $\ \ 1\uparrow^y z=1\uparrow^{y'} z'.$)

Proof:

Suppose, for the sake of contradiction, that there is a counterexample to $(1)$, in which the LHS of the implication holds but not the RHS. Then the LHS is a nontrivial equation for some hyperoperation(s) beyond exponentiation, which is impossible as per $(*)$. QED

up vote 5 down vote accepted

To understand the linked question and its answer, it's important to realize that the word "equation" has a very precise meaning in this context.

Quick summary of what follows: the defining recursion of the Ackermann function is nontrivial, but isn't an equation in the right language; and the argument in question 2 is incorrect, since equations involve quantifying over all elements of the structure.

First off, we need to define terms. A term in a functional language (which is just a collection of function symbols, nothing too complicated; the word "functional" is included because we often consider other kinds of languages) is an expression built from the function symbols in that language, variables, and parentheses; an equation is then a sentence of the form $$\forall x_1,...,x_n(s(x_1, ..., x_n)=t(x_1, ..., x_n)),$$ where $s, t$ are terms in the variables $x_1, ..., x_n$. For instance, the language of groups contains a binary function symbol (the group operation), a unary function symbol (the inverse operation), and a nullary function symbol (the identity element).

By contrast, the definition by recursion of the Ackermann function isn't an equation in the relevant language: that language consists only of the binary function symbol "$\uparrow^n$," and the defining recursion involves the symbol "$+$" as well. So the definition of "equation" is quite strict. Note that this crops up in a few places in the linked question, where several properties of exponentiation are proposed which are not, in fact, equations in the language of exponentiation alone.

A structure in a given functional language is just a set, together with some functions corresponding to the function symbols (with the correct arities). For instance, if our language $\Sigma$ consists of two unary function symbols $@$ and $\%$, then one example of a $\Sigma$-structure is $(\mathbb{Z}; @(x)=x+1, \%(x)=x-1)$. It should be clear what it means for an equation to hold in a structure - for instance, in the above structure the equation $$\forall x(@(\%(x))=\%(@(x))).$$ holds.

An equation is trivial if it is true no matter how the function symbols are interpreted. That is, given a functional language $\Sigma$, an equation $E$ in the language $\Sigma$ is trivial if it is true in every $\Sigma$-structure. For instance, the equation from the previous paragraph isn't trivial: consider the $\Sigma$-structure where both $@(x)$ and $\%(x)$ are interpreted as "$x+1$."

It's not hard to convince yourself that there really aren't very many of these; in fact, an equation is trivial iff the two terms are exactly the same! So that further justifies the name.

This answers your first question. Towards the second, note the universal quantifier in the definition of an equation: simply having an instance of one thing equalling another doesn't constitute an equation, an equation specifies that two specific terms are always equal. So the answer to your second question is no.


Incidentally, the most relevant subject here is universal algebra.

  • Thanks for this very informative answer! – r.e.s. Jun 8 '17 at 2:38

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.