Fall 2009 Final

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 class^confirm?. 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:

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¶

8.3Accuracy and discussion¶

Done in class on Wednesday, November 23