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

Question

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?

Answer 1

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$.