Franklin's Notes

Model Theory for Sentential Logic

The formal language of sentential logic contains the following symbols:

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:

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:



back to home page