Return to the class

__Homework 6__

**#2.1**: Let $\mathcal{V}$ be the vocabulary $\{+, <, 1,2,3\}$ where $+$ is a binary function, $<$ is a binary relation, and $1$, $2$, and $3$ are constants. We write $(x+y)$ for $+(x,y)$ and $x < y$ for $< (x,y)$. Consider the following $\mathscr{V}$-formulas:

- $\forall x \exists y ((x+y)=1)$
- $\forall x \neg (x<1)$
- $((1+1)=2)$
- $2 < 1$
- $\forall x(2<1) \rightarrow (x+2 < x+1)$
- $\forall x \forall y \exists z(x+y=z)$
- $\forall x \forall y \forall z (((x+3=y) \wedge (x+3=z)) \rightarrow (y=z))$
- $\forall x \forall y \forall z (((x+y=3) \wedge (x+z=3)) \rightarrow (y=z))$
- $\forall x \forall y(((x+3) < (y+3)) \rightarrow (x < y))$
- $\forall x \forall y ((x<2) \rightarrow ((x+3)=4))$

(a) Which of these 10 formulas are sentences?

*Solution*: 1, 2, 3, 4, 6, 7, 8, 9, 10

(b) Which of these 10 formulas are satisfiable?

*Solution*: all of them

(c) Which of these 10 formulas are tautologies?

*Solution*: none of them

(d) Let $\mathbf{N}^+$ be the $\mathcal{V}$-structure having universe $\mathbb{N}$ that interprets the symbols of $\mathcal{V}$ in the usual way. Which of the above sentences does $\mathbf{N}^+$ model?

*Solution*: 2, 3, 6, 7, 8, 9

(e) Let $\mathbf{R}^+$ be the $\mathcal{V}$-structure having universe $\mathbb{R}$ that interprets the symbols of $\mathcal{V}$ in the usual way. Which of the above sentences does $\mathbf{R}^+$ model?

*Solution*: 1, 3, 6, 7, 8, 9

**#2.2**: Let $\mathcal{V}$ be the vocabulary consisting of a binary relation $P$ and a unary relation $F$. Interpret $P(x,y)$ as "$x$ is the parent of $y$" and $F(x)$ as "$x$ is female".

(a) Define a $\mathcal{V}$-formula $\phi_B(x,y)$ that says that $x$ is a brother of $y$.

*Solution*: Let $\phi_B(x,y)$ denote
$$\exists z(\underbrace{P(z,x) \wedge P(z,y)}_{x \text{ and } y \text{ have the same parent, } z} \wedge \underbrace{\neg F(x)}_{x \text{ is not female}})$$

(b) Define a $\mathcal{V}$-formula $\phi_A(x,y)$ that says that $x$ is an aunt of $y$.

*Solution*: Let $\phi_A(x,y)$ denote
$$\exists p_1 \left( \underbrace{P(p_1,y)}_{p_1 \text{ is parent of } y} \wedge \exists x \exists p_2 \left( \underbrace{P(p_2,x) \wedge P(p_2,p_1)}_{p_2 \text{ is parent of both } p_1 \text{ and } x} \wedge \underbrace{\neg (x=p_1)}_{x \text{ and } p_1 \text{ are different people}} \wedge \underbrace{F(x)}_{x \text{ is female}} \right) \right)$$

(c) Define a $\mathcal{V}$-formula $\phi_C(x,y)$ that says that $x$ and $y$ are cousins.

*Solution*: Let $\phi_C(x,y)$ denote
$$\exists p_1 \exists p_2 \exists p_3 \left( P(p_1,x) \wedge P(p_2,y) \wedge \underbrace{P(p_3,p_1) \wedge P(p_3,p_2)}_{p_3 \text{ is parent of both } p_1 \text{ and } p_2} \wedge \underbrace{\neg (p_1 = p_2)}_{p_1 \text{ and } p_2 \text{ are different people}} \right)$$

(d) Define a $\mathcal{V}$-formula $\phi_O(x)$ that says that $x$ is an only child.

*Solution*: Let $\phi_O(x)$ denote
$$\exists p_1 \forall y ( \underbrace{P(p_1,y) \rightarrow y=x}_{\text{if } p_1 \text{ is parent of } y \text{, then } y=x})$$

(e) Define a $\mathcal{V}$-formula $\phi_T(x)$ that says that $x$ has exactly two brothers.

*Solution*: Let $\phi_T(x)$ denote
$$\exists p_1 \exists y \exists z \forall w \left( \underbrace{P(p_1,x) \wedge P(y,x) \wedge P(z,x)}_{x, y, \text{ and } z \text{ all have a common parent, } p_1} \wedge \underbrace{\neg F(y) \wedge \neg F(z)}_{y \text{ and } z \text{ aren't sisters}} \wedge \underbrace{\neg(x=y) \wedge \neg(x=z) \wedge \neg(y=z)}_{x, y, \text{ and } z \text{ are different people}} \right)$$

(f) Give an example of a family relationship that cannot be defined by a $\mathcal{V}$-formula.

*Solution*: Our vocabulary can not express "married to" as a $\mathcal{V}$-formula.

**#2.7**: Let $\mathcal{V}_N=\{+,\cdot,1\}$. Let $\mathbf{N}$ be the $\mathcal{V}_N$-structure having underlying set $\mathbb{N}$ that interprets this vocabulary in the usual manner.

(a) Define a $\mathcal{V}_N$-formula $\epsilon(x)$ such that, for any $a \in \mathbb{N}, \mathbf{N} \vDash \epsilon(a)$ if and only if $a$ is even.

*Solution*: We *want* to say $a=2z$" but we don't have a symbol for $2$ in our vocabulry. So instead we will write $a=z+z$:

$$\exists z \left( a = z+z \right)$$
(b) Define a $\mathcal{V}_N$-formula $\pi(x)$ such that, for any $a \in \mathbb{N}$, $\mathbf{N} \vDash \pi(a)$ if and only if $a$ is prime.

*Solution*: A natural number $a$ is called prime if its only divisors are $1$ and itself. We say that $b$ divides $a$ provided that $\dfrac{a}{b}=n$ is a natural number. Rearranging this equation we see that $b$ divides $a$ if and only if there is a natural number $n$ so that $a=nb$.

Therefore for $a$ to be prime, it means anytime that we write $a$ as $nb$, then $b=a$ or $b=1$. In other words we let $\pi(a)$ be
$$\forall n \forall b (\underbrace{a = n \cdot b}_{\text{if } a \text{ is written as the product } b \cdot n} \rightarrow \underbrace{((b=a) \vee (b=1))}_{\text{then } b=a \text{ or } b=1}).$$

(c) Define a $\mathcal{V}_N$-formula $\mu(x,y)$ such that, for any $a$ and $b$ in $\mathbb{N}$, $\mathbf{N} \vDash \mu(a,b)$ if and only if $a$ and $b$ are relatively prime (that is, the greatest common divisor of $a$ and $b$ is $1$).

*Solution*: We will write $x$ is relatively prime to $x$ to mean that if there is any $z$ so that $x = n \cdot z$ and $y= m \cdot z$, then $z=1$. In other words, let $\mu(x,y)$ be
$$\forall n \forall m \forall z \left( \underbrace{(x = n \cdot z \wedge y = m \cdot z)}_{\text{if }x\text{ and }y\text{ are multiples of }z} \rightarrow \underbrace{z=1}_{\text{then that common multiple must be }1} \right).$$