Franklin's Notes

Model Theory for Sentential Logic

The formal language of sentential logic contains the following symbols:

• logical connectives $\land$ and $\neg$

• parentheses $($, $)$

• sentence symbols from a nonempty set $\mathscr{S}$

Sentences are defined recursively via the following rules, which can be used to "build up" more and more complex sentences:

1. Every sentence symbol $S\in\mathscr{S}$ is a sentence
2. If $\varphi$ is a sentence then $(\neg\varphi)$ is a sentence
3. If $\varphi$ and $\psi$ are sentences, then so is $(\varphi\land\psi)$
4. A finite sequence of symbols is a sentence if and only if it can be obtained by applying rules $(1),(2),(3)$ finitely many times

We can prove things about sentences in general by applying induction to this recursive definition, although we will sometimes "bend the rules" by using certain notational conventions for the sake of brevity.

Exercise 1. If $S$ is a symbol in a formal language, let $\kappa[S]$ denote the number of times that symbol appears in a specified sentence. Prove that, in any particular sentence,
- $\kappa[~(~]=\kappa[~)~]$
- $\kappa[\neg]+\kappa[\land]=\kappa[~(~]$
- $\sum_{S\in\mathscr{S}}\kappa[S] = \kappa[\land]+1$

All of this is just a matter of syntax . A model for $\mathscr{S}$, denoted $A$, is just a subset of $\mathscr{S}$. It can be thought of as the set of true statements in some "possible world" which is described by the language $\mathscr{S}$. We express the idea that $\varphi$ is true in a model $A$ by writing $A\vDash \varphi$. (Synonymously, we may say that $\varphi$ holds in $A$, or $A$ is a model of $\varphi$, or if this is not the case, we say that $\varphi$ fails in $A$ or $\varphi$ is false in $A$.) This notion is defined recursively by the following properties:

• If $\varphi$ is a sentence symbol, then $A\vDash\varphi$ if and only if $\varphi\in A$

• If $\varphi$ is $\psi\land\theta$, then $A\vDash\varphi$ if and only if both $A\vDash\psi$ and $A\vDash\theta$

• If $\varphi$ is $\neg\psi$, then $A\vDash\varphi$ if and only if it is not the case that $A\vDash\psi$
Since every sentence is only finitely long, we can show inductively that this is an unambiguous definition.

A sentence $\varphi$ is called valid if it holds in all models of $\mathscr{S}$. At first, it may seem that it is impossible to verify whether a sentence is valid if $\mathscr{S}$ is infinite, because doing so would require "checking" whether it holds in infinitely many models $A$. However, there is always a way of checking whether $\varphi$ is valid in finitely many steps, based on the syntactical notion of a tautology: if $S_1,...,S_n$ are all of the symbols occurring in $\varphi$, we only need to check the $2^n$ possible combindations of true-false assignments for these symbols. If $\varphi$ is a tautology, then we write $\vdash \varphi$.

Where to go from here:

• Possible sets of all models addresses the converse question "if to every set of sentences $\Sigma$ there corresponds a set of possible worlds $K$ in which those sentences are satisfied, is it true that every set of models $K$ is precisely the set of possible worlds satisfying some set of sentences $\Sigma$?" (The answer is no - but why?)

• Model Theory for First-order Logic takes the complexity up a notch by constructing formal languages with function symbols, relation symbols, and quantification.