W1: FOL with Identity

First-Order Logic with Identity

Syntax, Sematics, and Proof System

The majority of problems in this course proceed by induction on complexity of formulae. Note that “strong induction” is exactly the same as ordinary mathematical induction, just allowing for slightly more “natural” properties. Note also that, even though we’re taking predicates as subsets of (products of) the domain rather than as characteristic functions from the domain to $\{0,1\}$, we can still elegantly treat sentence letters as nullary predicates: we identify a nullary product $⟨⟩$ with $\varnothing$, falsity (that is, 0) with $\varnothing$, and truth (that is, 1) with $\{\varnothing \}$, such that $⟨⟩\in 1$ but $⟨⟩\notin 0$.