Fall 2010 Final

1Question 1¶

1.1Question¶

Translate into propositional formulas and determine validity.

(a) If queens are quizzical or rooks run rampant, then pawns don't prefer palindromes. Either pawns prefer palindromes and queens are quizzical, or rooks run rampant. Therefore pawns don't prefer palindromes and rooks run rampant. (5 marks)
(b) If queens are quizzical and roks run rampant, then pawns don't prefer palindromes. Either pawns prefer palinromes and queens are quizzical, or rooks run rampant. Therefore pawns don't prefer palindromes and rooks run rampant. (5 marks)

1.2Answer¶

(a) $(q \lor r) \to \neg p,\, (p \land q) \lor r \vdash \neg p \land r$. This is valid, as it's impossible to invalidate it. This can be proved by contradiction. Assume there is a valuation $V$ that makes all the premises come out $\top$ but makes the conclusion come out $\bot$. To make the second premise come out $\top$, there are two possibilities. The first is that $V(r) = \top$, in which case, for the first premise to come out $\top$, we must have $V(p) = \bot$, in which case the conclusion would also come out $\top$. The second is that $V(p) = V(q) = \top$. But in this case, the first premise would evaluate to $V(\top \to \bot)$ which comes out $\bot$. So there is no valuation that invalidates this argument and so the argument is valid.
(b) $(q \land r) \to \neg p, \, (p \land q) \lor r \vdash \neg p \land r$. This is invalid. For instance, if $V(p) = V(q) = \top$ and $V(r) = \bot$, then the conclusion comes out $\bot$ due to the valuation of $r$ but the premises both come out $\top$, as the first premise becomes $V(\bot \to \bot)$ and the second becomes $V(\top \lor \bot)$. So this is an invalid argument as there is a valuation that invalidates it.

1.3Accuracy and discussion¶

I think

2Question 2¶

2.1Question¶

Suppose that $R$ is a binary relation on the non-empty set $A$. We define another binary relation $S \subseteq A \times A$ as follows: for $a, b \in A$ we put $(a, b) \in S$ if and only if there is a natural number $n$ and $a_0, a_1 ... a_n$ such that $a_0 = a$, $a_n = b$ and for each $j < n$, $(a_j, a_{j+1}) \in R$.

(a) Show that $S$ is transitive and $R \subseteq S$. (5 marks)
(b) Prove that, if $T \subseteq A \times A$ is transitive and $R \subseteq T$, then $S \subseteq T$. (5 marks)
(c) Show that, if $R$ is reflexive and symmetric, then $S$ is an equivalence relation. (5 marks)

2.2Answer¶

(a) Transitivity of $S$: Later

2.3Accuracy and discussion¶

Later

3Question 3¶

3.1Question¶

(a) Suppose that $(L_1; \leq_1)$ and $(L_2; \leq_2)$ are lattices such that $L_1 \cap L_2 = \{ \top_2 = \bot_1 \}$. That is, the bottom element of $L_1$ is the top element of $L_2$, and otherwise they have no elements in common. Show that the lattice $L$ with underlying set $L_1 \cup L_2$ is modular if and only if each of $L_1$ and $L_2$ is; show that $L$ is distributive if and only if each of $L_1$ and $L_2$ is. (So the order on $L$ is given by $a \leq b$ for any $a \in L_2$, $b \in L_1$; and if both $a, b \in L_j$, then $a \leq b$ if and only if $a \leq_j b$ for $j = 1, 2$. (8 marks)
(b) Hasse diagram not included, can't do this question

3.2Answer¶

(a) Later

3.3Accuracy and discussion¶

Later

4Question 4¶

4.1Question¶

One of the following can be proved logically; i.e., it is valid. The other is not. Identify which is which. Give a quasi-formal proof for the valid one, and a structure showing that the other is not valid. [$f$, $g$ and $h$ are unary function symbols. You may use transitivity and symmetry of equality freely in your proof.]

$$\forall (gfx = hfx), \forall y \exists x (fx = y) \vdash \forall y (gy = hy)$$

$$\forall (fgx = fhx),\, \forall y \exists x (fy = y) \vdash \forall y (gy = hy)$$

4.2Answer¶

The first is valid, the second is not.

A short and elegant proof of the first¹:

Sequent	Justification
(1) $\forall x(gfx = hfx) \vdash gfx = hfx$	Straightforward $\forall$-elimination
(2) $\forall y \exists x(fx = y) \vdash \exists x (fx = y)$	$\forall$-elimination
(3) $fx = y, gfx = hfx \vdash gy = hy$	Substitution rule 1
(4) $\forall x (gfx = hfx), fx = y \vdash gy = hy$	Informal transitivity using (1), (3)2
(5) $\forall x (gfx=hfx),\,\exists x (fx=y) \vdash gy = hy$	$\exists$-elimination from (4)
(6) $\forall x(gfx=hfx),\,\forall y \exists x (fx=y) \vdash gy=hy$	Informal transitivity using (2), (5)
(7) $\forall x (gfx=hfx), \, \forall y \exists x (fx=y) \vdash \forall y gy=hy)$	$\forall$-introduction from (6)

