Formal Proof: (a iff (b iff c)) iff ((a iff b) iff c)

  • Thread starter tgt
  • Start date
  • Tags
    Proof
In summary, the conversation is about trying to prove the statement (a iff (b iff c)) iff ((a iff b) iff c)) using deduction rules. The method of using a truth table is suggested but the aim is to use deduction rules. The concept of contradictions and tautologies is also discussed, with the conclusion that deductions are always tautologies. Examples are provided to illustrate this concept. Finally, the conversation touches on the use of definitions and reducing statements to a canonical form.
  • #1
tgt
522
2

Homework Statement


GIve a formal proof or derivation of:

(a iff (b iff c)) iff ((a iff b) iff c))

The Attempt at a Solution


I've tried it for a long time. Idea is to assume (a iff (b iff c)) then get ((a iff b) iff c)) and then vice versa. BUt no matter how I try, I always get some if conditions istead of the iff.
 
Last edited:
Physics news on Phys.org
  • #2
Well, the most brain-dead way is to write down a truth table, and invoke the fact that a proposition is a tautology if and only if all of the entries in its truth table are "true".
 
  • #3
Hurkyl said:
Well, the most brain-dead way is to write down a truth table, and invoke the fact that a proposition is a tautology if and only if all of the entries in its truth table are "true".

The aim was to use deduction rules to prove it. In other words to deduce it all. That is the method I'm trying to use to prove it.
 
  • #4
Hurkyl said:
Well, the most brain-dead way is to write down a truth table, and invoke the fact that a proposition is a tautology if and only if all of the entries in its truth table are "true".

Just thinking about it, deductions are always tautologies. i.e if one is asked to deduce B from A, A and B are the same statement but in different form.
 
  • #5
tgt said:
Just thinking about it, deductions are always tautologies. i.e if one is asked to deduce B from A, A and B are the same statement but in different form.
Not so. The simplest counterexample is probably to let A be "contradiction" and to let B be "tautology". You can deduce B from A, but I doubt you could argue that they are "the same statement but in a different form".

(I chose contradiction and tautology because they appear in the two trivial proofs: you can deduce anything from a contradiction, and from anything you can deduce a tautology)
 
  • #6
How about the solution to the OP? It seems impossible but it is so obvious.
 
  • #7
Hurkyl said:
Not so. The simplest counterexample is probably to let A be "contradiction" and to let B be "tautology". You can deduce B from A, but I doubt you could argue that they are "the same statement but in a different form".

(I chose contradiction and tautology because they appear in the two trivial proofs: you can deduce anything from a contradiction, and from anything you can deduce a tautology)

What do you mean by being able to deduce anything from a contradiction?

Is that this: Suppose we have a contradiction then we add the negation of the thing we are trying to deduce at the beginning of the contradiction. Then the end result is that we have deduced the thing we are trying to prove.

i.e Assume

John is dead,
Tim has a bread,
Tim does not have a bread
Contradiction!
Hence John is not dead.

But we could just as easily prove John is dead by reversing things.
 
  • #8
tgt said:
Then the end result is that we have deduced the thing we are trying to prove.
...
But we could just as easily prove John is dead by reversing things.
That is exactly correct. Such is the nature of contradictions.
 
  • #9
tgt said:
How about the solution to the OP? It seems impossible but it is so obvious.

Just use the definition:

A=>B is not(A) OR B

Plug things in and reduce both sides to some canonical form.
 
  • #10
Hurkyl said:
That is exactly correct. Such is the nature of contradictions.

What about the example,

Phil is gone,
John is dead,
Tim has a bread,
Tim does not have a bread
Contradiction!

Now we could choose between concluding
John is not dead and Phil is not gone?

Any choice would be okay?What about the example,

John is dead,
Suppose there are finitely many primes,
Conclude a contradiction that the product of those primes plus 1 cannot be a prime nor not a prime.

Now we can either conclude John is not dead or There are infinitely many primes. EIther choice being correct?What about the example,

pi is an irrational number
Suppose there are finitely many primes,
Conclude a contradiction that the product of those primes plus 1 cannot be a prime nor not a prime.

Now we can either conclude pi is rational or There are infinitely many primes. EIther choice being correct?
 
  • #11
matt grime said:
Just use the definition:

A=>B is not(A) OR B

Plug things in and reduce both sides to some canonical form.

I've worked out the problem using the technique of deduction.
 
  • #12
