Intereting Posts

Prove that if $a,b,$ and $c$ are positive real numbers, then $\frac{a^3}{b}+\frac{b^3}{c}+\frac{c^3}{a} \geq ab + bc + ca$.
Choosing two random numbers in $(0,1)$ what is the probability that sum of them is more than $1$?
Smallest positive integer that gives remainder 5 when divided by 6, remainder 2 when divided by 11, and remainder 31 when divided by 35?
Solutions for diophantine equation $3^a+1=2^b$
Kähler form convention
Gradient of the TV norm of an image
Using calculus of residues to evaluate a trig integral
Convergence of fixed point iteration for polynomial equations
Difference between “only if” and “if and only if”
Irreducible elements in $\mathbb{Z}$ and is it a Euclidean domain?
In an incomplete inner product space, is a closed linear subspace equal to the orthogonal complement of its orthogonal complement?
Generate a number with a die that has three 0s and three 1s
Is a mild solution the same thing as a weak solution?
Show that if the sum of components of one vector adds up to 1 then the sum of the squares of the same vector is at least 1/n
Confused about Euclidean Norm

**Problem:** Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$

**Source:** As was noted in the original post, this problem is from Daniel J. Velleman’s book *How to Prove It*. The exercise may be found as problem 7 (a) on page 54 (second edition). I got a copy of this book, and I saw that some exercises have solutions in the book. The exercise directly before this one had the solution, “Either make a truth table or reason as follows: […]”. This makes me think the author had a truth table solution in mind for this exercise, as a purely direct proof by using a chain of logical equivalences has proven to be exceedingly difficult. I am very interested in obtaining a solution that uses a chain of logical equivalences similar to my answer to this problem. I have spent several hours working on this problem now, but I have not succeeded at all–I cannot seem to “pull the right-hand side out of the left-hand side”, as this seems the most natural approach. For anyone interested, I have presented a truth table without the fluff below.

**Truth table solution:**

- Can I construct a complete (as a Boolean algebra) $\aleph_0$ saturated elementary extension of a given Boolean algbera?
- If $\bigcup F = A$ then $A\in F$ then prove that $A$ has exactly one element
- General McNugget problem
- substituting a variable in a formula (in logic)
- In Fitch, is a symbol not in a specified language automatically free?
- Classes, sets and Russell's paradox

$$

\boxed{

\begin{array}{c|c|c|c}

P & Q & R & (P\to Q)\land (Q\to R) & (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)] \\ \hline

T & T & T & T & T \\

T & T & F & F & F \\

T & F & T & F & F \\

T & F & F & F & F \\

F & T & T & T & T \\

F & T & F & F & F \\

F & F & T & T & T \\

F & F & F & T & T

\end{array}}

$$

**Chain of equivalences proof:** It seems that the main issue is “coaxing” the right-hand side out of the left-hand side. For instance, by using distributivity, I can see that somehow $(P\to Q)\land(Q\to R)$ is equivalent to

$$

[(P\to R)\land(P\to Q)\land(Q\to P)]\lor[(P\to R)\land(R\to Q)\land(Q\to R)].\tag{1}

$$

I have tried numerous times trying to manipulate the left-hand side into the expression given in $(1)$, but I have not succeeded so far–everything is such an enormous mess. Perhaps there is some strategy involved in using equivalences (in terms of ease of manipulation); for example, should one use

$$

P\leftrightarrow Q\equiv (P\land Q)\lor(\neg P\land\neg Q)

$$

or

$$

P\leftrightarrow Q\equiv (P\to Q)\land (Q\to P)

$$

- Why is there this strange contradiction between the language of logic and that of set theory?
- $$ is not true or false
- Difference between elementary logic and formal logic
- Translating sentences into propositional logic formulas.
- Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this
- Two styles of semantics for a first-order language: what's to choose?
- How does (ZFC-Infinity+“There is no infinite set”) compare with PA?
- Undefinable Real Numbers
- Logic Behind Epsilon-Delta Proofs (Single-Variable Calculus)
- Modal set-theory

There are several algorithms to convert classical propositional sentences into normal forms. I’ll pretend to be as dumb as a computer and convert the two sentences into their disjunctive normal form in a systematic way.

\begin{align}

& {(P \to R) \wedge [(P \leftrightarrow Q) \vee (R \leftrightarrow Q)]}\\

& = (\neg P \vee R) \wedge [(P \wedge Q) \vee (\neg P \wedge \neg Q) \vee (R \wedge Q) \vee (\neg R \wedge \neg Q)] \\

& = [(\neg P \vee R) \wedge P \wedge Q] \vee [(\neg P \vee R) \wedge \neg P \wedge \neg Q] \vee \\

& \phantom{{} = {}} [(\neg P \vee R) \wedge R \wedge Q] \vee [(\neg P \vee R) \wedge \neg R \wedge \neg Q] \\

& = [P \wedge Q \wedge R] \vee [(\neg P \wedge \neg Q) \vee (\neg P \wedge \neg Q \wedge R)] \\

