Frisören rakar sig. Bertrand Russells paradox

Den mest kända av de paradoxer som upptäcktes redan under förra seklet är den antinomin som Bertrand Russell upptäckte och meddelade av honom i ett brev till G. Ferge. Russell upptäckte sin paradox relaterad till området logik och matematik 1902. Samma antinomi diskuterades samtidigt i Göttingen av de tyska matematikerna Z. Zermelo (1871-1953) och D. Hilbert. Idén låg i luften, och dess publicering gav intryck av en exploderande bomb Miroshnichenko P.N. Vad förstörde Russells paradox i Freges system? // Modern logik: problem med teori, historia och tillämpning inom vetenskap. - SPb., 2000. - S. 512-514. . Denna paradox orsakade i matematiken, enligt Hilbert, effekten av en fullständig katastrof. De enklaste och viktigaste logiska metoderna, de vanligaste och mest användbara begreppen, är hotade. Det visade sig att det i Cantors mängdlära, som entusiastiskt accepterades av de flesta matematiker, finns märkliga motsättningar som är omöjliga, eller åtminstone mycket svåra, att bli av med. Russells paradox förde fram dessa motsättningar med särskild klarhet. De mest framstående matematikerna under dessa år arbetade på dess upplösning, såväl som på upplösningen av andra hittade paradoxer i Cantors mängdteori. Det blev omedelbart uppenbart att varken i logiken eller i matematiken, under hela deras långa historia av deras existens, var något bestämt utarbetat som kunde tjäna som grund för att eliminera antinomin. Uppenbarligen var det nödvändigt att avvika från vanliga sätt att tänka. Men varifrån och åt vilket håll? Courant R., Robbins G. Vad är matematik? - Ch. II, § 4.5.

Hur radikalt skulle förkastandet av etablerade teoretiseringssätt vara? Med ytterligare studier av antinomin växte övertygelsen om behovet av ett fundamentalt nytt tillvägagångssätt stadigt. Ett halvt sekel efter upptäckten har specialister på grunderna för logik och matematik L. Frenkel och I. Bar-Hillel redan sagt utan några reservationer: , hittills undantagslöst misslyckats, är uppenbarligen otillräckliga för detta ändamål. Den moderna amerikanske logikern H. Curry skrev lite senare om denna paradox: ”När det gäller den logik som kändes under 1800-talet, trotsade situationen helt enkelt förklaring, även om det naturligtvis i vår utbildade tid kan finnas människor som ser (eller tror de ser ), vad är felet” Miroshnichenko P.N. Vad förstörde Russells paradox i Freges system? // Modern logik: problem med teori, historia och tillämpning inom vetenskap. - SPb., 2000. - S. 512-514 ..

Russells paradox i sin ursprungliga form är kopplad till begreppet en uppsättning, eller en klass. Vi kan prata om mängder av olika objekt, till exempel om mängden av alla människor eller om mängden naturliga tal. Ett element i den första uppsättningen kommer att vara vilken enskild person som helst, ett element i den andra - varje naturligt tal. Det är också möjligt att betrakta uppsättningar själva som vissa objekt och tala om uppsättningar av uppsättningar. Man kan till och med introducera sådana begrepp som uppsättningen av alla uppsättningar eller uppsättningen av alla koncept. Med avseende på vilken uppsättning som helst som tas godtyckligt, verkar det rimligt att fråga sig om det är dess eget element eller inte. Uppsättningar som inte innehåller sig själva som ett element kommer att kallas vanliga. Till exempel är mängden av alla människor inte en person, precis som mängden atomer inte är en atom. Uppsättningar som är korrekta element kommer att vara ovanliga. Till exempel är en mängd som förenar alla mängder en mängd och innehåller därför sig själv som ett element.

Eftersom det är ett set kan man också fråga om det är vanligt eller ovanligt. Svaret är dock nedslående. Om den är vanlig måste den per definition innehålla sig själv som ett element, eftersom den innehåller alla vanliga mängder. Men det betyder att det är en ovanlig uppsättning. Antagandet att vår uppsättning är en vanlig mängd leder alltså till en motsägelse. Så det kan inte vara normalt. Å andra sidan kan det inte heller vara ovanligt: ​​en ovanlig mängd innehåller sig själv som ett element, och elementen i vår uppsättning är bara vanliga mängder. Som ett resultat kommer vi till slutsatsen att mängden av alla vanliga uppsättningar inte kan vara vare sig vanliga eller extraordinära.

Således är mängden av alla uppsättningar som inte är korrekta element ett korrekt element om och endast om det inte är ett sådant element. Detta är en klar motsägelse. Och det erhölls på grundval av de mest rimliga antaganden och med hjälp av till synes obestridliga steg. Motsägelsen säger att en sådan uppsättning helt enkelt inte existerar. Men varför kan det inte finnas? Det består trots allt av föremål som uppfyller ett väldefinierat villkor, och själva villkoret verkar inte på något sätt vara exceptionellt eller dunkelt. Om en mängd så enkelt och tydligt definierad inte kan existera, vad är då egentligen skillnaden mellan möjliga och omöjliga mängder? Slutsatsen att den aktuella uppsättningen inte existerar låter oväntat och oroande. Det gör vår allmänna uppfattning om en uppsättning amorf och kaotisk, och det finns ingen garanti för att den inte kan ge upphov till några nya paradoxer.

Russells paradox är anmärkningsvärd för dess extrema allmänning Courant R., Robbins G. Vad är matematik? - Ch. II, § 4.5. . För dess konstruktion behövs inga komplexa tekniska begrepp, eftersom i fallet med vissa andra paradoxer är begreppen "uppsättning" och "element av uppsättningen" tillräckliga. Men denna enkelhet talar bara om dess grundläggande natur: den berör de djupaste grunderna för vårt resonemang om mängder, eftersom den inte talar om några speciella fall, utan om mängder i allmänhet.

Andra varianter av paradoxen Russells paradox är inte specifikt matematisk. Den använder begreppet en mängd, men berör inte några speciella egenskaper som är associerade specifikt med matematik.

Detta blir uppenbart när paradoxen omformuleras i rent logiska termer. Av varje egenskap kan man med stor sannolikhet fråga sig om den är tillämplig på sig själv eller inte. Egenskapen att vara varm gäller till exempel inte sig själv, eftersom den inte i sig själv är varm; egenskapen att vara konkret hänvisar inte heller till sig själv, för det är en abstrakt egenskap. Men egenskapen att vara abstrakt, att vara abstrakt, är tillämplig på en själv.

Låt oss kalla dessa egenskaper otillämpliga på sig själva otillämpliga. Gäller egenskapen att vara otillämplig för sig själv? Det visar sig att otillämplighet är otillämplig bara om den inte är det. Detta är naturligtvis paradoxalt. Den logiska, egenskapsrelaterade varianten av Russells antinomi är lika paradoxal som den matematiska, mängdrelaterade varianten.

Russell föreslog också följande populära version av paradoxen som upptäcktes av honom Katrechko S.L. Russells Barbers paradox och Plato-Aristoteles dialektik // Modern Logic: Problems of Theory, History and Application in Science. - SPb., 2002. - S. 239-242 .. Låt oss föreställa oss att rådet i en by definierade barberarens plikter på detta sätt: att raka alla män i byn som inte rakar sig själva, och bara dessa män. Ska han raka sig? Om så är fallet kommer det att hänvisa till de som rakar sig, och de som rakar sig själva, han ska inte raka sig. Om inte kommer han att tillhöra dem som inte rakar sig, och därför måste han raka sig själv. Vi kommer alltså fram till att denna barberare rakar sig om och bara om han inte rakar sig själv. Detta är naturligtvis omöjligt.

