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?

  • $\begingroup$ If you already have set theory there, then relations can be coded as sets. Perhaps that book does not presuppose set theory? $\endgroup$ – GEdgar Jun 26 '17 at 17:46
  • $\begingroup$ I do not have set theory. The book is about finite model theory. $\endgroup$ – Larry B. Jun 26 '17 at 18:57
  • $\begingroup$ So that answers your question. Quantification on relations is "second order". Given set theory, it is the same as Quantification on sets. But without set theory, it is not the same. So third order would be quantification on relations of relations. $\endgroup$ – GEdgar Jun 26 '17 at 20:34

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))$
  • $\begingroup$ I know how to translate first-order logic quantifiers into sets. I do not know how to translate second- or third-order logic quantifiers into statements about sets. I was looking for something more exact. $\endgroup$ – Larry B. Jun 24 '17 at 0:12
  • $\begingroup$ Well in second order logic, you have relation variables $R_a^1,\dots,R_a^n,\dots$ of arity $n$. I'll write $\forall_2$ for second order quantification. You rewrite $\forall_1 x$ to $\forall x\in D$ and $\forall_2 R_a^i$ to $\forall R_a^i\subseteq D^a$, where $D$ is the domain. $\endgroup$ – xavierm02 Jun 24 '17 at 9:39
  • $\begingroup$ Excellent! How do you write quantification for third-order logic like you did for first/second order? If you edit your answer with third-order quantifications, I'll accept it. $\endgroup$ – Larry B. Jun 26 '17 at 16:52
  • $\begingroup$ @LarryB. I updated the answer. $\endgroup$ – xavierm02 Jun 26 '17 at 21:12

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.