# Second-order reachability in second-order logic

By second-order reachability I mean a second-order lifting of the reachability problem on first-order structures. So let $$R(X,Y)$$ be a second-order binary predicate (i.e. it links a set of elements $$X$$ to another set of elements $$Y$$. Then we have some first-order predicates $$P(x)$$ and $$Q(y)$$.

Lifting how I would express reachability in second-order logic, I can express this second-order reachability in third-order logic:

$$\forall \mathbb{P} \bigl(\mathbb{P}(P) \land \forall X Y ((\mathbb{P}(X) \land R(X,Y)) \to\mathbb{P}(Y)) \to \mathbb{P}(Q)\bigr)$$

But is this needed? Is this second-order reachability problem expressible in second-order logic, or do I need third-order quantifiers, similarly to how first-order reachability needs second order ones?

In fact, we can always stay in the second-order realm (as long as our "base structure" is infinite)!

First, let's look at the particular case where our base structure is $$\mathcal{N}=(\mathbb{N};+,\times)$$. Over $$\mathcal{N}$$ we can code finite sequences of sets as individual sets as follows: the set $$X\subseteq\mathbb{N}$$ codes a finite sequence of sets iff every element of $$X$$ has the form $$2^x3^y$$ for some $$x,y\in\mathbb{N}$$, and there is some $$m$$ such that whenever $$2^k\vert u\in X$$ we have $$k. The idea then is that such an $$X$$ codes the sequence whose $$i$$th term is $$\{j: 2^i3^j\in X\}$$.

Now suppose $$R$$ is a second-order binary operation on $$\mathcal{N}$$. Given $$A,B\subseteq\mathbb{N}$$, we have that $$A$$ is $$R$$-connected to $$B$$ iff there is some $$X$$ which codes a finite sequence of sets $$(X_i)_{i with the property that $$X_0=A$$, $$X_{m-1}=B$$, and for each $$i we have $$X_iRX_{i+1}$$. This is purely second-order over $$\mathcal{N}$$, so we've avoided third-order quantification.

OK, but what if we're looking at a very low-expressive-complexity structure, such as a(n infinite) pure set? Well, we can still do the job!

• In pure second-order logic, we can determine when a set $$X$$ is finite ("Every well-order on $$X$$ is also a co-well-order" - and if you want to avoid reliance on the axiom of choice here, you can also include the clause "$$X$$ is well-orderable," which interestingly is optimal in a precise sense).

• We now can express "$$A$$ is $$R$$-connected to $$B$$" as "There is a pairing operation $$\langle\cdot,\cdot\rangle$$, a set $$X$$, and a binary relation $$\trianglelefteq$$ such that

• the set $$L:=\{x:\exists y(\langle x,y\rangle\in X)\}$$ is finite,

• $$\trianglelefteq$$ is a binary relation on $$L$$,

• if $$x$$ is the $$\trianglelefteq$$-least (resp. greatest) element of $$L$$ then $$\{y: \langle x,y\rangle\in X\}$$ is $$A$$ (resp. $$B$$), and

• if $$x,x'\in L$$ and $$x'$$ is the $$\trianglelefteq$$-successor of $$x$$ then we have $$\{y: \langle x,y\rangle\in X\}R\{y: \langle x',y\rangle\in X\}.$$

Note, though, that there was a cost: over $$\mathcal{N}$$ we just needed to quantify over sets, whereas here we need to quantify over relations. This is unavoidable: monadic second-order logic is not strong enough to perform this sort of construction without a sufficiently rich base structure.

• Thanks, this is really interesting! How many quantifier alternations do you think are needed to express all these things? Sep 17 at 6:38