Relationship between propositional logic, first-order logic, second-order logic higher-order logic, and type theory

Question

I understand there is propositional logic, first-order logic, second-order logic higher-order logic, and type theory, where the latter logics are extensions of the former logics. Can someone explain the differences between these types of logics for someone who knows some basic linear algebra, set theory, calculus, and boolean algebra. Specific examples of the differences are appreciated, because wikipedia is a bit over my head on this one.

Answer 1

I'll speak about their grammatical differences, leaving their proof- and model-theoretic differences for someone more qualified to discuss. Each of these logics has a vocabulary $V$, which is the set of symbols out of which its well-formed formulas (e.g. terms, sentences) are generated. One usually singles out a subset of $V$ as the set of logical vocabulary $V_L$. It is these $V_L$s that distinguish logics at the ground level, making it very transparent which is an extension of which. Let's see:

• $V_L$(PL) = { '$\lnot$' , '$\land$' }

• $V_L$(FOL) = $V_L$(PL) $\cup$ { '=' , ' $\forall_1$ ' } where $\forall_1$ quantifies over individuals

• $V_L$(SOL) = $V_L$(FOL) $\cup$ { ' $\forall_2$' } where $\forall_2$ quantifies over properties (of individuals)

• $V_L$(HOL) = $V_L$(FOL) $\cup$ { ' $\forall_n$' } where $\forall_n$ quantifies over yet higher-order properties

• $V_L$(TT) = $V_L$(_OL) $\cup$ { ' $\lambda$' } where _OL is a _-order logic (usually _ > 0)

Of course, each of these systems could be defined in different ways, choosing different sets of logical vocabulary. This is just one way of going about it. Now, as you already said, each of these logics extends the ones coming before it. With this vocabulary talk we can give precise meaning to that:

Def. Logic A is an extension of logic B iff $V_L$(B) $\subset$ $V_L$(A).

In the event that the converse doesn't hold, A is said to be a proper extension of B.

Lastly, for specific examples of differences, consider these formulas:

• PL: '$\phi \lor \lnot \phi$'

• FOL: '$\forall x (x = x)$'

• SOL: '$(a = b) \equiv \forall P (P(a) \leftrightarrow P(b))$'

• TT: $\forall x ([\lambda x. x](x) = x)$

Each of these sentences is also valid for logics following it (the other direction doesn't hold, of course). Notice that higher-order logic is left out, because there is no sentence $\phi$ s.t. HOL $\models \phi$ but SOL $\not\models \phi$, due to the fact that the power-set operation is SOL-expressible (Hintikka 1995).

For corrections/suggestions, please leave a comment or simply edit this post.