Syntax of Logic

Idea

The syntactic component defines:

• An alphabet of symbols (propositional variables, connectives, quantifiers)
• Formation rules for constructing well-formed formulas
• Structural properties of the language (decidability of well-formedness)

Structure

The syntax is defined relative to a signature $\Xi$ containing function symbols and relation symbols with fixed arities.

Alphabet

• Variable: $x,y,z,\dots$
• Logical connectives: $\neg ,\wedge ,\vee ,\to ,\perp$
• Quantifiers: $\forall ,\exists$
• Equality: $=$ (typically treated as a logical constant)
• Auxiliary symbols: parentheses
• Relation variables: $P,Q,R,\dots$ in second- and higher-order systems

Type system

We have base types ($\mathrm{U}$ for individuals, $\mathrm{Prop}$ for truth values) and an arrow constructor for functions.

In higher-order logic the system is close to the typing system of Simply-Typed Lambda Calculus.

$$\frac{}{\mathrm{Prop}\mathbf{type}}\frac{}{\mathrm{U}\mathbf{type}}\frac{{\tau }_1\mathbf{type}{\tau }_2\mathbf{type}}{{\tau }_1\to {\tau }_2\mathbf{type}}$$

In first-order settings,

$$\frac{}{\mathrm{U}\mathbf{typ}{\mathbf{e}}_1}\frac{\tau \mathbf{typ}{\mathbf{e}}_1}{U\to \tau \mathbf{typ}{\mathbf{e}}_1}$$

And in second order settings

$$\frac{}{\mathrm{Prop}\mathbf{typ}{\mathbf{e}}_2}\frac{\mathrm{X}\mathbf{typ}{\mathbf{e}}_1}{\mathrm{X}\mathbf{typ}{\mathbf{e}}_2}\frac{{\tau }_1\mathbf{typ}{\mathbf{e}}_1{\tau }_2\mathbf{typ}{\mathbf{e}}_2}{{\tau }_1\to {\tau }_2\mathbf{typ}{\mathbf{e}}_2}$$

The Signature ($\Xi$) and Context ($\Gamma$)

To write typing judgments, we need a context which we factor into:

• $\Xi$: A global signature of constants, which includes function symbols, relation symbols, and logical connectives.
• $\Gamma$: A local context mapping variables to their types (e.g., $x:\mathrm{U},P:\mathrm{U}\to \mathrm{Prop}$).

Because we are currying, logical connectives and quantifiers are just constants in $\Xi$ with specific type signatures:

• Connectives:
  • $\neg :\mathrm{Prop}\to \mathrm{Prop}$
  • $\wedge ,\vee ,\to :\mathrm{Prop}\to \mathrm{Prop}\to \mathrm{Prop}$
• Equality:
  • ${=}_{\tau }:\tau \to \tau \to \mathrm{Prop}$ (Polymorphic equality for any type $\tau$)
• Quantifiers:
  • ${\forall }_{\tau },{\exists }_{\tau }:(\tau \to \mathrm{Prop})\to \mathrm{Prop}$

Terms

Variables and Constants:

$$\frac{(x:\tau )\in \Gamma }{\Gamma ⊢x:\tau }\text{ (Var)}\frac{(c:\tau )\in \Xi }{\Gamma ⊢c:\tau }\text{ (Const)}$$

Application: Instead of a function taking a list of terms $f(\bar{t})$, it takes one term at a time.

$$\frac{\Gamma ⊢t_1:{\tau }_1\to {\tau }_2\Gamma ⊢t_2:{\tau }_1}{\Gamma ⊢t_1{t}_2:{\tau }_2}\text{ (App)}$$

How this works for relations: If $R:\mathrm{U}\to \mathrm{U}\to \mathrm{Prop}$, applying $R$ to $x:\mathrm{U}$ gives $(Rx):\mathrm{U}\to \mathrm{Prop}$. Applying that to $y:\mathrm{U}$ gives $(Rxy):\mathrm{Prop}$. This is an atomic formula!

Abstraction: To bind variables, we need use the higher-order abstract syntax approach and turn all variable bindings into a lambda abstraction.

$$\frac{\Gamma ,x:{\tau }_1⊢t:{\tau }_2}{\Gamma ⊢\lambda x:{\tau }_1.t:{\tau }_1\to {\tau }_2}\text{ (Abs)}$$

Syntactic Sugar

Traditional syntax can be seen as “syntactic sugar” over these curried applications:

• $x=y$ is sugar for $({=}_{\tau }xy)$
• $\varphi \wedge \psi$ is sugar for $(\wedge \varphi \psi )$
• $\forall x.\varphi$ is sugar for ${\forall }_{\tau }(\lambda x.\varphi )$

By framing $\forall$ as a function that takes a predicate (a function from $\tau \to \mathrm{Prop}$) and returns a $\mathrm{Prop}$, you completely eliminate the need for special binding rules for quantifiers—the lambda abstraction handles all the binding mechanically.

**

Would you like me to show you how standard logical deduction rules (like Modus Ponens or Universal Instantiation) are formalized using this same curried syntax?