Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$A \lor \neg A$ is stated as a "tautology", but is it really a tautology? It can be proven by counterposition. And therefore it is not a tautology when it can be proven(?)

Update

Here's the proof (by contradiction) I mean:

¬(A∨¬A) (assumption)
   A      (assumption)
   A∨¬A  (rule of introduction)
  人      (contradiction)
 ¬A
 A∨¬A   (rule of introduction)
 人      (contradiction)
¬¬(A∨¬A)
A∨¬A
share|improve this question
2  
I'm having a hard time understanding your question.Why do you think $A \vee \neg A$ isn't a tautology? –  Git Gud Feb 3 '13 at 8:59
1  
Make a truth table, it cannot be proven otherwise as you will see –  Math_Illiterate Feb 3 '13 at 9:13
1  
I'm not sure what you mean, but $1=1$ isn't a tautology. –  Git Gud Feb 3 '13 at 9:29
2  
@GitGud Why isn't "1=1" a tautology? I could've misunderstood. –  909 Niklas Feb 3 '13 at 9:31
1  
Um, I hate to wade into this deep philosophical discussion, but why do you have a couple of Han characters for people in your proof? The usual symbol for a contradiction is the up tack, $\bot$. –  Rahul Feb 3 '13 at 10:50
show 5 more comments

3 Answers 3

up vote 10 down vote accepted

$A\vee \neg A$ is a tautology in classical (i.e., Aristotelian) logic because you can prove that using the deduction rules of the classical proposition calculus no matter what the truth value of $A$ is, the truth value of $A\vee \neg A$ is always true. That is the meaning of tautology.

In non-classical logical systems, such as intuitionism or constructivism, $A \vee \neg A$ is not a tautology. There the interpretation of $P \vee Q$ is not "either P or Q is true" but rather the more constructive "Either I have a proof of P or I have a proof of Q". A famous example to illustrate this is the following: Theorem: There exist two irrational numbers $a,b$ such that $a^b$ is rational. A classical proof can go like this: if $\sqrt2 ^\sqrt2$ is rational we are done. Else, consider $(\sqrt2^{\sqrt2})^{\sqrt2}=\sqrt2^2=2$, a rational. Classically this finishes the proof but constructively it is not a valid proof since it does not actually show which one of the two candidates works.

share|improve this answer
    
Thank you for the answer. I added the proof I was thinking of. –  909 Niklas Feb 3 '13 at 9:25
    
@Ittay Weiss don't you mean $\displaystyle \bigl(\sqrt{2}^\sqrt{2} \bigr)^\sqrt{2}=\sqrt{2}^{\sqrt{2}\cdot \sqrt{2}}$? –  Git Gud Feb 3 '13 at 12:29
    
This is why I would call $A\ \or\ \not A$ an axiom rather than a tautology in most uses of first order predicate calculus, but not all. For example, the Fundamental Theorem of Algebra holds for the constructive complex numbers. –  Barbara Osofsky Feb 3 '13 at 14:52
    
@BarbaraOsofsky \neg to get $\neg$ and \vee to get $\vee$. –  Git Gud Feb 3 '13 at 20:41
    
I prefer $\\lor$ for $\lor$ so I was willing to accept that missing letter, but thanks for pointing out the $\\neg$. I find inputting the LaTeX the hardest part of commenting expecially since in commenting I cannot see the mathjax and there is a strict time limit on editing and only 2 edits. –  Barbara Osofsky Feb 4 '13 at 2:10
add comment

Part of the problem here may be that "tautology" has a far more specific meaning in mathematical logic than in ordinary usage. The more specific meaning is "a statement S that always true, solely on the basis of how S is constructed from smaller statements by means of propositional connectives and the meanings (truth tables) of the connectives". So $A\lor\neg A$ is a tautology because it is true solely because of the meanings of $\lor$ and $\neg$. But $1=1$ is not a tautology because its truth depends on the meaning of $=$, which is not a propositional connective. Similarly, if $P$ is a unary predicate, then $P(a)\to(\exists x)\,P(x)$, though logically valid, is not a tautology because its validity depends on the meanings of both $\to$ and $\exists$, the latter of which is not a propositional connective.

In ordinary, non-technical usage, "tautology" means (according to my dictionary) saying the same thing in different words; I've heard it used more generally to mean anything that is obviously true. So all of the examples in my first paragraph would be tautologies in this sense.

share|improve this answer
    
plus the fact that the sub-statements (values) are bi-valent –  Nikos M. Jun 24 at 2:42
add comment

Try constructing a truth table and you will see that it is in fact a tautology.

share|improve this answer
    
But what's the difference then between tautologies and truths? –  909 Niklas Feb 3 '13 at 9:25
2  
@NickRosencrantz A tautology is a statement which truth table is always true. A logical truth is a statement that is always true after you interpret its meaning. For instance, if I say that "every goba is esdel or not every goba is esdel" you know that this is true even though you don't know what a goba or an esdel are. The statement $1=1$ is a logical truth and you know that only after knowing the meaning of $1$, $+$ and $=$. –  Git Gud Feb 3 '13 at 10:13
    
@GitGud 'If I say that "every goba is esdel or not every goba is esdel" you know that this is true even though you don't know what a goba or an esdel are.' Not so. The most you know is that if it is a contentful English sentence, then it expresses a truth. But if you don't know whether it is contentful, you can't know whether it is true. –  Peter Smith Feb 3 '13 at 12:16
    
@PeterSmith I get what you're saying and I love such detail. However I chose to keep things simpler by taking a "statement" in english, I think it's an easier way to make things clearer. I'm going to e-mail one of these days, by the way. –  Git Gud Feb 3 '13 at 12:19
    
@PeterSmith *e-mail you –  Git Gud Feb 3 '13 at 12:25
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.