Argumentet om frisören bygger på antagandet att en sådan frisör existerar. Den resulterande motsägelsen innebär att detta antagande är falskt, och det finns ingen sådan bybor som skulle raka alla dessa och bara de bybor som inte rakar sig själva. En frisörs plikter verkar inte motsägelsefulla vid första anblicken, så slutsatsen att det inte kan finnas någon låter lite oväntat. Denna slutsats är dock inte paradoxal. Villkoret som bybarberaren måste uppfylla är i själva verket självmotsägande och därför omöjligt. Det kan inte finnas en sådan frisör i byn av samma anledning som det inte finns någon person i den som skulle vara äldre än han själv eller som skulle födas före hans födelse Miroshnichenko P.N. Vad förstörde Russells paradox i Freges system? // Modern logik: problem med teori, historia och tillämpning inom vetenskap. - SPb., 2000. - S. 512-514 ..

Argumentet om barberaren kan kallas en pseudoparadox. I sin kurs är den strikt analog med Russells paradox, och det är detta som gör den intressant. Men det är fortfarande inte en sann paradox.

Ett annat exempel på samma pseudo-paradox är det välkända katalogargumentet. Ett visst bibliotek bestämde sig för att sammanställa en bibliografisk katalog som skulle omfatta alla dessa och endast de bibliografiska kataloger som inte innehåller referenser till dem själva. Ska en sådan katalog innehålla en länk till sig själv? Det är lätt att visa att idén med att skapa en sådan katalog inte är genomförbar; den kan helt enkelt inte existera, eftersom den samtidigt måste innehålla en referens till sig själv och inte inkludera.

Det är intressant att notera att katalogisering av alla kataloger som inte innehåller referenser till sig själva kan ses som en oändlig, aldrig sinande process. Låt oss säga att en katalog, säg K1, kompilerades vid något tillfälle, inklusive alla andra kataloger som inte innehåller referenser till dem själva. Med skapandet av K1 dök en annan katalog upp som inte innehåller en länk till sig själv. Eftersom målet är att göra en komplett katalog över alla kataloger som inte nämner sig själva, är det uppenbart att K1 inte är lösningen. Han nämner inte en av dessa kataloger - han själv. Inklusive detta omnämnande av honom själv i K1, får vi K2-katalogen. Den nämner K1, men inte K2 själv. Om vi ​​lägger till ett sådant omnämnande till K2 får vi KZ, som återigen inte är komplett på grund av att det inte nämner sig själv. Och på utan slut.

Ytterligare en logisk paradox kan nämnas - de holländska borgmästarnas paradox, liknande frisörens paradox. Varje kommun i Holland måste ha en borgmästare och två olika kommuner kan inte ha samma borgmästare. Ibland visar det sig att borgmästaren inte bor i sin kommun. Låt oss anta att det antas en lag genom vilken ett område S exklusivt tilldelas sådana borgmästare som inte bor i sina kommuner, och som uppmanar alla dessa borgmästare att bosätta sig i detta territorium. Antag vidare att det finns så många av dessa borgmästare att själva territoriet S bildar en egen kommun. Var ska borgmästaren i denna specialkommun S bo? Enkla resonemang visar att om borgmästaren i en specialkommun bor i territorium S, så ska han inte bo där, och vice versa, om han inte bor i territoriet, då måste han bo i detta territorium. Att denna paradox är analog med frisörens paradox är ganska uppenbart.

Russell var en av de första som föreslog en lösning på "sin" paradox. Lösningen han föreslog kallades "typteori": en mängd (klass) och dess element tillhör olika logiska typer, typen av en mängd är högre än typen av dess element, vilket eliminerar Russells paradox (typteori användes också av Russell för att lösa den berömda "Liar"-paradoxen). Många matematiker accepterade dock inte Russells lösning, eftersom de ansåg att den lägger alltför stränga begränsningar på de matematiska påståendena av Katrechko S.L. Russells Barbers paradox och Plato-Aristoteles dialektik // Modern Logic: Problems of Theory, History and Application in Science. - St. Petersburg, 2002. - S. 239-242 ..

Situationen är liknande med andra logiska paradoxer. "Logikens antinomier", skriver von Wright, "har förbryllat oss sedan de upptäcktes och kommer förmodligen alltid att förbrylla oss. Vi bör, tycker jag, se dem inte så mycket som problem som väntar på att bli lösta, utan som outtömlig råvara för eftertanke. De är viktiga eftersom att tänka på dem berör de mest grundläggande frågorna i all logik, och därför allt tänkande” Wrigt G.Kh. bakgrund. Logik och filosofi under XX-talet // Vopr. filosofi. 1992. Nr 8..

Alla uppsättningar som inte innehåller sig själva som sitt element. Innehåller den sig själv som ett element? Om så är fallet, så borde det per definition inte vara ett element - en motsägelse. Om inte - så måste det per definition vara ett element - återigen en motsägelse.

Motsägelsen i Russells paradox härrör från användningen i resonemang av det internt motsägelsefulla begreppet uppsättningar av alla uppsättningar och idéer om möjligheten till obegränsad tillämpning av den klassiska logikens lagar när man arbetar med mängder. Flera sätt har föreslagits för att övervinna denna paradox. Den mest kända är presentationen av en konsekvent formalisering för mängdteorin, i förhållande till vilken alla "verkligen nödvändiga" (på sätt och vis) sätt att arbeta med mängder skulle vara acceptabla. Inom ramen för en sådan formalisering, uttalandet om existensen uppsättningar av alla uppsättningar skulle vara irreducerbart.

Anta faktiskt att uppsättningen av alla uppsättningar existerar. Sedan måste det enligt urvalsaxiomet också finnas en mängd vars element är de och bara de mängder som inte innehåller sig själva som ett element. Men antagandet om att det finns en uppsättning leder till Russells paradox. Därför, med tanke på teorins konsistens, kan påståendet om existensen av en mängd inte härledas i denna teori, vilket krävdes för att bevisas.

Under genomförandet av det beskrivna programmet för att "rädda" teorin om mängder, föreslogs flera möjliga axiomatiseringar av den (Zermelo-Fraenkel-teorin ZF, Neumann-Bernays-Gödel NBG-teorin, etc.), men inga bevis har har hittats för någon av dessa teorier hittills överensstämmelse. Dessutom, som Gödel visade genom att utveckla ett antal ofullständighetsteorem, kan ett sådant bevis inte existera (på sätt och vis).

Ännu en reaktion på upptäckten Russells paradox L. E. Ya. Brouwers intuitionism dök upp.

Formuleringsalternativ

Det finns många populära formuleringar av denna paradox. En av dem kallas traditionellt för barberarens paradox och går så här:

En bybarberare beställdes "raka den som inte rakar sig, och raka inte den som rakar sig". Hur ska han hantera sig själv?

Ett annat alternativ:

Ett land utfärdade ett dekret: "Borgmästare i alla städer ska inte bo i sin egen stad, utan i en speciell stad av borgmästare". Var ska borgmästarens borgmästare bo?

Och en till:

Ett visst bibliotek bestämde sig för att sammanställa en bibliografisk katalog som skulle omfatta alla dessa och endast de bibliografiska kataloger som inte innehåller referenser till dem själva. Ska en sådan katalog innehålla en länk till sig själv?

se även

Litteratur