& \phantom{{} = {}} \vee [(\neg P \wedge Q \wedge R) \vee (Q \wedge R)] \vee

[\neg P \wedge \neg Q \wedge \neg R] \\

& = (P \wedge Q \wedge R) \vee [(\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge \neg Q \wedge R)] \vee\\

& \phantom{{}={}} [(\neg P \wedge Q \wedge R) \vee (P \wedge Q \wedge R)]

\vee [\neg P \wedge \neg Q \wedge \neg R] \\

& = (P \wedge Q \wedge R) \vee (\neg P \wedge \neg Q \wedge R) \vee (\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge Q \wedge R).

\end{align}

\begin{align}

& (P \to Q) \land (Q \to R) \\

& = (\lnot P \lor Q) \land (\lnot Q \lor R) \\

& = [\lnot P \land \lnot Q] \lor [\lnot P \land R] \lor [Q \land R] \\

& = [(\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R)] \lor [(\lnot P \land Q \land R) \lor (\lnot P \land \lnot Q \land R)] \lor \\

& \phantom{{}={}} [(P \land Q \land R) \lor (\lnot P \land Q \land R)] \\

& = (\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) \lor (P \land Q \land R).

\end{align}

Now you should see how the general method works. If you want to redo it without pretending to be as dumb as a computer, some steps can be skipped. In fact, the final form doesn’t have to be expanded out in full. You can just try to make both expressions look like this:

$$

(Q \land R) \vee (\lnot P \land \lnot Q).

$$

It is fairly approachable if you split up according to whether $Q$ is true or false.

For conciseness, call the two formulas be $\Phi$ and $\Psi$. We can show that each of them is equivalent to $(R\land Q) \lor (\neg P\land \neg Q)$, and therefore they are equivalent to each other.

More precisely, I will show that $\Xi\land Q \equiv \neg R\land Q$ and $\Xi\land \neg Q\equiv \neg P\land \neg Q$, for $\Xi\in\{\Phi,\Psi\}$. We then have

$$ \begin{align} \Xi \equiv{}& \Xi\land (Q\lor \neg Q) \\

\equiv{}& (\Xi\land Q) \lor (\Xi\land \neg Q) \\

\equiv{}& (R\land Q) \lor (\neg P\land \neg Q) \end{align} $$

Thus there are four computations to do:

$$ \begin{align} \Phi\land Q

\equiv{}& (P\to Q)\land (Q\to R)\land Q \\

\equiv{}& (P\to Q)\land Q \land R \\

\equiv{}& Q\land R \end{align} $$

$$ \begin{align} \Phi\land \neg Q

\equiv{}& (P\to Q)\land (Q\to R)\land \neg Q \\

\equiv{}& (P\to Q)\land (\neg Q\lor R)\land \neg Q \\

\equiv{}& (P\to Q)\land \neg Q \\

\equiv{}& (\neg Q\to \neg P)\land \neg Q\\

\equiv{}& \neg P \land \neg Q \end{align} $$

$$ \begin{align} \Psi\land Q

\equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land Q \\

\equiv{}& (P\to R)\land ((P\leftrightarrow Q \land Q) \lor (R\leftrightarrow Q)\land Q)) \\

\equiv{}& (P\to R)\land ((P\land Q) \lor (R\land Q)) \\

\equiv{}& (P\to R)\land (P\lor R) \land Q\\

\equiv{}& (\neg P \lor R)\land (P\lor R) \land Q \\

\equiv{}& ((\neg P \land P) \lor R) \land Q \\

\equiv{}& (\bot \lor R) \land Q \\

\equiv{}& R \land Q \end{align} $$

$$ \begin{align} \Psi\land \neg Q

\equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land \neg Q \\

\equiv{}& (P\to R)\land ((P\leftrightarrow Q \land \neg Q) \lor (R\leftrightarrow Q)\land \neg Q)) \\

\equiv{}& (P\to R)\land ((\neg P\land \neg Q) \lor (\neg R\land \neg Q)) \\

\equiv{}& (P\to R)\land (\neg P\lor \neg R) \land \neg Q\\

\equiv{}& (\neg P \lor R)\land (\neg P\lor \neg R) \land \neg Q \\

\equiv{}& (\neg P \lor (R \land \neg R)) \land \neg Q \\

\equiv{}& (\neg P \lor \bot) \land \neg Q \\

\equiv{}& \neg P \land \neg Q \end{align} $$

Here I’ve used distribution plenty of times, as well as rules such as

- $(A\to B)\land A \equiv A\land B$
- $(A\to B)\land B \equiv B$
- $(A\lor B)\land A \equiv A$
- $(A\leftrightarrow B)\land A\equiv A\land B$

If you want a more intuitive proof of the forward direction (the more difficult one) that more displays the gist, probably the best thing is to first show the rule that $\vdash (Q \rightarrow P) \vee (R \rightarrow Q)$. This disjunction holds because