Phil is gone,
John is dead,
Tim has a bread,
Tim does not have a bread
Contradiction!
This seems to me to be nonsense, not a contradiction. Presumably, the way this is laid out, the first three statements are the hypothesis, and the fourth is the conclusion. Because Phil being gone and John being dead have nothing to do with Tim having bread, it seems to me that this can be reduced to
Tim has bread ==> Tim doesn't have bread
This is not a contradiction. If Tim has bread, then it is not true that he doesn't have bread, so the first statement does not imply the second. If Tim indeed doesn't have bread, then the first statement isn't true, so any statement at all could be appear as the conclusion, and the implication would be true, but meaningless.

BTW, in English, we don't say someone has "a bread": we say someone has bread or has a loaf of bread.
 
  • #13
Mark44 said:
This seems to me to be nonsense, not a contradiction. Presumably, the way this is laid out, the first three statements are the hypothesis, and the fourth is the conclusion. Because Phil being gone and John being dead have nothing to do with Tim having bread, it seems to me that this can be reduced to
Tim has bread ==> Tim doesn't have bread
This is not a contradiction. If Tim has bread, then it is not true that he doesn't have bread, so the first statement does not imply the second. If Tim indeed doesn't have bread, then the first statement isn't true, so any statement at all could be appear as the conclusion, and the implication would be true, but meaningless.

BTW, in English, we don't say someone has "a bread": we say someone has bread or has a loaf of bread.

You are misunderstood. All 4 statements are intended to be the hypothesis which we arrive at a contradiction. The conclusion is that one of the hypothesis was wrong.
 
Last edited:
  • #14
Maybe I misunderstood, but I wasn't misunderstood, since you apparently understood what I was saying.

It wasn't clear to me which statements were the hypothesis, and which were the conclusion. Going back to your syllogism, let's throw out the statements about Phil and John, since they don't have anything to do with anything. That leaves us with a hypothesis of (Tim has bread) AND (Tim does not have bread). This hypothesis can never be true, so you could have any conclusion, and overall the implication would be true.

For any implication, p ==> q, the implication will be true or valid under three circumstances, and false or invalid under one circumstance. The three true circumstances are:
1. p is true and q is true.
2. p is false and q is true.
3. p is false and q is false.

The invalid circumstance is:
4. p is true and q is false.

Depending on what you have for the conclusion, your syllogism of Tim having and not having bread falls into the 2nd or 3rd category.
 
  • #15
tgt: you seem to be confusing this example of a vacuous proof with proof by contradiction.

Here are three valid arguments:

Tim has a bread.
Tim does not have a bread.
Therefore, John is dead

Tim has a bread.
Tim does not have a bread.
Therefore, John is alive.

Phil is gone implies Tim has a bread.
Phil is gone imples Tim does not have a bread.
Therefore, Phil is not gone.


The first two are an example of "contradiction implies anything". The third is an example of proof by contradiction.
 
  • #16
Mark44 said:
Maybe I misunderstood, but I wasn't misunderstood, since you apparently understood what I was saying.

Well, I understood that you misunderstood which seems valid.

I do acknowledge that my presentation of arguments was not clear.
 
  • #17
Hurkyl said:
Phil is gone implies Tim has a bread.
Phil is gone imples Tim does not have a bread.
Therefore, Phil is not gone.

Wouldn't your proof by contradiction need the extra assumption to get the contradiction. So it would be better if it was:

1. Phil is gone
2. Phil is gone implies Tim has a bread.
3. Phil is gone imples Tim does not have a bread.
Therefore, Phil is not gone.

Where 1,2 and 3 are assumptions.
 
  • #18
tgt said:
Wouldn't your proof by contradiction need the extra assumption to get the contradiction. So it would be better if it was:

1. Phil is gone
2. Phil is gone implies Tim has a bread.
3. Phil is gone imples Tim does not have a bread.
Heavens no! Those three statements are a contradiction!
 
  • #19
Hurkyl said:
Heavens no! Those three statements are a contradiction!

We are trying to deduce a contradiction which is what we get after combining those three statements.

To give more detail it's

If:
Phil is gone
Phil is gone implies Tim has a bread.
Phil is gone imples Tim does not have a bread.

Then:
Tim has a bread
Tim does not have a bread

We get a contradiction.

Conclusion:
One or more of our assumptions was wrong (or is it only one assumption was wrong?)
We say that Phil is not gone.

But couldn't we conclude that the statement 'Phil is gone implies Tim has a bread' is incorrect hence the reverse of that statement is true instead?
 
  • #20
With regards to the OP. I realized that I've made a mistake. The technique is to use natural deduction to prove the statement.

http://www.ags.uni-sb.de/~chris/papers/2002-pisa.pdf [Broken]
 
Last edited by a moderator:
  • #21
