Here is something I have pondered for a while but because it does not "fit" my current knowledge of "formality" and even legality, I am curious.

Suppose I want to prove A => B. This is equiv. to ~B => ~A. Now, let me assume that is false.. that is, if I assume ~B, then ~B => A. However, let's say I find a counter-example to this statement (I construct one assuming ~B is true but A cannot possibily be true). Then, does this prove A => B?

Maybe I am just missing something obvious. I thought of this one day while working on a proof in graph theory.

Suppose I want to prove A => B. This is equiv. to ~B => ~A.


OK.


Now, let me assume that is false.. that is, if I assume ~B, then ~B => A.


\neg B \rightarrow A is not the negation of \neg B \rightarrow \neg A. Check the truth tables.

\neg B \rightarrow A is not the negation of \neg B \rightarrow \neg A. Check the truth tables.

I know.. you missed what I said. It's "proof by contradiction," only in "reverse."

Perhaps I did miss what you said. It looks to me like you are trying to do the following.

1. Start with \neg B \rightarrow A.
2. Construct a counterexample for 1, thus concluding that 1 is false.
3. Therefore, \neg B \rightarrow \neg A must be true, by negation.
4. Therefore, A \rightarrow B must be true, by contraposition.

But the inference from 2 to 3 is invalid for the reason I stated.

Could you tell me which line(s) misrepresent what you said?

Suppose I want to prove A => B. This is equiv. to ~B => ~A. Now, let me assume that is false.. that is, if I assume ~B, then ~B => A. However, let's say I find a counter-example to this statement (I construct one assuming ~B is true but A cannot possibily be true). Then, does this prove A => B?
Hi Absane,
Finding a counter-example to ~B => A does prove that ~B => A is false, but does not prove that ~B => ~A is true.

(This is the same as what Tom is pointing out.)

Oh ok.. seems Tom2 did understand what I said. It seems you are both correct, but something is nagging at me telling me that I am right.

I think it is this: Assume \neg B is true. Than either \neg B \rightarrow A is true or \neg B \rightarrow \neg A. Isn't this right?

I think it is this: Assume \neg B is true. Than either \neg B \rightarrow A is true or \neg B \rightarrow \neg A. Isn't this right?

No, \neg B might not imply anything about A . For example, B could be the statement "it is raining outside" and A could be "we're having chicken for dinner." So, knowing the weather doesn't tell you anything about what you're having for dinner. You need an additional assumption that either \neg B \rightarrow A or \neg B \rightarrow \neg A must be true.

No, \neg B might not imply anything about A . For example, B could be the statement "it is raining outside" and A could be "we're having chicken for dinner." So, knowing the weather doesn't tell you anything about what you're having for dinner. You need an additional assumption that either \neg B \rightarrow A or \neg B \rightarrow \neg A must be true.

Heh.. that's all I needed.. a simple counter example to my counter example idea. Heh. Thank you. What other kind of assumption might we need?

Suppose I want to prove A => B. This is equiv. to ~B => ~A.

No, its not. The truth tables for A=>B and ~A=>~B are

A B A=>B ~A=>~B
0 0 1 1
0 1 1 0
1 0 0 1
1 1 1 1


Perhaps you are think of equivalence (<=>) rather than implication (=>)?

Yea, I meant <=>.

No, its not. The truth tables for A=>B and ~A=>~B are


What Absane wrote in the part you quoted is correct. If you look closely, you'll see that you mis-transcribed it.

Well here is a new idea. Isn't this true?

Given two statements A and B, at most 2 statements are true, but at least one is true (depending on the truthness of both statements):

A \rightarrow B
A \rightarrow \neg B
\neg A \rightarrow B
\neg A \rightarrow \neg B

Is this correct? Or is my head not on straight again? I figure that this only works if we have all the information required to make such a claim. Like, whether it rains or not says nothing about whether a tornado will form or not. So, we cannot make any kind of connection between the two.

Like... Let A = x is even and B = four divides x.

How this compares to my four statements:
1) False.
2) False.
3) False.
4) True.

Given two statements A and B, at most 2 statements are true, but at least one is true (depending on the truthness of both statements):

A \rightarrow B
A \rightarrow \neg B
\neg A \rightarrow B
\neg A \rightarrow \neg B


I don't know where you're getting this from. No matter what the truth values of A and B are, precisely three of those conditionals are true.

I figure that this only works if we have all the information required to make such a claim.
Then it's not true in general.
Like... Let A = x is even and B = four divides x.
Try A = "x is even" and B = "three divides x".

Then it's not true in general.

Yea I guess. Insn't that the point of proofs? To show that given the minimal conditions, something else is true.

Try A = "x is even" and B = "three divides x".

Yea.. all four are false.

What the hell am i thinking? I supposed I am motivated by trying to figure out many different proof methods.

Absane, I have no idea of how you're assigning those truth values. Let's go back to your earlier examples.

A="x is even" and B="4 divides x".

The truth values of the four conditionals obviously depends on the value of x. You never specify that value and yet, somehow, you proceed to write down truth values of the conditionals anyway.

For instance, you say that A \rightarrow B is false. Not so. If x=3 then that conditional is true. Any conditional with a false antecedent is true.

Oh.. sorry Tom2.. I was assuming that A was true. It's a force of habit.

Yea I guess. Insn't that the point of proofs? To show that given the minimal conditions, something else is true.
True, but mathematics is studied by human beings who do not show equal interest in all theorems :)

Any conditional with a false antecedent is true.
What does this mean? Initially reading this I thought you must have misunderstood something, but it seems Absane is agreeing with you.

przyk,

I haven't misunderstood anything, I assure you. The conditional schema A \rightarrow B has 3 components:

the antecedent, which is A,

the operator, which is \rightarrow,

and the consequent, which is B.

As I said, the truth value of any conditional statement whose antecedent is false, is "T". Just examine the truth table for conditionals.

Actually, since I've posted I think I realize what Absane is doing to get his truth values for his conditionals. He is interpreting the unquantified schema:

A \rightarrow B

as the quantified schema:

\forall (x \in \mathbb{Z})(A \rightarrow B) (where A and B are as he described in his earlier post).

If you quantify the conditional universally like that, Absane's truth value assignments are exactly right. So I guess he's not so much wrong as he is sloppy. :D But strictly speaking, to say that "A -->B" is "false" when A= x is even and B= four divides x, is sheer nonsense. The truth value of the conditional obviously depends on the value of x. But when you quantify the conditional, it does not.