LOGIC, MEANING AND COMPUTATION Essays inMemoryofAlonzoChurch Edited by C. ANTHONY ANDERSON University of California, Santa Barbara, U.S.A. and MICHAEL ZELENY PTYX, Los Angeles, California, U.S.A. .... "KLUWER ACADEMIC PUBLISHERS DORDRECHTI BOSTON I LONDON JOHN CORCORAN SECOND-ORDER LOGIC Abstract.This expositoryarticlefocuses onthefundamental differences betweenfirst-orderlogicand second-orderlogic. It employs second-order propositionsand second-order reasoning in a naturalway to illustrate the fact that second-orderlogic is actually a familiarpartof ourtraditionalintuitive logical frameworkandthatit is notan artificialformalismcreatedby sp ecialists for technical purposes. To illustratesome of the main relationships between first-order logic and second-order logic, this paper introduces basic logic, a kind of zeroorderlogic,whichis m or erudimentarythanfirst-order and whichis transcended by first-orderin the same way thatfirst-orderis transcended by second-order. The heuristiceffectiveness and the historicalimportance of second-order logic are reviewedin thecontext of thecontemporarydebate over the legitimacyof second-order logic. Rejectionof second-orderlogic is viewed as involvingradical repudiationof partof ourscientifictradition. Buteven if genuine logic comes to be regardedas excludingsecond-orde r reasoning, which is a real possibility, its effect iveness as a heuristic instrumentwillremain and its importan cefor understandingthehistoryof logicand m athematics willnotbe diminished. Secondorde r logic may some day be gone, but it will never be forgotten. Technical formalisms have been avoidedentire ly in aneffortto reachan inte rdisciplinary audience, butevery efforthas been made to limit the inevitable sacrifice of rigor. No matterwhathumanactionyou consider,if everyonedoes it to everyone doing it tothem, theneveryonehas it done tothem by everyone to whom theydo it. For example, if everyoneteacheseveryonewho teaches them, theneveryone istaughtby everyonetheyteach.Likewise, if everyonehelps everyonewho helpsthem, theneveryoneis helpedby everyonetheyhelp. The same holds for"encourages", "hinders","supports", "opposes", "ignores" , andtherest. Each oftheabovepropositionsis actuallya tautology, a propositionimplied by its ownnegation. In fact, each ofthemcan be proved to betrueby logical reasoningalone; e.g., by deducingthem from theirown negations. Since every propositionin thesame form as atautologyis againa tautology, a discourseformallysimilarto thatexpressedaboveobtainsin every universe of discourse,notjustin theuniverseof humans. In metalogic,forexample, we often discuss theuniverseof propositionsin so far as various logicalrelationsareconcerned. By a logical relation I mean relationssuch asimplication, consequence, contradiction, compatibility, independence,etc. More specifically, I mean whatare calledbinaryrelations on theuniverse ofpropositions.If R indicatesuch arelationand ifa andb are eachindividualpropositions, thenaRb canbe used toexpressthepropo61 C. Anthony Anderson and M. Zeleny (eds.), Logic. Meaning and Computation, 61-75. © 2001 Kluwer Academic Publishers. Printed in the Netherlands. 62 JOHN CORCORAN sit ionthatthefirstpropositiona is relatedby R to the secondproposition b. It is notexcluded,of course,thata andb arethesame proposition.For example, everypropositionimplies itselfandsome butnoteveryproposition contradictsitself. Now logicalrelationsarecertainlynotactions. Saccheri's Postulatecontradicts theParallelPostulatebutthereis no actionthatSaccheri's Postulate couldperform. Nevertheless, as we havejustseen, relation verbs function grammaticallyin certaincontextsin a mannersimilarto thefunctionof action verbs. The relationverbs significantin theuniverseof humansinclude the following:outweighs,outlives,succeeds (inseveralsenses), precedes (in several senses), equals (in many senses), and manyothers. The actionverbs significant intheuniverse ofhumansinclude the following: calls (inatleast one sense), serves (inat leastone sense), teaches,commands, obeys, and many others. In normalEnglishsome of thelogicalrelationsareexpressedby relation verbs, as we have seen. For example,implicationis expressedby 'implies' and contradictionis expressedby 'contradicts'. However, some ofthemare expressedby relation nouns. For example, consequenceis expressedby the relationoun 'consequence'.The law oftransitivityof consequenceis that everyconsequenceof aconsequenceof apropositionis againa consequenceof thatproposition. Moreover,thereare logicalrelationsexpressedby relation adjectives. Compatibilityand independenceare expressedby 'compatible' and 'independent'.Aristotle's fundamentalaw ofcompatibilityof truthis thatevery twotruepropositionsarecompatiblewith eachother. Using 'independent' in themost widelyacceptedsense we can saythateveryproposition which isindependentof a givenpropositionis neitherimplied by norcontradictedby the givenproposition, and conversely, everypropositionwhich is neitherimplied by norcontradictedby a givenpropositionis independentof the givenproposition. One reasonfor reviewing the various waysthatlogicalrelationsare expressed inEnglishis topointoutwhatallcreativewritersalreadyknow, viz. thatknowledge of theconventionalrules of Englishshouldenhancebutnot inhibitEnglishwriting. For example, my very firstsentenceuses the pluralpronoun'them' as coreferentialwith 'everyone',which issingular. Even worse, fromthepoint of view ofconventionalrules, is my use ofthefiller 'you consider'.The propositionbeing expressedis not apredictionof what willhappenif you considersomething.The propositionis notaboutyou per se atall.The sentenceexpressesa general proposition predicatinga certain complexpropertyof everyactionon the universe ofhumans. The phrase'no matterwhathumanactionyou consider'is justa heuristicallyeffective way ofexpressinga universalquantifier. From a logicalpointof view the following would dojustas well: 'everyhumanactionis one suchthat', 'everyhuman actionis one where', 'wit h everyhumanaction', etc. At anyrate,a sentence thatviolatesthe conventionalrules of Englishapplicableto the expression SECOND-ORDER LOGIC 63 of a givenpropositionis sometimes neverthelessa perfectlyacceptableand effective way ofexpressingthatveryproposition. Whethera sentenceis an acceptableand effectiveexpressionof a given propositionis a matterof howreaderstakeit, andnot amatterofconventions establishedin thepast. Now wearereadyto presenta discourseobtaining in theuniverseof propositionsandformallysimilarto theone whichbegan thisessay. No matterwhatlogicalrelationyou consider,if every givenproposition bears it to every proposition bearingit tothegiven proposition,thenevery givenpropositionis borneit by everypropositionthegiven proposition bearsit to. For example, if everypropositioncontradictseveryproposition contradictingit, theneverypropositionis contradictedby everyproposition it contradicts. Likewise, if everypropositionimplies everypropositionimplying it,theneverypropositionis implied by everypropositionit implies. The same holds for "is aconsequenceof', "is compatiblewith", "is logically equivalento", "is independentof', "is a contradictoryoppositeof', and the rest. The propositionsexpressedin theabove paragrapharealltautologiesand theyare all laws of logic.The propositionsin thefirstparagraphofthisessay are alltautologiesbutnone ofthem are laws of logicbecausetheyare not abouta logicalsubject-matter. The proposition"Everypropositionimplies everypropositionimplyingit" isabouta logicalsubject-matterbutit is not a law of logicbecauseit is false. For example, "Everypropositionis true" implies "Everyfalsepropositionis true", butnot conversely.The proposition "Everypropositioncontradictseverypropositioncontradictingit" is a law of logic, ofcourse,butit is not a tautologybecauseit is inthesame form as a propositionconsideredjustabove and found to be false. By a law of logic Imean a truepropositionabouta logicalsubject-matter, e.g., about propositions,aboutarguments,aboutargumentations, etc. The twoproperties,being tautologousandbeing a law of logic, areorthogonal in thesensethateach ofthefourcombinationsofthetwo is exemplified. We have seen abovethatsome butnoteverytautologyis a law of logicand thatsome butnoteverynon-tautologyis a law of logic.Thereis much confusionconcerningthiselementarypoint. Some butnotall oftheconfusion is more or lessdeliberatelynurturedin theserviceof variousdogmas which, happily,are waning inpopularity. The proposition,"Every propositioncontradictsevery propositioncontradictingit", is thelaw ofsymmetry (or reciprocity)of contradictionand "Some propositionimplies some propositionnot implying it in return"is thelaw of non-symmetry(or non-reciprocity)ofimplication. "No contradictoryoppositeof a contradictoryoppositeof a propositionis a contradictory oppositeof thatproposition"is the law ofantitransitivityof contradictory opposition. A contradictory opposite of apropositionis, of course, apropositionlogicallyequivalento thenegationof thatproposition.For example, 64 JOHN CORCORAN "Some truepropositionis nottautologous"and "Not everytrueproposition is tautologous"are bothcontradictoryoppositesof "Everytrueproposition is tautologous".In orderto avoid confusion itshouldbe notedthat,although every twopropositionsthatarecontradictoryoppositesof eachothercontradicteach other,not every twopropositionsthatcontradicteachotherare contradictoryopposites. To takean extremeexample, "No propositionimplies itself'contradicts"Some propositionimplies everyproposition".The same exampleillustratesanotherpointthatclarifiesthingsand helps to avoid confusion, viz. thatalthoughno truepropositioncontradictsa trueproposition,some falsepropositionscontradictfalsepropositions. In fact, some falsepropositionscontradicthemselves. Thus althoughno twocontradicting propositionsarebothtrue, some twocontradictingpropositionsareboth false. In such cases, i.e., when twocontradictingpropositionsarebothfalse, theyare notcontradictoryoppositesbecauseevery twocontradictoryoppositeshave differenttruth-values. A contmdiction (or a self-contradiction)is a propositionthatcontradicts itself, i.e., thatimplies its ownnegation.Every contradictionis a contradictoryopposite of a tautologyand everytautologyis a contradictoryoppositeof a contradiction.A propositionis said to becontmdictory (or selfcontradictory)if it is acontradiction.Everytwocontradictorypropositions contradicteach otherbut no twocontradictorypropositionsare contradictoryopposites of eachother. The expression'two contradictorypropositions'means "twopropositionseach of which iself-contradictory"whereas 'twocontradicting propositions'means "twopropositionscontradictingeach other"which, in view of thesymmetricalnatureof "contradicts" , amounts to "twopropositionsone of whichcontradictstheother". In ordinarytechnicalEnglish,'is contraryto' and 'is a contraryto' are ambiguous. Sometimes, "contradicts"is meantand sometimes "is a contradictoryopposite of' is meant. Surprisingly,the ambiguitydoes not seem to betroublesome.However, in former times logicians hadattacheda third technicalmeaningthatdid lead toconfusion. Two propositionswere said to be contraries (sc of eachother)if theycontradicteachotherbuttheir negationsdo notcontradicteachother. For example, "Everynumberis prime" and "Everynumberis non-prime" arecontraries. It is easy to provethat every twocontradictingpropositionsthatarenotcontradictoryoppositesare contraries,andvice versa. In modernlogic,'contrary'is rarelyused inthe obsoletetechnicalsense. We have had occasionjustnow tostateseveral laws of logic and to mention(or talkabout)several laws of logic. As indicatedabove, by a law of logic I mean atruepropositionabouta logicalsubject-matter(propositions, arguments,argumentations,etc.). The most basic laws of logic arethelaws of excludedmiddle, non-contradiction, and truthandconsequence: "Every propositionis eithertrueor false", "Nopropositionis bothtrueand false" and "Everypropositionimplied by atruepropositionis true". SECOND-ORDER LOGIC 65 The laws of logic, in fact allpropositionsaboutlogicalsubject-matterare in some sensesecond-level (or meta-level) propositionsin thesensethat hey are aboutthingsthatarethemselvesaboutthings(usually, of course, nonlogicalthings). Some people, eitherignorantof or inoppositionto logical traditon, call suchpropositions'second-order' .This is not how 'secondorder'is used in this essayalthoughsome second-levelpropositionsare also second-order. A propositionis classified asbasic, first-order, second-order, etc., not on the basis ofwhatit isaboutbutratheron thebasis of its logical structure. Thevery firstpropositionof this essay issecond-order. Thesecond propositionis first-order.Everypropositionto the effectthatone named propositionis in a mentionedlogicalrelationto anothernamed proposition is basic, e.g., "Saccheri'sPostulatecontradictsthe ParallelPostulate". It will become obviousthatthetwo properties,being second-level and being second-order,areorthogonal. The basic propositions, veryroughlyspeaking, are thosewithoutcommon nouns. It is perhapseasiest todescribethe basic propositions of arithmetic (BPA) . Actually,insteadof describingthe BPA outright,it isconveniento describethebasic sentences of arithmetic (BSA) and thento saythatthebasic propositionsofarithmeticarethepropositionsexpressedby the basic sentenceswhenthesentencesare understoodin theirintendedinterpretations. Now, thesubstantivesof thebasic sentencesof arithmeticare exclusively numerals (number-names)in thewide sense: 'zero','one', 'two', 't hree',... , 'zeroplus one', 'zero plustwo', . .. , 'two plus (zero timesone)', . ... Among thenumeralsI alsointend: 'two-squared','two-cubed', etc. The atomic sentencesof arithmeticinclude, inthefirst place, all so-calledequations: 'one plus one is two', 'one plus two isne',etc., in otherwords anysentencein the patternnumeral is numeral. The 'is' here, of course, isntendedto express numericalidentitywhich is oftenimproperlycalledequality andexpressedby 'equals'. Next we havethesentencesthatnormallyattributea qualityto a number, e.g., 'one iseven','one is odd', 'two isprime', 'five isperfect';and so on. Next we have thes ntencesthatnormallyrelateone numbertoanother, e.g., 'two exceedsthree','threedivides two', etc.These includetheidentities (orequalities,equations)alreadymentioned. Next we have thes ntences thatnormallyindicatethat hreenumbersare in aternaryrelation,e.g., 'two is betweenone andthree', etc. Thereare alsoquaternaryrelationalsentences,e.g., 'one is tothreeas threeis tonine'. And so on.Anythingofthissortis countenancedas long as thereare no common nouns. Evencommon nouns are allowed as long asthey areunderstoodas nominalizedadjectives(e.g., 'two is aprime' means "two is prime") or asnominalizedrelatives(e.g., 'two is a divisor of four' means "two divides four"), etc. Once theatomicbasic sentencesofarithmetichave been determined,the basicsentencescan be defined as the so-calledtruthfunctionalcombinationsofatomicsentences,theatomicsentencespluswhat can beobtainedfrom atomic sentencesby negations,conjunctions, disjune66 JOHN CORCORAN tions, conditionals,bi-conditionals, etc. It should be explicitlymentioned in thisconnectionthatpassives (or converses) ofbinaryrelationverbs are againbinaryrelationalverbs and thussentencesuch as 'two isdivided by four', 'two is exceeded by four', etc. are included. Likewise includedare sentencesinvolving the so-called modifiedr lationverbs : 'properlydivides', 'immediatelyprecedes', 'immediately exceeds', etc. Basic logic is the logic of basicpropositions. Basic logic isconcernedfundamentallywith thequestionof how wedeterminethevalidity orinvalidity of anargumentwhose premisesandconclusion are exclusively basic propositions. As you know, anargumentis determinedto be valid by giving a derivation(or adeduction)of its conclusion from its premises. This means giving anextendeddiscourse,normallymuch longerthanthepremises-plusconclusionwhich showsstep-by-stephow theconclusion can be seen to be truewere the premises true.The rules for making up thesed rivationsare obtainedby lookingatwhatpeople dowithbasic propositions when they are reasoning correctly. Inorderto deduce from any set of basic premises any basic conclusionthatactuallyfollows, itis sufficient to use rules from a very small set. These includetheusual rules ofpropositionalogic,therule of substitutionof identities,therule of conversion (the activeand passive are interdeducible)and the logical axioms ofidentity("one is one", etc.). To show thata given basic conclusion does notf llowfrom a given basic premise-set, it is sufficient toproducea counterargument, i.e., a conclusion anda premise-settogetherin thesame form and having false conclusionand truepremises. For example, to showthattheargumenton the left below is invalid itis sufficient to noticethattheargumenton theright is inthesame form andhas truepremises and false conclusion. Two is notthree. Threeis not two plus two. ? Two is not two plus two. One is not two. Two is not one times one. ? One is not one times one. The argumenton therightis obtainedin threesteps fromtheargument on theleft.First'one' is substitutedeverywhere for 'two' on theleft. Thenin the "new" leftargument(in which'two'no longer occurs),'two' issubstituted everywherefor'three'.Then in the "second new" leftargument,'times' is substitutedfor'plus'. Strictlyspeakingan argument (more properly,premise-conclusion argument) is a twopartsystem composed of a set ofpropositionscalledthe premise-set and a singlepropositioncalled theconclusion. To represent or express anargumentwe use anargument-textwhich is a list ofsentences (notpropositions)followed by a single sentence somehowmarkedas the conclusion-sentence. Some logic books use a line above the conclusionsentence,butit is easier and less messy to use aquestion-markas above. The methodoutlinedabove oftransformingoneargument-textintoanother SECOND-ORDER LOGIC 67 argument-textin such a waythattheargumentrepresentedby thesecondis in thesame form astheargumentrepresentedby thefirst works only whenthe argument-textsarewrittenin a so-calledlogically perfect language in which theoutergrammaticalform ofthesentencesmirrorsexactlytheinnerlogicai form ofthepropositions. Whenlogical issues areimportant,thelanguagein questionis regimented (normalized) so thatit becomes logicallyperfect(or approximatelyso). This is why I write'two plus (zero times one)' insteadof 'twoplus zerotimes one'. Logicianstypicallygo immediatelyto asymbolic languagecarefullyconstructedto be logicallyperfectbutformany purposes, especiallythatofexposition,thismethod,thoughvirtuallyessentialfor some purposes,can becounter-productive. Basic logiccanbe calledfinite logic becauseevery finite invalidargument of basic logic isrefutableby a counterargumentwhose propositionshave reference only to a finiteumberof individuals.By a finiteargumentI mean an argumenthaving only a finitenumberof premises and by referenceonly to a finitenumberof individualsI mean not onlythatthepropositionsrefer only to finitelymanyindividuals(which is obvious)butalsothathefunctions referredto are all defined on one andthesame finiteuniverseof discourse. By theway,thisincludestheso-calledzero-premisearguments(arguments havingthenullpremise-set)which are valid when and only whent econclusion is atautology.Some examplesfollow. ? One is one. ? If one is twothentwo is one. ? If (if one is not twothenone is two)thenone is two. ? If one exceeds twothentwo is exceeded by one. It follows fromwhatwassaid abovethatevery basicpropositionthatis not a contradictionis in thesame logical form as atruebasic propositionhaving referenceonly to a finitenumberof objects. This means thatamong the basic propositionsthereare noso-calledinfinity propositions. In orderfor a propositionto be aninfinity proposition it isnecessaryandsufficient hatit be non-contradictoryandfor everypropositionin thesame formhavingreference only to a finitenumberof individualsto be false. Inotherwords aninfinity propositionis a propositionexpressedby a sentencewhich is "satisfiable" only in infinite universes ofdiscourse. Basic logic covers most ofthearithmeticreasoningdone by school children,all ofthelogic "done" bycomputers(thoughin a sensecomputerscan simulate finitestretchesofhigherlogics),andmuch ofthelogic onthenormal aptitudetest. In a sense,first-order logic (FOL) begins when wegeneralizebasic propositions. In fact, it is notstretchingthingsto saythatbasic tautologiesare tautologiesbecause theyare instancesof first-ordertautologies.When you prove a basictautologyyou feelthatyou have notexhaustedyourreasoning 68 JOHN CORCORAN in thatdirection. To illustratehisI will give a basictautologyandthengive four first-ordergeneralizations. ? If threeexceeds twothentwo is exceeded bythree. ? Everynumberexceedingtwo is anumberthattwo isexceededby. ? Everynumberthatthreeexceeds is exceeded bythree. ? Everynumberexceedinga givennumberis a numberthegiven number is exceeded by. ? Everynumberthata givennumberexceeds is exceeded bythegiven number. We areinclinedto thinkthatthebasic tautologyis logicallyderivedfrom its generalization, e.g., that"if threeexceeds twothentwo isexceededby three"is truebecause "everynumberexceedingtwo is onethattwo is exceeded by" istrue... thusemphasizingthefactthat heformeris no peculiarity ofthree.Likewise weareinclined tothinkthat helattergeneralizationis truebecauseofthetruthof its generalization,viz. "Everynumberexceeding an arbitrarynumberis one thatthearbitrarynumberis exceededby" ... thusemphasizingthatno peculiarityof two is involved. The first order sentences of arithmetic (FOSA) arethesentences obtainable fromthebasic sentencesby quantificationand takingtruth-functional combinations. It is important hat heseoperationsaretakenrecursively, e.g., a basic sentencecan be generalizedand thencombined withothergeneralizationsby truth-functionalcombinationsandthengeneralizedagainbefore takingfurthertruth-functionalcombinations. The first-order propositions of arithmetic (FOPA) arethepropositionsexpressedby thefirst-ordersentences interpretedin theusual way. Below is anexampleof one ofthesimplestvalid argumentsin first-orderlogic. Everynumberis eithereven or odd. No numberis bothevenandodd. Everynumberwhich isodd is one whosesquareis odd. ? Everynumberwhosesquareis even isitselfeven. Thereis a radicalincreasein expressivepower offirst-orderlanguagesas comparedto basiclanguages.Forexample,eventhefirstpremise in theabove argumentimplies infinitelymany basic consequencesbutit is not implied by any numberof its basicconsequences,not even by all ofthemtogether. The idea thata generalizationis logicallyequivalento theset of itssingular instancesis butone ofthefallaciesthatis to beconfrontedby thoseseeking to reducefirst-orderlogic to basic logic. Below are a few ofthesingular instancesof thepropositionunderdiscussion. SECOND-ORDER LOGIC One is eitherodd or even. Two is eitherodd or even. Threeis eitherodd or even. 69 As mentionedabove basic logic issometimes called finite logic because each of itsconsistent(or non-contradictory)propositionsis finitelysatisfiable. This is no longertrueof first-orderlogic. Indeed, theconjunction of the following twopropositionsis notsatisfiablein any finiteuniverseof discourse. Zero isnotthesuccessor of anynumber. Every twonumberswhicharesuccessorsrespectivelyof distinctnumbers arethemselvesdistinct. It is known, however,thateveryfirst-orderpropositionwhich isconsistent is satisfiablein a countableuniverse of discourse. In fact, everyconsistent first-orderpropositionthatis notsatisfiablein a finiteuniverseof discourse is, like the aboveconjunction,satisfiablein theuniverseof naturalnumbers. For thisreason,first-orderlogic can be calledcountable logic. Justas every validbasic argumentis deducibleusing a small set of axioms and rules of inference, thesame is trueof validfirst-orderarguments. This means thatas faras knowledge ofvalidityof first-orderargumentsis concerned,humanknowing faculties are equal tothetask.Theso-called principle of sufficiency ofreason,viz. thateverytruepropositioncan be known to be true,can be shown to be false.Humanfaculties of knowingtruthare not equal tothetaskof knowingtruth-truthoutrunsknowledge. Withvalidity of first -order aryuments, reasonis sufficient--everyvalidfirst-orderargument can be known to be valid.Whetherevery validargument(whatevertheorder) can be known to be valid is aquestionof considerablecomplexityand well beyondthescope of thiselementaryexposition. Thereis anothermuch lessimportantfactaboutfirst-orderand basic logic thatis worthmentioning. Forthiswe have to divide the logicalconceptsinto positive and negative . Withoutgoing into thedetails, let me saythatthere are nosurpriseshere. "Every", "Some" , "Is", "And", "Or", "If ' , etc. are positive. "Not", "No", "Distinct","Nor", etc. are negative. The resultis thateverycontradictoryfirst-orderpropositioninvolves atleastone negative logicalconcept. Justas we motivatedthetransitionfrombasic logic tofirst-orderlogic by reflecting onthefactthatthe reasoningused toestablisha basic tautology seems strongerthanneeded forthatpurpose and indeed is sufficient (or virtuallyso) to establishallgeneralizationsof thebasic tautology,we use the same sortof insightto transcendfirst-orderlogic.Considerthe following first-orderpropositions. 70 JOHN CORCORAN No numberdivides exactlythenumbersthatdo not dividethemselves. No numberprecedesexactlythenumbersthatdo notprecedethemselves. No numberexceedsexactlythenumbersthatdo not exceedthemselves. No numberperfectsexactlythenumbersthatdo notperfect hemselves. The relationof perfectingarises inconnectionwith theso-calledperfect numbers. Everynumberhavingproperdivisors isperfectedonly bythesuccessor of the sum of itsproperdivisors. The othernumbers,viz. zero, one andthe primenumbers,are notperfectedby anynumbersat all.Thus four is perfectedby threesince two istheonlyproperdivisor of four.Butsix is perfectedby itself. In fact, as you may have seen already, everyp rfectnumber perfectsitselfand, conversely, everynumberperfectingitselfis perfect. Now, thereason forintroducingtheperfectingrelationis to give anexample of atautologyin thesame form asthefirstthreeof the above setbutnot as mathematicallytrivial.Thefirst of the abovepropositionsis mathematically trivialbecause zero, which istheonlynumberthatdoes not divide itself, is divided by everyothernumber. The second istrivialbecauseeverynumber precedesothernumbersbutnotitself.The thirdis trivialforsimilarreasons. Now, as you know, each of the above can be deduced fromtheirown respectivenegationsby familiar(but intricate)reasoning.The fact isthat thefollowingpremise-conclusionargumentis valid. Some numberperfectsexactlythenumbersthatdo notperfectthemselves. ? No numberperfectsexactlythe numbersthatdo notperfectthemselves. A deductionof thisargument,i.e., a deductionof itsconclusionfrom its premise, can easily betransformedinto anindirectproof of its conclusion. The reasonthata deductionof a conclusionfrom thenull-premiseset is a proof (i.e., a deductionwhose premisesareknown to betrue)is becauseuniversalpropositionswith null"subjects"are vacuouslytrue. Everymember of thenull set of premises is known to betrue. . . therebeing nocounterexamples. Once one ofthesetautologieshas been proved to betrueby a deduction from thenull set ofpremises theothersare alsovirtuallyproved to betrue also. The reason for this is theprincipleof form fordeductions:every argumentationin the same form as adeductionis againa deduction. Thus a proofof, say,thefourthcan beobtainedfrom a proofof, say, the first by substitutingin thelatterthe concept "perfects" for theconcept"divides". So it is clearthathereasoningestablishingone ofthefourvirtually establishes much more. SECOND-ORDER LOGIC 71 Now we move tothe second-ordergeneralizationf theabove. Actually, thefollowingsecond-orderpropositionis atonce ageneralizationf each of theabove four firstordertautologiesand, in a certainreasonablesense, the onlygeneralization. No matterwhichnumericalrelationyou consider, no numberbearsit to exactlythenumbersthatdo notbearit tothemselves. Once you have seenthatthisis trueyou will feelthatit is theground of thetruthofthepreviousfourpropositions,e.g., thatthetruthof thefourth of themdependson nopeculiarityof theperfectingrelation. My main pointin this essay isthatthereasoningin a given logic achieves more thancan beexpressedin thatlogicandthat hetranscendingof a given logic by going to ahigherorderis one way ofreapingthefullfruitof one's reasoningin a given logic. This vagueprincipleappliesnotjustto first-order in relationto basic logicand to second-orderlogic inrelation to first-order butin generalto any logic inrelationto thenext lowerorder. In basic sentences,thereareno common nouns. In first-ordersentences, thereare common nouns,butno "second-ordernouns" such as'property', 'relation','function' , etc.The presenceofnounsinevitablyandautomatically entailsthepresenceof quantifiersbecausenounsrequire articlesandarticles expressquantifiers. For example, thefollowingsentencesexpressthesame proposition. Every falsepropositionimplies a trueproposition. Everypropositionwhich is false implies somepropositionwhich istrue. For everypropositionwhich is falsethereexistsa propositionwhich is trueand which isimplied by thefalseproposition. The same phenomenoncan be exemplified intheuniverseof natural numbers(beginningwithzero). Every oddnumberexceeds an even umber. Everynumberwhich isodd exceeds somenumberwhich is even. For everynumberwhich isodd thereexistsa numberwhich is evenand which is exceeded bytheodd number. Whenwe move tosecond-orderby addingsecond-ordernounswe alsoadd second-orderadjectiveswhose rangesof significance are thesecond-orderobjectsdenotedby thesecond-ordernouns.Examplesofsecond-orderadjectives are thefamiliartermsindicatingpropertiesof relations:reflexive,symmetrical,transitive,dense, etc. The following aretypicalsecond-ordersentences involving suchexpressions. 72 JOHN CORCORAN Everyreflexiverelationrelateseveryobjectto itself. Everyrelationthatrelateseveryobjectto itselfis reflexive. Everysymmetricrelationrelatesto eachotherevery two bjectsone of which itrelatesto theother. Everyrelationthatrelatesto eachotherevery two bjectsone of which it relatesto theotheris symmetric. Orthogonalityis a second-orderelationbetweenproperties.In orderfor one propertyto beorthogonalto anotherit is necessaryandsufficientthat therebe fourobjects,one havingbothproperties,one havingthefirstbut lackingthesecond, onelackingthe firstbut havingthe second, and one lackingboth.Theseexamplesshowthatmuch ofthisessay has beenwritten using asecond-orderlanguage. Since basic logic is finiteand since first-orderlogic iscountable,neither is adequatetoaxiomatizetheorieswhose universes ofdiscourseareuncountable. The most familiarexamplesof suchtheoriesarecalculusandgeometry. Nowjustas first-orderlogic is not finite,second-orderlogic is notcountable. Thereare consistentsecond-orderpropositionswhich are notsatisfiablein any countableuniverse. One example is from Hilbert'saxiom set forthe theoryof realnumbers(which isfoundationalforcalculus).Anotheris from Veblen's axiom set forEuclideangeometry.Naturally,second-orderlogic can be calleduncountable logic. First-orderlogic isnoteven adequateto axiomatizetheorieswhose universes ofdiscoursearecountablyinfinite. The paradigmcase ofsucha theory is numbertheory, orthearithmeticof naturalnumbers, which requiresthe principle of mathematical induction (PM!) . Everypropertybelongingto zeroandtothesuccessorof everynumber to which it belongs also belongs to everynumberwithoutexception. In orderfor apropertyto belong to everynumberit is sufficient for thatpropertyto belong tothesuccessorof everynumberhavingit and alsothatzero have it. Mathematicalinductionis thesecond-ordergeneralizationf each ofthe followingpropositionswhich areamong its first-orderinstances. If zero is evenand thesuccessorof every evennumberis even, then everynumberis even. If zero isperfectandthesuccessorof everyperfectnumberis perfect, then everynumberis perfect. In first-orderaxiomatizationsofarithmeticPMI, induction,is replacedby theinfinite set of itsfirst-orderinstances,a set which is insufficient to imply SECOND-ORDER LOGIC 73 mathematicalinduction.In fact, nosetoftruefirst-orderpropositionsis sufficient to implyPMI andthereforenofirst-orderaxiomatizationofarithmetic adequatelycodifiesourknowledge ofarithmetic. Moreover,thegroundof our knowledge oftheinstancesis ourknowledge ofPMI itself.Thus infinitely manyof the so-calledaxioms offirst-orderarithmeticarenotaxiomaticin the traditionalsense. Nevertheless,thereare able logiciansand mathematicians who reject thetraditionalsecond-orderaxiomatizationsdue toDedekindand Peanoin favor ofirst-orderaxiomatizationswhichdatefrom the1930's. Justas second-orderlogic isnecessaryto fullyexploitfirst-ordereasoning as well as tounderstandthegroundoffirst-ordertautologies,likewise secondorderlogic isnecessaryto fullyexploitfirst-orderknowledge inarithmeticas well as tounderstandthegroundof acceptanceof first-orderaxiomatizationsof arithmetic. Even logicianswho rejectsecond-orderaxiomatizations of arithmeticadmit theirhistoricimportanceand make heuristicand pedagogical use of suchaxiomatizations.By theway, thesame thingmay be said ofaxiomatizationsofsettheory,butthetechnicaldetailsinvolved in set theoryrequiredistinctionsandprincipleswhich gobeyondthescope ofthis essay. In thecase of basic logic, as well asthatof first-orderlogic, a small set of simple rules ofinferencesuffices toenableevery validargumentto be deduced. This is no longerthecase withsecond-orderlogic. In fact, it is a corollarytothefamous G6delIncompletenessTheoremthatno simple set of rules is sufficient forthispurpose. This means that heprincipleof sufficiency ofreasonwhenappliedtosecond-ordervalidityis false. To beexplicit, there are finite validargumentsin second-orderlogic whoseconclusionscan not be deduced(in a finitenumberofsteps using simple rules) fromtheirpremisesets. This resultis known astheincompleteness of second-order logic. Thereare logicians who feelthathumanreasoningmust be equalto the taskof determiningthevalidityof validarguments.In most cases such logicians areempiricisticallyorientedand are fully willing toacceptthefact thattherearetruepropositionsaboutthematerialuniversethatcannotbe known to betrue. But theyfeelthatvalidityis intrinsicallyamenableto analytica priori methodsand, in particular,thatevery validargumentmust be deducible. One wayoutof thisquandaryis to denythatsecond-order logic is really logic. Incidentally,second-orderaxiomatizationsdo not evadetheincompletability ofarithmetic. First-orderaxiomatizationsare deficientbecausefirst-order languagesare too weak toexpressourknowledge ofarithmeticeven though first-ordereasoningis adequateto first-ordervalidity. Withinsecond-order thesituationis reversed.Second-orderaxiomatizationsare deficientbecause second-orderreasoningis too weak to deduce all ofthe consequencesof second-orderaxioms even thoughsecond-orderlanguageis strongenough toexpressourknowledge ofarithmetic. In fact,oursecond-orderarithmetic knowledge impliesabsolutelyeverytruesecond-orderarithmeticproposition 74 JOHN CORCORAN even thosethatwe are powerless todeduce(using any givensimple set of rules fixed inadvance). Anotherphenomenonthatgives some logiciansdoubtsaboutsecond-order logic isexistenceofcontradictorypropositionsdevoid ofnegativelogical concepts. Recallthatin first-orderlogic everycontradictorypropositioninvolves at least onenegativelogicalconcept. Below are twosecond-orderpropositionsthefirst of which istautologicalndthesecond of which iscontradictory, neitherof which involvenegativelogicalconcepts. Everyobjecthas atleastone property. Everypropertybelongsto atleastone object. The reasonthatthesecondpropositionis self-contradictoryis thatit contradictsthefollowingtautology. No objecthas thepropertyof beingdistinctfrom itself. We have seenthatsecond-orderlogic differsradicallyfrom first-order. First-orderis a logic ofcountability;second-orderis a logic ofuncountability. First-orderis deductivelycomplete; second-orderis deductivelyincomplete. Infirst-ordereverycontradictionis negative;in second-orderthereare self-contradictorypropositionswhich are exclusivelypositive. The abovementionedhistoricexamplesofaxiomatizedsciencesremind us thathigherorderreasoningis not arecentinnovationbut rathera featureof human thoughthavinga longhistory. Moreover, it isnotthecase thatlogicians startedoutstudyingbasic logicand thenmoved on tofirst-orderand then tosecond-order,etc. Inthefirst place,Aristotle'slogic is afragmentof firstorderand fundamentalaspectsof basic logic were not to bediscoveredfor some centurieslater.In thesecond place, inmoderntimes higher-orderlogics werestudiedbefore first-orderlogic wasisolatedas a systemworthyofstudy in its ownright. AfterAristotle's logic had been assimilatedby laterthinkers,people emergedwho couldnot accepttheidea thatAristotle'slogic was not comprehensive. These conservativelogiciansattemptedto "reduce"all logically cogentreasoningto Aristotle'syllogisticlogic. Likewise, afterfirst-order logic had beenisolatedand had beenassimilatedby thelogiccommunity, people emergedwho couldnotaccepttheidea thatfirst-orderlogic was not comprehensive.Theselogicians can be viewed not asconservativeswho want to reinstatean outmodedtraditionbutratheras radicalswho wantto overthrowan establishedtradition. It remainsto be seenwhetherhigher-order logic will ever regainthedegree ofacceptancethatit enjoyedbetween1910 and 1930. Buttherehas never been aseriousdoubtconcerningits heuristic andhistoricimportance. In fact, people who do not knowsecond-orderlogic can notunderstandthemoderndebateover itslegitimacyandtheyarecutoff fromtheheuristicadvantagesof second-orderlogic. And, whatmay be SECOND-ORDER LOGIC 75 worse,theyare cut-off from anunderstandingofthehistoryof logicandthe historyof mathematics, andthusareconstrainedto havedistortedviews of thenatureofthetwosubjects.As Aristotlefirst said, we do notunderstand a disciplineuntilwe have seen itsdevelopment. It is atruismthata person's conceptions ofwhata discipline is and ofwhatit can become arepredicated on aconceptionofwhatit has been. ACKNOWLEDGEMENTS This essayis based on atutorialthatI led at the OhioUniversityInference Conference,October9-11,1986. I am indebtedtoProfessorRichardButrick not only fororganizingtheconferencebutalso fororganizingme. In the yearpriorto theconference hesuppliedme, by phone andin writing,with dozens ofquestions,hypotheses,suggestionsandrequestsfrom whichthebasic contentandgoals of mytutorialemerged. James Gasser, Woosuk Park and Ronald Rudnicki helped withtheeditingand proof-reading. I am also indebtedto thestudentsand colleagueswithwhom I studiedsecond-order logic over the years, especially George Weaver,StewartShapiro, Michael Scanlanand EdwardKeenan. Verylittlein this essay is original. Most of whatis here isalreadyin thewritingsof Alfred Tarski, Leon Henkin, Alonzo Church, Georg Kreisel and George Boolos. Almost everyhumanisticallyoriented essay onmodernlogic isindebtedto Tarski,Church,andQuine. Their technicalcompetence,theirobjectivity,theircreativityand, above all,their constantattentionto thehumanimportanceof logic are largelyresponsible forpreserving,transformingand revitalizinga richtraditionthat racesback toAristotle. One sign ofthevitalityofthetraditionis thefactthatnot one of theabove-mentionedlogicians agrees witheverythingwrittenin this essay, even when theheuristicover-simplificationsare emended.