Undergrad Understanding Implication Problems: Examples & Explanations

[Avatrin]

(1) Given: b
(2) Suppose: a
(3) By implication with (2) and (1), a→b

I just saw this proof... And, I don't understand why this is true. How am I supposed to think about problems like this one?

Edit:
Here's another one:

(1) Given: (p∧q)→r
(2) Suppose: p
(3) Suppose: q
(4) By conjunction with (2) and (3), p∧q.
(5) By MP with (1) and (4), r
(6) By implication with (3) and (5), (q→r)
(7) By implication with (2) and (6), p→(q→r)

The only steps here I understand are 1 to 5. I don't know why 6 and 7 are true.

 

[Delta2]

We know that an implication A→B is true when A and B are both true. So apply this for A= q B=r (have proved that q and r are true from steps 1-5), and then for A=p, B=q→r

 

[andrewkirk]

The only steps here I understand are 1 to 5. I don't know why 6 and 7 are true.

Line 2 makes an assumption, and thereby opens what is called a conditional proof (CP). The conditional proof is closed by discharging the assumption that made it, at a later line. We'll come to what that means shortly.

Conditional proofs can be nested within each other. Above there are two CPs, one commencing at 2 and ending at 7, the other commencing at 3 and ending at 6. The last line of a CP closes the proof by asserting A->B, where A was the assumption that opened the proof and B is the statement immediately before the closing line. Closing the proof 'discharges' the assumption A, which means that A is no longer assumed but, in its place, we have A->B, which is valid everywhere from there on within the next enclosing CP.
All interim results deduced inside a CP are invalid outside it, except for the closing statement.

So line 6 closes the inner CP giving the result (3)->(5)
Then line 7 closes the outer CP giving the result (2)->(6)

The first example is actually written in a confusing manner. A better way to write it is:
(1) Given: b
(2) Suppose: a
(3) b (from 1)
(4) By implication with (3) and (1), a→b
Written that way, we see that a CP is opened at (2) and closed at (4) with the statement (2)->(3).

It's possible to loosen the rules for closing CPs so that the antecedent of the closing statement (the statement after the arrow ->) can be any statement that is in scope at that point. That is the approach that was taken in the first example. But that requires explicitly laying out the scoping rules, which may be more complex than you want to get.

 

[Avatrin]

I am still having issues understanding this, so we may have to go deeper.

For instance, in the first proof, we know b is true, and we are assuming a is true as well. Why does this imply a→b? Why not b→a?

 

[FactChecker]

These are sort of degenerate implications. In the first example, once you know that b is always true, anything will imply b. Remember that a -> b is equivalent to "b or not a". Since b is given, "b or not a" is always true no matter what a is. So a->b is always true no matter what a is. The second example is more complicated but similar.

 

[verty]

Does this make sense?

Given $p \lor q$:
Suppose $\lnot p$.
$q$
$\lnot p \to q$

 

[andrewkirk]

Why does this imply a→b? Why not b→a?

It is the first and not the second because that's how the inference rule for conditional proofs works. We open a proof at line n with statement P, and close it at statement m>n with the statement P->Q, where Q is the statement on line m-1 (or, more generally, any statement made between lines 1 and m-1 inclusive, excluding statements that were made on lines interior to conditional proofs that were closed before line m+1. All lines of a CP are 'interior to' the CP, except its last line).

It's not clear whether your uncertainty is about how the inference rule was applied in this particular case, or in why the inference rule is written that way.

 

[Stephen Tashi]

For instance, in the first proof, we know b is true, and we are assuming a is true as well. Why does this imply a→b? Why not b→a?

The notation you are using distinguishes between being "given" a statement and "assuming" a statement. In many contexts of writing about mathematics, we don't make such a distinction. For example, if we are working a trigonometry word problem where certain information is "given", we might also say the information is "assumed".

The material you are studying deals with reliable patterns of reasoning. In the particular pattern:
Given B:
Assume A:
Conclude: A implies B

We do not conclude A is true. We could conclude B is true because it is "given". That is the distinction being made between "given" and "assume".

As other have noted, this pattern of reasoning is valid, but not very prominent in writing typical mathematical proofs. On a page of a mathematics text, certain definitions and theorems have been established on previous pages. It would be rare for an author to bother saying that some hypothesis on the page implies the results established on previous pages.


The more common pattern is:
Assume A
Prove B (by some method)
Conclude: A implies B

In this pattern, we cannot conclude that A is true and we cannot conclude that B is true. We only conclude the implication is true.