2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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<m$. 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<m}$ with the property that $X_0=A$, $X_{m-1}=B$, and for each $i<m-1$ 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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