LEC LOG 1

First order logic

Denote by $S$ the underlying set which is the universe of discourse. Let $L=(R,F,C)$ be a context free language (look this up), where $R$ is the set of relational symbols defined on $S$, $F$ is the set of functional symbols (not functions, mind you) defined on $S$, and $C$ is the set of constant symbols. We also have access to variables (we do not include them in the definition of $L$ because we can use the same variables for all $L$).

Terms evaluate to elements in $S$.

$$\text{term}:=c|x|f(t_1,\dots ,t_n),$$

where $c\in C$, $x$ is a variable, and $f\in F$, and $t_1,\dots ,t_n\in T$.

Formulas are defined by the BNF

$$\text{formula}:=r(t_1,\dots ,t_n)|t_1\equiv t_2|⌐\phi |\phi \vee \psi |\exists x\phi .$$

$\wedge$, $⟹$, and $\forall$ can defined in terms of $\vee$ and $⌐$.

---

An $L$-structure $\mathcal{M}$ consists of

1. $S^{\mathcal{M}}$: the universe of discourse
2. $r^{\mathcal{M}}$, $f^{\mathcal{M}}$, $c^{\mathcal{M}}$. These actually assign concrete relations, functions and elements of $S$ to symbols in $R$, $F$, and $C$.

Variable valuations $\sigma :\text{Var}\to S^{\mathcal{M}}$ (not part of the model itself)

$I=(\mathcal{M},\sigma )$, $x^I=\sigma (x)$, $c^I=c^{\mathcal{M}}$, $f(t_1,\dots ,t_n{)}^I=f^{\mathcal{M}}(t_1^I,t_2^I,\dots ,t_n^I)$.

$$\begin{array}{rl}& I⊫r(t_1,\dots ,t_n)\text{ if }{r}^{\mathcal{M}}(t_1^{\mathcal{M}},\dots ,t_n^{\mathcal{M}}).\\ & I⊫t_1\underset{\text{syntactic, just a symbol }}{\underbrace{\equiv }}{t}_2\text{ if }{t}_1^I\underset{\text{semantic, means what = usually means}}{\underbrace{=}}{t}_2^I\\ & I⊫\neg \phi \text{ if }I⊯\phi \\ & I⊫{\phi }_1\vee {\phi }_2\text{ if }I⊫{\phi }_1\text{ or }I⊫{\phi }_2\\ & I⊫\exists x\phi \text{ if there exists }x\in S\text{ such that }(\mathcal{M},\sigma [x\mapsto s])⊫\phi .\end{array}$$

Free variables are defined analogously to Definition 66.2.

Definition 227.1(Definition).

1. $\text{free}(c)=\varnothing$.
2. $\text{free}(x)=\{x\}$.
3. $\text{free}(f(t_1,\dots ,t_n))={\bigcup }_{i=1}^n\text{free}(t_i)$.
4. $\text{free}(r(t_1,\dots ,t_n))={\bigcup }_{i=1}^n\text{free}(t_i)$.
5. $\text{free}(⌐\phi )=\text{free}(\phi )$.
6. $\text{free}({\phi }_1\vee {\phi }_2)=\text{free}({\phi }_1)\cup \text{free}({\phi }_2)$.
7. $\text{free}(\exists x\phi )=\text{free}(\phi )\setminus \{x\}$.

Lemma 227.2(Lemma).

If two valuations $\sigma ,{\sigma }^{\prime }$ agree on $\text{free}(\phi )$, then $(\mathcal{M},\sigma )⊫\phi ⟺(\mathcal{M},{\sigma }^{\prime })⊫\phi$.

If $\phi$ doesn’t have any free variables, it is called a sentence. If $\phi$ is a sentence, then $[\phi ]$ denotes the partition of the collection of all models into the ones which satisfy $\phi$ and the ones that don’t (the valuation doesn’t matter here, since $\phi$ doesn’t have any free variables).

If $\phi$ has one free variable $x$ (denoted by $\phi (x)$), then for a given model $\mathcal{M}$, $[\phi (x)]$ defines a partition of $S$ into elements which satisfy $\phi (x)$ and ones that do not. For example, $\phi (x)=\exists yE(x,y)$ defines the set of non-isolated vertices on a graph (thus, this set is said to be FO-definable). As an other example, star graphs are FO-definable: