9
$\begingroup$

Why do we assume the if part when proving if then statements? The truth table of if then is: $$ A=T \land B=T \quad (A \implies B) = T\\ A=T \land B=F \quad (A \implies B) = F\\ A=F \land B=T \quad (A \implies B) = T\\ A=F \land B=F \quad (A \implies B) = T $$

Why don't we show each case? Why do we just assume A and show B?

$\endgroup$
3
  • 1
    $\begingroup$ I don't see any assumptions here. Are you reading the right-hand side as, for example, "If A, then B = T", rather than "A => B is true"? $\endgroup$
    – chepner
    Dec 14, 2023 at 15:35
  • $\begingroup$ I meant that $A\implies B$ is true. @chepner $\endgroup$
    – mawaior
    Dec 14, 2023 at 16:42
  • 1
    $\begingroup$ Don't compare boolean variables to truth values. Presumably, by A = T, you mean A == True, which is the same as just A. If you just write A∧B rather than A = T ∧ B = T, then we don't have to parse the order operations, and it's a lot easier to read. $\endgroup$ Dec 15, 2023 at 6:46

10 Answers 10

31
$\begingroup$

Notice that if $A$ is false, it doesn't matter whether $B$ is true or not: the if statement comes out true either way. This is called Vacuous Truth.

The only thing that might make the statement fail is $A$ true and $B$ false. So we have to confirm any one of three equivalent things:

  • that assuming $A$ to be true forces $B$ to be true
  • that assuming $B$ to be false forces $A$ to be false - this statement is called the contrapositive of the original
  • that assuming both $A$ to be true and $B$ to be false causes a contradiction (note that any contradiction whatsoever will do: the principle of explosion says that a falsehood can imply absolutely anything)

Actually, there's two others, both of which are vacuous truths, which isn't terribly exciting:

  • If $A$ is always false then it doesn't matter what $B$ is, the implication is "true"
  • Similarly if $B$ is always true, then it doesn't matter what $A$ is
$\endgroup$
9
  • 3
    $\begingroup$ We could also proceed by showing that it is impossible for A to be true and B false, by providing an argument that shows such an assumption to entail a contradiction. $\endgroup$ Dec 14, 2023 at 12:23
  • 2
    $\begingroup$ Yes, @MariuszPopieluch, but how is that not a specific variation on the more general theme of assuming A true and proving that that leads to B also being true? $\endgroup$ Dec 14, 2023 at 15:03
  • $\begingroup$ Why don't we show that the assumption is false? $\endgroup$
    – mawaior
    Dec 14, 2023 at 16:45
  • 1
    $\begingroup$ @mawaior showing that the assumption is false also works. There are many different ways to show that A→B; its just that assuming A and then proving B is a particularly popular one. $\endgroup$ Dec 14, 2023 at 17:23
  • 1
    $\begingroup$ @mawaior - what you choose to show (how you choose go about proving) is a consideration separate from the truth table. You're not proving the truth table. Think of it like this. You have some set of individual elements ("the universe"), each of which has some combination of properties, A & B, associated with it. Not necessarily all possible combinations. To prove the implication, what you're trying to do is demonstrate that for all elements that are present, their individual combinations of A & B all give the value 'true' in the truth table. $\endgroup$ Dec 14, 2023 at 21:28
11
$\begingroup$

Why don't we show each case? Why do we just assume A and show B?

You are definitely allowed to show each case individually! But the amazing thing is that assuming A and then showing B always gives the same answer. This is called the deduction theorem: any time you assume A and then prove B, it will match the results of using a truth table.

$\endgroup$
3
  • $\begingroup$ Oh so theoretically we should prove each case but because of deduction theorem it is enough to assume A and show B because when we assume A and show B it covers all cases because of deduction theorem. Am I right? $\endgroup$
    – mawaior
    Dec 14, 2023 at 17:06
  • $\begingroup$ @mawaior correct. The deduction theorem is based on combining the conditional proof with the tautologies P→(Q→P) and (P→(Q→R))→((P→Q)→(P→R)) in a special way (the page I linked has a proof). And we can check that those two tautologies are true by checking their truth tables. $\endgroup$ Dec 14, 2023 at 17:17
  • $\begingroup$ @mawaior or perhaps more simply: the deduction theorem is true because anytime A is false, A→B is true. If we check the cases when A is true, that's enough. (Or we can check the cases when B is false. Whatever is most convenient.) $\endgroup$ Dec 14, 2023 at 17:21
7
$\begingroup$

