2
$\begingroup$

I understand the general concept, that if you define a statement X such that X = X $\Rightarrow$ Y, you can prove that X is true regardless of Y so you can then prove any statement. What I don't quite understand is how one proves that X is true.

I have tried to prove it using the three main ways of proving an implication, contradiction, contrapositive, and direct, but the last two methods are unsatisfactory.

Contradiction:
Suppose X is true and Y is false.
Then X $\Rightarrow$ Y is false.
But X = X $\Rightarrow$ Y.
X cannot be both true and false. So X cannot be true when Y is false.
So X $\Rightarrow$ Y is true, so X is true.
QED

This way I understand and seems fine, what trips me up is direct and contrapositive, with direct assuming what you are trying to show and contrapositive showing that X is both true and false.

Direct:
Suppose X is true.
Then since X = X $\Rightarrow$ Y is true, and X is true, Y is true.
So X $\Rightarrow$ Y is true, and hence X is true.
QED

This seems to assume what we are trying to prove.

Contrapositive:
Suppose Y is false.
If X is true, then X $\Rightarrow$ Y is false.
But X = X $\Rightarrow$ Y so X is false.
X cannot be both true and false, so X is false.
Therefore X $\Rightarrow$ Y is true, so X is true.
QED

This is troubling because X has been shown to be both true and false.

I guess what I am asking is what is the accepted way to prove that a statement X = X $\Rightarrow$ Y is true to construct Curry's paradox, and why do some proof methods seem incorrect or contradictory?

$\endgroup$
  • $\begingroup$ You'll probably like the ability to post mathematical notation which includes using standard logical operators. You should in any case use parentheses to clarify this post. $\endgroup$ – hardmath Jul 9 '18 at 18:18
  • $\begingroup$ See my recently posted question math.stackexchange.com/questions/2836087/… $\endgroup$ – Dan Christensen Jul 10 '18 at 3:10
  • 1
    $\begingroup$ The point of the paradox is to prove that "Y is true" for arbitrary Y. $\endgroup$ – DanielV Jul 10 '18 at 4:35
  • $\begingroup$ Thanks I have updated the formatting. $\endgroup$ – Aphyd Jul 10 '18 at 5:01
1
$\begingroup$

Both the "direct" and "contrapositive" arguments you gave work just as well as the "contradiction" argument.

The "direct" argument doesn't fall prey to assuming what you are trying to prove. It uses the structure that if we assume $A$ and prove $B$ from that assumption, we obtain $A \implies B$ assumption-free. Using this, we assume $X$ and prove $Y$ (dependent on assuming $X$). Thus we have $X \implies Y$ assumption-free. Then we get $X$ assumption-free by the equivalence of $X \implies Y$ and $X$ -- this is different from the original assumption of $X$ because now it is assumption-free.

The "contrapositive" argument doesn't show $X$ is both false and true. It shows $X$ is false under the assumption that $Y$ is false. This gives us $X \implies Y$ assumption-free, so $X$ is true assumption-free. Nowhere in the course of the argument is $X$ shown to be false assumption-free.

$\endgroup$
  • $\begingroup$ Thanks, this helped me understand. It was just strange to prove a self referencing statement. $\endgroup$ – Aphyd Jul 10 '18 at 4:04
3
$\begingroup$

First of all, $X \leftrightarrow (X \rightarrow Y)$ implies both $X$ and $Y$, and the whole point of the Curry Paradox is to show that $Y$ is true ... $X$ is just a 'helper'.

Second, you can show that $X \leftrightarrow (X \rightarrow Y)$ implies both $X$ and $Y$ in various ways:

First, truth-table:

\begin{array}{cc|c} X&Y&X \leftrightarrow (X \rightarrow Y)\\ \hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F\\ \end{array}

We see that $X \leftrightarrow (X \rightarrow Y)$ is only true in row 1 ... when $X$ and $Y$ are both true

Second, algebra:

$X \leftrightarrow (X \rightarrow Y) \overset{Equivalence}\Leftrightarrow$

$(X \rightarrow (X \rightarrow Y)) \land ((X \rightarrow Y) \rightarrow X) \overset{Implication}\Leftrightarrow$

$(\neg X \lor (\neg X \lor Y)) \land (\neg (\neg X \lor Y) \lor X) \overset{Association, DeMorgan}\Leftrightarrow$

$(\neg X \lor \neg X \lor Y) \land ((X \land \neg Y) \lor X) \overset{Idempotence, Absorption}\Leftrightarrow$

$(\neg X \lor Y) \land X \overset{Reduction}\Leftrightarrow$

$Y \land X$

Third, formal proof:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.