• Courant R, Robbins G. Vad är matematik? - Ch. II, § 4.5
• Miroshnichenko P. N. Vad förstörde Russells paradox i Freges system? // Modern logik: problem med teori, historia och tillämpning inom vetenskap. - SPb., 2000. - S. 512-514.
• Katrechko S.L. Russells paradox om barberaren och Platons dialektik - Aristoteles // Modern logik: problem med teori, historia och tillämpningar inom vetenskapen. - St. Petersburg, 2002. - S. 239-242.
• Martin Gardner Tja gissa vad! = Ah! fick dig. Paradoxer att pussla och glädja. - M .: Mir, 1984. - S. 22-23. - 213 sid.

Anteckningar

Wikimedia Foundation. 2010 .

Se vad "Russell Paradox" är i andra ordböcker:

- (grekiska paradoxos unexpected, strange) i vid bemärkelse: ett uttalande som strider skarpt mot den allmänt accepterade, etablerade åsikten, förnekandet av vad som verkar vara "utan tvekan korrekt"; i en snävare mening två motsatta påståenden, för ... ... Filosofisk uppslagsverk

Russells paradox, en mängdteoretisk antinomi upptäckt 1903 av Bertrand Russell och senare självständigt återupptäckt av E. Zermelo, vilket visar ofullkomligheten i språket i G. Cantors naiva mängdteori, och inte dess inkonsekvens. Antinomy ... ... Wikipedia

paradox- PARADOX (från grekiska para outside och doxa opinion). 1) I en vid (icke-logisk) mening, allt som på ett eller annat sätt strider mot (avviker) från den allmänt accepterade åsikten, bekräftad av tradition, lag, regel, norm eller sunt förnuft. ... ... Encyclopedia of Epistemology and Philosophy of Science

Positionen, som till en början ännu inte är uppenbar, men tvärtemot förväntningarna uttrycker sanningen. I forntida logik var en paradox ett uttalande vars tvetydighet främst syftar på dess riktighet eller felaktighet. AT … … Filosofisk uppslagsverk

- (paradoxen för klassen av alla välgrundade klasser) en paradox i mängdteorin, som är en generalisering av paradoxen Burali Forti. Uppkallad efter den ryske matematikern D. Mirimanov. Innehåll 1 Formulering ... Wikipedia

Visar att antagandet om existensen av en mängd av alla ordningstal leder till motsägelser och därför är teorin om mängder, där konstruktionen av en sådan mängd är möjlig, motsägelsefull. Innehåll 1 Formulering 2 Historia ... Wikipedia

- (från de grekiska paradoxerna oväntat, konstigt) oväntat, ovanligt (åtminstone i form) omdöme (påstående, mening), skarpt i strid med den allmänt accepterade, traditionella åsikten i denna fråga. I denna mening är epitetet "paradoxalt" ... Stora sovjetiska encyklopedien

Cantors paradox är en paradox inom mängdteorin, som visar att antagandet om existensen av en mängd av alla mängder leder till motsägelser och därför är en teori inkonsekvent där konstruktionen av en sådan mängd ... ... Wikipedia

Denna term har andra betydelser, se Paradox (betydelser). Robert Boyle. Bevisschema för att en evighetsmaskin inte existerar Paradox ... Wikipedia

Böcker

• Kollapsen av det metafysiska konceptet om ämnesområdets universalitet i logiken. Frege-Schroeder-kontrovers, B. V. Biryukov. Den här boken diskuterar den dramatiska historien om matematisk logik förknippad med begreppet "resonerande universum" - ämnesområdet i logik. Åsiktskonflikten mellan två...

Russells paradox (Russells antinomi, också Russell-Zermelo paradox) är en mängdteoretisk paradox (antinomi) som upptäcktes 1901 av Bertrand Russell, vilket visar inkonsekvensen i Freges logiska system, vilket var ett tidigt försök att formalisera Georg Cantors naiva mängdteori. Tidigare upptäckt men inte publicerad av Ernst Zermelo.

På ett informellt språk kan paradoxen beskrivas på följande sätt. Låt oss komma överens om att kalla en uppsättning "vanlig" om den inte är dess eget element. Till exempel är uppsättningen av alla människor "vanlig", eftersom uppsättningen i sig inte är en person. Ett exempel på en "ovanlig" mängd är mängden av alla mängder, eftersom den i sig är en mängd, och därför i sig själv är ett korrekt element.

Man kan betrakta en uppsättning som endast består av alla "vanliga" uppsättningar, en sådan uppsättning kallas Russell set . En paradox uppstår när man försöker avgöra om denna mängd är "vanlig" eller inte, det vill säga om den innehåller sig själv som ett element. Det finns två möjligheter.

• Å ena sidan, om den är "vanlig", måste den inkludera sig själv som ett element, eftersom den per definition består av alla "vanliga" mängder. Men då kan det inte vara "vanligt", eftersom "vanliga" set är de som inte inkluderar sig själva.
• Det återstår att anta att denna uppsättning är "ovanlig". Den kan dock inte inkludera sig själv som ett element, eftersom den per definition bara måste bestå av "vanliga" mängder. Men om den inte inkluderar sig själv som ett element, så är det en "vanlig" uppsättning.

I alla fall blir det en motsägelse.

Encyklopedisk YouTube

1 / 5

✪ Föreläsning 1. Definition av en uppsättning. De Morgans lagar. Russells paradox. Weierstrass teorem

✪ 3 Russells paradox

✪ Bertrand Russell Råd till framtida generationer

✪ Föreläsning 21: Naiv mängdteori och luddig logik

✪ Monty Hall Paradox - Numberphile

undertexter

Formulering av paradoxen

Russells paradox kan formuleras i naiv mängdteori. Därför är naiv mängdteori inkonsekvent. Ett motsägelsefullt fragment av naiv mängdteori, som kan definieras som en första ordningens teori med en binär medlemsrelation ∈ (\displaystyle \in ) och urvalsschema: för varje logisk formel med en fri variabel i naiv mängdteori finns ett axiom

∃ y ∀ x (x ∈ y ⟺ P (x)) (\displaystyle \exists y\forall x(x\in y\iff P(x))).

Detta axiomschema säger det för alla tillstånd P (x) (\displaystyle P(x)) det är många y , (\displaystyle y,) bestående av dessa x , (\displaystyle x,) som uppfyller villkoret P (x) (\displaystyle P(x)) .

Detta är tillräckligt för att formulera Russells paradox på följande sätt. Låta P (x) (\displaystyle P(x)) det finns en formel x ∉ x . (\displaystyle x\notin x.)(Det är P (x) (\displaystyle P(x)) betyder att många x (\displaystyle x) innehåller inte sig själv som ett element, eller, i vår terminologi, är en "vanlig" mängd.) Sedan, enligt urvalets axiom, finns det en mängd y (\displaystyle y)(Russell set) sådan att

∀ x (x ∈ y ⟺ x ∉ x) (\displaystyle \forall x(x\in y\iff x\notin x)).

Eftersom detta är sant för alla x , (\displaystyle x,) det gäller också x = y. (\displaystyle x=y.) Det är

y ∈ y ⟺ y ∉ y . (\displaystyle y\in y\iff y\notin y.)

Av detta följer att en motsägelse härleds i naiv mängdlära.

