What are the axioms of deduction?

  • Thread starter MathematicalPhysicist
  • Start date
  • Tags
    Theorem
In summary, the conversation discusses the concept of deduction and its relationship with axioms. The deduction theorem is mentioned as a way to prove statements using logical rules such as OR, AND, and IMPLIES. It is also noted that proof by contradiction and mathematical induction can be seen as forms of deduction. The conversation concludes by questioning the role of these logical axioms in other methods of proof and their fundamental nature in deductive reasoning.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
http://mathworld.wolfram.com/DeductionTheorem.html

before reading this i thought deduction was axiomatic process like induction but now i see there is a theorem for it, then what are the axioms of deductions?
 
Physics news on Phys.org
  • #2
The rules I think you mean are the obvious ones, so sorry if this sounds patronizin.

Statements are true or false, each is the negation of the other (and not(not( X) is X).

AvB is true when at least one of A and B is true, false otherwise (OR)
AnB is true only when A and B are true (AND)
A=>B is false if A is true and B is false, but is true otherwise. (IMPLIES)

A=>B is equivalent to not(A) v B as can be seen by considering truth tables.

thus the deduction theorem is, I think, equivalent to the statement

(AnB)=>C <=> A=>(B=>C)

which can be shown to be true by writing them both in n/v form



OR and AND are also called conjunction and disjunction though I can never remember which way round it is.
 
  • #3
matt grime said:
The rules I think you mean are the obvious ones, so sorry if this sounds patronizin.

Statements are true or false, each is the negation of the other (and not(not( X) is X).

AvB is true when at least one of A and B is true, false otherwise (OR)
AnB is true only when A and B are true (AND)
A=>B is false if A is true and B is false, but is true otherwise. (IMPLIES)

A=>B is equivalent to not(A) v B as can be seen by considering truth tables.

thus the deduction theorem is, I think, equivalent to the statement

(AnB)=>C <=> A=>(B=>C)

which can be shown to be true by writing them both in n/v form
so they are these, didnt know they were the axioms of deduction.

can we make a generalisation to logic that induction and ad absurdum methods of prooving are all derived from the same axioms of deduction, and that they are the root of logic?
 
  • #4
I suspect that the answer to that depends on logic you are using.

ad absurdum, or proof by contradiction:

Suppose we want to prove X is true, so we take not(X) and show that not(X) implies Y is true for some statement Y that is false. The only way for this to happen is if not(X) is false, ie X is true. This is strongly dependent on having a 2-valued logic with not(not(X)) <=> X, and having the proposition: if A then B being equivalent to not(A) OR B.

Thus I suppose one would say it is dependent on the Logic one uses.

Induction is different in that induction depends upon something other than logic. Namely the existence of a well ordered set. Induction is a method of proof in any system possessing such an object, it is not itself a logical object. But that is just my *opinion*. NB, a set is well ordered if any subset has a minimal element. So, induction here (rather than the usual phrasing of it) states: suppose there is a list of propostions indexed by some well ordered set, and the truth of all statements indexed by x where x <N implies the truth of the statement labelled by N, then they are all true, else there would be a subset for which it is false, and that can't have a minimum.
 
  • #5
so do you know of any logic systems where the first axioms you listed previously as "deduction axioms" arent the root of the ad absurdum method? ( i gather from the example you have given that the 2 value logic has the root of its reasoning from the "axioms of deduction").

i read somewhere that mathematical induction is usually regarded as a sort of deduction (a primitive one, where you have the identity and you just need to prove it is correct) so i thought to include this as a method of proof that might be concluded from the axioms of deduction.
 
  • #6
I can't quite tell what you mean. The theorem of deduction is a theorem in the system of logic we commonly use for mathematics. I've no idea about any other systems of logic: not my thing. And seeing as I don't list any such thing as the "deductive axioms" (you chose to call them that not me), I can't tell you what is the root of reductio ad asburdum is in relation to this.

If deduction were an axiom then having a theorem of deduction would seem strange wouldn't it?


proof by contradiction shows that X=>Y is true and Y is false, thus showing that X is false, and not(X) is true. Make of that what you will.

If you will: (X=>Y)AND(Y is false) imply X is false.
 
  • #7
matt grime said:
I can't quite tell what you mean. The theorem of deduction is a theorem in the system of logic we commonly use for mathematics. I've no idea about any other systems of logic: not my thing. And seeing as I don't list any such thing as the "deductive axioms" (you chose to call them that not me), I can't tell you what is the root of reductio ad asburdum is in relation to this.

If deduction were an axiom then having a theorem of deduction would seem strange wouldn't it?


proof by contradiction shows that X=>Y is true and Y is false, thus showing that X is false, and not(X) is true. Make of that what you will.

If you will: (X=>Y)AND(Y is false) imply X is false.
this is why i asked what are the axioms that you used in order to conclude the "deduction theorem", so i called them (perhaps inappropiately) deduction axioms.

and now i ask are they used in other methods of proof ( i think yes), are they fundamental that these methods are derived from them?

from what i understand these are the axioms of deduction (as i call them :approve: ):"Statements are true or false, each is the negation of the other (and not(not( X) is X).

AvB is true when at least one of A and B is true, false otherwise (OR)
AnB is true only when A and B are true (AND)
A=>B is false if A is true and B is false, but is true otherwise. (IMPLIES)".
 
  • #8
btw, matt, can you please tell me if i remembered correctly, "if and only if A then B" the table inference of the whole sentence when A-F and B-T is F unlike the simple "if" sentence that the inference would be T?

thanks.
 
  • #9
This is just Boolean logic. you'll get far better and more numerous answers reading a book on it than asking a non-expert like me
 
  • #10
did your last reply was about the if and only if question, if so what about my previous question?

btw, as i can see it you are the only one who paid attention to this thread of mine so i don't if other even give a damn.
 
  • #11
I don't really wish to give any answers on a subject that I'm not familiar with beyond basic explanations. I'm sure there are some very subtle points to be discussed on this, and I'm not the person who should lead that discussion.

anyway, that said, from what I can decipher, A iff B is what you meant to enquire about, and if that is the case, then A iff B is obviously (A=>B)and(B=>A), whose truth table is easy to write down, especially as that statement is the same as (not(A)orB)and(not(B)orA)

i've had to make too many guesses at what precisely it is you mean, and that is why I don't want to answer too many more questions. I think reading a book in your own first language would be a better option than me guessing your intention.
 
  • #12
thanks, matt.
you still didnt answered my question (which this thread was opene for in the first place), here it is in case you forgot -
loop quantum gravity said:
this is why i asked what are the axioms that you used in order to conclude the "deduction theorem", so i called them (perhaps inappropiately) deduction axioms.

and now i ask are they used in other methods of proof ( i think yes), are they fundamental that these methods are derived from them?

from what i understand these are the axioms of deduction (as i call them :approve: ):"Statements are true or false, each is the negation of the other (and not(not( X) is X).

AvB is true when at least one of A and B is true, false otherwise (OR)
AnB is true only when A and B are true (AND)
A=>B is false if A is true and B is false, but is true otherwise. (IMPLIES)".
 
  • #13
I did answer your original question. The deduction theorem follows from the identity

(AnB)=C => (A=>(B=>C)

which is true in any axiomatic system where it's true, if you see what I mean, and can be deduced from the commonly used axioms of the orindary bi-valued logic we use all the time in mathematics. (it may be true in other axiomatic systems too.)

Proof by contradiction is the statement that

(X=>Y is true)and(Y is false) => X is false.

which again follows from the basics of bivalued logic

and induction is not a logical law since it only applies when the logical laws are applied to a system that contains a well ordered set, and is a technique of proof, not a metaproof (ie a proof about proofs) and follows from a 'contradictory' or 'deductive' nature, but only when your model of set theory contains a well odered set.
 
  • #14
got it, thanks.
 

What is the Deduction Theorem?

The Deduction Theorem is a fundamental theorem of mathematical logic that states that if a statement can be derived from a set of assumptions, then it can also be derived from the addition of one more assumption to that set.

How does the Deduction Theorem work?

The Deduction Theorem works by breaking down a complex statement into simpler statements and then using logical rules to show that the original statement is a logical consequence of the simpler ones.

What is the significance of the Deduction Theorem?

The Deduction Theorem is significant because it allows us to prove the validity of mathematical arguments by reducing them to a set of axioms and logical rules. This makes it a valuable tool in mathematical and scientific reasoning.

Can the Deduction Theorem be applied in other fields besides mathematics?

Yes, the Deduction Theorem can be applied in other fields such as computer science, philosophy, and linguistics to formalize and prove arguments and theories.

Are there any limitations to the Deduction Theorem?

Yes, the Deduction Theorem has limitations as it only applies to formal logical systems and cannot be used to prove statements in all areas of knowledge. Additionally, it assumes that the premises and conclusions are true, which may not always be the case in real-world scenarios.

Similar threads

Replies
1
Views
770
Replies
8
Views
1K
Replies
34
Views
1K
Replies
72
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
Replies
29
Views
1K
Replies
10
Views
1K
  • General Discussion
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
Replies
13
Views
1K
Back
Top