If we take a first-order theory (like $\mathsf{ZFC}$, or $\mathsf{ZFC}$ plus some additional axioms) as the foundation of mathematics, does that imply that mathematical reasoning (theorems, proofs, algorithms, etc.) must be expressible in first-order logic (and associated rules of inference) in order to be "legitimate"? (not that you necessarily have to actually write it all out in FOL syntax, but that you have confidence that you could do so). Is there any sort of consensus around whether such "first-orderizability" is deemed a requirement of "legitimate" mathematical reasoning?
Some comments/observations related to the question:
In Mathematical Logic by Ebbinghaus et. al. (2nd ed.), section VII.2 states that, given a foundation of set theory with axioms $\boldsymbol{\Phi_0}$ (and the first-order language of set theory denoted by $L^S$), then:
Mathematically provable propositions have formalizations which are derivable from $\boldsymbol{\Phi_0}$. Thus it is in principle possible to imitate all mathematical reasoning in $L^S$ using the rules of the sequent calculus. In this sense, first-order logic is sufficient for mathematics.
But then later (section IX.2) they say:
The class of torsion groups cannot be characterized in first-order logic. But we can axiomatize this class if we add to the group axioms the "formula" $\forall x (x \equiv e \lor x \circ x \equiv e \lor x \circ x \circ x \equiv e \lor \ldots)$. Thus we gain expressive power when allowing infinite disjunctions and conjunctions. Such formations are characteristic of the so-called infinitary languages…This leads to the system $\mathcal{L}_{\omega_{1},\omega}$
This seems like a direct contradiction of the first quote (from VII.2). If a notion like "let $\mathfrak{G}$ be a torsion group" can't be expressed in (finitary) first-order logic, then it's hard to see how one can argue that this language is "sufficient for all mathematics".
More generally, the following considerations seem to weigh against restricting mathematical reasoning to arguments expressible in standard (finitary) first-order logic ("FOL"):
- Since an infinitary language like $L_{\omega_{1},\omega}$ is an extension of FOL, it seems like one could take $L_{\omega_{1},\omega}$ (instead of FOL) to be the language of a set theory like $\mathsf{ZFC}$ (the axioms remain valid statements of the language). In that case it would seem at least plausible that with a more expressive language (i.e. $L_{\omega_{1},\omega}$) having become available, one might be able to use it to formally prove statements which are true in every model of $\mathsf{ZFC}$ yet are not provable in FOL (maybe not even expressible in FOL).
- This post re "non-first-orderizability" on Terence Tao's blog (see especially last paragraph staring with "It seems to me that first order logic is limited") appears to take the position that mathematical reasoning need not be "first-orderizable", or even formalizable at all in any known formal language (see Tao's comments regarding "mathematical English").
Update/Clarification:
I realize that different axiom systems differ as to which first-order statements they can prove. So potentially statement $S$ is not formally derivable as a consequence of first-order axioms $\boldsymbol{\Phi}$, but $S$ is a formal consequence of some stronger first-order axiom system $\boldsymbol{\Psi}$.
But what I have in mind is a different issue, namely the notion of a statement in “mathematical English” (to borrow Tao’s phrase) which, due to its logical “structure”, cannot in any way even be expressed as a formula in first-order logic (regardless of what axioms or ontological assumptions one stipulates).
- Such “inherently non-first-orderizable” statements are what Tao seems to be describing in the last paragraph of the blog post, starting with “first order logic is limited by the linear…nature of its sentences” and following up with “this does not fully capture all of the dependency tree of variables” and “subtleties may appear when one deals with large categories”.
- A concrete example might be something equivalent to a formula involving infinite disjunction in $L_{\omega_{1}, \omega}$: given a well-defined infinite collection of (finite) sub-formulas $\Phi_{n}$, imagine the (infinite) formula $\Phi_{0}(x) \land (\Phi_{1}(x) \lor \Phi_{2}(x) \lor \Phi_{3}(x) \lor \ldots)$ Surely such a statement is not, in general, expressible in (standard, finitary) first-order logic (unless somehow it can always be made first-order-expressible by “upgrading” to a stronger theory? like upgrading from $\mathsf{ZFC}$ to Kelley-Morse set theory, or something like that?)
Best Answer
Yes, when someone says that ZFC is a suitable foundation for mathematics, that means that all standard mathematical notions can be expressed in the language of ZFC using first-order logic and all standard mathematical arguments can be written as derivations from ZFC using first-order logic.
For your particular example of torsion groups, there is a first-order formula $\psi(x)$ with one parameter in the language of set theory such that, for any $x,$ $\psi(x)$ holds iff $x$ is a torsion group.
The statement that torsion groups can't be characterized in first-order logic means something different, namely:
There is no first-order sentence $\varphi$ in the language of group theory such that, for every group $G,$ $G$ is a torsion group iff $G$ satisfies the sentence $\varphi.$
Note that $\varphi$ here is required to be in the language of group theory; it can only quantify over elements of the group (not subsets of the group, or natural numbers, or anything else), and it can't refer to any functions or relations other than the multiplication operation of the group.
So how would you write the original formula $\psi$ in the language of set theory? The formula $\psi(x)$ would say something like the following (you'd have to expand all the circumlocutions fully, of course, but, although that's a bit unwieldy, it's routine to do):
$x$ is an ordered pair $\langle G, \circ\rangle.$
$\circ$ is a function mapping $G\times G$ to $G$ satisfying the axioms for a group.
For every $a\in G,$ there exists a natural number $n$ and a function $f: n+1\to G$ such that:
(i) $f(0) = a;$
(ii) $(\forall k\lt n)(f(k)\circ a = f(k+1));$
(iii) $f(n)$ is the identity element of the group $\langle G, \circ\rangle.$
This is a first-order formula in the language of set theory, but you can see that it is not a formula in the language of group theory; it talks about objects other than elements of $G,$ and it involves quantifying over natural numbers (and also functions, or finite tuples from $G).$
(For anybody who hasn't seen the usual set-theoretic convention regarding natural numbers, I should mention that $\psi$ as written above uses the formulation that for any natural number $m,$ we have $m = \{k \mid k \lt m\}.)$