A question on elementary logic

54 Views Asked by At

Suppose, for the sake of discussion, that I am given that the following implication is true: $$q<n \implies \bigg(q<n \iff \sigma(q)<\sigma(n) \iff \sigma(q)/n < \sigma(n)/q\bigg).$$ Assume further that $\sigma(q)/q < \sigma(n)/n$ holds.

Here is my question:

Does it follow (by Exportation) that the implication $$\sigma(q)<\sigma(n) \implies q<n$$ holds?

It is known that $$q<n \implies \bigg(q<n \iff \sigma(q)<\sigma(n) \iff \sigma(q)/n < \sigma(n)/q\bigg)$$ is logically equivalent to $$q<n \implies \bigg(q<n \implies \sigma(q)<\sigma(n) \implies \sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg).$$

I guess it all boils down as to whether $$q<n \implies \bigg(q<n \implies \sigma(q)<\sigma(n) \implies \sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg)$$ can be simplified to $$\sigma(q)/n < \sigma(n)/q \implies \bigg(\sigma(q)<\sigma(n) \implies q<n\bigg),$$ by using the assumption $\sigma(q)/q < \sigma(n)/n$ and Exportation.

MY ATTEMPT

By Exportation, we get that $$q<n \implies \bigg(q<n \implies \sigma(q)<\sigma(n) \implies \sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg)$$ is logically equivalent to $$\bigg(q<n \land q<n\bigg) \implies \bigg(\sigma(q)<\sigma(n) \implies \sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg)$$ This simplifies to $$q<n \implies \bigg(\sigma(q)<\sigma(n) \implies \sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg)$$ which in turn is logically equivalent to $$\bigg(q<n \land \sigma(q)<\sigma(n)\bigg) \implies \bigg(\sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg),$$ again by Exportation. Simplifying, we obtain $$\sigma(q)/n < \sigma(n)/q \implies \bigg(\sigma(q)/n < \sigma(n)/q \implies \sigma(q)<\sigma(n) \implies q<n\bigg).$$ This is logically equivalent to $$\bigg(\sigma(q)/n < \sigma(n)/q \land \sigma(q)/n < \sigma(n)/q\bigg) \implies \bigg(\sigma(q)<\sigma(n) \implies q<n\bigg),$$ still by using Exportation. This simplifies to $$\sigma(q)/n < \sigma(n)/q \implies \bigg(\sigma(q)<\sigma(n) \implies q<n\bigg).$$ Now, together with the unconditional result $\sigma(q)/q < \sigma(n)/n$, the hypothesis $\sigma(q)/n < \sigma(n)/q$ simplifies to $\sigma(q)<\sigma(n)$. Consequently, we have $$\sigma(q)<\sigma(n) \implies \bigg(\sigma(q)<\sigma(n) \implies q<n\bigg).$$ One final application of Exportation then yields the desired result.

IS THIS PROOF CORRECT?

1

There are 1 best solutions below

0
On BEST ANSWER

Your proof cannot be correct, because the result does not follow.

For a counterexample, take $q=\sigma(q) = n =1$, and $\sigma(n)=2$. Then $q<n$ is false, and so the whole implication is automatically true. It is also true that $\sigma(q)/q < \sigma(n)/n$. But it is not true that $\sigma(q) < \sigma(n) \rightarrow q < n$.

Of course, this only tells us that your proof is not correct, and not what is wrong with your proof.

One thing wrong with your proof is that $P \leftrightarrow Q \leftrightarrow R$ is not equivalent to $P \rightarrow Q \rightarrow R \rightarrow Q \rightarrow P$: First of all, the conditional is not associative, so you need parentheses to indicate what that second statement even means, but going by the rest of your proof, you must mean $P \rightarrow (Q \rightarrow (R \rightarrow (Q\rightarrow P)))$. But that is a tautology, and hence not equivalent to $P \leftrightarrow Q \leftrightarrow R$, which clearly is not a tautology.