8
$\begingroup$

Let $\mathcal{L}$ be the formal system of statement calculus. Let $A$ be a formula of $\mathcal{L}$. Then each of the three formulas \begin{gather*} A \vee (\sim A) \\ A \implies [(\sim A) \implies A] \\ (\sim A) \implies [A \implies (\sim A)] \\ \end{gather*} is a theorem of $\mathcal{L}$. By case analysis, $$[(\sim A) \implies A] \vee [A \implies (\sim A)]$$ is a theorem of $\mathcal{L}$. But this seems intuitively incorrect.

For example, each of the statements \begin{gather*} (\forall x \in \mathbb{N})[(x < 3) \implies (x \ge 3)]\\ (\forall x \in \mathbb{N})[(x \ge 3) \implies (x < 3)] \end{gather*} is false. However, the disjunction of these two statements is true, by the argument above.

Edit. I guess the example was not very good.

Suppose you flip a coin. It is a fair coin and it cannot stand up on its side. It lands at your feet on a solid, flat surface.

Let $A$ be the statement that the coin shows heads. Then $(\sim A)$ is the statement that the coin shows tails. The statement \begin{gather*} \text{"if the coin shows heads, then it shows tails,}\\ \text{or}\\ \text{if the coin shows tails, then it shows heads"} \end{gather*} is true, even though both disjuncts are false.

Maybe this question no longer belongs on math.stackexchange.com.

$\endgroup$
  • 5
    $\begingroup$ I think the concept of vacuous truth is relevant here. Either $A$ or its negation is true thus it is always the case that one of the implication statements $(\sim A) \rightarrow A$ or $A \rightarrow (\sim A) $ is vacuously true. $\endgroup$ – jdods May 17 '18 at 3:07
  • 1
    $\begingroup$ Consider "if the moon is made of cheese, then the coin shows tails." It's true, since the moon isn't made of cheese. So "if the coin shows heads, then the coin shows tails" is also true if the coin doesn't show heads. $\endgroup$ – Dan Brumleve May 17 '18 at 3:11
  • 2
    $\begingroup$ With your coin example, imagine flipping the coin and it comes up heads. Then "if it is tails, then it is heads" is true vacuously. "False implies true" is true. If the coin hasn't been flipped yet then no truth values are assigned. I think it is confusing since it is not intuitive, but thinking of "if it is tails, then it is heads" as intuitively false is built on the idea of the premise "it is tails" being true. And that is correct! A coin that shows tails certainly does not show heads! $\endgroup$ – jdods May 17 '18 at 3:14
  • 1
    $\begingroup$ @RandyRanderson, also, This question is perfectly suited for mathSE, in my opinion. $\endgroup$ – jdods May 17 '18 at 3:25
  • 9
    $\begingroup$ But obviously $\forall x (x \ge 3) \lor \forall (x < 3)$ (which is FALSE) is NOT equiv to : $\forall x (x \ge 3 \lor x <3)$ (which is TRUE). And this is a perfect counterexample showing that the universal quantifier does not distribute over disjunction. $\endgroup$ – Mauro ALLEGRANZA May 17 '18 at 6:18
8
$\begingroup$

Perhaps what is counter-intuitive is the fact that whenever $A$ is false, then $A\Rightarrow B$ is true, based on how logical implication is defined: $$ \begin{array}{|c|c|c|} \hline A & B & A\Rightarrow B \\ \hline {\bf F} & F & {\bf T}\\ {\bf F} & T & {\bf T}\\ T & F & F\\ T & T & T\\ \hline \end{array} $$

Applied to the example of the coin:

if the coin shows heads, then it shows tails
                     or
if the coin shows tails, then it shows heads

Let's say a coin is flipped, and it shows heads.

Then the following statement is false:

the coin shows tails

and thus the second half of the disjunction is true:

if the coin shows tails, then it shows heads

therefore the whole disjunction is true.

Similarly if tails were shown.

$\endgroup$
  • $\begingroup$ I think it's important to note that while "if the coin shows tails, then it shows heads" sounds false by intuition and in terms of natural language, this intuition is based on the idea that when a coin actually shows tails, this means that it certainly does not show heads. In otherwise, the intuition is based on the premise of the implication being true. (This is not really a comment on this answer, I just wanted to add this for the general audience.) $\endgroup$ – jdods May 18 '18 at 2:00
26
$\begingroup$

$$ (\forall x \in \mathbb{N})[x < 3 \implies x \ge 3] \lor (\forall x \in \mathbb{N})[x \ge 3 \implies x < 3] $$ is not true, and your analysis doesn't imply that it ought to be.

What is true by your argument is $$ (\forall x \in \mathbb{N})\bigl[(x < 3 \implies x \ge 3) \lor (x \ge 3 \implies x < 3)\bigr] $$ but you can't move the quantifiers into the middle of its structure and expect it to remain true.


In general, $(A\to B)\lor(B\to A)$ is always true in classical logic, no matter whether $A$ and $B$ are negations of each other or not. Perhaps even more intuition-challenging, $(A\to B)\lor(B\to C)$ is always true too.


Response to edit: I think you're being confused by two different uses of "if ... then" in mathematical English.

  1. On one hand in casual non-formal mathematical English, "if it's heads, then it's tails" would mean something like

    In every relevant situation where it's heads, it is also the case that it's tails.

    (and one then hopes that the context makes it clear which situations are "relevant").

  2. On the other hand, in (classical) formal logic, the formula "${\rm heads}\Rightarrow{\rm tails}$" means

    In the particular situatation we're looking at, it is not the case that it is heads yet it isn't tails.

    Which is the same as saying

    The particular situation we're looking at is not a counterexample to sense (1).

