# Exercises #3 – Quantified Theories

These were pulled from Exercises for $\S$3 and Exercises for $\S$4 of Chapter I in Bourbaki’s set theory book.

#### Exercise 1.

Let $A$ be a relation in logical theory $\mathfrak{T}$. If $A\iff (\mbox{not } A)$ is a theorem in $\mathfrak{T}$, show that $\mathfrak{T}$ is contradictory.

#### Solution.

The negation of $A\iff (\mbox{not } A)$ is itself, so its negation must also be a theorem by hypothesis, implying $\mathfrak{T}$ is contradictory.

$\blacksquare$

#### Exercise 2.

Let $A$ and $B$ be relations in $\mathfrak{T}$, and let $x$ be a letter, distinct from the constants of $\mathfrak{T}$, which does not appear in $A$. If $B\implies A$ is a theorem in $\mathfrak{T}$, then $((\exists x)B)\implies A$ and $((\forall x)B)\implies A$ is a theorem in $\mathfrak{T}$.

#### Solution.

If $B\implies A$ is a theorem in $\mathfrak{T}$, then by $C31$,

$(\exists x) B\implies (\exists x) A$

is also a theorem in $\mathfrak{T}$. But $(\exists x) A$ is equivalent to $(\tau_X(A)|x)A$ and since $x$ does not appear in $A$, the latter is simply $A$, hence $(\exists x) A$ is equivalent to $A$. It follows that

$(\exists x) B\implies A$

Replacing $\exists$ with $\forall$ in the argument will give the proof of $((\forall x)B)\implies A$.

$\blacksquare$

#### Exercise 3.

Let $A$ and $R$ be relations in $\mathfrak{T}$, and let $x$ be a letter distinct from the constants of $\mathfrak{T}$. If $R\implies A$ is a theorem in $\mathfrak T$, then

$(\exists x) R\iff (\exists_Ax)R$

is a theorem in $\mathfrak T$. If $(\mbox{not }R\implies A$ is a theorem in $\mathfrak T$, then

$(\forall x) R\iff (\forall_Ax)R$

is a theorem in $\mathfrak T$. If $A$ is a theorem in $\mathfrak T$, then

$(\exists x) R\iff (\exists_Ax)R$ and $(\forall x) R\iff (\forall_Ax)$

are theorem in $\mathfrak T$.

#### Solution.

By I.C21, $(A\mbox{ and }R)\implies R$ is a theorem in $\mathfrak{T}$, so by I.C31, $(\exists x) (A\mbox{ and }R)\implies (\exists x) R$ is a theorem in $\mathfrak{T}$, so by definition of $\exists_A$, $(\exists_A x)R\implies (\exists x)R$. Conversely, since $R\implies A$ is a theorem in $\mathfrak{T}$, then $R\implies (A\mbox{ and }R)$ is a theorem in $\mathfrak{T}$ since $R\implies R$ by I.C8, so by I.C31, $(\exists x) R\implies (\exists x) (A\mbox{ and }R)$ is a theorem in $\mathfrak{T}$. Thus by definition of $\exists_A$, $(\exists x)R\implies (\exists_A x)R$ is a theorem in $\mathfrak{T}$. It follows that $(\exists x)R\iff (\exists_A x)R$ is a theorem in $\mathfrak{T}$.

If $(\mbox{not } R)\implies A$, then $(\exists x)(\mbox{not } R)\iff (\exists_A x)(\mbox{not } R)$ is a theorem in $\mathfrak{T}$ by what was just shown. The negation $\mbox{not } (\exists_A x)(\mbox{not } R)\iff \mbox{not } (\exists x)(\mbox{not } R)$ is also a theorem in $\mathfrak{T}$ by I.C23, and by definition of $\forall_A$, this is precisely $(\forall x) R\iff (\forall_Ax)R$ (By I.C22).

Now if $A$ is a theorem in $\mathfrak{T}$, then $R\implies A$ and $\mbox{not } R\implies A$ are theorems in $\mathfrak{T}$ by I.C9. A priori, this implies

$(\exists x) R\iff (\exists_Ax)R$ and $(\forall x) R\iff (\forall_Ax)$
$\blacksquare$

This site uses Akismet to reduce spam. Learn how your comment data is processed.