Paradoxen skulle inte uppstå om vi antog att Russell-uppsättningen inte existerar. Detta antagande i sig är dock paradoxalt: i Cantors mängdteori tror man att vilken egenskap som helst bestämmer mängden element som uppfyller denna egenskap. Eftersom egenskapen för en mängd att vara "vanlig" verkar väldefinierad, måste det finnas en uppsättning av alla "vanliga" mängder. Denna teori kallas nu naiv mängdteori .

Populära versioner av paradoxen

Det finns flera versioner av Russells paradox. Till skillnad från själva paradoxen kan de som regel inte uttryckas på ett formellt språk.

Lögnarparadox

Russells paradox är relaterad till lögnarens paradox som är känd sedan urminnes tider, vilket är följande fråga. Givet ett uttalande:

Detta påstående är falskt.

Är detta påstående sant eller inte? Det är lätt att visa att detta påstående varken kan vara sant eller falskt.

Russell skrev om denna paradox:

Russell själv förklarade lögnarparadoxen på detta sätt. För att säga något om yttranden måste man först definiera själva begreppet "yttrande", samtidigt som man inte använder begrepp som ännu inte har definierats. Således kan påståenden av den första typen definieras som inte säger något om påståenden. Sedan kan man definiera påståenden av den andra typen som talar om påståenden av den första typen, och så vidare. Påståendet "det här påståendet är falskt" faller inte under någon av dessa definitioner och är därför inte vettigt.

Frisörens paradox

Russell nämner följande version av paradoxen, formulerad som en gåta som någon föreslog honom.

Låt en barberare bo i en viss by, som rakar alla byns invånare som inte rakar sig, och bara dem. Rakar frisören sig själv?

Varje svar leder till en motsägelse. Russell noterar att denna paradox inte är likvärdig med hans paradox och är lätt att lösa. I själva verket, precis som Russells paradox visar att det inte finns någon Russell-uppsättning, visar barberarens paradox att det inte finns någon sådan frisör. Skillnaden är att det inte finns något förvånande i att en sådan frisör inte finns: inte för någon egendom finns det en frisör som rakar människor med den här egenskapen. Men det faktum att det inte finns någon uppsättning element som ges av någon väldefinierad egenskap motsäger den naiva idén om uppsättningar och kräver förklaring.

Alternativ om kataloger

Den formulering som ligger närmast Russells paradox är följande version av hans presentation:

Bibliografiska kataloger är böcker som beskriver andra böcker. Vissa kataloger kan beskriva andra kataloger. Vissa kataloger kan till och med beskriva sig själva. Är det möjligt att katalogisera alla kataloger som inte beskriver sig själva?

En paradox uppstår när man försöker avgöra om denna katalog ska beskriva sig själv. Trots formuleringarnas uppenbara närhet (detta är faktiskt Russells paradox, där kataloger används istället för set), löses denna paradox, liksom frisörens paradox, enkelt: en sådan katalog kan inte sammanställas.

Grelling-Nelson paradox

Denna paradox formulerades av tyska matematiker Kurt Grelling och Leonard Nelson 1908. Det är i själva verket en översättning av Russells ursprungliga version av paradoxen, uttryckt av honom i termer av predikatlogik (se brev till Frege), till ett icke-matematiskt språk.

Låt oss kalla adjektivet reflekterande om detta adjektiv har egenskapen som definieras av detta adjektiv. Till exempel, adjektiven "ryska", "flerstaviga" - har de egenskaper som de definierar (adjektivet "ryska" är ryska, och adjektivet "flerstaviga" är flerstaviga), så de är reflexiva, och adjektiven "tyska", "enstavigt" - är icke-reflexiv. Kommer adjektivet "icke-reflexiv" att vara reflexivt eller inte?

Varje svar leder till en motsägelse. Till skillnad från frisörens paradox är lösningen på denna paradox inte så enkel. Man kan inte bara säga att ett sådant adjektiv ("icke-reflexiv") inte existerar, eftersom vi just har definierat det. Paradoxen uppstår genom att definitionen av begreppet "icke-reflexiv" är felaktig i sig. Definitionen av denna term beror på värden adjektivet som det gäller. Och eftersom ordet "icke-reflexiv" i sig är ett adjektiv i definitionen uppstår en ond cirkel.

Berättelse

Russell upptäckte förmodligen sin paradox i maj eller juni 1901. Enligt Russell själv försökte han hitta ett fel i Cantors bevis på det paradoxala faktum (känd som Cantors paradox) att det inte finns något maximalt kardinalnummer (eller uppsättning av alla uppsättningar). Som ett resultat fick Russell en enklare paradox. Russell kommunicerade sin paradox till andra logiker, särskilt Whitehead och Peano. I sitt brev till Frege den 16 juni 1902 skrev han att han hade funnit en motsägelse i " Begreppskalkyl” - en bok av Frege, utgiven 1879. Han lade fram sin paradox i termer av logik och sedan i termer av mängdteori, med hjälp av Freges definition av en funktion:

Jag upplevde svårigheter på bara ett ställe. Du hävdar (s. 17) att en funktion själv kan agera som en okänd. Det tyckte jag också. Men nu förefaller denna uppfattning mig tveksam på grund av följande motsägelse. Låta w predikat: "att vara ett predikat som inte kan tillämpas på sig självt." Burk w vara tillämplig på sig själv? Alla svar antyder motsatsen. Därför måste vi dra slutsatsen att wär inte ett predikat. På samma sätt finns det ingen klass (som helhet) av de klasser som, som helhet, inte tillhör dem själva. Av detta drar jag slutsatsen att ibland bildar en viss uppsättning inte en holistisk formation.

Originaltext (tyska)

Nur in einem Punkte ist mir eine Schwierigkeit begegnet. Sie behaupten (S. 17) es könne auch die Funktion das unbestimmte Element bilden. Dies habe ich früher geglaubt, jedoch jetzt scheint mir diese Ansicht zweifelhaft, wegen des folgenden Widerspruchs: Sei w das Prädicat, ein Prädicat zu sein welches von sich selbst nicht prädicirt werden kann. Kann man w von sich selbst prädiciren? Aus jeder Antwort folgt das Gegentheil. Deshalb muss man schließen dass w kein Prädicat ist. Ebenso giebt es keine Klasse (als Ganzes) derjenigen Klassen die als Ganze sich selber nicht angehören. Daraus schliesse ich dass unter gewissen Umständen eine definierbare Menge kein Ganzes bild .

Frege fick brevet precis vid den tidpunkt då han avslutade arbetet med den andra volymen av The Fundamental Laws of Arithmetic (tyska: Grundgesetze der Arithmetik). Frege hann inte korrigera sin mängdlära. Han lade bara till en appendix till den andra volymen med en utläggning och sin analys av paradoxen, som började med den berömda anmärkningen:

Det är osannolikt att något värre kan hända en vetenskapsman än om marken dras ut under hans fötter i samma ögonblick som han slutför sitt arbete. Det var i denna position som jag befann mig när jag fick ett brev från Bertrand Russell, när mitt arbete redan var avslutat.

Originaltext (tyska)

Einem wissenschaftlichen Schriftsteller kann kaum etwas Unerwünschteres begegnen, als daß ihm nach Vollendung einer Arbeit eine der Grundlagen seines Baues erschüttert wird. In diese Lage wurde ich durch einen Brief des Herrn Bertrand Russell versetzt, as der Druck dieses Bandes sich seinem Ende näherte .

z ∈ ( x: P (x) ) ⟺ P (z) (\displaystyle z\in \(x\kolon P(x)\)\iff P(z)),

som sa att det är möjligt att konstruera en uppsättning element som tillfredsställer egenskapen P (x) , (\displaystyle P(x),) han föreslog att man skulle använda följande axiom:

z ∈ ( x: P (x) ) ⟺ P (z) & z ≠ ( x: P (x) ) (\displaystyle z\in \(x\kolon P(x)\)\iff P(z)\ \&\ z\neq \(x\kolon P(x)\)),

eliminerar därmed möjligheten för en uppsättning att vara medlem i sig själv. Men en liten [ som?] modifiering av Russells paradox bevisar att detta axiom också leder till en motsägelse.

Russell publicerade sin paradox i sin bok " Matematikens principer"år 1903.

Nedan är några av de möjliga tillvägagångssätten för att konstruera ett system av axiom fritt från Russells paradoxer.

Russells typteori

Russell själv var den första som föreslog en teori fri från Russells paradox. Han utvecklade en teori om typer, vars första version dök upp i Russell och Whiteheads bok Matematikens principer"år 1903. Denna teori bygger på följande idé: enkla objekt i denna teori har typ 0, uppsättningar av enkla objekt har typ 1, uppsättningar av uppsättningar av enkla objekt har typ 2, och så vidare. Således kan ingen uppsättning ha sig själv som ett element. Varken mängden all mängder eller Russellmängden kan definieras i denna teori. En liknande hierarki införs för uttalanden och egenskaper. Propositioner om enkla objekt tillhör typ 1, propositioner om egenskaperna hos propositioner av typ 1 tillhör typ 2, och så vidare. I allmänhet är en funktion per definition av en högre typ än de variabler som den beror på. Detta tillvägagångssätt låter dig bli av med inte bara Russell-paradoxen, utan också många andra paradoxer, inklusive lögnarparadoxen (), Grelling-Nelson-paradoxen, Burali-Forti-paradoxen. Russell och Whitehead visade hur man reducerar all matematik till typteorins axiom i deras tredelade Principia Mathematica, publicerad 1910-1913.

Detta tillvägagångssätt mötte dock svårigheter. I synnerhet uppstår problem med att definiera sådana begrepp som den bästa övre gränsen för uppsättningar av reella tal. Per definition är en minsta övre gräns den minsta av alla övre gränser. Därför, när man bestämmer den minsta övre gränsen, används uppsättningen av reella tal. Därför är den minsta övre gränsen ett objekt av högre typ än de reella talen. Detta betyder att det inte i sig är ett reellt tal. För att undvika detta var det nödvändigt att införa den sk reducerbarhet axiom. På grund av dess godtycke vägrade många matematiker att acceptera reduceringsaxiomet, och Russell kallade det själv för en defekt i sin teori. Dessutom visade sig teorin vara mycket komplex. Som ett resultat har det inte fått någon bred tillämpning.

Zermelo-Fraenkels mängdlära

Det mest kända tillvägagångssättet för axiomatisering av matematik är Zermelo-Fraenkel (ZF) mängdteorin, som uppstod som en förlängning av Zermelos teorier(1908). Till skillnad från Russell behöll Zermelo de logiska principerna och ändrade endast mängdlärans axiom. Tanken med detta tillvägagångssätt är att det är tillåtet att endast använda uppsättningar byggda från redan byggda uppsättningar med en viss uppsättning axiom. Till exempel säger ett av Zermelos axiom att det är möjligt att konstruera en mängd av alla delmängder av en given mängd (det booleska axiomet). Ett annat axiom ( urvalsschema) säger att från varje uppsättning är det möjligt att välja en delmängd av element som har en given egenskap. Detta är huvudskillnaden mellan Zermelo mängdlära och naiv mängdteori: i naiv mängdlära kan du överväga mängden av alla element som har en given egenskap, och i Zermelo mängdlära kan du bara välja en delmängd från en redan konstruerad mängd . I Zermelos mängdteori är det omöjligt att konstruera en uppsättning av alla mängder. Därmed kan Russell-setet inte heller konstrueras där.

Klasser

Ibland i matematik är det användbart att betrakta alla mängder som en helhet, till exempel för att betrakta helheten av alla grupper. För att göra detta kan mängdteorin utökas med begreppet klass , som till exempel i Neumann- Bernays- Gödel (NBG)-systemet. I denna teori är samlingen av alla uppsättningar klass. Denna klass är dock inte en uppsättning och är inte medlem i någon klass, vilket undviker Russells paradox.

Ett starkare system som gör att man kan ta kvantifierare över klasser, och inte bara över mängder, är t.ex. Morse-mängdlära - Kelly(MK). I denna teori är huvudbegreppet konceptet klass, men inte set. Uppsättningar i denna teori anses vara sådana klasser som i sig är delar av vissa klasser. I denna teori, formeln z ∈ ( x: P (x) ) (\displaystyle z\in \(x\kolon P(x)\)) anses likvärdig med formeln

P (z) & ∃ y . z ∈ y (\displaystyle P(z)\ \&\ \finns y.z\i y).

Därför att ∃ y . z ∈ y (\displaystyle \exists y.z\in y) i denna teori betyder att klassen z (\displaystyle z)är många, ska denna formel förstås som ( x: P (x) ) (\displaystyle \(x\kolon P(x)\))är allas klass set(inte klasser) z (\displaystyle z), Så att P (z) (\displaystyle P(z)). Russells paradox i denna teori löses av det faktum att inte varje klass är en uppsättning.

Man kan gå längre och överväga samlingar av klasser - konglomerat, samlingar av konglomerat och så vidare.

Inverkan på matematik

Axiomatisering av matematik

Russells paradox, tillsammans med andra matematiska antinomier som upptäcktes i början av 1900-talet, stimulerade en revidering av matematikens grunder, vilket resulterade i konstruktionen av axiomatiska teorier för att motivera matematiken, av vilka några nämns ovan.

I alla nya axiomatiska teorier som konstruerades eliminerades de paradoxer som kändes till vid mitten av 1900-talet (inklusive Russells paradox). Men att bevisa att nya liknande paradoxer inte kan upptäckas i framtiden (detta är problemet med konsistensen av de konstruerade axiomatiska teorierna), visade det sig, i den moderna förståelsen av detta problem, vara omöjligt (se Gödels satser om ofullständighet) .

intuitionism

Parallellt uppstod en ny trend inom matematiken, kallad intuitionism, vars grundare är L. E. Ya. Brouwer. Intuitionismen uppstod oberoende av Russells paradox och andra antinomier. Upptäckten av antinomier i mängdteorin ökade dock intuitionisters misstro mot logiska principer och påskyndade bildandet av intuitionism. Intuitionismens huvudtes säger att för att bevisa existensen av något objekt är det nödvändigt att presentera en metod för dess konstruktion. Intuitionister avvisar sådana abstrakta begrepp som mängden av alla uppsättningar. Intuitionismen förnekar lagen om den uteslutna mitten, men det bör noteras att lagen om den uteslutna mitten inte behövs för att härleda en motsägelse från Russells antinomi eller någon annan (i någon antinomi är det bevisat att A (\displaystyle A) innebär negation A (\displaystyle A) och förnekelse A (\displaystyle A) innebär A , (\displaystyle A,) dock från (A ⇒ ¬ A) & (¬ A ⇒ A) (\displaystyle (A\Högerpil \neg A)\&(\neg A\Högerpil A))även i intuitionistisk logik följer en motsägelse). Det är också värt att notera att man i senare axiomatiseringar av intuitionistisk matematik hittade paradoxer liknande Russells, som t.ex. Girards paradox i den ursprungliga lydelsen Martin Löf.

