Indirect Proof (Logic question)

  • Thread starter Edgardo
  • Start date
  • #1
703
13

Main Question or Discussion Point

Hi all,

I've got a question about indirect proof, whether I have understood it correctly:

a) Suppose I want to show A=>B, where A and B are two statements.

In the method of indirect proof I assume that [tex]\neg B[/tex] (not B) is true and use the given statement A to show a contradiction. Therefore, B must be true (because either B or [tex]\neg B[/tex] is true).

In short what I do:
[tex]\neg B[/tex] true (assumption) and A true (given statement) => contradiction

Is that correct?


b) Now another question:
Suppose I assume B is true (instead of [tex]\neg B[/tex] true) and use the given statement A such that it leads to a true statement like 1=1.
Have I showed anything with that?

In short what I do here:
B true (assumption) and A true (given statement) => no contradiction.
But that doesn't tell me anything, right?
 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
3
If you assume:

1) ~B
2) A

and derive a contradiction, then you will have proven that A & ~B is false, i.e. you will have proven ~(A & ~B), which is equivalent to (A => B).

For part b), no that's useless. First of all, you can derive a true statement like 1=1 from the contradictory premises as well. There's a difference between deriving something that isn't a contradiction, and proving that no contradiction can be derived whatsoever. You can derive 1=1 from anything, in fact you can derive 1=1 from nothing - it is a theorem.
 
  • #3
703
13
Thanks for you answer.

AKG said:
If you assume:

1) ~B
2) A

and derive a contradiction, then you will have proven that A & ~B is false, i.e. you will have proven ~(A & ~B), which is equivalent to (A => B).
Is that a theorem proven in logic? Or is it an axiom?

Is (A => B) <=> (~B => ~A) an axiom?
 
  • #4
honestrosewater
Gold Member
2,105
5
What do => and <=> mean to you? Is (A => B) a statement that can be either true or false? Or does (A => B) mean that (A -> B) is always true?
 
  • #5
AKG
Science Advisor
Homework Helper
2,565
3
Those are both theorems, unless honestrosewater wants to add something about the difference between -> and =>. As far as mathematicians and others who do math are concerned, the symbols can be used interchangeable, and we're normally not concerned with whether our conditional is technically a material conditional or necessary conditional.
 
  • #6
honestrosewater
Gold Member
2,105
5
No, if the difference isn't the source of the confusion, I have nothing to add. :smile:

Eh, except that I don't know what 'an axiom or theorem of logic' is anymore than I know what 'an axiom or theorem of math' is. Even 'an axiom or theorem of classical propositional calculus' doesn't narrow it down enough for me to say whether a certain statement is an axiom or theorem, as there are several different versions of the so-called 'classical propositional calculus' (some of which don't even have any axioms). And if => denotes logical (or necessary) implication, you're talking about the metatheory, which isn't even usually set down explicitly and I imagine can be different even for the same object theory. And IMO, whether a certain statement is an axiom or theorem isn't even of much importance outside of a particular calculus, as you can adopt any theorem as an axiom and can derive the same set of theorems from different sets of axioms. Anywho, if you guys know what you're talking about, don't let me get in the way. :smile:
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,770
911
Edgardo said:
In the method of indirect proof I assume that [tex]\neg B[/tex] (not B) is true and use the given statement A to show a contradiction. Therefore, B must be true (because either B or [tex]\neg B[/tex]
is true).
Strictly speaking, that's wrong. What you show is not that B is true but rather than A implies B.
 

Related Threads for: Indirect Proof (Logic question)

Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
7
Views
9K
Replies
6
Views
654
Replies
8
Views
2K
Top