Third order logic: quantifying sets of sets or relations of ...?

Question

I'm reading a book that uses first- and second-order logic. The author defines first-order logic normally, but then defines second-order logic as "quantification on relations." Almost everywhere else I've looked on the internet, folks use "quantification over sets". What's the difference? Are these interpretations equivalent, and how?

I prefer the relation semantics because it doesn't bring in set theory (quantification over sets of sets). I have not found any definition of third-order logic that does not involve sets. Is there a way to define third-order logic in terms of relations/predicates?

Answer 1

A set is like a unary relation / predicate: You can represent the set $X\subseteq \mathbb N$ by $$P_X:n\mapsto \left\{\begin{array}{ll}\operatorname{true}&\text{if }n\in X\\\operatorname{false}&\text{otherwise}\end{array}\right.$$ and then, instead of $n\in X$, you write $P_X(n)$.

So quantifying over relations (or arbitrary arity) is more general. Second order logic allows you to quantify over any relation, while monadic second order logic only allows you to quantify over unary relations (i.e. sets).

---

In the other direction, if we write $\forall_i$ for $i^\text{th}$ order quantification, and $D$ for the domain, you can translate formulas in the following way:

• First order quantification: $\forall_1x$ becomes $\forall x \in D$
• Second order quantification: $\forall_2 R$ becomes $\forall R \subseteq D^a$ where $a$ is the arity of the symbol $R$. Note that this can also be written $\forall R \in \mathcal P(D^a)$
• Third order quantification: $\forall_3 X$ becomes $\forall X \in \mathcal P(\mathcal P(D^a))$