Counterexample to the second:

Let $f(x) = \left \lfloor \frac{x}{2} \right \rfloor$, $g(x) = 0$, $h(x) = 1$, over the natural numbers. The first premise, that $\forall (fgx = fhx)$, is indeed true, as $f(0) = \left \lfloor 0 \right \rfloor = 0 = \left \lfloor 0.5 \right \rfloor = f(1)$. The second premise is also true, as $f(x)$ is indeed onto. However, it is not true that $\forall y (gy = hy)$, since $g(y) = 0$ and $h(y) = 1$ and $0 \neq 1$.

4.3Accuracy and discussion¶

Done in-class on Friday, November 25.

5Question 5¶

5.1Question¶

We invent a structure $\mathcal{M} = (M; f^{\mathcal{M}}, P^{\mathcal{M}})$, where $f$ is a unary function symbol and $P$ is a binary relation symbol as follows: $M = \{a, b, c, d\}, f^{\mathcal{M}}(a) = f^{\mathcal{M}}(b) = d, f^{\mathcal{M}}(c) = a, f^{\mathcal{M}}(d) = b$, and $P^{\mathcal{M}} = \{(a, b), (a, d), (b, c), (c, a), (d, b), (d, c)\}$. Decide whether or not

$$\mathcal{M} \models \forall x \exists y (Pfyfx)$$

and justify your answer.

5.2Answer¶

No. This fails if $x = c$, because then $Pfyfx = P(fy)a$, and so $fy$ must be $c$ in order for $P(fy)a$ to be true. But there is no $x$ in the domain such that $fx = c$.

5.3Accuracy and discussion¶

A bit short but it should be right?

6Question 6¶

6.1Question¶

Give an informal proof from Peano arithmetic of the following. You may use anything done in class or on the assignments, but for not instance the fundamental theorem of arithmetic, since we did not prove that. Recall we use the abbreviation $\Phi(x)$ for "$x$ is a prime number". (15 marks)

$$\forall x \forall y \forall z ((\Pi(x) \land \Pi(y) \land \Pi(y) \land y \neq z) \to x \cdot x \neq y \cdot z)$$

6.2Answer¶

Later

6.3Accuracy and discussion¶

Later

7Question 7¶

7.1Question¶

One of the following distributive laws holds for all ordinals and the other sometimes doesn't. Give an informal proof for the true one, and a counterexample for the (sometimes) false one. (The addition and multiplcation are of course ordinal addition and multiplication). (10 marks)

$$\alpha \cdot (\beta + \gamma) = (\alpha \cdot \beta) + (\alpha \cdot \gamma)$$

$$(\alpha + \beta) \cdot \gamma = (\alpha \cdot \gamma) + (\beta \cdot \gamma)$$

7.2Answer¶

Later

7.3Accuracy and discussion¶

Later

8Question 8¶

8.1Question¶

Give a formal in Prenex normal form which is equivalent to the formula

$$(\exists Pxy \to \forall x Qxy) \land \neg \forall y \exists x ((Pxy \lor \neg Qyx) \land \neg Pxz)$$

Here of course P and Q are binary predicate symbols. (10 marks)

8.2Answer¶

Sequent	Justification
$(\exists x Pxy \to \forall x Qxy) \land \exists y \forall x(\neg ((Pxy \lor \neg Qyx) \land \neg Pxz)))$	Not sure how this is justified but it works
$(\neg \exists x Pxy \lor \forall x Qxy) \land ...$	Replacing the implies
$(\forall x \neg Pxy \lor \forall x Qxy) \land ...$	Replacing $\neg \exists$ with $\forall \neg$
$(\forall u \neg Puy \lor \forall x Qxy) \land ...$	Change of bound variables
$\forall u (\neg Puy \lor \forall v Qvy) \land ...$	Moving a $\forall$ outside, changing a bound variable
$\forall u \forall v (\neg Puy \lor Qvy) \land ...$	Moving another $\forall$ outside
$\forall u \forall v \exists y \exists x (...)$	Moving everything outside

8.3Accuracy and discussion¶

Done in class, something might have been incorrectly copied though. Not sure about the justification.