- $Q \rightarrow \bot$ entails $Q \rightarrow P$ ($Q \rightarrow \_$ considered as a function preserves entailment, and $\bot \vdash P$),
- $Q$ entails $R \rightarrow Q$,
- $\vdash (Q \rightarrow \bot) \vee Q$ (the law of excluded middle of classical logic).

Given the rule, it’s immediate that

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash ((P \rightarrow Q) \wedge (Q \rightarrow R)) \wedge ((Q \rightarrow P) \vee (R \rightarrow Q))$.

It follows simply from distributivity that the right hand side (and thus the left hand side) of this entailment entails $(P \leftrightarrow Q) \vee (R \leftrightarrow Q)$. And it is easy to show that

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash P \rightarrow R$.

Since a conjunction is entailed if (and only if) both conjuncts are entailed, you’re done (with the forward direction).

Here is an alternative chain-of-equivalences proof, which uses some laws of logic that may not be well-known.

$

\newcommand{\calc}{\begin{align} \quad &}

\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}

\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }

\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }

\newcommand{\endcalc}{\end{align}}

\newcommand{\ref}[1]{\text{(#1)}}

\newcommand{\equiv}{\leftrightarrow}

\newcommand{\then}{\to}

\newcommand{\followsfrom}{\gets}

\newcommand{\true}{\text{true}}

\newcommand{\false}{\text{false}}

$Below, I will use the fact that $\;\equiv\;$ is associative; and to reduce the number of parentheses, I will just write, e.g., $\;\phi \equiv \psi \equiv \chi\;$. Also, I will use the fact that $\;\lor\;$ distributes over $\;\equiv\;$.

We start at the most complex side, and rewrite $\;(P \equiv Q) \;\lor\; (R \equiv Q)\;$ towards the left hand side, under the assumption that $\;P \then R\;$:

$$\calc

(P \equiv Q) \;\lor\; (R \equiv Q)

\op=\hint{$\;\lor\;$ distributes over $\;\equiv\;$}

P \lor (R \equiv Q) \;\equiv\; Q \lor (R \equiv Q)

\op=\hint{$\;\lor\;$ distributes over $\;\equiv\;$, twice}

P \lor R \;\equiv\; P \lor Q \;\equiv\; Q \lor R \;\equiv\; Q \lor Q

\op=\hints{assumption $\;P \then R\;$ means $\;P \lor R \equiv R\;$;}\hint{simplify $\;Q \lor Q\;$; reorder equivalences}

P \lor Q \;\equiv\; Q \;\equiv\; Q \lor R \;\equiv\; R

\op=\hint{write $\;\phi \lor \chi \equiv \chi\;$ as $\;\phi \then \chi\;$, twice}

(P \then Q) \;\equiv\; (Q \then R)

\op=

\hints{write $\;\phi \equiv \psi\;$ as $\;(\phi \land \psi) \lor (\lnot\phi \land \lnot\psi)\;$}

\hint{– to introduce our goal $\;(P \then Q) \land (Q \then R)\;$}

\big((P \then Q) \land (Q \then R)\big) \;\lor\; \big(\lnot (P \then Q) \land \lnot (Q \then R)\big)

\op=\hint{write $\;\phi \then \chi\;$ as $\;\lnot \phi \lor \chi\;$, and DeMorgan, twice}

\big((P \then Q) \land (Q \then R)\big) \;\lor\; (P \land \lnot Q \land Q \land \lnot R)

\op=\hint{contradiction: $\;\lnot Q \land Q \;\equiv\; \false\;$; simplify}

(P \then Q) \;\land\; (Q \then R)

\endcalc$$

Now we can wrap up the proof:

$$\calc

(P \then R) \;\land\; \big((P \equiv Q) \lor (R \equiv Q)\big)

\op=\hint{the above calculation}

(P \then R) \;\land\; (P \then Q) \;\land\; (Q \then R)

\op=\hint{$\;\then\;$ is transitive}

(P \then Q) \;\land\; (Q \then R)

\endcalc$$

- Orbits of action of $SL_m(\mathbb{Z})$ on $\mathbb{Z}^m$
- consecutive prime power
- Dual residual for linearized ADMM
- Questins on Formulae for Eigenvalues & Eigenvectors of any 2 by 2 Matrix
- Integral classes in de Rham cohomology
- Repeated roots for polynomial in $\overline{ \mathbb F_{p}}$
- Visualizing Concepts in Mathematical Logic
- The sum of two continuous periodic functions is periodic if and only if the ratio of their periods is rational?
- Is this a valid partial fraction decomposition?
- Field Extension problem beyond $\mathbb C$
- Is there a faster way to do this? Find an orthogonal matrix $P$ and a diagonal matrix $D$ such that $A=PDP^T$
- Differential equations with dense solutions
- (non?)-surjectivity of the exponential map to $SL(2,\mathbb{C})$
- Integral operator is bounded on $L^p$ if it maps $L^p$ to itself
- Surprising applications of topology