2

We say that a formula $\phi$ with free variables $v_1,\ldots,v_n$ represents the $n$-ary relation $R\subset\mathbb{N}^n$ in the axiom system $A_E$ (this contains axioms for addition, multiplication, ordering, and the first two Peano axioms) if for any $a_1,\ldots,a_n\in\mathbb{N}$,

$$(a_1,\ldots,a_n)\in R\Rightarrow A_E\vdash\phi(S^{a_1}0,\ldots,S^{a_n}0)$$ $$(a_1,\ldots,a_n)\not\in R\Rightarrow A_E\vdash\neg\phi(S^{a_1}0,\ldots,S^{a_n}0)$$

We say that a formula $\theta$ with free variables $v_1,\ldots,v_{n+1}$ functionally represents the $n$-ary function $f:\mathbb{N}^n\to\mathbb{N}$ if for any $a_1,\ldots,a_n\in\mathbb{N}$,

$$A_E\vdash\forall v_{n+1}(\theta(S^{a_1}0,\ldots,S^{a_n}0,v_{m+1})\leftrightarrow v_{m+1}=S^{f(a_1,\ldots,a_n)}0)$$

If a formula functionally represents a function $f$, then it represents $f$ as a relation, but the converse is supposedly not true. I am trying to find a counterexample for the converse. I expect this will come down to cleverly using a formula which is true in the theory of $\mathbb{N}$ but which is not provable from $A_E$. Also, note that if $\phi$ represents $R$, then $$R=\{(a_1,\ldots,a_n):\ \vDash_{\mathbb{N}}\phi(S^{a_1}0,\ldots,S^{a_n}0)\}$$

So, what is an example of a formula $\phi$ and a function $f$ such that $\phi$ represents $f$ as a relation but does not functionally represent $f$?

Anonymous
  • 2,630
  • 8
  • 27

1 Answers1

2

Hint: Take the simple case of a one-place $f$. What is the difference between a two-place $\theta$ (i) representing $f$ in a theory $T$ as a relation and (ii) representing $f$ as a function (in your terminology)?

It is easily seen that, in addition to satisfying the requirements for (i), what's needed is that for each $n$, $T \vdash \exists! y\,\theta(S^n, y)$. [Informally, $T$ knows that $\theta$ is functional (for numerals).] And in each case that, in part, requires $T$ proving a universal quantification. But weak induction-free arithmetics like Robinson arithmetic are notoriously bad at proving universal quantifications, even when they can prove each numeral instance ...

Peter Smith
  • 54,743
  • Thanks for the hint! Yea, I managed to gather that the $\rightarrow$ direction of the functionally represent definition says that $\theta$ is functional. So this means that I need to choose a formula which is functional but which cannot be proven functional from $A_E$. Another issue is that I don't really know any explicit examples of sentences which cannot be proven from $A_E$. I just know they exist by Godel's incompleteness theorem but I don't know if I can construct a desired formula from an arbitrary one which $A_E$ cannot prove. – Anonymous May 18 '20 at 11:21
  • Which theory exactly is your $A_E$? – Peter Smith May 18 '20 at 12:06
  • The axioms are listed on page 203 at http://agnigarh.tezu.ernet.in/~zubin/isc/extra/MathematicalIntroductionToLogic-Enderton.pdf – Anonymous May 18 '20 at 12:26
  • Also, I noticed they mention that $\forall y(y\neq 0\to\exists x(y=Sx))$ is not a consequence of $A_E$. I'm trying think how to use that right now. – Anonymous May 18 '20 at 12:28
  • 1
    Ah , I should have remembered Enderton's label! Doesn't the usual proof that $\forall x,0 + x = x%$ doesn't hold in Robinson Arithmetic just carry over to this theory too (though it proves each numeral instance)? [Just cook up a countermodel comprising the natural numbers and two rogue elements.] – Peter Smith May 18 '20 at 12:31
  • Yes, I can see how to give a counter model for $\forall x(0+x=x)$ over $A_E$ (and I also thought of a counter model for $\forall y(y\neq 0\to\exists x(y=Sx))$ but that's longer). Where I am having trouble is using this sentence to construct a formula in two free variables with the desired property. If I let be $\forall x(0+x=x)$, then I need to come up with a $\phi$ in two free variables and a function $f$ which it represents such that for some $n\in\mathbb{N}$, $\psi$ is implied by $\forall y(\phi(S^n0,y)\to y=S^{f(n)}0)$. I am having difficulty making that jump. – Anonymous May 18 '20 at 13:36