Prove this claim about language and structures.

Question

I have a very thin background in logic and I am attempting the first problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below:

Suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean combination of $\phi_1,\ldots,\phi_n$. Then there is $S \subseteq \mathcal{P}(\{1,\ldots,n\})$ such that

$$\models \psi \Leftrightarrow \bigvee_{X \in S} \left(\bigwedge_{i \in X} \phi_i \wedge \bigwedge_{i \notin X} \neg \phi_i \right)$$

My issues are:

1. I do not understand how to parse what $\mathcal{P}$ is in this context:

$$S \subseteq \mathcal{P}(\{1,\ldots,n\})$$

2. I do not know how to parse this

$$\models \psi \Leftrightarrow sentence$$

3. Finally, could someone provide a proof of this problem?

Note, this is not assigned as homework. I am doing this to "catch up" to the rest of the class.

Answer 1

Basically, we can base a proof of this fact building a truth-table for $\psi$ in terms of the sub-formulae : $\phi_1, \ldots, \phi_n$.

We have to pick-up the rows of the t-t for which $\psi$ is evaluated to $TRUE$ and then write a "long" conjunction with $\phi_i$ : if in that row it has the value $TRUE$, and $\lnot \phi_i$ : if in that row it has the value $FALSE$.

This account for :

$$\left(\bigwedge_{i \in X} \phi_i \wedge \bigwedge_{i \notin X} \neg \phi_i \right).$$

Each row corresponding to $TRUE$ under $\psi$ account for one of the "long" concjunctions above and we have to build a "long" disjunction with all them.

This account for :

$$\bigvee_{X \in S}$$

---

See Disjunctive normal form.

---

Examples

1) Consider $\psi := \lnot (\phi_1 \rightarrow \lnot \phi_2)$ and build-up the t-t :

\begin{array}{cc|cc|c}\phi_1&\phi_2&\lnot \phi_2&\phi_1 \to \lnot \phi_2&\psi\\\hline T&T&F&F&T\\T&F&T&T&F\\F&T&F&T&F\\F&F&T&T&F\end{array}

You can see that :

$\psi \Leftrightarrow (\phi_1 \land \phi_2)$.

In this trivial case we have : $n=2$ and thus $\mathcal P( \{1,2 \}) = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \}$.

$X= \{ 1, 2 \}$ is the only element of $S$, because we have only one row of the t-t evaluated to $TRUE$.

Thus, the only "long" concjunction is made with all the sub-formulae which in that row are evaluated to $TRUE$.

2) Consider insted $\psi := \phi_1 \rightarrow \lnot \phi_2$; now we have that $\psi$ is evaluated to $TRUE$ in three rows of the above t-t.

Thus we have :

$\psi \Leftrightarrow [(\phi_1 \land \lnot \phi_2) \lor (\lnot \phi_1 \land \phi_2) \lor (\lnot \phi_1 \land \lnot \phi_2)]$.

In this case we have that $S$ has three elements (we have three $Xs$) : $S = \{ \{ 1 \}, \{ 2 \}, \emptyset \}$.

---

You can try a slightly more complex case, with a boolean combination of $\phi_1, \phi_2, \phi_3$.