I apologize in advance for my lack of knowledge about the terminology of formal logic. I am only interested in informal logic to the extent that a practicing mathematician needs it to proceed. Despite years of experience in mathematics, I am finding myself confused about what a contradiction means. According to this site,
A contradiction is a conjunction of the form "A and not-A"… So, a contradiction is a compound claim, where you’re simultaneously asserting that a proposition is both true and false.
I doubt that this is mathematical definition though, as Wikipedia's article on contradiction defines that
a proposition is a contradiction if false can be derived from it, using the rules of the logic. It is a proposition that is unconditionally false
Two questions:
- Main question: I'm confused as to the difference between a contradiction and a false statement. If I say that $x\in S\wedge x\not\in S$ then is this a contradiction or a false statement? There seems to be two ideas at play, one being a statement that is simply false like "The sky is red" versus something like $P\wedge \neg P$ where the $P$ can be any statement with a true/false value like a proposition or quantified predicate but regardless of whether $P$ is $0$ or $1,$ the value of $P\wedge\neg P$ is $0 $ (false). In the former case, there is no varying in the underlying components whereas in the latter we compute a truth table to find that we always get $0.$ I am running into the issue of distinguishing between the two because this article on proof by contradiction uses the $\bot$ symbol and I don't know whether it is refering to a false statement or a logical contradiction, where by a false statement I mean something like "The sky is red" and by a contradiction I mean a statement like $P\wedge\neg P$ whose truth table has all $0$'s in the final column (I don't know if these are the right definitions for the terms).
- Side question: Are all contradictions, that is those statements that evaluate to a truth table of all $0$'s in the final column, logically equivalent to a statement of the form $P\wedge \neg P$? A counterexample or proof would be appreciated.
Best Answer
Your understanding is correct. Put simply, a contradiction is a sentence that is always false. More precisely,
In propositional logic, interpretations are valuation functions which assign propositional variables a truth value, so a contradiction comes down to having 0's as the final column in all rows (= valuations) of the truth table.
In predicate logic, interpretations are structures consisting of a domain of discourse and an interpretation function defining a mapping from symbols to objects, functions and relations on it, so a contradiction is a statement which evaluates to false no matter the choice of objects and interpretation of the non-logical symbols.
Take the expression $\exists x (x < 0)$, for instance: This sentence is false in the structure of the natural numbers, but true when we evaluate it in the integers, or under some none-standard interpretation of the natural numbers where e.g. the symbol $<$ ist taken to mean "greater than". The statement is not valid (= true in all structures), but it is not contradictory (= false in all structures), either: While it may be coincidentally false in some particular structure/the situation we're currently interested in, it is logically possible for it to become true.
On the other hand, $\exists x (x < 0) \land \neg \exists x (x < 0)$ is true in neither of the above three structures structures; in fact, it fails to be true in any structure whatsoever: No matter which domain of objects we take and which interpretation we assign to the symbols $<$ and $0$, the form of the statement $A \land \neg A$ makes it inherently impossible to ever become true.
To pick up your example, "The sky is red" is only coincidentally false in the actual world because our earthly sky just so happens to be blue, but it is possible to imagine a universe in which the atmosphere is constituted differently and the sky is indeed red: The sentence false in the real world, but it is not contradictory. In symbols, the sentence can be formalized as $p$, and will have a truth table with both a true and a falsy column.
On the other hand, $x \in S \land x \not \in S$ is another statement of the form $A \land \neg A$, and thus a contradiction: It is false in all structures, and thus also in our real-world conception of sets in standard ZF set theory. Its truth table has only 0's, no matter which value the component statements take.
The symbol $\bot$ is used to refer to a contradiction. And indeed, any contradictory statement is logically equivalent to (and can be transformed into, using rules of inference) both $A \land \neg A$ and $\bot$: All contradictory statements have the same truth table with only 0's in the last column.