Review Suggested Edit

You can't approve or reject suggested edits because you haven't yet earned the Edit Posts ability.

Completeness of the Propositional Calculus

~~Here is the theorem and its proof from Mathematical and Philosophical Logic from Harrie de Swart (p.35) some signs have been changed for clarity e.g. Pn+1 became P_[n+1].~~
~~> Let Γ be a (possibly infinite) set of formulas such that every finite subset of Γ has a model//1//. Then Γ has a model.~~
~~Proof.~~
Let Γ be a (possibly infinite) set of formulas such that every finite subset of Γ has a model. We will define an interpretation i of the atomic propositional formulas P₁, P₂, P₃, ... such that for every natural number n, Φ(n), where
Φ(n) := every finite subset of Γ has a model in which P₁, P₂, ..., Pₙ take the values i(P₁), i(P₂), ..., i(Pₙ). Once having shown this, it follows that i(A) = 1 for every formula A in Γ. For given a formula A in Γ, take n so large that all atomic formulas occurring in A are among P₁, ..., Pₙ. Since {A} is a finite subset of Γ and because of Φ(n), A has a model in which P₁, ..., Pₙ take the values i(P₁), ..., i(Pₙ). So, i(A) = 1.
Let i(P₁) = 0 and suppose Φ(1) does not hold. That is, there is a finite subset Γ' of Γ which has no model in which P₁ takes the value i(P₁) = 0. Then we define i(P₁) = 1 //2// and show that Φ(1), i.e., every finite subset of Γ has a model in which P₁ takes the value i(P₁) = 1. For let Δ be a finite subset of Γ. Then Δ ∪ Γ' is a finite subset of Γ and hence has a model i. Since i is a model of Γ', i(P₁) = 1.
~~Suppose we have defined i(P₁), ..., i(Pₙ) such that Φ(n). Then we can extend the definition of i to Pₙ₊₁ such that Φ(n + 1). For suppose that Φ(n + 1) does~~
not hold if i(P_[n+1]) = 0. That is, there is a finite subset Γ' of Γ which has no model in which P_1, ..., P_n, P_[n+1] take the values i(P_1), ..., i(P_n), 0. Then we define i(P_[n+1]) = 1 and show that Φ(n + 1), i.e., every finite subset of Γ has a model in which P_1, ..., P_n, P_[n+1] take the values i(P_1), ..., i(P_n), 1. For let Δ be a finite subset of Γ. Then Δ ∪ Γ' is a finite subset of Γ and hence, by the induction hypothesis, Δ ∪ Γ' has a model in which P_1, ..., P_n take the values i(P_1), ..., i(P_n). Since i is a model of Γ', i(P_[n+1]) = 1.
//1//: I understand the we have the same model for every Right? An interpretation corresponds to one line in the (possibly infinite) truth table of the atomic variables P1, ... , Pn...
//2// I don't understand what is this new remastered definition. If i (P1) = 0, that is, the true value of P1 is 'False', how can I change this? And if we change it from 'False' to 'True', we can destroy the model of an other formula e g. A = ~P1.
I was expecting something as this. Say we have only P1 and P2 and formulas that are true when P1 is false and P2 is true. One subset is Gamma 1 = { P1 or P2, P2 or P1}, another is Gamma 2 = {P1→P2, ~P2 →P1}, another is Gamma 3 = {~P1}. If Gamma contains a false formula according to our interpretation, such as P1, there is nothing to do, Gamma has no model, because if P1 turns to be true, then Gamma3 has no model. In other words Gamma cannot have a model if it contains two contradictory formulas.
~~I tried to read the theorem and its proof elsewhere. It seems straightforward but I miss something.~~

