Invalid Argument vs. Contradiction?

I'm confused about the differences between valid/invalid arguments and contradictions/tautologies.

An argument is valid when the statement "all of it's hypothesis are true implies the conclusion" is a tautology.

When we show an argument is invalid we are showing the above quoted implication-statement is false in at least one case. Right?

Do we ever need to prove that an argument is equivalent to a contradiction? I am trying to think of an example where this would be the case, or even could be the case, but...

• Well, an argument is valid when "hypotheses true and conclusion false" is a contradiction (in the sense that its truth table is all F). – user21467 May 17 '14 at 3:13
• Take the argument: "p -> q";"~p" therefore "q". In the corresponding truth table there is a row where the hypothesis are all true and the conclusion false, therefore the argument is invalid. But there is also a row where the conditions are true and the conclusion is true. This is not, then, a contradiction, but it is invalid. – hefalump May 17 '14 at 3:35
• A valid argument is as you said : when $\Gamma \vDash \alpha$; thus, if $\Gamma$ is a finite set of sentences, then it is equivalent to : $\vDash (\gamma_1 \land ... \land \gamma_n ) \rightarrow \alpha$; i.e. the last formula is a tautology. A contradiction is a formula which is always false. Thus, an invalid argument (from a finite set of premises) is a formula like the above which is false in at least one case (when all of $\gamma$s are true but $\alpha$ is false). False in at least one case does not mean in all cases... – Mauro ALLEGRANZA May 17 '14 at 7:37

First: terminology. An argument is a collection of statements (more details below) while a tautology or contradiction is a single statement. So with regard to your last question, it makes no sense to say that "an argument is equivalent to a contradiction" - they are different kinds of objects.

BTW a remark on the side - one of the first things you need to do in studying any mathematical topic is to make sure you know what kinds of things you are talking about. For example, I frequently have students attempting a problem concerning a function $T$ and trying to prove that $0$ is an element of $T$. This makes no sense at all because a function does not have "elements", only a set can have elements.

Second: you shouldn't go overboard on notation. It's very easy to forget that the symbols actually mean something and just try to apply rules to them. However in your question you have used no notation at all and I think some would be helpful. I will assume that you are studying propositional logic; if you later move on to predicate logic, similar ideas apply.

So, an individual statement of propositional logic is a tautology if it is always true, and a contradiction if it is always false. A very simple example of a tautology is $$p\vee(\neg p)\ ;$$ informally this means "$p$ is either true or false", and this statement is clearly true as a whole, regardless of whether $p$ is in fact true or false. Likewise, $$p\wedge(\neg p)$$ is a contradiction since it is inevitably false, no matter what $p$ may be. Just a very simple example like $$p$$ could be true and could be false, so it is neither a tautology nor a contradiction. For a harder example such as $$(p\to(q\vee\neg r))\to(r\to(p\to q))\tag{*}$$ you would draw up a truth table and observe whether the final result is all true, all false or neither of these. I'll leave this one for you as an exercise.

Next: an argument is a (finite) sequence of statements. The last statement in the sequence is called the conclusion and the preceding ones are the premises or assumptions or hypotheses. Saying that an argument is valid essentially means that the logic is correct, regardless of the actual facts asserted: more precisely, it means that in any case where all the hypotheses are true, the conclusion must also be true. The best known example is \eqalign{&p\to q\cr &p\cr \therefore\ &q\ ,\cr} sometimes referred to as modus ponens. Hopefully it is intuitively clear that if $p\to q$ and $p$ are true then $q$ must be true: essentially, this is just the meaning of "if. . . then". Another (slightly silly) example is \eqalign{&p\cr &\neg p\cr \therefore\ &p\wedge(\neg p)\ .\cr} Of course in this case the two hypotheses cannot be simultaneously true; but it is obvious that if they were then the conclusion would have to be true: this is really no more than the meaning of the word "and". So the argument is valid, even though the conclusion is false! Here is an example of an invalid argument: \eqalign{&p\to(q\vee r)\cr &q\to r\cr &\neg q\cr \therefore\ &\neg p\ .\cr} You can find by trial and error that if $p$ is true, $q$ false and $r$ true, then the three assumptions are true but the conclusion is false. Now suppose that we have an argument \eqalign{&P_1\cr &\vdots\cr &P_n\cr \therefore\ &Q\ .\cr} To say that this is a valid argument means

in all cases, if $P_1,\ldots,P_n$ are all true then $Q$ is true;

that is,

in all cases, if $P_1\wedge\cdots\wedge P_n$ is true, then $Q$ is true;

that is,

in all cases, $(P_1\wedge\cdots\wedge P_n)\to Q$ is true.

That is, the above argument is valid if and only if the statement $$(P_1\wedge\cdots\wedge P_n)\to Q$$ is a tautology. So, if you have an argument where the trial and error is too hard, you can construct this statement, write up a truth table, decide whether the statement is a tautology or not, and hence decide whether the argument is valid or not.

The case you are asking for, where the truth values turn out to be always false, is not really of any particular interest - the idea is that for a valid argument, if we confirm that the premises are true, then we can be certain that the conclusion is true. So if the truth values are even sometimes false, the argument is of no value. However, it is certainly possible to construct an "extreme" case: you would need $P_1,\ldots,P_n$ to be always true, that is, tautologies, and $Q$ always false, that is, a contradiction. An example would be \eqalign{&p\vee(\neg p)\cr &p\to p\cr \therefore\ &p\wedge(\neg p)\ .\cr}

Hope this helps. Good luck!

Answer to $(*)$: it's a tautology.

• "This makes no sense at all because a function does not have "elements", only a set can have elements." Nope. A function can get thought of as a set. For example, in {0, 1, 2} we have a unary function f:0->1, 1->2, 2->0. The elements of the function are the ordered pairs (0, 1), (1, 2), and (2, 0). And aren't the elements of the nullary functions in {0, 1, 2} "0", "1", and "2" respectively? – Doug Spoonwood May 22 '14 at 22:01
• That's true of course but I can assure you it is not the intention of the students who make this mistake, so I was simplifying the remark. Also note that in your first example, if someone were to say $0\in f$ it would be wrong. Not only that, it would be exactly the same kind of error as I mention , in that they would be attempting to apply to the number $0$ a concept which in this example can only apply to a a pair of numbers. – David May 22 '14 at 22:56
• In your second example, are you asserting that $0$ is an element of $0$? If I understand your notation correctly, $\{0,1,2\}$ is not a function but a set of functions, and there is certainly no problem with a function (nullary or otherwise) being an element of a set of functions. – David May 22 '14 at 22:59
• In my second example I wasn't sure or of not if 0 is an element of the nullary function 0. A unary function corresponds to an ordered pair, a binary function to an ordered triple, and so on. 0 belongs to the element (0, 1) of the function {(0, 1), (1, 0)}. So, it seems to follow that 0 belongs to the nullary function 0, though maybe I've made a mistake in reasoning here. – Doug Spoonwood May 23 '14 at 0:17
• As I understand it a nullary function is a set with just one element. So it is true that $0\in\{0\}={\bf0}$. Also, $0$ is an element of the ordered pair $(0,1)$ if you use the interpretation $(0,1)=\{0,\{0,1\}\}$, but not if you use the more elementary interpretation. So $0$ would not be an element of the set $\{(0,1),(1,0)\}$ but an element of an element of the set. Must say however - not that I want to kill off the discussion - that my original point was in reference to students who make basic mistakes in elementary topics. These fine distinctions are, I believe, irrelevant to that point. – David May 23 '14 at 0:37

Well, put model theoretically "valid" says that every model of your premises is also a model of your conclusion. "Invalid" says that there is at least one model of your premises in which the conclusion doesn't hold.

The only sense I can assign to "an argument being equivalent to a contradiction" is an argument in which the conclusion is a contradictory statement. In which case validity is still a live question and it breaks down into which of two cases we have: You can have contradictory premises, in which case the implication will be vacuously valid (since there is no model in which a contradiction is true). Or you can have a consistent set of premises, in which case the argument is invalid since there will be a model of your premises and none will be models of the conclusion.

The instances where either side of the implication is consistent are probably the usual ones you have in mind, like "if $x$ is a group then $x$ is abelian" or "ZF implies the existence of $X^Y$ for all sets $X,Y$". But in either case we can see that "valid" and "invalid" exhaust the semantic relations between premises and conclusions.

• Let me know if I can clarify anything; I'm pretty much the world's worst communicator... – Malice Vidrine May 17 '14 at 2:57
• I think I am looking for an example where every row of a truth table which produces all true premises produces a false conclusion, rather than a subset of true premise conditions breaking validity. And, if this super-ultra-not-valid-ness means anything. After thinking on it a bit more I suspect it would not. It will be, I think, analogous to one thing to disprove, all to prove. – hefalump May 17 '14 at 3:43
• @hefalump - think at $p \lor \lnot p$ as premise (it is always true) and $p \land \lnot p$ as conclusion (it is always false). Clearly : $p \lor \lnot p \nvDash p \land \lnot p$. This is an invalid argument and, in addition, we have that $(p \lor \lnot p) \rightarrow (p \land \lnot p)$ is a contradiction. – Mauro ALLEGRANZA May 17 '14 at 8:07
• @Mauro: Thanks, that's a good example in the spirit of one I was tempted to give. The idea being that the cases hefalump has in mind are just those cases where $\phi$ is an invalid conclusion precisely because $\neg\phi$ is a valid one. – Malice Vidrine May 17 '14 at 12:36

An argument that from $A$ derives $B$ is valid if and only if $A \Rightarrow B$ can be derived from the starting axioms. Derivability should be distinguished from truth value because the assignment of truth values to statements according to derivability will of course depend on the rules in our formal system, and may have nothing to do with truth in the actual world we live in, unless the real world follows exactly the same rules as our system. Also, in some formal systems there are statements such that neither it nor its negation can be derived. However if we make the assumption that our formal system has no such statements, and is powerful enough for us to describe and manipulate its statements and derivations completely within it, then it makes sense for us to assign derivable statements the value of true and non-derivable well-formed statements the value of false, and then we can indeed say that an argument that from $A$ derives $B$ is valid if and only if $x$ is true, where $x$ is the statement ( $A \Rightarrow B$ is true for all possible values for all the variables ). Likewise an argument that from $A$ derives $B$ is invalid if and only if $x$ is false. In such systems, every invalid argument corresponds to a false statement with no free variables, which is a contradiction.

The reason why you could not think of an example where you want to prove that an argument is a contradiction is precisely because of the quantification over the variables as described above. A valid argument must be true for all possible bindings of free variables, whereas an invalid argument must just be false for at least one possible binding, which is not necessarily contradictory unless it is further 'wrapped up' in universal quantifiers to bind all its free variables. In other words, it may not be a contradiction because it may be true for some bindings, but it becomes a contradiction if you encapsulate it into a statement saying that it is true for all bindings.