Diagonalt argument (självtillämpning)

Trots det faktum att Russells resonemang leder till en paradox, används huvudidén för detta resonemang ofta i beviset för matematiska teoremer. Som nämnts ovan fick Russell sin paradox genom att analysera Cantors bevis på att det största kardinalnumret inte existerade. Detta faktum motsäger existensen av en uppsättning av alla uppsättningar, eftersom dess kardinalitet måste vara maximal. Men enligt Cantor-satsen har mängden av alla delmängder av en given mängd en större kardinalitet än själva mängden. Beviset för detta faktum är baserat på följande diagonalt argument?!:

Låt det vara en en-till-en korrespondens , som till varje element x (\displaystyle x) set X (\displaystyle X) matchar en delmängd s x (\displaystyle s_(x)) set x. (\displaystyle X.) Låta d (\displaystyle d) kommer att vara en uppsättning element x (\displaystyle x) Så att x ∈ s x (\displaystyle x\in s_(x)) (diagonal uppsättning). Sedan komplementet till denna uppsättning s = d ¯ (\displaystyle s=(\överlinje (d))) kan inte vara en av s x. (\displaystyle s_(x).) Därför var korrespondensen inte en-till-en.

Cantor använde det diagonala argumentet för att bevisa oräknelighet riktiga nummerår 1891. (Detta är inte hans första bevis på att reella tal är oräkneliga, utan det enklaste).

Besläktade paradoxer

Självtillämpbarhet används i många andra paradoxer än de som diskuterats ovan:

• Allmaktsparadoxen är en medeltida fråga: "Kan en allsmäktig gud skapa en sten som han själv inte kan lyfta?"
• Paradoxen Burali-Forti (1897) är en analog till paradoxen Cantor för ordningstal.
• Mirimanovs paradox (1917) är en generalisering av Burali-Forti-paradoxen för klassen av alla välgrundade klasser.
• Richards paradox (1905) är en semantisk paradox som visar vikten av att skilja på matematikens språk och metamatematiken.
• Berry's paradox (1906) är en förenklad version av Richards paradox publicerad av Russell.
• Kleene-Rosser paradox(1935) - formulering av Richards paradox i termer av λ-kalkylen.
• Currys (1941) paradox är en förenkling av Kleene-Rossers paradox.
• Girards paradox(1972) - formulering av Burali-Forti-paradoxen i termer av intuitionistisk typteori .
• är en halvt skämtande paradox som påminner om Berrys paradox.

Anteckningar

1. Godhard Link (2004) Hundra år av Russells paradox, Med. 350, ISBN 9783110174380 , .
2. Russells antinomi // Dictionary of Logic. Ivin A. A., Nikiforov A. L.- M.: Tumanit, VLADOS, 1997. - 384 sid. - ISBN 5-691-00099-3.
3. Andrew David Irvine, Harry Deutsch. Russell "s Paradox // The Stanford Encyclopedia of Philosophy / Edward N. Zalta. - 2014-01-01.
4. Antinomi- artikel från Mathematical Encyclopedia. A. G. Dragalin
5. A.S. Gerasimov. Kursens matematiska logik och teoretiska beräkningsbarhet. - Tredje upplagan, reviderad och förstorad. - St. Petersburg: LEMA, 2011. - S. 124-126. - 284 sid.

Den mest kända av de paradoxer som upptäckts redan i vårt århundrade är antinomin som upptäckts av B. Russell. Idén låg i luften och publiceringen gav intrycket av en exploderande bomb. Denna paradox orsakade i matematiken, enligt D. Hilbert, "effekten av fullständig katastrof." De enklaste och viktigaste logiska metoderna, de vanligaste och mest användbara begreppen, är hotade. Det blev omedelbart uppenbart att varken i logiken eller i matematiken, under hela deras långa historia av deras existens, var något bestämt utarbetat som kunde tjäna som grund för att eliminera antinomin. Uppenbarligen var det nödvändigt att avvika från vanliga sätt att tänka.

Russells paradox i sin ursprungliga form är kopplad till begreppet en uppsättning, eller en klass. Vi kan prata om mängder av olika objekt, till exempel om mängden av alla människor eller om mängden naturliga tal. Ett element i den första uppsättningen kommer att vara vilken enskild person som helst, ett element i den andra - varje naturligt tal. Det är också möjligt att betrakta uppsättningar själva som vissa objekt och tala om uppsättningar av uppsättningar. Man kan till och med introducera sådana begrepp som uppsättningen av alla uppsättningar eller uppsättningen av alla koncept. Med avseende på vilken uppsättning som helst som tas godtyckligt, verkar det rimligt att fråga sig om det är dess eget element eller inte. Uppsättningar som inte innehåller sig själva som ett element kommer att kallas vanliga. Till exempel är mängden av alla människor inte en person, precis som mängden atomer inte är en atom. Uppsättningar som är korrekta element kommer att vara ovanliga. Till exempel är en mängd som förenar alla mängder en mängd och innehåller därför sig själv som ett element. Uppenbarligen är varje set antingen vanligt eller ovanligt.

Betrakta nu uppsättningen av alla vanliga uppsättningar. Eftersom det är ett set kan man också fråga om det är vanligt eller ovanligt. Svaret är dock nedslående. Om den är vanlig måste den per definition innehålla sig själv som ett element, eftersom den innehåller alla vanliga mängder. Men det betyder att det är en ovanlig uppsättning. Antagandet att vår uppsättning är en vanlig mängd leder alltså till en motsägelse. Så det kan inte vara normalt. Å andra sidan kan det inte heller vara ovanligt: ​​en ovanlig mängd innehåller sig själv som ett element, och elementen i vår uppsättning är bara vanliga mängder. Som ett resultat kommer vi till slutsatsen att mängden av alla vanliga uppsättningar inte kan vara vare sig vanliga eller extraordinära.

Således är mängden av alla uppsättningar som inte är korrekta element ett korrekt element om och endast om det inte är ett sådant element. Detta är en klar motsägelse.

Motsägelsen säger att en sådan uppsättning helt enkelt inte existerar. Men varför kan det inte finnas? Det består trots allt av föremål som uppfyller ett väldefinierat villkor, och själva villkoret verkar inte på något sätt vara exceptionellt eller dunkelt. Om en mängd så enkelt och tydligt definierad inte kan existera, vad är då egentligen skillnaden mellan möjliga och omöjliga mängder? Slutsatsen om att den övervägda uppsättningen inte existerar låter oväntat och inspirerar till ångest. Det gör vår allmänna uppfattning om en uppsättning amorf och kaotisk, och det finns ingen garanti för att den inte kan ge upphov till några nya paradoxer.

Russells paradox är anmärkningsvärd för sin extrema generalitet. För dess konstruktion behövs inga komplexa tekniska begrepp, eftersom i fallet med vissa andra paradoxer är begreppen "uppsättning" och "element av uppsättningen" tillräckliga. Men denna enkelhet talar bara om dess grundläggande natur: den berör de djupaste grunderna för vårt resonemang om mängder, eftersom den inte talar om några speciella fall, utan om mängder i allmänhet.

Russells paradox är inte specifikt matematisk. Den använder begreppet en mängd, men berör inte några speciella egenskaper som är associerade specifikt med matematik. Detta blir uppenbart när paradoxen omformuleras i rent logiska termer.

