Theory (First-Order Logic)

first-order-logic

Definition

Theory (First-Order Logic)

A theory is a set of sentences.

Models and Consequences

Definition

Models of a Theory (First-Order Logic)

For a theory $\Gamma$:

$$\mathrm{Mod}(\Gamma )=\{\mathcal{M}\mid \mathcal{M}\models \Gamma \}$$

Here $\mathcal{M}$ ranges over structures. $\mathrm{Mod}(\Gamma )$ collects every structure that satisfies all sentences in $\Gamma$.

Link to original

Definition

Consequences of a Theory (First-Order Logic)

For a theory $\Gamma$:

$$\mathrm{Cons}(\Gamma )=\{\phi \mid \Gamma \models \phi \}$$

Here $\phi$ ranges over sentences. $\mathrm{Cons}(\Gamma )$ collects every sentence entailed by $\Gamma$.

Link to original

Monotonicity

Adding sentences shrinks the set of models and grows the set of consequences:

$$\mathrm{Mod}(\Gamma \cup \{\phi \})\subseteq \mathrm{Mod}(\Gamma ),\mathrm{Cons}(\Gamma )\subseteq \mathrm{Cons}(\Gamma \cup \{\phi \})$$

Equivalently: if $\Gamma \models \phi$ then ${\Gamma }^{\prime }\models \phi$ for every ${\Gamma }^{\prime }\supseteq \Gamma$.

Entailment

Definition

Theory Entailment (First-Order Logic)

A theory $\Gamma$ entails a sentence $\phi$, written $\Gamma \models \phi$, if for every structure $\mathcal{M}$:

$$\mathcal{M}\models \Gamma ⟹\mathcal{M}\models \phi$$

where $\mathcal{M}\models \Gamma$ means $\mathcal{M}\models \psi$ for all $\psi \in \Gamma$.

Link to original