Post History

60%

+1 −0

Q&A Compactness of the Propositional Calculus

1 answer · posted 4d ago by kouty ‭ · last activity 14h ago by kouty ‭

Question logic

#10: Post edited by $user avatar$ kouty ‭ · 2024-12-17T21:32:27Z (about 21 hours ago)

Copy Link

Raw

Markdown

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$, the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the Truth Value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.~~
---

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$.[^3] 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 a common model for every subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$,and the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the Truth Value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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 \land P_2, P_2 \land 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 formula that is false under 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.
---

#9: Post edited by $user avatar$ kouty ‭ · 2024-12-16T04:32:21Z (3 days ago)

Copy Link

Raw

Markdown

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$, the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that holds the Truth Value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$, the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the Truth Value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

#8: Post edited by $user avatar$ kouty ‭ · 2024-12-15T19:37:53Z (3 days ago)

Copy Link

Raw

Markdown

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$, the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that holds the Truth Value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

#7: Post edited by $user avatar$ kouty ‭ · 2024-12-15T18:06:12Z (3 days ago)

Copy Link

Raw

Markdown

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$.[^3] 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 everysubset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

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$.[^3] 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 subset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

#6: Post edited by $user avatar$ kouty ‭ · 2024-12-15T18:03:58Z (3 days ago)

Copy Link

Raw

Markdown

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$.[^3] 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

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$.[^3] 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 everysubset 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

#5: Post edited by $user avatar$ kouty ‭ · 2024-12-15T12:48:30Z (3 days ago)
typo

Copy Link

Raw

Markdown

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

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$.[^3] 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$.
[^3]: Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1), the set $\Gamma\ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the truth value 0 because of as a consequence of the value of $i(P_1)$.
So for a good model, we decide to attribute the value 1 to $i(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.
---

#4: Post edited by $user avatar$ kouty ‭ · 2024-12-15T03:58:02Z (4 days ago)
typo

Copy Link

Raw

Markdown

~~Completeness of the Propositional Calculus~~

Compactness of the Propositional Calculus

#3: Post edited by $user avatar$ Derek Elkins‭ · 2024-12-15T03:55:15Z (4 days ago)
TeXify. Remove set-theory tag. Change footnotes into real footnotes, which may not be an improvement. Break the text into paragraphs, though it can probably be done better or more in line with the original source.

Copy Link

Raw

Markdown

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

#2: Post edited by $user avatar$ kouty ‭ · 2024-12-14T17:29:02Z (4 days ago)

Copy Link

Raw

Markdown

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?~~
//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) 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.

#1: Initial revision by $user avatar$ kouty ‭ · 2024-12-14T17:07:30Z (4 days ago)

Copy Link

Raw

Markdown

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?

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

set-theory logic

Communities

Post History