Is A∨¬A a tautology when there is a proof (by contradiction)?

$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.


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.


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

Tags:

Logic

Proof Verification

Related

How do I prove that $f(x)f(y)=f(x+y)$ implies that $f(x)=e^{cx}$, assuming f is continuous and not zero? Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems How to show that $[0,1]^{\omega}$ is not locally compact in the uniform topology? Rotating one 3d-vector to another What is the Topology of point-wise convergence? Evaluate:: $ 2 \sum_{n=1}^\infty \frac{(-1)^{n+1}}{n+1}\left( 1 + \frac12 +\cdots + \frac 1n\right) $ Calculus question taking derivative to find horizontal tangent line Proof : cannot draw this figure without lifting the pen How to determine whether a function of many variables is convex or non-convex? Is the graceful labeling conjecture still unsolved? Find all the functions which satisfy the functional equation $f(y+f(x))=f(x)f(y)+f(f(x))+f(y)-xy$. What does it mean to restricting a function to a line in convex optimization?

Recent Posts