Are there 'finitistic' nonrecursive functions (assuming Church's Thesis is false)?

Question

[Note: In what follows, I will be using the same type of argument Laszlo Kalmar did in his paper "An Argument Against the Plausibility of Church's Thesis" found in Constructivity in Mathematics, (Amsterdam, 1959, pp. 72-80). Kalmar considered the following nonrecursive function derived from the nonrecursive function $\mu_y[T_1(x,x,y)]$ found in Kleene's paper, "General Recursive Functions of Natural Numbers" (pp. 237-253 of Martin Davis' book The Undecidable, in particular Thm. XIV):

$$\psi(x)=\begin{cases} \mu y(\phi(x,y)=0) & \text{if } (\exists y)(\phi(x,y)=0) \\ 0 & \text{if }(\forall y)(\phi(x,y)\ne0)\end{cases}$$ where $\phi$ is an appropriate general recursive function of two arguments (since Elliot Mendelson argues in his paper, "On some recent criticism of Church's Thesis", Notre Dame Journal of Formal Logic Vol. IV, No. 3, July 1963, that, "if [Kalmar's--my comment] arguments were correct, then Church's Thesis would be false", I will not concern myself with the unplausible consequences).

Kalmar argues as follows: "...for any natural number $p$ for which a natural number $y$ with $\phi(p,y)=0$ exists, an obvious method for the calculation of the least such $y$, i.e. of $\psi(p)$ can be given: calculate in succession the values of $\phi(p,0), \phi(p,1),\phi(p,2),\ldots$ (each of which can be calculated, on acount of the general recursivity of of $\phi$, in a finite number of steps) until we obtain a natural number $q$ for which we have $\phi(p,q)=0$ and take this $q$. On the other hand for any natural number $p$ for which we can prove, not in the frame of some fixed postulate system but by means of arbitrary--of course, correct--arguments that no natural number $y$ with $\phi(p,y)$ exists, we also have a method to calculate the value of $\psi(p)$ in a finite number of steps: prove that no natural number $y$ with $\phi(p,y)$ exists, which requires in any case but a finite number of steps, and gives immediately the the value $\psi(p)=0$." The reader should note that in Mendelson's paper, no account is given as to why this argument is false.

Question 1. Is Kalmar's argument as stated above false, and if so, why?]

Now to my argument. It is based on Kleene's theorem XV in the same paper. In it Kleene makes the following statement:

"...nonrecursive functions can be defined by the schema

$$\tau(x)= \begin{cases}0 & \text{if } (\exists y)R(x,y)\\ 1 & \text{if } (\forall y)\lnot R(x,y)\end{cases}$$ where $R(x,y)$ is primitive recursive [pg. 251 of Davis--my comment] ." Recall that $R(x,y)$ is primitive recursive iff there is a primitive recursive function $\pi(x,y)$ such that

$$R(x,y)\Longleftrightarrow \pi(x,y)= \begin{cases} 0 & \text{if } R(x,y)\text{ true} \\ 1 & \text{if } R(x,y)\text{ false} \end{cases}$$ By the Law of Excluded Middle if $R(x,y)$ is primitive recursive then $\lnot R(x,y)$ is primitive recursive also.

Now consider Kalmar's argument as applied to Kleene's schema. For any natural number $p$ for which a natural number $y$ with $R(p,y)$ ($\pi(p,y)=0$) exists, one can calculate in succession $\pi(p,0), \pi(p,1), \pi(p,2),\ldots$, until one obtains a natural number $q$ such that $\pi(p,q)=0$ and for which $R(p,q)$ holds. On the other hand, consider, for any natural number $p$ for which one can prove, not in the frame of some fixed postulate system, but by means of arbitrary--of course, correct--arguments one also has a method to calculate the value $\pi(p)$ in a finite number of steps: prove that no natural number $y$ with $\pi(p,y)=0$ (i.e. $\lnot R(p,y)$ is true) exists (that this can be done is immediate by the fact that $\lnot R(x,y)$ is primitive recursive if $R(x,y)$ is for any substitution of numerals $p,y$ for the variables $x,y$), which requires in any case but a finite number of steps. Therefore, it would seem to be reasonable to conclude that, given Church's Thesis to be false, my aforementioned example is an example of a 'finitistic', nonrecursive function (since Mendelson claims that "if his [Kalmar's] arguments were correct, then Church's Thesis would be false.") The following question now presents itself:

