Fall 2009 Final CC-BY-NC

Maintainer: admin

1Question 1

1.1Question

Translate into propositional formulas and determine consistency.

(a) If pistachios are perfect and quizzes are quiet, then ragweed is riotous. If pistachios are perfect, then either quizzes are quiet or ragweed is riotous. Pistachios are perfect and ragweed is not riotous. (5 marks)
(b) If pistachios are perfect and quizzes are quiet, then ragweed is riotous. If pistachios are perfect, then either quizzes are quiet or ragweed is riotous. Pistachios are not perfect and ragweed is riotous. (5 marks)

1.2Answer

(a) $(p \land q) \to r,\, p \to (q \lor r), \, p \land \neg r$. Not consistent; for the third statement to hold, we must have $V(p) = \top$ and $V(r) = \bot$. For the second one to hold, we must have $V(q) = \top$, but for the first one to hold, we must have $V(q) = \bot$.
(b) $(p \land q) \to r,\,p \to (q \lor r),\,\neg p \land r$. Consistent - if we have $V(p) = \bot$, $V(r) = \top$, and $V(q) = $ either $\top$ or $\bot$, then all three statements hold.

1.3Accuracy and discussion

Meh

2Question 2

2.1Question

Suppose that the binary relation $R$ on the nonempty set $A$ is reflexive and transitive (no assumptions about symmetry/antisymmetry made).

(a) $E$ on $A$ is defined by $aEb$ if and only if $aRb$ and $bRa$. Show that $E$ is an equivalence relation on $A$. (5 marks)
(b) Prove that, if $a'Ea$ and $b'Eb$, then $aRb$ if and only if $a'Rb'$. (5 marks)
(c) Set of equivalence classes: $A / E$; the class containing $a \in A$: $[a]$. We define a relation $\bar R$ of $A / E$ by $[b]\bar R[b]$ if and only if $aRb$. Prove that $\bar R$ is a partial order of $A / E$. (5 marks)

2.2Answer

(a) Any relation that is reflexive, symmetric, and transitive is an equivalence relation. That the relation is reflexive is obvious, as $R$ is reflexive - $aRa$ for all $a \in A$, and so $aEa$ as well. That the relation is symmetric is clear from the definition of $E$, as for all $a \in A$, $aEb$ if and only if $aRb$ and $bRa$, meaning that both $aEb$ and $bEa$ are true. That the relation is transitive is due to the fact that $R$ is transitive - if $aRb$ and $bRc$, then $aRc$, and so if $bRa$ and $cRb$, then $aEb$ and $bEc$. But since $cRb$ and $bRa$, then $cRa$, due to the transitivity of $R$, and since $cRa$ and $aRc$, then $aEc$. So $E$ is transitive, reflexive, and symmetric, and thus an equivalence relation.
(b) First, we prove that if $aRb$, then $a'Rb'$. Since $a'Ea$, then $a'Ra$ and $aRa'$, and since $b'Eb$, then $b'Rb$ and $bRb'$. If $aRb$, then we must also have that $a'Rb'$ by the transitivity of $R$, as $a'Ra$ and $aRb$ entails that $a'Rb$, and $a'Rb$ and $bRb'$ entails that $a'Rb'$. Then, we prove that if $a'Rb'$, then $aRb$. Using transitivity again, we have that $aRb'$ (from $aRa'$ and $a'Rb'$), and so we have that $aRb$ (from $aRb'$ and $b'Rb$). Therefore, we have that $aRb$ if and only if $a'Rb'$.
(c) For this relation to be a partial order, it must be reflexive (or irreflexive for strict, but this specific relation is not), antisymmetric, and transitive. Reflexivity: $[a]\bar R[a]$ is true, because $aRa$ due to the reflexivity of $R$. Antisymmetry: if $[a]R[b]$ and $[b]R[a]$, then $[a] = [b]$, because if $aRb$ and $bRa$, then $a$ and $b$ would be in the same equivalence classconfirm?. Transitivity: if $[a]R[b]$ and $[b]R[c]$, then $[a]R[c]$, due to the transitivity of $R$ (as $aRb$ and $bRc$ entail $aRc$). So $\bar R$ is a partial order of $A / E$.

2.3Accuracy and discussion

Not sure about justification of antisymmetry and transitivity for (c).

3Question 3

3.1Question

$(L_1; \leq_1)$ and $(L_2; \leq_2)$ are lattices not containing $\top$ or $\bot$, with $L_1 \cap L_2 = \varnothing$. Let $L = L_1 \cup L_2 \cup \{\top, \bot \}$. Define $\leq$ on $L$ by $a \leq b$ if any only if either: $a \bot$, or $b = \top$, or $a, b \in L_1$ and $a \leq_1 b$, or $a \in L_2$ and $a \leq_2 b$. Show that if $L_1$ or $L_2$ (or both) has at least two elements, then $L$ is not modular. (10 marks)

3.2Answer

Show that there is a copy of $N_5$ ("five"), the smallest non-modular lattice. Use $\alpha, \beta, \gamma$ somehow.

3.3Accuracy and discussion

If only one of $L_1$ and $L_2$ has two elements, then doesn't the other have to have at least one element? Otherwise, we don't have enough elements to make up a five? Finish this.

