# Verification of Lindenbaum's Lemma proof for the Mendelson system and a question of maximally consistent sets.

In this proof I will use Mendelson's axiom system (the one in this book).

Question 1: Could someone check my work? I feel some parts are a bit hard to see/read, but I think the general idea works.

Theorem.

Every consistent set $\Gamma$ is contained in a maximally consistent set $\Delta$.

Proof

Let $\text{Form}=\{e_i:i\in \Bbb N\}$.

Let\begin{alignat*}{3} \Delta_0&=\Gamma\\ \Delta_{n+1}&= \begin{cases} \Delta_n\cup\{e_n\},&\text{If $\Delta_n\cup\{e_n\}$ is consistent.}\\ \Delta_n, & \text{Else.} \end{cases} \end{alignat*} Let $\Delta=\bigcup_i\Delta_i$.

It's obvious that $\Gamma\subseteq \Delta$. It's also obvious, by induction on $i$, that all the $\Delta_i$ are consistent.

Now, suppose $\Delta$ is not consistent. Then, there exists a $\gamma\in\text{Form}$ such that $\Delta\vdash \gamma$ and $\Delta\vdash\neg \gamma$. Let $\alpha_1,\alpha_2,...,\alpha_k=\gamma$, $\beta_1,\beta_2,...,\beta_s=\neg\gamma$ be proofs of $\gamma$ and $\neg \gamma$ from $\Delta$.

Now, in this proofs there are at most $k+s$ formulas of $\Delta$ appearing as hypothesis'. We define $S$ to be the set of all these formulas. We have that $|S|\le k+s$, so $S$ is finite.

Let $M:=\max\{i:e_i\in S\}$. By the construction of the $\Delta_i$, we see that $S\subset \Delta_M$ and the proofs above are also proofs from $\Delta_M$, so it is inconsistent, this is a contradiction.

Now, let $\varphi$ be a formula that's not in $\Delta$, we want to show that $\Delta\cup\{\varphi\}$ is inconsistent. Suppose it's consistent.

By the enumeration of the formulas, we have that $\varphi=e_n$ for some $n$. Also, as $\Delta=\bigcup_i \Delta_i$, we have that $e_n\not \in \Delta_i$ for all $i$. In particular, it was not added to $\Delta_{n+1}$, and this must've been because $\Delta_n\cup\{e_n\}$ was inconsistent, but as $\Delta_n\cup\{e_n\}\subseteq\Delta\cup\{e_n\}$, we have that this last one is inconsistent. This completes the proof.

Question 2: Let $\Gamma$ is a maximally consistent set. I want to show that if $$f:\text{Var}\to\{0,1\}\\ f(p)=\begin{cases} 0, & \text{If p\not\in\Gamma.}\\ 1, & \text{Else.} \end{cases}$$ And $v$ is the unique valuation extending $f$, then $v$ satisfies $\Gamma$, but I couldn't prove it with this particular system, could someone help me with this?

• Looks fine to me, and no wasted words. Commented Jan 24, 2016 at 2:08

For Question 2.

We have to note that if $Γ$ is maximally consistent, then $Γ$ is closed under derivability, i.e. if $Γ \vdash \varphi$, then $\varphi \in Γ$.

Proof Let $Γ \vdash \varphi$ and suppose $\varphi \notin Γ$. Then $Γ ∪ \{ \varphi \}$ must be inconsistent (by maximality). Hence [here you can find the proof for Mendelson's system] : $Γ \vdash ¬ \varphi$, so $Γ$ is inconsistent; contradiction.

The proof that the said $v$ satisfy $\Gamma$ is by induction.

i) for $\varphi$ atomic, the claim holds by definition of $v$.

ii) for $\varphi := \lnot \psi$, if $\varphi \in \Gamma$, then by consistency: $\psi \notin \Gamma$.

Thus $v(\psi)=0$ by induction hypothesis, so that $v(\varphi)=1$.

If $\varphi \notin \Gamma$, then by maximality: $\lnot \varphi \in \Gamma$ and thus, by double negation [see Mendelson, Lemma 1.11(a), page 29] : $\psi \in \Gamma$.

Then $v(\psi)=1$, by induction hypotheses, and thus $v(\varphi)=0$.

iii) for $\varphi := \psi \to \tau \in \Gamma$, assume that $v(\psi \to \tau)=0$, i.e. $v(\psi)=1$ and $v(\tau)=0$.

Then $\psi \in \Gamma$ and $\tau \notin \Gamma$, by induction hypotheses, so that $\Gamma \vdash \varphi$ and $\Gamma \vdash \lnot \tau$. But from $\psi \to \tau \in \Gamma$ and $\Gamma \vdash \psi$, it follows that $\Gamma \vdash \tau$, by modus ponens, and the consistency of $\Gamma$ is contradicted. Hence $v(\psi \to \tau)=1$.

If $\varphi := \psi \to \tau \notin \Gamma$, then $v(\psi \to \tau)=0$.

Assume not, i.e. $v(\psi \to \tau)=1$, i.e. either $v(\psi)=0$ or $v(\tau)=1$. By induction hypotheses, this means: either $\psi \notin \Gamma$ or $\tau \in \Gamma$.

If $\psi \notin \Gamma$, then $\Gamma \vdash \lnot \psi$ and from $\vdash \lnot \psi \to (\lnot \tau \to \lnot \psi)$ we have $\Gamma \vdash \lnot \tau \to \lnot \psi$.

But $\vdash (\lnot \tau \to \lnot \psi) \to (\psi \to \tau)$ [see Mendelson, Ex.1.47(d), page 28], and thus : $\Gamma \vdash \psi \to \tau$.

If $\tau \in \Gamma$, then from $\vdash \tau \to (\psi \to \tau)$ we have $\Gamma \vdash \psi \to \tau$.

In both cases : $\Gamma \vdash \psi \to \tau$, contradicting the consistency of $\Gamma$. Hence, $v(\psi \to \tau)=0$.

Thus, we have concluded the proof by induction that :

$v(\varphi)=$ iff $\varphi \in \Gamma$.

• Hmm, I'm having a bit of trouble following you, is your inductive hypothesis "if $\alpha$ is a formula with complexity $n$, we have that $v(\alpha)=1$ iff $\alpha\in\Gamma$"? I'm using a language which also has $\wedge$ and $\vee$ could you sketch what to do in those cases? Commented Jan 24, 2016 at 15:49
• @YoTengoUnLCD - yes, induction is on the complexity of the formula, i.e. on the number of connectives. Thus, the base step is with atomic formulae (i.e. propositional letters) and the induction step must be performed for each conncetive of the language : in Mendelson's system only $\lnot$ and $\to$ are primitive: thus, these two sub-cases are enough. Commented Jan 24, 2016 at 16:03