Necessity and sufficiency - Wikipedia

In general, a necessary condition is one that must be present in order for another condition to occur, while a sufficient condition is one that produces the ... Necessityandsufficiency FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Termstodescribeaconditionalrelationshipbetweentwostatements Thisarticleisabouttheformalterminologyinlogic.Forcausalmeaningsoftheterms,seeCausality.Fortheconceptsinstatistics,seeSufficientstatistic. Inlogicandmathematics,necessityandsufficiencyaretermsusedtodescribeaconditionalorimplicationalrelationshipbetweentwostatements.Forexample,intheconditionalstatement:"IfPthenQ",QisnecessaryforP,becausethetruthofQisguaranteedbythetruthofP(equivalently,itisimpossibletohavePwithoutQ).[1]Similarly,PissufficientforQ,becausePbeingtruealwaysimpliesthatQistrue,butPnotbeingtruedoesnotalwaysimplythatQisnottrue.[2] Ingeneral,anecessaryconditionisonethatmustbepresentinorderforanotherconditiontooccur,whileasufficientconditionisonethatproducesthesaidcondition.[3]Theassertionthatastatementisa"necessaryandsufficient"conditionofanothermeansthattheformerstatementistrueifandonlyifthelatteristrue.Thatis,thetwostatementsmustbeeithersimultaneouslytrue,orsimultaneouslyfalse.[4][5][6] InordinaryEnglish(alsonaturallanguage)"necessary"and"sufficient"indicaterelationsbetweenconditionsorstatesofaffairs,notstatements.Forexample,beingamaleisanecessaryconditionforbeingabrother,butitisnotsufficient—whilebeingamalesiblingisanecessaryandsufficientconditionforbeingabrother. Anyconditionalstatementconsistsofatleastonesufficientconditionandatleastonenecessarycondition. Contents 1Definitions 2Necessity 3Sufficiency 4Relationshipbetweennecessityandsufficiency 5Simultaneousnecessityandsufficiency 6Seealso 7References 8Externallinks Definitions[edit] Intheconditionalstatement,"ifS,thenN",theexpressionrepresentedbySiscalledtheantecedent,andtheexpressionrepresentedbyNiscalledtheconsequent.Thisconditionalstatementmaybewritteninseveralequivalentways,suchas"NifS","SonlyifN","SimpliesN","NisimpliedbyS",S→N,S⇒Nand"NwheneverS".[7] Intheabovesituation,NissaidtobeanecessaryconditionforS.Incommonlanguage,thisisequivalenttosayingthatiftheconditionalstatementisatruestatement,thentheconsequentNmustbetrue—ifSistobetrue(seethirdcolumnof"truthtable"immediatelybelow).Inotherwords,theantecedentScannotbetruewithoutNbeingtrue.Forexample,inorderforsomeonetobecalledSocrates,itisnecessaryforthatsomeonetobeNamed.Similarly,inorderforhumanbeingstolive,itisnecessarythattheyhaveair.[8] Intheabovesituation,onecanalsosaySisasufficientconditionforN(referagaintothethirdcolumnofthetruthtableimmediatelybelow).Iftheconditionalstatementistrue,thenifSistrue,Nmustbetrue;whereasiftheconditionalstatementistrueandNistrue,thenSmaybetrueorbefalse.Incommonterms,"thetruthofSguaranteesthetruthofN".[8]Forexample,carryingonfromthepreviousexample,onecansaythatknowingthatsomeoneiscalledSocratesissufficienttoknowthatsomeonehasaName. Anecessaryandsufficientconditionrequiresthatbothoftheimplications S ⇒ N {\displaystyleS\RightarrowN} and N ⇒ S {\displaystyleN\RightarrowS} (thelatterofwhichcanalsobewrittenas S ⇐ N {\displaystyleS\LeftarrowN} )hold.ThefirstimplicationsuggeststhatSisasufficientconditionforN,whilethesecondimplicationsuggeststhatSisanecessaryconditionforN.Thisisexpressedas"SisnecessaryandsufficientforN","SifandonlyifN",or S ⇔ N {\displaystyleS\LeftrightarrowN} . Truthtable S N S ⇒ N {\displaystyleS\RightarrowN} S ⇐ N {\displaystyleS\LeftarrowN} S ⇔ N {\displaystyleS\LeftrightarrowN} T T T T T T F F T F F T T F F F F T T T Necessity[edit] Thesunbeingabovethehorizonisanecessaryconditionfordirectsunlight;butitisnotasufficientcondition,assomethingelsemaybecastingashadow,e.g.,themooninthecaseofaneclipse. TheassertionthatQisnecessaryforPiscolloquiallyequivalentto"PcannotbetrueunlessQistrue"or"ifQisfalse,thenPisfalse".[8][1]Bycontraposition,thisisthesamethingas"wheneverPistrue,soisQ". ThelogicalrelationbetweenPandQisexpressedas"ifP,thenQ"anddenoted"P⇒Q"(PimpliesQ).Itmayalsobeexpressedasanyof"PonlyifQ","Q,ifP","QwheneverP",and"QwhenP".Oneoftenfinds,inmathematicalproseforinstance,severalnecessaryconditionsthat,takentogether,constituteasufficientcondition(i.e.,individuallynecessaryandjointlysufficient[8]),asshowninExample5. Example1 Forittobetruethat"Johnisabachelor",itisnecessarythatitbealsotruethatheis unmarried, male, adult, sincetostate"Johnisabachelor"impliesJohnhaseachofthosethreeadditionalpredicates. Example2 Forthewholenumbersgreaterthantwo,beingoddisnecessarytobeingprime,sincetwoistheonlywholenumberthatisbothevenandprime. Example3 Considerthunder,thesoundcausedbylightning.Onesaysthatthunderisnecessaryforlightning,sincelightningneveroccurswithoutthunder.Wheneverthereislightning,thereisthunder.Thethunderdoesnotcausethelightning(sincelightningcausesthunder),butbecauselightningalwayscomeswiththunder,wesaythatthunderisnecessaryforlightning.(Thatis,initsformalsense,necessitydoesn'timplycausality.) Example4 Beingatleast30yearsoldisnecessaryforservingintheU.S.Senate.Ifyouareunder30yearsold,thenitisimpossibleforyoutobeasenator.Thatis,ifyouareasenator,itfollowsthatyoumustbeatleast30yearsold. Example5 Inalgebra,forsomesetStogetherwithanoperation ⋆ {\displaystyle\star} toformagroup,itisnecessarythat ⋆ {\displaystyle\star} beassociative.ItisalsonecessarythatSincludeaspecialelementesuchthatforeveryxinS,itisthecasethate ⋆ {\displaystyle\star} xandx ⋆ {\displaystyle\star} ebothequalx.ItisalsonecessarythatforeveryxinSthereexistacorrespondingelementx″,suchthatbothx ⋆ {\displaystyle\star} x″andx″ ⋆ {\displaystyle\star} xequalthespecialelemente.Noneofthesethreenecessaryconditionsbyitselfissufficient,buttheconjunctionofthethreeis. Sufficiency[edit] Thatatrainrunsonschedulecanbeasufficientconditionforarrivingontime(ifoneboardsthetrainanditdepartsontime,thenonewillarriveontime);butitisnotalwaysanecessarycondition,sincethereareotherwaystotravel(ifthetraindoesnotruntotime,onecouldstillarriveontimethroughothermeansoftransport). IfPissufficientforQ,thenknowingPtobetrueisadequategroundstoconcludethatQistrue;however,knowingPtobefalsedoesnotmeetaminimalneedtoconcludethatQisfalse. Thelogicalrelationis,asbefore,expressedas"ifP,thenQ"or"P⇒Q".Thiscanalsobeexpressedas"PonlyifQ","PimpliesQ"orseveralothervariants.Itmaybethecasethatseveralsufficientconditions,whentakentogether,constituteasinglenecessarycondition(i.e.,individuallysufficientandjointlynecessary),asillustratedinexample5. Example1 "Johnisaking"impliesthatJohnismale.SoknowingthatJohnisakingissufficienttoknowingthatheisamale. Example2 Anumber'sbeingdivisibleby4issufficient(butnotnecessary)forittobeeven,butbeingdivisibleby2isbothsufficientandnecessaryforittobeeven. Example3 Anoccurrenceofthunderisasufficientconditionfortheoccurrenceoflightninginthesensethathearingthunder,andunambiguouslyrecognizingitassuch,justifiesconcludingthattherehasbeenalightningbolt. Example4 IftheU.S.Congresspassesabill,thepresident'ssigningofthebillissufficienttomakeitlaw.Notethatthecasewherebythepresidentdidnotsignthebill,e.g.throughexercisingapresidentialveto,doesnotmeanthatthebillhasnotbecomealaw(forexample,itcouldstillhavebecomealawthroughacongressionaloverride). Example5 Thatthecenterofaplayingcardshouldbemarkedwithasinglelargespade(♠)issufficientforthecardtobeanace.Threeothersufficientconditionsarethatthecenterofthecardbemarkedwithasinglediamond(♦),heart(♥),orclub(♣).Noneoftheseconditionsisnecessarytothecard'sbeinganace,buttheirdisjunctionis,sincenocardcanbeanacewithoutfulfillingatleast(infact,exactly)oneoftheseconditions. Relationshipbetweennecessityandsufficiency[edit] BeinginthepurpleregionissufficientforbeinginA,butnotnecessary.BeinginAisnecessaryforbeinginthepurpleregion,butnotsufficient.BeinginAandbeinginBisnecessaryandsufficientforbeinginthepurpleregion. Aconditioncanbeeithernecessaryorsufficientwithoutbeingtheother.Forinstance,beingamammal(N)isnecessarybutnotsufficienttobeinghuman(S),andthatanumber x {\displaystylex} isrational(S)issufficientbutnotnecessaryto x {\displaystylex} beingarealnumber(N)(sincetherearerealnumbersthatarenotrational). Aconditioncanbebothnecessaryandsufficient.Forexample,atpresent,"todayistheFourthofJuly"isanecessaryandsufficientconditionfor"todayisIndependenceDayintheUnitedStates".Similarly,anecessaryandsufficientconditionforinvertibilityofamatrixMisthatMhasanonzerodeterminant. Mathematicallyspeaking,necessityandsufficiencyaredualtooneanother.ForanystatementsSandN,theassertionthat"NisnecessaryforS"isequivalenttotheassertionthat"SissufficientforN".Anotherfacetofthisdualityisthat,asillustratedabove,conjunctions(using"and")ofnecessaryconditionsmayachievesufficiency,whiledisjunctions(using"or")ofsufficientconditionsmayachievenecessity.Forathirdfacet,identifyeverymathematicalpredicateNwiththesetT(N)ofobjects,events,orstatementsforwhichNholdstrue;thenassertingthenecessityofNforSisequivalenttoclaimingthatT(N)isasupersetofT(S),whileassertingthesufficiencyofSforNisequivalenttoclaimingthatT(S)isasubsetofT(N). Simultaneousnecessityandsufficiency[edit] Seealso:Materialequivalence TosaythatPisnecessaryandsufficientforQistosaytwothings: thatPisnecessaryforQ, P ⇐ Q {\displaystyleP\LeftarrowQ} ,andthatPissufficientforQ, P ⇒ Q {\displaystyleP\RightarrowQ} . equivalently,itmaybeunderstoodtosaythatPandQisnecessaryfortheother, P ⇒ Q ∧ Q ⇒ P {\displaystyleP\RightarrowQ\landQ\RightarrowP} ,whichcanalsobestatedaseachissufficientfororimpliestheother. Onemaysummarizeany,andthusall,ofthesecasesbythestatement"PifandonlyifQ",whichisdenotedby P ⇔ Q {\displaystyleP\LeftrightarrowQ} ,whereascasestellusthat P ⇔ Q {\displaystyleP\LeftrightarrowQ} isidenticalto P ⇒ Q ∧ Q ⇒ P {\displaystyleP\RightarrowQ\landQ\RightarrowP} . Forexample,ingraphtheoryagraphGiscalledbipartiteifitispossibletoassigntoeachofitsverticesthecolorblackorwhiteinsuchawaythateveryedgeofGhasoneendpointofeachcolor.Andforanygraphtobebipartite,itisanecessaryandsufficientconditionthatitcontainnoodd-lengthcycles.Thus,discoveringwhetheragraphhasanyoddcyclestellsonewhetheritisbipartiteandconversely.Aphilosopher[9]mightcharacterizethisstateofaffairsthus:"Althoughtheconceptsofbipartitenessandabsenceofoddcyclesdifferinintension,theyhaveidenticalextension.[10] Inmathematics,theoremsareoftenstatedintheform"PistrueifandonlyifQistrue". Because,asexplainedinprevioussection,necessityofonefortheotherisequivalenttosufficiencyoftheotherforthefirstone,e.g. P ⇐ Q {\displaystyleP\LeftarrowQ} isequivalentto Q ⇒ P {\displaystyleQ\RightarrowP} ,ifPisnecessaryandsufficientforQ,thenQisnecessaryandsufficientforP.Wecanwrite P ⇔ Q ≡ Q ⇔ P {\displaystyleP\LeftrightarrowQ\equivQ\LeftrightarrowP} andsaythatthestatements"PistrueifandonlyifQ,istrue"and"QistrueifandonlyifPistrue"areequivalent. Seealso[edit] Affirmingtheconsequent Biologicaltestsofnecessityandsufficiency Causality Closedconcept Denyingtheantecedent Ifandonlyif Materialimplication(disambiguation) Principleofsufficientreason Wasonselectiontask Modusponens Modustollens References[edit] ^ab"[M06]Necessityandsufficiency".philosophy.hku.hk.Retrieved2019-12-02. ^Bloch,EthanD.(2011).ProofsandFundamentals:AFirstCourseinAbstractMathematics.Springer.pp. 8–9.ISBN 978-1-4419-7126-5. ^Confusion-of-Necessary(2019-05-15)."ConfusionofNecessarywithaSufficientCondition".www.txstate.edu.Retrieved2019-12-02. ^Betz,Frederick(2011).ManagingScience:MethodologyandOrganizationofResearch.NewYork:Springer.p. 247.ISBN 978-1-4419-7487-7. ^Manktelow,K.I.(1999).ReasoningandThinking.EastSussex,UK:PsychologyPress.ISBN 0-86377-708-2. ^Asnina,Erika;Osis,Janis&Jansone,Asnate(2013)."FormalSpecificationofTopologicalRelations".DatabasesandInformationSystemsVII.249(DatabasesandInformationSystemsVII):175.doi:10.3233/978-1-61499-161-8-175. ^Devlin,Keith(2004),Sets,FunctionsandLogic/AnIntroductiontoAbstractMathematics(3rd ed.),Chapman&Hall,pp. 22–23,ISBN 978-1-58488-449-1 ^abcd"TheConceptofNecessaryConditionsandSufficientConditions".www.sfu.ca.Retrieved2019-12-02. ^StanfordUniversityprimer,2006. ^"Meanings,inthissense,areoftencalledintensions,andthingsdesignated,extensions.Contextsinwhichextensionisallthatmattersare,naturally,calledextensional,whilecontextsinwhichextensionisnotenoughareintensional.Mathematicsistypicallyextensionalthroughout."StanfordUniversityprimer,2006. Externallinks[edit] WikimediaCommonshasmediarelatedtoNecessityandsufficiency. Criticalthinkingwebtutorial:NecessaryandSufficientConditions SimonFraserUniversity:Conceptswithexamples vteLogic Outline History Fields Computerscience Formalsemantics(naturallanguage) Inference Philosophyoflogic Proof Semanticsoflogic Syntax Logics Classical Informal Criticalthinking Reason Mathematical Non-classical Philosophical Theories Argumentation Metalogic Metamathematics Set Foundations Abduction Analyticandsyntheticpropositions Contradiction Paradox Antinomy Deduction Deductiveclosure Definition Description Entailment Linguistic Form Induction Logicaltruth Name Necessityandsufficiency Premise Probability Reference Statement Substitution Truth Validity Liststopics Mathematicallogic Booleanalgebra Settheory other Logicians Rulesofinference Paradoxes Fallacies Logicsymbols  Philosophyportal Category WikiProject (talk) changes Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Necessity_and_sufficiency&oldid=1102005747" Categories:NecessityandsufficiencyConceptsinlogicConceptsinmetaphysicsDichotomiesMathematicalterminologyHiddencategories:ArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataCommonscategorylinkfromWikidata Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Inotherprojects WikimediaCommons Languages አማርኛالعربيةتۆرکجهCatalàČeštinaDeutschEspañolEsperantoEuskaraفارسی한국어ՀայերենInterlinguaItalianoҚазақшаမြန်မာဘာသာNederlandsPortuguêsРусскийSimpleEnglishSoomaaligaSuomiSvenskaУкраїнська粵語中文 Editlinks