hossameldeen/why-implication-is-true-for-false-hypotheses

## why-implication-is-true-for-false-hypotheses
This was written in response to: https://twitter.com/hillelogram/status/1227118562373963776

===

People mix the predicate "If a directed graph is a tree, it's a DAG" with the proposition "For all directed graphs, if a directed graph is a tree, it's a DAG".

First, for simplification: let's assume we're talking here about all graphs in the world with up to 10 nodes to be able to enumerate them. Also, note that we're talking about directed, not undirected, graphs.

To prove the proposition "For all..." is true, which is "(For graph G1, if it's a tree, it's a DAG) AND (For graph G2, if it's a tree, it's a DAG) AND...", since it's ANDs, we need to prove (For graph G1, if...) is true and we need to prove (For graph G2, if...) is true, ... etc.

Now, some of these Gs are trees and some are not. If you define the implication to return false if its first part is false, then you'll have some FALSEs between the ANDs and the "For all..." would've been false although we know it should be true (All trees are DAGs, we know it's true).

But if you define the implication to return true if its first part is false, then you won't need to look at the cases where the graph is not a tree, which matches our understanding! ... You'd only need to go through the cases where Gx is a tree and show that it's a DAG in these case.

Put another way: saying the implication returns true if a graph is non-tree does NOT prove the proposition "For all graphs...", it only returns true for that case where the graph is non-tree. To prove "For all graphs...", we'd need to go through all graphs and see that for ALL of them the implication is true (either by a graph being a tree and a DAG, or by a graph being a non-tree).

I'd written another example/in another way before writing this one .. but I edited it and stopped in-between. But here it is anyway:

"""
People mix between the predicate "If I the train comes by nine, I'll be home by ten" and between the proposition "For all the times the train may come at, if the train comes by nine, I'll be home by ten".

If the train doesn't come by 9, you ask: Should the implication be true?

The answer: Depends on what you're asking about! ... If you're asking about the predicate, then yes, the predicate FOR THAT CASE would be true (we'll see why that is useful in a second). If you're asking about the proposition "For all...", the answer is: we don't know; we'd need to go through all cases/possible timelines and see.

Now, for "appreciating" why defining the implication predicate to be TRUE when its first part is false: In our example, to prove "For alll...", do you need to go through the cases where the train doesn't come by 9? No!

Define it otherwise. Define it to be FALSE if the first part is false and see what would happen.

In that case, we'd say that when the train doesn't come by 9, the predicate "If the train..." is false. Now, imagine if all the timelines in which the train came by nine I was home by 10! In that case, the proposition "For all..." would be FALSE although it's in your understanding should be true!

Okay, the timelines may be hard to grasp (and non-scientific, probably). Let's talk about a more realistic example. Also, we'll look at it from another point of view this time:

Let's say we're trying to prove "If a directed graph is a a tree, it's a DAG". To be able to enumerate all cases, let's say we're implicitly talking about graphs of up to 10 nodes.

We think: If we have a non-tree graph, then the predicate FOR THAT graph would be true ... but that shouldn't be enough to prove it for all graphs!

And indeed it isn't enough. The non-tree graph didn't prove it for all graphs. To prove it for all graphs, we'd need to go through all graphs.

Now, ask yourself:

If we say it should be false for the non-tree graphs

Again, you ask yourself: If a directed graph is not a tree, should the implication be true?

The answer: The implication for THAT non-tree graph should be true! (the predicate). But this does NOT mean that "For all directed graphs, if a directed graph is a tree, it's a DAG". To prove the "For all...", you'd need to go through all the graphs and see.

Now: What if you define the implication
"""
	This was written in response to: https://twitter.com/hillelogram/status/1227118562373963776

	===

	People mix the predicate "If a directed graph is a tree, it's a DAG" with the proposition "For all directed graphs, if a directed graph is a tree, it's a DAG".

	First, for simplification: let's assume we're talking here about all graphs in the world with up to 10 nodes to be able to enumerate them. Also, note that we're talking about directed, not undirected, graphs.

	To prove the proposition "For all..." is true, which is "(For graph G1, if it's a tree, it's a DAG) AND (For graph G2, if it's a tree, it's a DAG) AND...", since it's ANDs, we need to prove (For graph G1, if...) is true and we need to prove (For graph G2, if...) is true, ... etc.

	Now, some of these Gs are trees and some are not. If you define the implication to return false if its first part is false, then you'll have some FALSEs between the ANDs and the "For all..." would've been false although we know it should be true (All trees are DAGs, we know it's true).

	But if you define the implication to return true if its first part is false, then you won't need to look at the cases where the graph is not a tree, which matches our understanding! ... You'd only need to go through the cases where Gx is a tree and show that it's a DAG in these case.

	Put another way: saying the implication returns true if a graph is non-tree does NOT prove the proposition "For all graphs...", it only returns true for that case where the graph is non-tree. To prove "For all graphs...", we'd need to go through all graphs and see that for ALL of them the implication is true (either by a graph being a tree and a DAG, or by a graph being a non-tree).

	I'd written another example/in another way before writing this one .. but I edited it and stopped in-between. But here it is anyway:

	"""
	People mix between the predicate "If I the train comes by nine, I'll be home by ten" and between the proposition "For all the times the train may come at, if the train comes by nine, I'll be home by ten".

	If the train doesn't come by 9, you ask: Should the implication be true?

	The answer: Depends on what you're asking about! ... If you're asking about the predicate, then yes, the predicate FOR THAT CASE would be true (we'll see why that is useful in a second). If you're asking about the proposition "For all...", the answer is: we don't know; we'd need to go through all cases/possible timelines and see.

	Now, for "appreciating" why defining the implication predicate to be TRUE when its first part is false: In our example, to prove "For alll...", do you need to go through the cases where the train doesn't come by 9? No!

	Define it otherwise. Define it to be FALSE if the first part is false and see what would happen.

	In that case, we'd say that when the train doesn't come by 9, the predicate "If the train..." is false. Now, imagine if all the timelines in which the train came by nine I was home by 10! In that case, the proposition "For all..." would be FALSE although it's in your understanding should be true!

	Okay, the timelines may be hard to grasp (and non-scientific, probably). Let's talk about a more realistic example. Also, we'll look at it from another point of view this time:

	Let's say we're trying to prove "If a directed graph is a a tree, it's a DAG". To be able to enumerate all cases, let's say we're implicitly talking about graphs of up to 10 nodes.

	We think: If we have a non-tree graph, then the predicate FOR THAT graph would be true ... but that shouldn't be enough to prove it for all graphs!

	And indeed it isn't enough. The non-tree graph didn't prove it for all graphs. To prove it for all graphs, we'd need to go through all graphs.

	Now, ask yourself:

	If we say it should be false for the non-tree graphs

	Again, you ask yourself: If a directed graph is not a tree, should the implication be true?

	The answer: The implication for THAT non-tree graph should be true! (the predicate). But this does NOT mean that "For all directed graphs, if a directed graph is a tree, it's a DAG". To prove the "For all...", you'd need to go through all the graphs and see.

	Now: What if you define the implication
	"""