Av varje egenskap kan man med stor sannolikhet fråga sig om den är tillämplig på sig själv eller inte. Egenskapen att vara varm gäller till exempel inte sig själv, eftersom den inte i sig själv är varm; egenskapen att vara konkret hänvisar inte heller till sig själv, för det är en abstrakt egenskap. Men egenskapen att vara abstrakt, att vara abstrakt, är tillämplig på en själv. Låt oss kalla dessa egenskaper otillämpliga på sig själva otillämpliga. Gäller egenskapen att vara otillämplig för sig själv? Det visar sig att en otillämplighet är otillämplig bara om den inte är det. Detta är naturligtvis paradoxalt. Den logiska, egendomsrelaterade varianten av Russells antinomi är lika paradoxal som den matematiska, mängdrelaterade varianten.

B. Russell föreslog också följande populära version av paradoxen han upptäckte. ”Barberaren rakar alla dessa och bara de invånare i staden som inte rakar sig själva. Vem rakar frisören?" Frisörens paradox ligger i det faktum att det påstås vara omöjligt att svara på denna fråga.

För att förstå situationen kommer vi att dela in stadens invånare i tre grupper. Denna uppdelning visas i den vänstra bilden: de som rakar sig är på topp; de som är rakade - underifrån; de som inte rakar sig alls (munkar, barn, kvinnor...) är utanför ellipsen.

Betrakta först verkan av villkor (1). Låt barberaren raka alla som inte rakar sig själva, det vill säga hela den nedre halvan av ellipsen (kläckning markerar frisörens klienter). Men tillstånd (1) tillåter honom att raka sig och den som rakar sig själv, det vill säga sig själv. Tillstånd (1) tillåter honom att placera sig i den övre halvan av ellipsen, där invånarna själva rakar sig, och raka sig där. Detta visas i mitten av bilden.

Om villkor (2) gäller, och frisören rakar bara de som inte rakar sig, betyder det att han rakar en del av den nedre halvan av ellipsen och inte rakar sig själv, det vill säga inte befinner sig i den övre halvan av ellipsen . Men invånarna i den nedre halvan får inte rakas av en barberare, utan av någon annan. Och en frisör kan vara bland dessa människor (höger figur). Så frisören kan raka sin vän, och frisören kommer att raka den skuggade delen av den nedre halvan av ellipsen.

Men om båda villkoren (1) och (2) gäller, så har barberaren ingen plats i ellipsen. Han rakar sig inte alls. Och det finns ingen paradox här. Han är därför antingen en munk, eller en robot, eller ett barn, eller en kvinna, eller en icke-invånare i staden ... Och om det inte finns någon i staden förutom att raka män, och därför ellipsens utseende är tom, så existerar helt enkelt inte en frisör som uppfyller villkoren (1) och (2). Det är absurt att fråga i det här fallet vem som rakar honom. Många sådana frisörer är tomma.

Och här kommer vi att märka att frågan "Vem rakar frisören?", var felaktig från första början, precis som den klassiska frågan: "Varför slår du din pappa?" Innan man frågar vem som rakar barberaren måste man få en överenskommelse om att någon rakar honom.

Argumentet om frisören kan kallas en pseudoparadox. I sin kurs är den strikt analog med Russells paradox, och det är detta som gör den intressant. Men det är fortfarande inte en sann paradox.

Ett annat exempel på samma pseudo-paradox är det välkända katalogargumentet.

Ett visst bibliotek bestämde sig för att sammanställa en bibliografisk katalog som skulle omfatta alla dessa och endast de bibliografiska kataloger som inte innehåller referenser till dem själva. Ska en sådan katalog innehålla en länk till sig själv? Det är lätt att visa att idén med att skapa en sådan katalog inte är genomförbar; den kan helt enkelt inte existera, eftersom den samtidigt måste innehålla en referens till sig själv och inte inkludera. Det är intressant att notera att katalogisering av alla kataloger som inte innehåller referenser till sig själva kan ses som en oändlig, aldrig sinande process.

Låt oss säga att en katalog vid något tillfälle kompilerades, säg K1, inklusive alla andra kataloger som inte innehåller referenser till dem själva. Med skapandet av K1 dök en annan katalog upp som inte innehåller en referens till sig själv. Eftersom målet är att göra en komplett katalog över alla kataloger som inte nämner sig själva, är det uppenbart att K1 inte är lösningen. Han nämner inte en av dessa kataloger - han själv. Inklusive detta omnämnande av honom själv i K1, får vi K2-katalogen. Den nämner K1 men inte K2 själv. Lägger man till ett sådant omnämnande till K2 får vi K3, som återigen är ofullständigt på grund av att det inte nämner sig självt. Och så vidare utan slut.

Ägaren till en frisersalong i en by skrev följande meddelande: "Jag rakar de och bara de invånare i byn som inte rakar sig själva." Frågan är vem som rakar frisören?

Utveckling matematisk logik särskilt intensifierades under 1900-talet i samband med utvecklingen av datateknik och programmering.

Ø Definition Matematisk logikär en modern form av logik som helt bygger på formella matematiska metoder. Den studerar endast slutsatser med strikt definierade objekt och bedömningar för vilka det är möjligt att entydigt avgöra om de är sanna eller falska.

Det grundläggande (odefinierade) begreppet matematisk logik är begreppet " enkelt uttalande". Ett påstående, som är ett enstaka påstående, brukar kallas enkel eller elementär.

Ø Definitionsförklaringär en deklarativ mening som kan sägas vara sann eller falsk.

Påståenden kan vara sanna I eller falska L.

Exempel: Planeten jorden solsystem. (Sann); Varje parallellogram är en kvadrat (falskt)

Det finns påståenden som det är omöjligt att med säkerhet säga om de är sanna eller falska. "Idag är vädret bra" (alla som gillar det)

Exempel påstående "Det regnar"– enkelt, och sant eller falskt beror på vilket väder det nu är utanför fönstret. Om det verkligen regnar, då är påståendet sant, och om det är soligt och det är meningslöst att vänta på regn, då är påståendet "Det regnar" kommer att vara falskt.

Exempel" " är inte ett påstående (det är inte känt vilka värden det tar).

"Sandra student" är inte ett talesätt

Ø DefinitionElementärt yttranden kan inte uttryckas i termer av andra yttranden.

Ø DefinitionSammansatt propositioner är propositioner som kan uttryckas med hjälp av elementära propositioner.

Exempel"Siffran 22 är jämn" är ett elementärt påstående.

Det finns två huvudsakliga tillvägagångssätt för att fastställa sanningen i uttalanden: empirisk (experimentell) och logisk.

På empiriskt förhållningssätt sanningen i påståendet fastställs med hjälp av observationer, mätningar, experiment.

logiskt tillvägagångssätt ligger i det faktum att sanningen i ett påstående fastställs på grundval av sanningen i andra påståenden, det vill säga utan att hänvisa till fakta, till deras innehåll, det vill säga formellt. Detta tillvägagångssätt är baserat på identifiering och användning av logiska samband mellan de påståenden som ingår i argumentet.

2.2 Propositionell logik

Först och främst måste du definiera begreppen, eftersom samma avsnitt ofta kallas på olika sätt: matematisk logik, propositionell (sats) logik, symbolisk logik, tvåvärdig logik, propositionell logik, boolesk algebra ...

Ø Definitionpropositionell logik- en gren av logiken där frågan om påståendens sanning eller falskhet övervägs och avgörs på grundval av att studera metoden att konstruera påståenden från e. elementärt(vidare inte nedbrutna och inte analyserade) uttalanden med hjälp av logiska operationer av konjunktion ("och"), disjunktion ("eller"), negation ("inte"), implikation ("om...då...") , etc. .