Confusion creeps in because "${\rm heads}\Rightarrow{\rm tails}$" is often pronounced "if heads then tails", as if its meaning were the same as in (1), but it is not when formulas are involved.

The sense in which you can prove that $(A\Rightarrow \neg A)\lor(\neg A\Rightarrow A)$ is true is (2) and only (2). It stops being true if you try to reinterpret the $\Rightarrow$s as if they meant (1).


Furthermore it it looks like you're also confusing yourself by the difference between "is true" and "has a proof" when you say that "this or that" is true but "this" and "that" are both false.

What you mean here is that you believe you have a proof of "this or that". But clearly it is not true because the definition of "or" is that "this or that" is true exactly when at least one of "this" and "that" is true -- and you have just argued that they are both false.

So when you ask,

How can "this" be false and "that" be false and "this or that" be true?

the answer is that they can't and you're mistaken about at least one of those parts. Same as if you have an apparent proof that concludes $2+2=3$: you shouldn't be asking "why is $2+2$ not $4$?" but "what is wrong with this thing that looks like a proof but obviously can't be?"

$\endgroup$
  • $\begingroup$ Do you have any comments on the edit? $\endgroup$ – Randy Randerson May 17 '18 at 3:00
  • 2
    $\begingroup$ @RandyRanderson: In your edit, the misplaced quantifiers are hiding behind the ambiguities of English. You're implicitly quantifying over all possible results of the coin flip, and you're performing this quantification in the wrong place. $\endgroup$ – user2357112 May 17 '18 at 5:54
  • $\begingroup$ @RandyRanderson think through the second 2 givens in the coin example. Why is it that if the coin shows heads on the first flip then 'coin shows trails in the first flip implies coin shows heads on the first flip'? Well it's because the final statement is true, and literally anything implies a true statement. This breaks down if we swap out the event A for another event, say by flipping the coin again. $\endgroup$ – Artimis Fowl May 17 '18 at 6:32
  • $\begingroup$ @RandyRanderson: I've updated with an extended attempt to explain. $\endgroup$ – Henning Makholm May 17 '18 at 11:42
  • $\begingroup$ +1 for $(A\implies B)\vee(B\implies C)$ is always true. Had to actually think about that one it's a really nice one. $\endgroup$ – DRF May 17 '18 at 13:01
12
$\begingroup$

For any arbitrary $x$ you have the schema: $\phi(x)\vee\psi(x)$

$$(A(x)\to\neg A(x))~\vee~(\neg A(x)\to A(x))$$

This does not suggest that: $(\forall x~\phi(x))~\vee~(\forall x~\psi(x))$.

What the schema means is that: $\forall x~(\phi(x)\vee\psi(x))$ .

$$\forall x~[(A(x)\to\neg A(x))\vee(\neg A(x)\to A(x))]$$

In breif; the schema must always be applied to the same entity.   The universal quantfier will not distribute over disjunction.


Then the statement, "if the coin shows heads, then it shows tails, or if the coin shows tails, then it shows heads" is true, even though both disjuncts are false.

Oh, no, you will find that they are not both false; one will always be true.   Let us look closer.

Okay, I just flipped a coin and it shows tails.   I can thereby truthfully asset that "If this coin shows heads, then it shows tails."   That material conditional statement is held to be true (since the antecedant is false).

Okay, I just flipped several more coins and now have one showing heads.   I can now truthfully asset that "If this coin shows tails, then it shows heads," because now that material conditional statement is the one held to be true.

So whatever coin toss I have, if it shows heads or tails, then one from the two conditional statements will hold true.   (Indeed, only one will hold true for any coin toss.)

$\endgroup$
5
$\begingroup$

The statement $$(x<3)\to (x\ge 3)$$ is not a contradiction, i.e. it is not ALWAYS false. It is merely false for $x<3$. If $x\ge 3$, then it is vacuously true. It contains a free variable, so we can't say that it is false.

The implications are confusing the issue. Consider the statement $x<3$ alone. It is not necessarily true. Also, the statement $x\ge 3$ is not necessarily true. But their disjunction is true.


The OP's edit makes no difference. What appears to be confusing OP (and confuses many learners of mathematics) is that $p\to q$ is true when $p$ is false. What I find helps is the theorem that $p\to q$ is equivalent to $q\vee \neg p$.

$\endgroup$
  • $\begingroup$ See edit....... $\endgroup$ – Randy Randerson May 17 '18 at 2:29
4
$\begingroup$

The issue is that the universal quantifier does not distribute over disjunction. Instead, consider the statement:

$\forall_{x \in \mathbb{N}}((x \lt 3 \rightarrow x \geq 3) \vee (x \geq 3 \rightarrow x \lt 3))$

This statement is true, by the propositional argument you gave.

$\endgroup$
-1
$\begingroup$

$ [A \to \neg A] \leftrightarrow [\neg A \vee \neg A] \leftrightarrow \neg A $

$ [\neg A \to A] \leftrightarrow [A \vee A] \leftrightarrow A $

So, you can see that $ [A \to \neg A] \vee [\neg A \to A]$ is the same as $ A \vee \neg A $

So this is true:

$ \forall x : P(x) \vee \neg P(x) $

But, and this is where your intuition went down the wrong path, this is not generally true:

$ [\forall x : P(x)] \vee [\forall x : \neg P(x)] $ as your number example showed.

$\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.