Here is the theorem and its proof from Mathematical and Philosophical Logic from Harrie de Swart (p.35).
> Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model[^1]. Then $\Gamma$ has a model.
>
> **Proof**:
>
> Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model. We will define an interpretation $i$ of the atomic propositional formulas $P_1, P_2, P_3, \dots$ such that for every natural number $n$, $\phi(n)$, where
$\phi(n)$ := "every finite subset of $\Gamma$ has a model in which $P_1, P_2, \dots, P_n$ take the values $i(P_1), i(P_2), \dots, i(P_n)$". Once having shown this, it follows that $i(A) = 1$ for every formula $A$ in $\Gamma$. For given a formula $A$ in $\Gamma$, take $n$ so large that all atomic formulas occurring in $A$ are among $P_1, \dots, P_n$. Since $\{A\}$ is a finite subset of $\Gamma$ and because of $\phi(n)$, $A$ has a model in which $P_1, \dots, P_n$ take the values $i(P_1), \dots, i(P_n)$. So, $i(A) = 1$.
>
> Let $i(P_1) = 0$ and suppose $\phi(1)$ does not hold. That is, there is a finite subset $\Gamma'$ of $\Gamma$ which has no model in which $P_1$ takes the value $i(P_1) = 0$. Then we define $i(P_1) = 1$[^2] and show that $\phi(1)$, i.e., every finite subset of $\Gamma$ has a model in which $P_1$ takes the value $i(P_1) = 1$. For let $\Delta$ be a finite subset of $\Gamma$. Then $\Delta \cup \Gamma'$ is a finite subset of $\Gamma$ and hence has a model $i$. Since $i$ is a model of $\Gamma'$, $i(P_1) = 1$.
>
> Suppose we have defined $i(P_1), \dots, i(P_n)$ such that $\phi(n)$. Then we can extend the definition of $i$ to $P_{n+1}$ such that $\phi(n + 1)$. For suppose that $\phi(n + 1)$ does not hold if $i(P_{n+1}) = 0$. That is, there is a finite subset $\Gamma'$ of $\Gamma$ which has no model in which $P_1, \dots, P_n, P_{n+1}$ take the values $i(P_1), \dots, i(P_n), 0$. Then we define $i(P_{n+1}) = 1$ and show that $\phi(n + 1)$, i.e., every finite subset of $\Gamma$ has a model in which $P_1, \dots, P_n, P_{n+1}$ take the values $i(P_1), \dots, i(P_n), 1$. For let $\Delta$ be a finite subset of $\Gamma$. Then $\Delta \cup \Gamma'$ is a finite subset of $\Gamma$ and hence, by the induction hypothesis, $\Delta \cup \Gamma'$ has a model in which $P_1, \dots, P_n$ take the values $i(P_1), \dots, i(P_n)$. Since $i$ is a model of $\Gamma'$, $i(P_{n+1}) = 1$.
[^1]: I understand the we have the same model for every Right? An interpretation corresponds to one line in the (possibly infinite) truth table of the atomic variables $P_1, \dots , P_n$ ...
[^2]: I don't understand what is this new remastered definition. If $i (P_1) = 0$, that is, the true value of $P_1$ is 'False', how can I change this? And if we change it from 'False' to 'True', we can destroy the model of an other formula e g. $A = \lnot P_1$.
I was expecting something as this. Say we have only $P_1$ and $P_2$ and formulas that are true when $P_1$ is false and $P_2$ is true. One subset is $\Gamma_1 = \{ P_1 \lor P_2, P_2 \lor P_1\}$, another is $\Gamma_2 = \{P_1 \to P_2, \lnot P_2 \to P_1\}$, another is $\Gamma_3 = \{\lnot P_1\}$. If $\Gamma$ contains a false formula according to our interpretation, such as $P_1$, there is nothing to do, $\Gamma$ has no model, because if $P_1$ turns to be true, then $\Gamma_3$ has no model. In other words $\Gamma$ cannot have a model if it contains two contradictory formulas.
I tried to read the theorem and its proof elsewhere. It seems straightforward but I miss something.

set-theory logic

logic

Communities

Review Suggested Edit