The only claim that a statement of the form “If P, then Q” is making is that P cannot be true without Q’s also being true. So the only way the claim can be false is for there to be some situation in which P holds while Q fails to hold.

Thus, the way to prove the claim directly is to show that Q holds whenever P does. That is why one explores only the universe of situations in which P holds, to see whether there is then any way for Q to fail to hold.

$\endgroup$
6
$\begingroup$

Notice that $A\implies B$ is true when $B$ is true, regardless of the truth of $A$. Notice also that $A \implies B$ is true when $A$ is false, regardless of the truth of $B$. Finally, notice that if $A\implies B$ is true, then either $A$ is false, or $B$ is true. So to prove that $A \implies B$, it is both necessary and sufficient to either prove that $A$ is false, or prove that $B$ is true.

This sounds odd, too simplistic. But that is because typically $A$ and $B$ will involve some variable $x$ (or more variables, but I will just discuss one), and what we are really doing is proving the statement:

For all $x, A(x) \implies B(x)$.

It is not the implication itself that must be proved by assumptions, but rather the quantization (the "for all"). This requires proving not one statement, but often infinitely many distinct statements, one for each potential value of $x$. For some values of $x, A(x)$ is true, and for the rest, it is false. But since $A$ being false is sufficient to prove that $A \implies B$ is true, in that latter case, there is nothing more to prove. The very fact that $A(x)$ is false is enough.

So to prove $A(x) \implies B(x)$, we only need to handle the values of $x$ for which $A(x)$ is true. And for those $x$, we need to show $B(x)$ is true.

Or, as Dan Uznanski has discussed, we could instead note that when $B(x)$ is true, nothing more needs to be done, and we need only handle the cases where $B(x)$ is false. There, what we need to show is that $A(x)$ is false.

$\endgroup$
5
$\begingroup$

"Why do we assume the if part when proving if then statements? [...] I meant that $A\implies B$ is true."

I think I know where the source of the confusion is: The mathematical statement $A\implies B$ is not 100% aligned with how "if this than that" is used in everyday conversation. It's not a statement about causality. We're not assuming A causes or leads to B, and we're not assuming the statement itself is reflecting the reality of the situation.

It just means "(I claim that) whenever A is true, B happens to be true also (for whatever reason)". In other words, you're making the claim that whenever A occurs, B co-occurs with it (but not necessarily vice versa).

The truth table covers all the possibilities abstractly, but in a concrete situation where there are many individual examples, you may or may not have representative examples for each truth value combination.

If you then take all the available examples, evaluate A and B, and the truth value of the overall statement for each individual case, you can draw conclusions about that set of examples. If there is even a single case for which the overall statement evaluates to false, then the statement is not true in general.

