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