What are the axioms of deduction?

[MathematicalPhysicist]

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?

 

[matt grime]

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.

 

[MathematicalPhysicist]

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?

 

[matt grime]

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.

 

[MathematicalPhysicist]

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.

 

[matt grime]

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.

 

[MathematicalPhysicist]

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 ):"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)".

 

[MathematicalPhysicist]

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.

 

[matt grime]

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

 

[MathematicalPhysicist]

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.

 

[matt grime]

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.

 

[MathematicalPhysicist]

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 -

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 ):"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)".

 

[matt grime]

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.

 

[MathematicalPhysicist]

got it, thanks.