We don't care about any case where A isn't true (or doesn't occur), because we're not really making any statement about such cases - there, we consider the overall statement to be vacuously true by definition.


E.g, suppose you're drawing cards from a standard deck of playing cards, and let the statement be
"whenever you draw a non-court card (A), there will be a number on it (B)"
Or:
"if you draw a non-court card (A), then there will be a number on it (B)"
Or:
$\text{non_court_card} \implies \text{number}$

Truth values of the statement for various cases:

  • A is not a court card and has a number on it - the statement is true
  • A is not a court card and has a letter on it (the aces) - the statement is false
  • A is a court card - the statement doesn't apply, so we consider it vacuously true (by definition).

enter image description here

So here, this particular implication is not true in general. We didn't assume the if part - the if part was a claim that turned out not to be universally true in this context.


Consider now this:
"whenever you draw a court card (A), there will be a letter on it (B)"
Or:
"if you draw a court card (A), then there will be a letter on it (B)"
Or:
$\text{court_card} \implies \text{letter}$

Cases:

  • A is not a court card - the statement doesn't apply, so we consider it vacuously true (by definition). This includes numbered cards, but also the aces.
  • A is a court card - you can see that the statement is satisfied in every case.

enter image description here

This means that the statement is true for the entire set.
(This is why the unusual idea of vacuous truth is useful - otherwise, the "non applicable" cases would be excluded.)

$\endgroup$
3
  • $\begingroup$ My confusion is not about assuming A. We assume A and shot that B is true in order to show $A \implies B$ is true. The problem I have is that we don't show that the other cases have the same truth values as implication has. $\endgroup$
    – mawaior
    Dec 14, 2023 at 20:24
  • $\begingroup$ There is a typo it is supposed to be show. *show $\endgroup$
    – mawaior
    Dec 14, 2023 at 20:35
  • $\begingroup$ @mawaior So, in my second example with the cards, suppose A is false. Whatever B is, $A \implies B$ will be true (according to the truth table). There's nothing to show. It's automatically true. It doesn't matter if the cases are actually present or not. It would be true if you removed some or all of the aces from the set you're considering, or some or all the numbered cards, or both. Or even if you remove the court cards. It only becomes a problem if there existed a court card with a number on it. $\endgroup$ Dec 14, 2023 at 20:53
5
$\begingroup$

The implication $A \implies B$ is defined as $$\text{Not-}A \text{ or } B.$$

So, to prove that the implication $A \implies B$ is true, we can consider two cases:

Case 1. Suppose $\text{Not-}A$ (i.e. $A$ is false). Then $\text{Not-}A \text{ or } B$ is true. So, by definition, the implication $A \implies B$ is true.

Case 2. Suppose $A$ (i.e. $A$ is true). Now we actually have to do some work showing that $B$ is true.

Case 1 always automatically works out as above. Which is why we usually don't bother stating it and instead jump straight to Case 2.

$\endgroup$
4
$\begingroup$

Think of things this way: the meaning of "if" is essentially tied to its inferential behaviour.

"If" is the connective such that an inference from an if ... then ... proposition like A, if then A then C, hence C is plainly correct, and likewise an inference to an if ... then ... proposition of the form Suppose A, then [mumble, mumble] C follows: so if A then C is plainly correct too. (Both these forms of inference are of course basic to the ways we handle conditionals in everyday reasoning and in mathematical reasoning alike.)

Imagine, if you like, encountering a new language with what looks like a connective $\diamond$. How would you tell that it means "if" rather than e.g. "and"? Not by asking the locals about truth-tables which thy probably have never heard of (their Frege hasn't been born yet!). Rather, you'd look to see if people use it in modus ponens inferences like $A, A \diamond C$, hence $C$, and are willing to assert $A \diamond C$ when they are willing to infer $C$ from the temporary supposition $A$ (do they in effect accept "conditional proof"?).

Now, it is an interesting, indeed surprising, fact that -- given some [disputable!!] background assumptions -- a connective for which modus ponens and conditional proof holds will have the truth-table of the "material conditional". But it is getting things upside down, really, to say that conditional proof is acceptable because of the truth-table, or needs to be justified in the light of the truth-table. Rather, the familiar truth-table is acceptable as representing a conditional connective [given those disputable background assumptions] because it is what is required given we need a conditional connective to allow modus ponens and conditional proof as correct modes of inference.

$\endgroup$
3
$\begingroup$

From the perspective of intuitionistic logic where all proofs are constructive, the only way to prove that $A \implies B$ is to show that given some evidence of $A$ we can construct evidence of $B$. This is sometimes more evident in the inference rule or sequent notations of modus ponens, or in the Curry-Howard correspondence view where a proof of implication is a also a function computing evidence from evidence.

In this perspective, we don’t use truth-tables at all (we cannot even claim that $A$ or $B$ must be true or false!); however, to construct evidence of $B$ from that of $A$ we must assume we have some evidence of $A$. Then later, if in fact we do, we have a way to create evidence of $B$ by following the construction in the proof of the implication.

$\endgroup$
3
$\begingroup$

From a truth table point of view:

If you study the truth table for $P \implies Q$ you will see that the implication is always true when $P$ is false. Therefore we don't have to handle that case. But when $P$ is true, also $Q$ must be true for the implication to be true. Thus we only need to show that $Q$ is true under the assumption that $P$ is true.

$\endgroup$
2
$\begingroup$

It should be noted that the only way $A \rightarrow B$ can be false is by $A$ being true and $B$ being false. Therefore, it suffices to focus on that case. That is, if assuming the truth of $A$ doesn't lead to the falsity of $B$, i.e. it leads to the truth of $B$, then we conclude that $A \rightarrow B$ is a tautology. Else $A \rightarrow B$ is not a tautology.

$\endgroup$
3
  • 1
    $\begingroup$ Why is $A\implies B$ a tautology? A tautology is a statement that all of its "output" values are true. An example: $A\lor \lnot A$ $\endgroup$
    – mawaior
    Dec 14, 2023 at 17:39
  • $\begingroup$ Oh I think I understand what you meant. Basically if A leads to the truth of B it can't lead to the falsity of B which is the only case where $A\implies B$ is false. Am I right? $\endgroup$
    – mawaior
    Dec 14, 2023 at 17:42
  • $\begingroup$ @mawaior you got it :) I hope the comment was helpful. $\endgroup$ Dec 14, 2023 at 19:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .