Shantila's Inside Logic #19

Completeness

The ten Rules that we have in our system allow us to prove any of the logical truths of basic logic that we can express in our simple formal language. In that sense, our system is "complete." What this means is that there are no valid sequents or logical truths that we can write down in our simple symbolic language for which a derivation cannot be constructed using the Rules of our system. This is a strong claim about our system and this claim itself can be proven definitively. (This sort of investigation is called meta-logic.) But actually proving it is not within the scope of this course in introductory logic.

One of the tremendous intellectual achievements of the 20th century was the proof that basic systems of logic like the very one we have developed are complete. This sort of "completeness" pertains to the connections between the basic ideas of standard logic: if, not, and, or.

Our system is "complete" in the sense that all of the basic valid relations between these ideas can be proved in our system.

Now does this mean that our system is a "complete system of logic" in the sense that there is nothing more to be done in logic? No, it most certainly does not mean that!! There are many ways in which this basic system can be extended so as to shine the spotlight on interesting forms of ordinary valid reasoning. There actually are some simple forms of valid reasoning that we can express in English but that we cannot even represent in our language and system (as we will see later in this course after the third test).

All the same, our system is "complete" insofar as all valid sequents that can be expressed in our language can be proved, and this basic system can be used as the foundation for developing more complex systems.

One might well wonder if this basic system of logic might be extended into a more complex system for, say, basic arithmentic. Suppose we start with our basic system and then add some special Rules for arithmetic; for example, explaining how concepts like + and = work in a statement like 1+1=2.

Could we then develop a "complete" system for elementary arithmetic, so that all of the basic truths of arithmetic (such as 1+1=2) also could be proved in the more complex system? The perhaps surprising answer is: definitely No. It is not possible to construct a consistent and complete formalization of arithmetic. The proof that there can be no such consistent formal system in which all the truths of arithmetic could be proved also was a stunning achievement made during the 20th century. There definitely are limits to the development of formal systems -- this is another "meta-theoretical" claim that can itself be proven.

Exploration of these points also goes well beyond the scope of this course. But you might want to learn about these matters on your own. What you have learned in this course so far will be an excellent start.

Here is a summary of all of our Rules.

Summary of the Rules

The Rule of Assumptions (A). This rule allows us to write, at any stage of an argument, any statement we choose to write. We may write a statement down as a new line, write "A" (for "Assumption") to the right of it, and to the left of it we put its own number to indicate that this line depends on itself.

Modus Ponens (MP). For any statements P and Q, given P>Q and P as premises, MP permits us to derive Q, where Q depends on any assumptions upon which P>Q and P depend.

Double Negation (DN). For any statement P, given ~~P as a premise, we may derive P as a conclusion; and vice versa (that is, given P as a premise, we may derive ~~P as a conclusion). In either case, the new line depends on exactly the same assumptions as the premise.

Modus Tollens (MT). For any statements P and Q, given P>Q and ~Q as premises, MT permits us to write ~P, where ~P depends on any assumptions upon which P>Q and ~Q depend.

&-Elimination (&E). Given P&Q as a premise, &E permits us to write P as a conclusion. P depends on all of the assumptions of P&Q. (Likewise for Q.)

&-Introduction (&I). Given both P and Q as premises, &I permits us to write P&Q as a conclusion, where P&Q depends on all of the assumptions of both P and Q (the ordering in which P and Q appear as lines in the proof does not matter).

Conditional Proof (CP). Given a proof of Q based on P as one of its assumptions, CP permits us to derive P>Q on the remaining assumptions.

v-Introduction (vI). Given any statement P as a premise, vI permits us to derive PvQ as a conclusion, where PvQ depends on all of the assumptions upon which P depends (likewise for QvP).

Disjunctive Syllogism (DS). Given a disjunction PvQ as a premise, together with ~P as a premise, DS permits us to derive Q as a conclusion, where Q depends on all the assumptions of the two premises. Likewise PvQ and ~Q together give us P with all the assumptions of the two premises.

Reductio ad Absurdum (RA). If we assume P and can derive a contradiction Q&~Q, for some Q, based upon P as an assumption, we may derive ~P as a conclusion based upon the remaining assumptions.

*EXTRA CREDIT

Practice

19.1 EXTRA CREDIT. Each of the following sequents is valid. Use our Rules to construct derivations for each of them.

104 ~(P>~Q) } P&Q

105 P>Q } ~PvQ

106 ~P>Q } PvQ

107 ~(P&Q) } ~Pv~Q

108 P, ~P } Q

109 ~(~P&~Q) } PvQ

110 P&(QvR) } (P&Q)v(P&R)

111 P>R } (PvQ)>(QvR)

112 (PvQ)vR, P>R, Q>R, R>S } S

113 QvR } RvQ

114 PvQ, P>R, Q>S } RvS

115 (P>R)&(Q>R) } (PvQ)>(RvS)

19.2 EXTRA CREDIT. The following argument is valid. Symbolize it and construct a derivation to show that it is valid.

The Falcons will win the track meet or I am a monkey's aunt. If the Falcons win, Toledo will come in second. If I am a monkey's uncle, then my nephew, Sam, is a monkey. So either Toledo will come in second or Sam is a monkey. (F: The Falcons win the track meet.T: Toledo comes in second in the track meet. A: I am a monkey's uncle. S: Sam is a monkey.)