Return to the class
Homework 7
2.5(a) Let $\mathcal{V}_{gp}$ be the vocabulary $\{+,0\}$ where $+$ is a binary function and $0$ is a constant. We use the notation $x+y$ to denote the terms $+(x,y)$. Consider the following $\mathcal{V}$-sentences:
$$\forall x \forall y \forall z (x+(y+z) = (x+y)+z),$$
$$\forall x((x+0=x) \wedge (0+x=x)),$$
and
$$\forall x ( \exists y (x+y=0) \wedge \exists z (z+x=0)).$$
Let $\gamma$ denote the conjunction of these three sentences. Show that $\gamma$ is satisfiable by exhibiting a model.
Solution: Consider the model $M=(\mathbb{R}|+,0)$, where $+$ and $0$ are interperted in the usual way. This structure models all of the given $\mathcal{V}$-sentences: the first sentence is the statement of the associative property of the real numbers, the second one states that the special constant $0$ is the "additive identity", and and third pertains to having additive inverses (i.e. $1+(-1)=0$ and $(-1)+1=0$).
2.8: Goldbach's conjecture states that every even integer greater than $2$ is the sum of two primes. Whether or not this is true is an open question of number theory. State Goldbach's conjecture as a $\mathcal{V}_{ar}$-sentence where $\mathcal{V}_{ar} = \{+, \cdot, 0,1 \}$.
Solution: We need to write a formula that checks if an element of the universe is a prime -- call it $P(a)$ for the moment. We will also need a formula that checks if an element of the universe is even or not -- call it $E(a)$. With these symbols, we can write Goldbach's conjecture as
$$(*) \hspace{35pt} \forall n \Big((\underbrace{E(n)}_{n\text{ is even}} \wedge \underbrace{\neg (n=0) \wedge \neg (n=1+1)}_{n\text{ is not zero or two}}) \rightarrow \exists a \exists b (\underbrace{P(a) \wedge P(b)}_{a\text{ and }b\text{ are prime}} \wedge (n=a+b)) \Big)$$
But this formula will not answer the question, because it is not a $\mathcal{V}_{ar}$-sentence. So what remains is expressing $E$ and $P$ in terms of $\mathcal{V}_{ar}$-sentences. However, we did exactly this in Homework 6 -- the formulas from my solution are written below: for $E(n)$ encoding "$n$ is even", I use
$$\exists z (n=z+z).$$
For $P(a)$ encoding "$a$ is prime", I use
$$\forall m \forall \ell ( a=m\cdot \ell \rightarrow ((\ell = a) \vee (\ell = 1))).$$
Therefore we substitute these into $(*)$ where appropriate to arrive at the following $\mathcal{V}_{ar}$ formula expressing Goldbach's conjecture:
$$\forall n \left[\left(\underbrace{\exists z (n=z+z)}_{E(n)} \wedge \neg (n=0) \wedge \neg (n=1+1) \right) \rightarrow \exists a \exists b \left(\underbrace{\Big(\forall m \forall \ell ( a=m\cdot \ell \rightarrow ((\ell = a) \vee (\ell = 1)))\Big)}_{P(a)} \wedge \underbrace{\Big(\forall m \forall \ell ( b=m\cdot \ell \rightarrow ((\ell = b) \vee (\ell = 1))) \Big)}_{P(b)} \wedge (n=a+b) \right) \right]$$
2.9: Let $\mathcal{V}_{ar} = \{+,\cdot,0,1\}$ be the vocabulary of arithmetic. Let $\mathbf{R}$ be the $\mathcal{V}_{ar}$-structure that has universe $\mathbb{R}$ and interprets the vocabulary in the usual manner.
(a) Define a $\mathcal{V}_{ar}$-formula $\alpha(x)$ such that, for any $\alpha \in \mathbb{R}$, $\mathbf{R} \vDash \alpha(a)$ if and only if $a$ is positive.
Solution: Let $\alpha(x)$ denote the formula
$$\exists b ( \neg (b=0) \wedge a = b \cdot b ).$$
This formula works because for any real number, its square $b^2=b\cdot b$ is a positive number.
(b) Define a $\mathcal{V}_{ar}$-formula $\beta(x,y)$ such that, for any $a, b \in \mathbb{R}$, $\mathbf{R} \vDash \beta(a,b)$ if and only if $a \leq b$.
Solution: $a \leq b$ is the same as saying $b-a \geq 0$ which is the same as saying $b-a=0$ OR $b-a>0$, or in other words $b-a=0$ OR "$b-a$ is positive". Since we do not have a "$-$" symbol, we will need to be clever of how to express "$-a$". So we will instead think of $b-a$ as $b+(-a)$. But how to express "$-a$"? It is the number with the property that $a+(-a)=0$, in other words we can say something like $\exists c(a+c=0)$ in order to invoke the existence of "$-a$" (we are encoding it as the variable $c$). A first shot at this problem yields something like
$$\exists c \left( (a+c=0) \rightarrow \Big( (b+c=0) \vee (b+c \text{ is positive}) \Big) \right)$$
This is not yet $\mathcal{V}_{ar}$-formula. However if we replace "$b+c$ is positive" using the result from part (a), we can do it:
$$\exists c \left( (a+c=0) \rightarrow \Big( (b+c=0) \vee \underbrace{(\exists s\left( \neg (s=0) \wedge (b+c=s\cdot s)\right)}_{b+c\text{ is positive}} \Big) \right)$$
(c) Define a $\mathcal{V}_{ar}$-formula $\gamma(x)$ such that, for any $a \in \mathbb{R}$, $\mathbf{R} \vDash \gamma(a)$ if and only if the absolute value of $a$ is less than $1$.
Solution: Rewrite $|a|< 1$ as $0 < 1-|a|$ and we see that this is equivalent to saying "$1-|a|$ is positive". How can we express the absolute value of any $a \in \mathbb{R}$ as $\mathcal{V}_{ar}$-formula? As a function, the absolute value is
$$|a| = \left\{ \begin{array}{ll}
a, & \quad a\geq0 \\
-a, & \quad a< 0.
\end{array}\right.$$
Think of this as saying "if $a$ is positive, then $|a|=a$ OR if $a$ is negative, then $|a|=-a$ OR if $a=0$, then $|a|=0$". So, given $a \in \mathbb{R}$, we will use the symbol $c$ to encode $|a|$: something like
$\Big((a$ positive$)\wedge (c=a)\Big)$ OR $\Big(\neg( a$ is positive$) \wedge ((c=-a) \vee (c=0)) \Big)$
We also have to contend with calling into existence "$-a$", so a further improvement is
$\underbrace{\exists d}_{\text{our symbol for} -a} \Bigg( (a+d=0) \wedge \Bigg[\Big((a$ positive$)\wedge (c=a)\Big) \bigvee \Big(\neg( a$ is positive$) \wedge ((c=d) \vee (c=0)) \Big)\Bigg]\Bigg)$
Now if we place in the formulas for "$a$ is positive" and "$\neg(a$ is positive$)$" we get
$\exists d \Bigg( (a+d=0) \wedge \Bigg[\Big((\exists z(a=z\cdot z)\wedge (c=a)\Big) \bigvee \Big(\neg( \exists z \left(\neg (z=0) \wedge (a=z \cdot z) \right) \wedge ((c=d) \vee (c=0)) \Big)\Bigg]\Bigg)$
Call that (long and complicated) $\mathcal{V}_{ar}$-formula $\xi(a,c)$ -- this formula says "$c$ is the absolute value of $a$". This problem wants us to encode "$1-|a|$ is positive". With our symbol $c$ this would say "$1-c$ is positive". Again, we have to call into existence $-c$ so we will write something like
$$\exists w (c+w=0 \wedge (1+w \text{ is positive})).$$
We need to use our formula $\xi$ to define $c$, so
$$\exists c\exists w \Big(\xi(a,c) \wedge (c+w=0) \wedge (1+w \text{ is positive})\Big).$$
Replacing the sentence "$1+w$ is positive" with its $\mathcal{V}_{ar}$ version yields
$$\underbrace{\exists c}_{\text{symbol for }|a|}\underbrace{\exists w}_{\text{symbol for } -|a|} \left(\underbrace{\xi(a,c)}_{c=|a|} \wedge \underbrace{(c+w=0)}_{|a|+(-|a|)=0} \wedge \underbrace{( \exists z\left((\neg (z=0)) \wedge (1+w=z \cdot z) \right)))}_{1+(-|a|)> 0}\right).$$
Since $\xi(a,c)$ is merely an abbreviation for a $\mathcal{V}_{ar}$-formula we may substitute it in. What we have is technically not a $\mathcal{V}_{ar}$-formula until we do: we finally write an expression for $\gamma(a)$:
$$\exists c\exists w \left(\underbrace{\exists d \Bigg( (a+d=0) \wedge \Bigg[\Big((\exists z(a=z\cdot z)\wedge (c=a)\Big) \bigvee \Big(\neg( \exists z(a=z \cdot z) \wedge ((c=d) \vee (c=0)) \Big)\Bigg]\Bigg)}_{\xi(a,c)} \wedge (c+w=0) \wedge ( \exists z\left(\neg (z=0)\wedge (1+w=z \cdot z)\right))\right).$$
2.11: Let $A$ and $B$ be definable subsets of structure $M$. Suppose that $A$ and $B$ are both sets of $n$-tuples of elements from the underlying set of $M$.
(a) Show that $A \cup B$ is definable.
Solution: Recall: let $\phi(x_1,\ldots,x_n)$ be a $\mathcal{V}$-formula and let $M$ be a $\mathcal{V}-structure$ with underlying set $\mathscr{U}$. The definable subset of the formula $\phi(x_1,\ldots,x_n)$ is the subset of $\mathscr{U}^n$ consisting of all $(b_1,\ldots,b_n)$ for which $M \vDash \phi(b_1,\ldots,b_n)$.
In this problem we are told that $A$ and $B$ are definable subsets of a structure $M$. Let $A$ be the subset corresponding to the formula $\phi(x_1,\ldots,x_n)$ and let $B$ correspondg to the formula $\psi(x_1,\ldots,x_n)$. Then the definable subset of $\phi \vee \psi$ is precisely $A \cup B$.
(b) Show that $A \cap B$ is definable.
Solution: Similar to above, but now the definable subset of $\phi \wedge \psi$ is precisely $A \cap B$.
(c) Show that $A \setminus B = \{a | a\in A, a \not\in B\}$ is definable.
Solution: Similar to above, but now the definable subset of $\phi \wedge \neg \psi$ is $(A \cap \underbrace{B^c}_{\text{complement of }B})=A \setminus B$
