# Prove this claim about language and structures.

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\})$$

1. I do not know how to parse this

$$\models \psi \Leftrightarrow sentence$$

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

• $\mathcal P( \{ 1,\ldots,n \})$ is the power-set of $\{ 1,\ldots,n \}$, i.e. the set of all subset of $\{ 1,\ldots,n \}$. Thus, $S \subset \{ 1,\ldots,n \}$ is a a set of subset of ... and $X \in S$ is a subset of ... Jan 19, 2015 at 14:48
• $\vDash \psi \Leftrightarrow sentence$ means that the two formulae $\psi$ and $sentence$ are logically equivalent. Jan 19, 2015 at 14:49

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

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

• So is it correct to say that the "sentence" on the RHS is enumerating all possible disjunctive normal forms? Additionally I am a bit unclear about the 2nd paragraph you wrote, is is necessary here that all possible $\psi$'s has to evaluate to TRUE? Jan 19, 2015 at 15:19
• @chibro2 - $\psi$ is a single formula, built-up from the $\phi_i$. I'll try with an example... Jan 19, 2015 at 15:23
• Oh I apologize, I did not keep in mind that the sentence on the RHS is for one $S \subseteq \mathcal{P}(1,\ldots,n)$. But I am still confused about the necessary "truthiness" of $\psi$. Jan 19, 2015 at 15:32
• @chibro2 - please, see the example; we have some rows where $\psi$ is evaluated to $T$, according to the boolean combination and the rules for the connectives. We have to choose only those rows... Jan 19, 2015 at 15:41
• Very nice answer, @Mauro. (+1, of course.) Jan 19, 2015 at 16:58