Ø Definition Propositionskalkylär ett axiomatiskt logiskt system, vars tolkning är satsernas algebra.

Av störst intresse är konstruktionen av ett formellt system, som bland alla möjliga påståenden särskiljer de som är logiska lagar (korrekt konstruerade resonemang, logiska slutsatser, tautologier, allmänt giltiga påståenden).

Formella teorier, som inte använder naturligt (vardagsspråk) behöver ett eget formspråk där uttrycken som möter i det är skrivna.

Ø Definition Det formella systemet som genererar uttalanden som är tautologier och bara dem kallas propositionskalkyl(IV).

Det formella IoT-systemet definieras av:

Vilka symboler används bäst för att beteckna logiska kopplingar?

Låt oss uppehålla oss vid följande beteckningar: negation, konjunktion, disjunktion, implikation och ekvivalens. Vanligtvis skrivs de logiska värdena för resultaten av att tillämpa connectives i form av tabeller (de så kallade sanningstabellerna).

2.3 Logiska kopplingar................................................... ................ ...

På naturligt språk spelar följande grammatiska medel rollen som bindemedel för att sammanställa komplexa meningar från enkla:

fackföreningar "och", "eller", "inte";

orden "om ..., då", "antingen ... eller",

"om och bara om" osv.

Inom propositionell logik måste de logiska bindemedel som används för att komponera komplexa propositioner definieras exakt.

Låt oss överväga logiska kopplingar (operationer) på uttalanden, där sanningsvärdena för sammansatta uttalanden endast bestäms av sanningsvärdena för de ingående uttalandena och inte av deras betydelse.

Det finns fem ofta använda logiska kopplingar.

negation (representerad av ett tecken),

konjunktion (tecken),

disjunktion (tecken v),

implikation (tecken)

ekvivalens (tecken).

Ø DefinitionNegation påståenden P är ett påstående som är sant om och endast om påståendet P är falskt.

Ø DefinitionSamband två satser P och Q - en sats som är sann om och endast om båda satserna är sanna.

Ø DefinitionÅtskiljande två propositioner P och Q - en proposition som är falsk om och endast om båda propositionerna är falska.

Ø Definitioninblandning två påståenden P och Q - ett påstående som är falskt om och endast om P är sant och Q är falskt. Påståendet P kallas paket implikationer och uttalandet Q - slutsats implikationer.

Ø DefinitionLikvärdighet två propositioner P och Q - en proposition som är sann om och endast om sanningsvärdena för P och Q är desamma.

Användningen av orden "om ..." "då ..." i logikens algebra skiljer sig från deras användning i dagligt tal, där vi som regel tror att om påståendet Xär falskt, då påståendet "Om X, då på' är inte vettigt alls. Dessutom, konstruera en mening med formen "if X, då på» i dagligt tal menar vi alltid att meningen på härrör från förslaget X. Användningen av orden "om, då" i matematisk logik kräver inte detta, eftersom betydelsen av propositioner inte beaktas i den.

2.4Logiska operationer

Grunden för digital teknik är tre logiska operationer som ligger till grund för alla datorutgångar. Dessa är tre logiska operationer: OCH, ELLER, INTE, som kallas "tre pelare av maskinlogik".

Logiska kopplingar eller logiska operationer kända från den diskreta matematikens gång kan appliceras på påståenden. Detta resulterar i formler. Formler blir propositioner genom att ersätta alla betydelser av bokstäverna.

Sanningstabeller för grundläggande logiska operationer.

Flera variabler kopplade samman genom logiska operationer kallas en logisk funktion.

Beskrivningen av alla kalkyler inkluderar en beskrivning av symbolerna för denna kalkyl (alfabet), formler, som är de slutliga konfigurationerna av symboler, och definitionen av härledbara formler.

2.5 Propositionskalkylalfabet

Yttrandekalkylalfabetet består av symboler i tre kategorier:

Den första av dem är tecknet på disjunktion eller logisk addition, den andra är tecknet på konjunktion eller logisk multiplikation, den tredje är tecknet på implikation eller logisk konsekvens, och den fjärde är tecknet på negation.

Propositionskalkylen har inga andra symboler.

2.6 Formler Tautologi

Propositionskalkylformler är sekvenser av symboler från propositionskalkylalfabetet.

Versaler i det latinska alfabetet används för att beteckna formler. Dessa bokstäver är inte kalkylsymboler. De är bara symboler för formler.

Ø Definitionsformel– välformulerat sammansatt uttalande:

1) Varje bokstav är formel.

2) Om , är formler, så är , , , , också formler.

Uppenbarligen är orden inte formler: ) (det tredje av dessa ord innehåller ingen parentes, och det fjärde innehåller inte parentes).

Observera att begreppet logiska kopplingar inte konkretiseras här. Vanligtvis införs vissa förenklingar i formlerna. Till exempel utelämnas parenteser i notationen av formler enligt samma regler som i propositionalgebra.

Ø Definition. Formeln kallas tautologi, om det bara tar sanna värden för alla bokstävervärden.

Ø Definition En formel som är falsk för valfritt värde på bokstäverna kallas motsägelse

Ø Definition Formeln kallas genomförbart, om den på någon uppsättning distribution av sanningsvärden för variabler tar värdet AND.

Ø Definition Formeln kallas motbevisbar, om den för en viss fördelning av variablernas sanningsvärden tar värdet L.

Exempelär formler enligt paragraf 2 i definitionen.

Av samma anledning kommer orden att vara formler:

Samtidigt med konceptet om en formel, konceptet underformler eller en del av en formel.

1. underformel den elementära formeln är sig själv.

2. Om formeln har formen är dess underformler: sig själv, formel A och alla underformler av formel A.

3. Om formeln har formen (A * B) (nedan, under symbolen * kommer vi att förstå någon av de tre symbolerna), då är dess underformler: sig själv, formler A och B och alla underformler till formler A och B.

Exempel För formel dess underformler kommer att vara:

- underformel av noll djup,

Underformler av det första djupet,

Underformler av det andra djupet,

Underformler av tredje djupet,

Underformel av fjärde djupet.

Allteftersom vi "dyker djupt in i formelns struktur", pekar vi ut underformler med ökande djup

Från den diskreta matematikens förlopp är de huvudsakliga logiska ekvivalenserna (ekvivalenserna) kända, vilka är exempel på tautologier. Alla logiska lagar måste vara tautologier.

Ibland kallas lagar uttagsregler, som bestämmer den korrekta slutsatsen från premisserna.

2.7 Lagar för propositionell logik

Logikens algebra har kommutativa och associativa lagar med avseende på operationerna av konjunktion och disjunktion och en distributiv lag för konjunktion med avseende på disjunktion, samma lagar äger rum i algebra av tal.

Därför, över formlerna för logikens algebra, kan du utföra samma transformationer som utförs i algebra av tal (öppningsparenteser, parentes, parentes den gemensamma faktorn).

Betrakta de grundläggande lagarna för propositionell logik.

1. Kommutativitet:

, .

2. Associativitet:

3. Distributivitet:

4. Idempotens: , .

5. Lag om dubbel negation: .

6. Lagen om uteslutning av tredje:.

7. Motsättningens lag: .

8. De Morgans lagar:

9. Lagar om idempotens(egenskaper för operationer med logiska konstanter)

Det finns inga exponenter och koefficienter i logikens algebra. Konjunktionen av identiska "faktorer" motsvarar en av dem

Här , och är alla bokstäver.

Exempel. tautologi formel.