Question 2: Have I misinterpreted or misapplied Kleene's Schema?

Addendum: I want to respond to two assertions made by Noah Schweber--one positive and one negative. The assertion I wish to respond positively to is the following:

Kalmar's argument is a complicated way of making the following claim: There is an effective way for a person to recognize "correct" $\Pi^0_1$ sentences.

The assertion that I want to respond negatively to is the folowing:

Kalmar's argument can't survive the choice of a fixed background theory...

In fact it can, and the background theory in question is $QF$--$IA$ which is $PRA$ transformed into a first-order theory by adding first-order logic. This is a conservative extension of $PRA$ and has the virtue of using $\Pi^0_1$-sentences instead of open formulas in $PRA$ (since there is a finitistic procedure for transforming a proof in $QF$--$IA$ of a $\Pi^0_1$-sentence into a proof in $PRA$ of the corresponding open formula, making provability, and the consistency of these theories, finitistically equivalent--all this found on pg. 2 of Ignjatovic's paper, "Hilbert's Program and the omega-rule"). Since it is known that R(x,y) and $\lnot$R(x,y) are primitive recursive and therefore decidable for any substitution of numerals $p$,$q$, then for each $p$,$q$ instance R($p$,$q$) ($\lnot$R($p$,$q$ )) is finitistically provable. Now Ignjatovic (pg.5) quotes Detlefsen paraphrasing Herbrand:

And, again, he says that a universal claim is merely a description or manual of operations which are to be executed in each particular case

Ignjatovic now quotes Detlefsen stating his $\omega$-rule (which I relate to Kleene's schema using brackets):

This view of the universal quantifier would seem to sponsor the following restricted $\omega$-rule: if I have an effective procedure $\mathbf P$ (a manual of operations $\mathbf P$) for showing of each individual [$p$,$q$] that [R($p$,$q$), $\lnot$R($p$,$q$)] is finitistically provable, then [$\forall$yR(x,y), $\forall$y$\lnot$R(x,y)] is also finitistically provable.

Now that I have Detlefsen's $\omega$-rule, I would like to be able to use Buldt's Lemma 3.6 to show that $QF$--$IA$ under the $\omega$-rule given by Buldt in his paper "The Scope Of Goedel's First Incompleteness Theorem" (an instance of Detlefsen's $\omega$-rule) is complete in Hilbert's sense for $\Sigma^0_1$ and $\Pi^0_1$ sentences of $QF$--$IA$:

Lemma 3.6: Let $\mathcal F^{\omega}_{\alpha}$ denote a semi-formal system of arithmetic that admits $\alpha$ applications of the $\omega$-rule [$\vdash_{\mathcal F}$$\varphi$(n), for all n$\in$$\mathbb N$ $\Rightarrow$ $\vdash_{\mathcal F}$($\forall$x)$\varphi$(x)--my comment] ($\alpha$ an ordinal number; $\mathcal F$ extending, say, $PA$), then for all n$\in$$\mathbb N$ $\mathcal F^{\omega}_{n}$ is $\Sigma^0_{2n}$- and $\Pi^0_{2n}$-complete.

It is easily seen that for 1 application of the $\omega$-rule one has that $\mathcal F^{\omega}_1$ is $\Sigma^0_2$- and $\Pi^0_2$-complete and if $\mathcal F$ is an extension of, say $PA$ then Lemma 3.6 will hold for fragments thereof, in particular for $QF$--$IA$ and also for the fragment of $QF$--$IA$ dealing with $\Sigma^0_{2}$ and $\Pi^0_{2}$ sentences. Note that 'complete in Hilbert's sense" means, for Buldt, the following:

$\mathcal F$ is Hilbert-complete iff $\sigma$$\vdash$$\varphi$ or $\Sigma$$\vdash$$\lnot$$\varphi$ for all $\varphi$$\in$$\mathscr L_0$, where $\Sigma$ is the set of axioms of $\mathcal F$ and $\mathscr L_0$ ={$\varphi$|$\varphi$ closed and $\mathfrak U$$\vDash$$\varphi$}

Observe that for $\mathfrak U$$\vDash$$\forall$x$\varphi$(x), $\vDash$$( \forall$x)$\varphi$(x) $\Longleftrightarrow$ $\vDash$$\varphi_x$($\mathbf i$) for all $\mathbf i$ $\in$ $\mathscr L$($\mathfrak U$) where $\mathscr L$($\mathfrak U$) is the first-order language obtained from $\mathscr L$ by adding all the names of individuals of $\mathfrak U$ (as new constants) to $\mathscr L$ and adding $\mathbf i$, $\mathbf j$ as syntactical variables which vary through names (Shoenfield, Mathematical Logic, pp. 18-19). Observe also that the implication in the $\Leftarrow$ direction is identical in form to Buldt's $\omega$-rule,

$\vdash_{\mathcal F}$$\varphi$(n), for all n$\in$$\mathbb N$ $\Rightarrow$ $\vdash_{\mathcal F}$$\forall$(x)$\varphi$(x)

and indeed is just the syntactical form of the $\Leftarrow$ direction of the semantical definition of $\forall$x$\varphi$(x). This being the case, it is clear that since R(x,y) is primitive recursive iff $\lnot$R(x,y) is primitive recursive for all substitutions of numerals formed from 0 by the application of the successor operation (these being the syntactical 'names' for numbers in $\mathbb N$), a single application of this $\omega$-rule to the variable y of the p.r. relations R(x,y), $\lnot$R(x,y) will produce only the true $\Pi^0_1$ sentences of $QF$--$IA$ for R(x,y), $\lnot$R(x,y) (and applying a single instance of the $\omega$-rule according to Buldt's proof of Lemma 3.6 will produce only the true $\Sigma^0_2$ and $\Pi^0_2$ sentences of $QF$--$IA$, so the term 'complete' in Lemma 3.6 can be construed to be 'Hilbert-complete'), one (through the use of Buldt's $\omega$-rule) will have an effective means to 'recognize' 'correct' (true) $\Pi^0_1$ sentences of $QF$--$IA$ and in such manner, Kalmar's argument against Church's Thesis is (at least to me) correct.

Answer 1

Kalmar's argument is indeed wrong. The problem, of course, lies in his justification of our ability to compute $\psi(x)=0$, where he writes

"We can prove, not in the frame of some fixed postulate system but by means of arbitrary - of course, correct -arguments that no natural number $y$ with $\varphi(p,y)$ exists, we also have a method to calculate the value of $\psi(p)$ in a finite number of steps: prove that no natural number $y$ with $\varphi(p,y)$ exists, which requires in any case but a finite number of steps, and gives immediately the the value $\psi(p)=0$." $\quad$ [Emphasis mine.]

By not relying on any fixed axiom system, Kalmar has indeed dodged Godel - but not in a good way. There is a gigantic unspoken assumption here: how do we identify a correct proof? Kalmar is implicitly assuming that "correct"ness can be recognized. Even defining correctness is no easy task if we're not Platonists; and even assuming we're happy with a "true" $\mathbb{N}$, how on earth do we argue that

• (1) Every true $\Pi^0_1$ sentence has an identifiably correct proof

and

• (2) We have some procedure to never mistake an incorrect proof for a correct proof?

Kalmar's argument is a complicated way of making the following claim:

There is an effective way for a person to recognize "correct" $\Pi^0_1$ sentences.

This flies in the face of experience: we've all (I suspect) made the embarrassing mistake of thinking that some statement was true - a fortiori consistent with the axiom system we're using - only to find out later that it is disprovable from that axiom system. Rephrased appropriately, this is a case of thinking some Turing machine doesn't halt, and then later finding out that it does. Kalmar claims implicitly that there is some process we can perform to avoid ever doing this, while at the same time eventually deducing each true $\Pi^0_1$ sentence.

EDIT: Let me clarify what I mean when I say that Kalmar's argument is incorrect. I am not saying (although I do believe) that Kalmar's conclusion is incorrect; rather (and ironically given his claim about correctness) he is assuming a principle which is not at all obviously true, and in fact is basically what he wants to prove in disguise. So his argument doesn't really do anything. If we accept Kalmar's mathematical optimism, then Church's Thesis is clearly false; but Kalmar gives us no reason to do this.

As to your main question, I'm not really sure what it means - what does "finitistic" mean here?