Franklin's Notes

Axiomatization in Sentential Logic

A set of sentences $\Delta$ is said to be a set of axioms for a theory $\Gamma$ if and only if $\Delta$ and $\Gamma$ have exactly the same consequences - that is, if $\Delta\vdash\Gamma$ and $\Gamma\vdash\Delta$. Further, a theory $\Gamma$ is called finitely axiomatizable if it has a finite set of axioms.

Proposition 1. $\Delta$ is a set of axioms for $\Gamma$ if and only if they are satisfied by exactly the same models (i.e. if $\Delta\vDash\Gamma$ and $\Gamma\vDash\Delta$).

Proposition 2. If $\Gamma_1$ and $\Gamma_2$ are two theories such that the set of models of $\Gamma_1$ is the complement of the set of models of $\Gamma_2$. Then both $\Gamma_1$ and $\Gamma_2$ are finitely axiomatizable.

Proof. $\Gamma_1\cup\Gamma_2$ is not satisfiable, so it is not finitely satisfiable, and there exist finite sets $\Delta_1\subset\Gamma_1$ and $\Delta_2\subset\Gamma_2$ such that $\Delta_1\cup\Delta_2$ is not satisfiable. Then $\Delta_1$ is a finite set of axioms for $\Gamma_1$ (if $A\vDash \Delta_1$, then $A$ does not satisfy $\Delta_2$ and is not a model of $\Gamma_2$, meaning that it must be a model of $\Gamma_1$), and $\Delta_2$ is a finite set of axioms for $\Gamma_2$ (by similar reasoning). $\blacksquare$

A set of axioms $\Delta$ is said to be independent if $\delta$ is not a consequence of $\Delta\backslash{\delta}$ for any $\delta\in\Delta$. We may readily prove that any theory has an independent set of axioms, under the constraint that $\mathscr{S}$ be a countable set:

Theorem 1. If $\mathscr{S}$ is countable, then every theory $\Gamma$ in $\mathscr{S}$ has a set of independent axioms $\Delta$.

Proof. First of all, if $\Gamma$ is finitely axiomatizable, the claim is trivial, for we may simply let $\Delta$ be a set consisting of a single statement which is the conjunction of the axioms in some finite set of axioms for $\Gamma$. So let's just consider the case in which $\Gamma$ is not finitely axiomatizable.

The models of $\Gamma$ are precisely the models which satisfy each of its finite subsets. Further, every finite subset of $\Gamma$ is equivalent to a sentence $\varphi$ which is given by the conjunction of the statements in that subset. Since $\mathscr{S}$ is countable, the set of sentences over $\mathscr{S}$ is countable, and so $\Gamma$ must be countable, so we may form a sequence of sentences which are in one-to-one correspondence with (and respectively equivalent to) the finite subsets of $\Gamma$:

Construct a subsequence of the $(\varphi_i)$ as follows. Let $n_0$ be the smallest natural number such that $\varphi_{n_0}$ is not a tautology, and $n_{k+1}$ be the smallest natural number such that which is always possible because $\Gamma$ is not finitely axiomatizable. Now let the set $\Delta$ consist of the following axioms:
1. $\varphi_{n_0}$
2. $\varphi_{n_0}\implies\varphi_{n_1}$
3. $(\varphi_{n_0}\land\varphi_{n_1})\implies\varphi_{n_2}$
4. $(\varphi_{n_0}\land\varphi_{n_1}\land\varphi_{n_2})\implies\varphi_{n_3}$
5. $\cdots$
Clearly this is a set of axioms for $\Gamma$: by induction, it is always possible to derive $\varphi_{n_k}$ for all natural numbers $k$, from which all $\varphi_i$ with $i\leq k$ are deducible, meaning that $\Delta$ axiomatizes all finite subsets of $\Gamma$, and hence axiomatizes $\Gamma$. To see why this is independent, recall that the $n_k$ were chosen such that $\varphi_{n_{k+1}}$ is never a consequence of $\varphi_{n_0}\land...\land\varphi_{n_k}$, meaning that, for each $k$, there exists a model $A_k$ in which $\varphi_{n_0}\land...\land\varphi_{n_k}$ holds but $\varphi_{n_{k+1}}$ does not hold. In this model, the axioms $(1)$ through $(k+1)$ hold (because $\varphi_{n_i}$ holds for $i\leq k$), and the axioms following $(k+2)$ hold (because $\varphi_{n_{k+1}}$ fails, meaning that $\varphi_{n_0}\land...\land\varphi_{n_{k+1}}\land...\land\varphi_{n_l}$ fails, making the implication is vacuously true), but the axiom $(k+2)$ does not hold.

It happens that any theory in general has an independent set of axioms:

Theorem 2. Every theory $\Gamma$ in $\mathscr{S}$ has a set of independent axioms $\Delta$.

I still haven't figured out how to prove this yet. According to Chang and Kiesler, the case when $\mathscr{S}$ is countable is quite a bit easier than the general case, which is listed as a very difficult exercise. Apparently, this is proven by Reznikoff, but I haven't worked through the proof. I'm optimistic about the possibility of using some sort of creatively-defined topology to make this proof easier...





back to home page