DiscMat assignment 12

exercise

12.5 Statements about Formulas

1）

$$\exists x(F\vee G)\equiv (\exists xF\vee \exists xG)$$

We prove the statement by showing that every model $\mathcal{A}$ for $\exists x(F\vee G)$ is also a model for $(\exists xF\vee \exists xG)$ and vice versa.

We first prove $\exists x(F\vee G)\models (\exists xF\vee \exists xG)$ Let $\mathcal{A}$ be a model such that $\mathcal{A}(\exists x(F\vee G))=1$ $⟹$ ${\mathcal{A}}_{[x\to u]}(F\vee G)=1$ for some $u$ in $U$ (semantics of $\exists$) $⟹$ ${\mathcal{A}}_{[x\to u]}(F)=1$ or ${\mathcal{A}}_{[x\to u]}(G)=1$ (semantics of $\vee$) Case Distinction:

• Case 1: $A_{[x\to u]}(F)=1$
  • $⟹\mathcal{A}(\exists xF)=1$ (semantics of $\exists$)
  • $⟹\mathcal{A}(\exists xF\vee \exists xG)=1$ (semantics of $\vee$)
• Case 2: $A_{[x\to u]}(G)=1$
  • $⟹\mathcal{A}(\exists xG)=1$ (semantics of $\exists$)
  • $⟹\mathcal{A}(\exists xF\vee \exists xG)=1$ (semantics of $\vee$)

$⟹\mathcal{A}(\exists xF\vee \exists xG)=1$ $⟹\exists x(F\vee G)\models (\exists xF\vee \exists xG)$

We then prove that $(\exists xF\vee \exists xG)\models \exists x(F\vee G)$ Let $\mathcal{A}$ be a model such that $\mathcal{A}(\exists xF\vee \exists xG)=1$ $⟹$ $\mathcal{A}(\exists x(F))=1$ or $\mathcal{A}(\exists x(G))=1$ (semantics of $\vee$) $⟹$ ${\mathcal{A}}_{[x\to u]}(F)=1$ for some $u$ in $U$ or ${\mathcal{A}}_{[x\to u]}(G)=1$ for some $u$ in $U$ (semantics of $\exists$) Case Distinction:

• Case 1: ${\mathcal{A}}_{[x\to u]}(F)=1$ for some $u$ in $U$
  • $⟹{\mathcal{A}}_{[x\to u]}(F\vee G)=1$ for some $u$ in $U$ (semantics of $\vee$)
  • $⟹\exists x(F\vee G)$ (semantics of $\exists$)
• Case 2: $A_{[x\to u]}(G)=1$ for some $u$ in $U$
  • $⟹{\mathcal{A}}_{[x\to u]}(F\vee G)=1$ for some $u$ in $U$ (semantics of $\vee$)
  • $⟹\exists x(F\vee G)$ (semantics of $\exists$)

$⟹\mathcal{A}(\exists x(F\vee G))=1$ $⟹(\exists xF\vee \exists xG)\models \exists x(F\vee G)$ $⟹(\exists xF\vee \exists xG)\equiv \exists x(F\vee G)$ (together with the other direction) The statement is proved

2）

$$\exists x\exists yF\equiv \exists y\exists xF$$

We prove the statement by showing that every model $\mathcal{A}$ for $\exists x\exists yF$ is also a model for $\exists y\exists xF$ and vice versa.

Let $\mathcal{A}$ be a model such that $\mathcal{A}(\exists x\exists yF)=1$ $⟺{\mathcal{A}}_{[x\to u]}(\exists yF)=1$ for some $u$ in $U$ (semantics of $\exists$) $⟺{\mathcal{A}}_{[x\to u][y\to v]}(F)=1$ for some $u$ in $U$ and for some $v$ in $U$ (semantics of $\exists$) $⟺{\mathcal{A}}_{[y\to v][x\to u]}(F)=1$ (updating different variables commutes) $⟺{\mathcal{A}}_{[y\to v]}(\exists xF)=1$ (semantics of $\exists$) $⟺\mathcal{A}(\exists y\exists xF)=1$ (semantics of $\exists$) $⟹\exists x\exists yF\equiv \exists y\exists xF$ (The proof for the other direction is analogous if we exchange $x$ and $y$)

3）

$\forall x\exists yF\equiv \exists y\forall xF$

We disprove this statement by providing a counterexample let $U=\mathbb{N}$ let $F\stackrel{def}{=}P(x,y)$ let $P(x,y)=1\stackrel{def}{⟺}x=y$ (interpreted as equality)

The statement can be rewritten as $\forall x\exists y(x=y)\equiv \exists y\forall x(x=y)$ We first consider the left side. For any given $x$, we can choose $y=x$, then $x=y$ is true. Therefore, the left side is evaluated to true. However, on the right side, if such a $y$ existed, then we would have $0=y$ and $1=y$, hence $1=0$, contradiction. Thus there is a model $\mathcal{A}$ such that $\mathcal{A}(\forall x\exists yF)=1$ and $\mathcal{A}(\exists y\forall xF)=0$, which breaks the logical equivalence.

Hence, the statement is disproved.