tgt said:
We are trying to deduce a contradiction which is what we get after combining those three statements.

To give more detail it's

If:
Phil is gone
Phil is gone implies Tim has a bread.
Phil is gone imples Tim does not have a bread.

Then:
Tim has a bread
Tim does not have a bread

We get a contradiction.

Conclusion:
One or more of our assumptions was wrong (or is it only one assumption was wrong?)
We say that Phil is not gone.

But couldn't we conclude that the statement 'Phil is gone implies Tim has a bread' is incorrect hence the reverse of that statement is true instead?
But look at your argument form:

{ phil is gone and (phil is gone implies tim has a bread) and (phil is gone implies tim does not have a bread) } implies contradiction

Therefore, not { phil is gone and (phil is gone implies tim has a bread) and (phil is gone implies tim does not have a bread) }


That's exactly the form I'm describing:

P implies contradiction
Therefore, not P
 
  • #22
What would not { phil is gone and (phil is gone implies tim has a bread) and (phil is gone implies tim does not have a bread) } be?

Would it be one of { phil is not gone or not(phil is gone implies tim has a bread) or not(phil is gone implies tim does not have a bread) }?

So we have 3 choices to choose from?

Your way of stating things "P implies contradiction Therefore, not P" is a bit too broad. Often we like to conclude an assumption in P which is wrong which is also the thing we are trying to prove.
 
  • #23
tgt said:
So we have 3 choices to choose from?
Right; DeMorgan's laws: not(P and Q and R) = not P or not Q or not R.

Often we like to conclude an assumption in P which is wrong which is also the thing we are trying to prove.

Sure, but that's the basic building block. e.g. we could proceed as:

P
(P and Q) implies contradiction
Therefore not (P and Q)
Therefore not P or not Q
Therefore P implies not Q
Therefore not Q

(Of course, the actual chain of logic would depend both on which set of rules you are using, and the particular route you decided to use)
 
  • #24
I suppose if you wanted to keep explicit track of when you're just using the logical connective and when you're talking about the existence of a proof, you could argue something like:

([itex]\vdash[/itex] is the symbol that means "there is a proof that starts with the left hand side and concludes with the right hand side")

([itex]\bot[/itex] is a symbol denoting a contradiction)

We have a metalogical theorem that
[itex]P, Q \vdash R[/itex] if and only if [itex]P \vdash Q \to R[/itex]​

You could organize your proof by contradiction as

First, prove [itex]P,Q \vdash \bot[/itex]
Then invoke the theorem to conclude [itex]P \vdash Q \to \bot[/itex]
And apply the law of noncontradiction to get [itex]P \vdash \neg Q[/itex]
 
  • #25
Just say in a maths proof, a contradiction is reached. Can we then immediately conclude anything? For example the sky is green?
 
  • #26
If a contradiction is reached in a mathematics-style proof, it usually means that the assumption that the hypothesis is true must be an incorrect assumption.

For example, if I want to prove that x = 1 implies that x2 - 1 = 0, I can do this by assuming that x = 1 and the opposite of the conclusion; i.e., that x2 - 1 [itex]\neq [/itex] 0.

I can square both sides of the equation x = 1 to get x2 = 1. I can then subtract 1 from both sides of the latter equation to get x2 - 1 = 0.

The last equation contradicts the assumption that x2 - 1 [itex]\neq [/itex] 0, so that assumption must be faulty, which leads us to conclude that x2 - 1 = 0.
 
  • #27
tgt said:
Just say in a maths proof, a contradiction is reached. Can we then immediately conclude anything? For example the sky is green?
Yes. That's why inconsistency is very bad in a mathematical theory (or any other kind of theory).

But in everyday examples, one never proves a contradiction -- one proves that some hypothesis implies a contradiction.
 
  • #28
Hurkyl said:
one proves that some hypothesis implies a contradiction.

After that we then conclude that the initial hypothesis must be incorrect. However what is interesting is that if there are two or more assumptions then only one is false. And anyone can be picked. In that case, do we pick the assumption that we wanted to be false at the start to be false?
 
  • #29
tgt said:
After that we then conclude that the initial hypothesis must be incorrect. However what is interesting is that if there are two or more assumptions then only one is false. And anyone can be picked.
No, it only disproves their conjunction. If you want to prove something about them individually, you need to do something else.
 
  • #30
Hurkyl said:
No, it only disproves their conjunction. If you want to prove something about them individually, you need to do something else.

So when using proof by contradiction to prove a statement, we better make sure the reverse of that statement is the only assumption in the proof (containing a contradiction)?
 

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
917
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
957
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Back
Top