4Question 4

4.1Question

One of the following statements is a logical theorem and the other is not. Identify which is which, and give a quasi-formal proof of the logical theorem; give a structure verifying that the other is not a logical theorem. $f$ and $g$ are unary function symbols. (20 marks)

$$\forall x \forall y (fgx = fgy \to x = y) \to \forall x \forall y (fx = fy \to x = y)$$

$$\forall x \forall y(fgy = fgy \to x = y) \to \forall x \forall y(gx=gy \to x = y)$$

4.2Answer

The second one is a logical theorem; the first is false.

Proof of the logical theorem:

Sequent Justification/rule
(1) $gx = gy \vdash fgx = fgy$ Substitution rule 1
(2) $fgx = fgy \to x = y, fgx = fgy \vdash x = y$ Tautology
(3) $fgx = fgy \to x = y, gx = gy \vdash x = y$ Transitivity using (1) and (2)
(4) $fgy = fgy \to x = y \vdash gx = gy \to x = y$ Deduction from (3)
(5) $\forall x \forall y (fgx = fgy \to x = y) \vdash fgx = fgy \to x = y$ $\forall$-elimination twice
(6) $\forall x \forall y (fgx = fgy \to x = y) \vdash gx = gy \to x = y$ Transitivity using (4) and (5)
(7) $\forall x \forall y (fgx = fgy \to x = y) \vdash \forall x \forall y (gx = gy \to x = y)$ $\forall$-introduction twice

Counterexample to the first statement: let the set be the natural numbers. Say $g: \mathbb{N} \to \mathbb{N}$ is given by $g(x) = 2x$, and let $\displaystyle f(x) = \left \lfloor \frac{x}{2} \right \rfloor$. $f(x)$ is clearly not one-to-one, but the composition is.

4.3Accuracy and discussion

Identification of the logical theorem was done in class, as was the counterexample. The proof was student-made and its correctness is debatable. @dellsystem

Can you just do a substitution right off the bat? Don't you need to start with a tautology? wikipedia link @tahnok

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 = \{\alpha, \beta, \gamma\}, f^{\mathcal{M}}(\alpha) = f^{\mathcal{M}}(\beta) = \gamma, f^{\mathcal{M}}(\gamma) = \alpha$, and $P^{\mathcal{M}} = \{(\alpha, \alpha), (\alpha, \gamma), (\beta, \gamma), (\gamma, \gamma)\}$. Decide whether or not

$$\mathcal{M} \models \forall x \exists y (Pxfy \land \neg Pfxy)$$

and justify your answer. (10 marks)

5.2Answer

Yes. For $x = \alpha$, $y = \alpha$ satisfies the formula, as $P\alpha f\alpha = P\alpha \gamma$ is true and $P\gamma \alpha$ is false. For $x = \beta$, $y = \alpha$ again satisfies the formula, as $P\beta f \alpha = P \beta \gamma$ is true and $P \gamma \alpha$ is false. For $x = \gamma$, $y = \beta$ satisfies the formula, as $P\gamma f \beta = P\gamma \gamma$ is true and $P \alpha \beta$ is false.

5.3Accuracy and discussion

Accurate I think

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 not for instance the fundamental theorem of arithmetic, since we did not prove that. Recall we use the abbreviation $\Pi(x)$ for "$x$ is a prime number" and $x \mid y$ for "x divides y". (15 marks)

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

6.2Answer

Later

6.3Accuracy and discussion

Later

7Question 7

7.1Question

Prove that if $\alpha$ is a limit ordinal, then for any ordinal $\beta$, $\beta + \alpha$ is a limit ordinal. (The addition is of course ordinal addition.) (10 marks)

7.2Answer

Later

7.3Accuracy and discussion

Later

8Question 8

8.1Question

Give a formula in prenex normal form which is equivalent to the formula

$$\forall y (Py \to Qxy) \land \neg \forall x (Px \land \exists y Qxy)$$

Here of course P is a unary predicate symbol and Q is a binary predicate symbol. (10 marks)

8.2Answer

Sequent Explanation
$\forall y (Py \to Qxy) \land \neg \forall x (\exists y(Px \land Qxy)$ Move the exists outside one
$\forall y (Py \to Qxy) \land \exists x \forall y (\neg (Px \land Qxy))$ Change the $\exists y$ to $\neg \forall y \neg$, double negatives cancel
$\forall z (Pz \to Qxz) \land \exists x \forall y (\neg (Px \land Qxy))$ Change of bound variable, from y to z
$\forall z ((Pz \to Qxz) \land \exists x \forall y (\neg (Px \land Qxy)))$ Move the forall around both
$\forall z((Pz \to Qxz) \land \exists w \forall y(\neg(Pw \land Qwy)))$ Change of bound variable, from x to w
$\forall z \exists w ((Pz \to Qxz) \land \forall y (\neg (Pw \land Qwy)))$ Move the exists outside one
$\forall z \exists w \forall y ((Pz \to Qxz) \land \neg (Pw \land Qwy))$ Move the forall outside one

8.3Accuracy and discussion

Done in class on Wednesday, November 23