2
$\begingroup$

Here $\mathbb{N}=\left\{n\in\mathbb{Z}:0<n\right\},$ function parameter lists are delimited as $\left[\dots\right],$ and $\underline{\exists}$ means there exists exactly one.

One way to state the principle of recursion is this:

For every arbitrary set $\Psi$ and function $F\left[x,\psi\right]:\mathbb{N}\times\left(\mathcal{D}\subseteq\Psi\right)\to\Psi$ there exists exactly one function $f\left[x\right]:\mathbb{N}\to\Psi$ such that

$$\psi_1\equiv f\left[1\right]\land\psi_{n^\prime} = f\left[n^\prime\right]=F\left[n,\psi_n\right]=F\left[n,f\left[n\right]\right].$$

Appealing to the above definitions, my statement of the principle of recursion in terms of quantifiers is:

$$\forall_\Psi\forall_F\underline{\exists}_f\left[\forall_{n\in\mathbb{N}}\left[\psi_1\equiv f\left[1\right]\land\psi_{n^\prime} = f\left[n^\prime\right]=F\left[n,\psi_n\right]=F\left[n,f\left[n\right]\right]\right]\right].$$

My understanding of what constitutes second order logic is the use of quantifiers on propositional forms. If quantifiers are used only on primitive variables, then we still have logic of the first order. An example of a statement in logic of the second order is the principle of induction:

$$\forall_{P}\left[\left(P\left[1\right]\land\forall_{n}P\left[n\right]\implies P\left[n^{\prime}\right]\right)\implies\left\{ x\backepsilon P\left[x\right]\right\} =\mathbb{N}\right].$$

My question is this: is a statement of the form giving the principle of recursion in terms of quatifiers considered to be of second order logic?

$\endgroup$
2
$\begingroup$

Yes, this is second-order (and indeed there's no first-order way to characterize $\mathbb{N}$ - this is a consequence of the compactness theorem for first-order logic).

The right way to think about this is to think about how the truth/falsity of the sentence in question in a given structure is determined. If (when evaluating quantifiers) we only ever need to look at elements of that structure, then we might be dealing with first-order logic; if we ever need to look at more complicated objects related to the structure - subsets of the structure, functions from the structure to the structure, or even an unrelated structure (e.g. defining torsion in a group by referring to $\mathbb{N}$), then we're definitely not dealing with first-order logic.


It's worth noting that there are other ways a sentence can fail to be first-order of course - infinitary logic, for example, only involves first-order quantification but does allow infinite Boolean combinations. (Hence my "might" in the above.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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