Holič se holí. Paradox Bertranda Russella

Nejznámějším z paradoxů objevených již v minulém století je antinomie objevená Bertrandem Russellem a jím sdělená v dopise G. Fergeovi. Russell objevil svůj paradox související s oblastí logiky a matematiky v roce 1902. Stejnou antinomii projednávali současně v Göttingenu němečtí matematici Z. Zermelo (1871-1953) a D. Hilbert. Nápad byl ve vzduchu a jeho zveřejnění působilo dojmem explodující bomby Mirošničenko P.N. Co zničilo Russellův paradox ve Fregeho systému? // Moderní logika: problémy teorie, historie a aplikace ve vědě. - SPb., 2000. - S. 512-514. . Tento paradox způsobil v matematice podle Hilberta efekt úplné katastrofy. Nejjednodušší a nejdůležitější logické metody, nejběžnější a nejužitečnější koncepty jsou ohroženy. Ukázalo se, že v Cantorově teorii množin, kterou s nadšením přijala většina matematiků, jsou podivné rozpory, kterých se nelze, nebo přinejmenším velmi těžko zbavit. Russellův paradox vynesl tyto rozpory na světlo se zvláštní jasností. Na jeho vyřešení, stejně jako na vyřešení dalších nalezených paradoxů Cantorovy teorie množin, pracovali nejvýznamnější matematici těch let. Okamžitě se ukázalo, že ani v logice, ani v matematice nebylo za celou dlouhou historii jejich existence rozhodně vypracováno nic, co by mohlo sloužit jako základ pro odstranění antinomie. Bylo jasné, že odklon od navyklých způsobů myšlení byl nutný. Ale odkud a jakým směrem? Courant R., Robbins G. Co je matematika? - Ch. II, § 4.5.

Jak radikální mělo být odmítnutí zavedených způsobů teoretizování? S dalším studiem antinomie neustále rostlo přesvědčení o potřebě zásadně nového přístupu. Již půl století po jeho objevení odborníci na základy logiky a matematiky L. Frenkel a I. Bar-Hillel bez výhrad konstatovali: , zatím bez výjimky neúspěšné, jsou pro tento účel zjevně nedostatečné. Moderní americký logik H. Curry o tomto paradoxu napsal o něco později: „Z hlediska logiky známé v 19. století se situace jednoduše vzpírala vysvětlení, i když samozřejmě v naší vzdělané době mohou existovat lidé, kteří vidí (resp. si myslí, že vidí ), v čem je chyba“ Miroshnichenko P.N. Co zničilo Russellův paradox ve Fregeho systému? // Moderní logika: problémy teorie, historie a aplikace ve vědě. - SPb., 2000. - S. 512-514 ..

Russellův paradox ve své původní podobě souvisí s konceptem množiny, neboli třídy. Můžeme mluvit o množinách různých objektů, například o množině všech lidí nebo o množině přirozených čísel. Jakýkoli prvek první sady bude individuální osoba, prvkem druhé je každé přirozené číslo. Za nějaké objekty je možné považovat i samotné množiny a mluvit o množinách. Lze dokonce zavést takové pojmy, jako je množina všech množin nebo množina všech pojmů. S ohledem na jakoukoli libovolně vybranou množinu se zdá rozumné ptát se, zda je jejím vlastním prvkem nebo ne. Množiny, které se neobsahují jako prvek, se budou nazývat běžné. Například množina všech lidí není osoba, stejně jako množina atomů není atom. Sady, které jsou správnými prvky, budou neobvyklé. Například množina, která spojuje všechny množiny, je množinou, a proto obsahuje sebe jako prvek.

Vzhledem k tomu, že se jedná o sadu, lze se na ni také zeptat, zda je obyčejná nebo neobvyklá. Odpověď je však odrazující. Pokud je obyčejný, pak podle definice musí obsahovat sám sebe jako prvek, protože obsahuje všechny běžné množiny. To ale znamená, že jde o neobvyklou sadu. Předpoklad, že naše množina je obyčejná množina, tak vede k rozporu. Takže to nemůže být normální. Na druhou stranu to nemůže být ani neobvyklé: neobvyklá množina obsahuje sebe jako prvek a prvky naší množiny jsou jen obyčejné množiny. V důsledku toho docházíme k závěru, že množina všech obyčejných množin nemůže být ani obyčejná, ani mimořádná.

Množina všech množin, které nejsou vlastními prvky, je tedy vlastním prvkem právě tehdy, když jím není. To je jasný rozpor. A bylo získáno na základě těch nejvěrohodnějších předpokladů a pomocí zdánlivě nezpochybnitelných kroků. Rozpor říká, že taková množina prostě neexistuje. Ale proč by nemohl existovat? Skládá se totiž z předmětů, které splňují přesně definovanou podmínku, a samotná podmínka se nezdá být nějak výjimečná nebo nejasná. Jestliže takto jednoduše a jasně definovaná množina nemůže existovat, jaký je tedy ve skutečnosti rozdíl mezi možnými a nemožnými množinami? Závěr, že uvažovaný soubor neexistuje, zní nečekaně a znepokojivě. Díky tomu je naše obecná představa o množině amorfní a chaotická a neexistuje žádná záruka, že z toho nemohou vzniknout nějaké nové paradoxy.

Russellův paradox je pozoruhodný svou extrémní obecností Courant R., Robbins G. Co je matematika? - Ch. II, § 4.5. . Pro jeho stavbu nejsou potřeba žádné složité technické koncepce, neboť v případě některých jiných paradoxů stačí pojmy „množina“ a „prvek množiny“. Ale tato jednoduchost jen vypovídá o její základní povaze: dotýká se nejhlubších základů našeho uvažování o množinách, protože nemluví o nějakých speciálních případech, ale o množinách obecně.

Jiné varianty paradoxu Russellův paradox není specificky matematický. Používá koncept množiny, ale nedotýká se žádných speciálních vlastností spojených specificky s matematikou.

To se ukáže, když je paradox přeformulován v čistě logických termínech. U každé vlastnosti se lze se vší pravděpodobností ptát, zda je na ni použitelná nebo ne. Vlastnost být horký, například, se nevztahuje na sebe, protože sám není horký; vlastnost být konkrétní se také nevztahuje k sobě samé, protože je to abstraktní vlastnost. Ale vlastnost být abstraktní, být abstraktní, je aplikovatelný na sebe.

Nazvěme tyto vlastnosti nepoužitelné samy o sobě nepoužitelné. Platí vlastnost být neaplikovatelný na sebe? Ukazuje se, že neaplikovatelnost je nepoužitelná pouze tehdy, když tomu tak není. To je samozřejmě paradoxní. Logická verze Russellovy antinomie související s majetkem je stejně paradoxní jako matematická verze související s množinami.

Russell také navrhl následující populární verzi paradoxu, který objevil Katrechko S.L. Russellův Barberův paradox a Plato-Aristotelova dialektika // Moderní logika: Problémy teorie, historie a aplikace ve vědě. - SPb., 2002. - S. 239-242 .. Představme si, že rada jedné obce definovala povinnosti holiče takto: oholit všechny muže z vesnice, kteří se neholí sami, a pouze tyto muže. Měl by se oholit sám? Pokud ano, bude se to týkat těch, kteří se holí sami, a těch, kteří se holí sami, by se holit neměl. Pokud ne, bude patřit k těm, kteří se sami neholí, a proto se bude muset oholit sám. Docházíme tak k závěru, že tento holič se holí právě tehdy, když se neholí sám. To je samozřejmě nemožné.

Argument o holičovi je založen na předpokladu, že takový holič existuje. Výsledný rozpor znamená, že tento předpoklad je mylný a neexistuje žádný takový vesničan, který by se holil všechny a pouze ty vesničany, kteří se neholí sami. Povinnosti holiče se na první pohled nezdají být rozporuplné, takže závěr, že žádný nemůže být, vyznívá poněkud nečekaně. Tento závěr však není paradoxní. Podmínka, kterou musí vesnický holič splnit, je ve skutečnosti rozporuplná, a tudíž nemožná. V obci nemůže být takový kadeřník ze stejného důvodu, že v ní není osoba, která by byla starší než on sám nebo která by se narodila před jeho narozením Miroshnichenko P.N. Co zničilo Russellův paradox ve Fregeho systému? // Moderní logika: problémy teorie, historie a aplikace ve vědě. - SPb., 2000. - S. 512-514 ..

Hádku o holičovi lze nazvat pseudoparadoxem. Svým průběhem je striktně analogický s Russellovým paradoxem, a právě proto je zajímavý. Ale pořád to není skutečný paradox.

Dalším příkladem stejného pseudoparadoxu je známý katalogový argument. Jistá knihovna se rozhodla sestavit bibliografický katalog, který by zahrnoval všechny a pouze ty bibliografické katalogy, které neobsahují odkazy na sebe. Měl by takový adresář obsahovat odkaz na sebe? Je snadné ukázat, že myšlenka vytvoření takového katalogu není proveditelná; prostě nemůže existovat, protože musí současně obsahovat odkaz na sebe a nezahrnovat.

Je zajímavé poznamenat, že katalogizaci všech adresářů, které na sebe neobsahují odkazy, lze považovat za nekonečný, nikdy nekončící proces. Řekněme, že v určitém okamžiku byl zkompilován adresář, řekněme K1, včetně všech ostatních adresářů, které na sebe neobsahují odkazy. S vytvořením K1 se objevil další adresář, který neobsahuje odkaz na sebe. Protože cílem je vytvořit kompletní katalog všech adresářů, které samy o sobě neuvádějí, je zřejmé, že K1 není řešením. Nezmiňuje jeden z těch adresářů -- sebe. Včetně této zmínky o sobě v K1 získáme katalog K2. Zmiňuje K1, ale ne K2 samotnou. Přidáním takové zmínky do K2 dostaneme KZ, která opět není úplná kvůli tomu, že se sama o sobě nezmiňuje. A dál bez konce.

Lze zmínit ještě jeden logický paradox – paradox nizozemských starostů, podobný paradoxu holiče. Každá obec v Holandsku musí mít starostu a dvě různé obce nemohou mít stejného starostu. Někdy se ukáže, že starosta ve své obci nebydlí. Předpokládejme, že by byl přijat zákon, kterým se určité území S přiděluje výhradně těm starostům, kteří v jejich obcích nebydlí, a nařizuje všem těmto starostům usadit se na tomto území. Předpokládejme dále, že těchto starostů je tolik, že území S samo tvoří samostatnou obec. Kde by měl starosta této zvláštní obce S bydlet? Jednoduchá úvaha ukazuje, že pokud starosta zvláštní obce žije na území S, pak by tam neměl bydlet, a naopak, pokud na území nebydlí, musí bydlet na tomto území. Že je tento paradox analogický s holičským paradoxem, je zcela zřejmé.

Russell byl jedním z prvních, kdo navrhl řešení „svého“ paradoxu. Řešení, které navrhl, se nazývalo „teorie typů“: množina (třída) a její prvky patří k různým logickým typům, typ množiny je vyšší než typ jejích prvků, což eliminuje Russellův paradox (teorii typů používal i Russell, aby vyřešil slavný paradox „lháře“). Mnoho matematiků však Russellovo řešení nepřijalo, protože se domnívali, že ukládá příliš přísná omezení na matematické výroky Katrechka S.L. Russellův Barberův paradox a Plato-Aristotelova dialektika // Moderní logika: Problémy teorie, historie a aplikace ve vědě. - Petrohrad, 2002. - S. 239-242 ..

Podobně je tomu i u dalších logických paradoxů. „Antinomie logiky,“ píše von Wright, „nás mátly od svého objevu a pravděpodobně nás budou mát stále. Myslím, že bychom je neměli považovat ani tak za problémy čekající na vyřešení, ale za nevyčerpatelný materiál k zamyšlení. Jsou důležité, protože přemýšlení o nich se dotýká nejzákladnějších otázek veškeré logiky, a tedy veškerého myšlení“ Wrigt G.Kh. Pozadí. Logika a filozofie ve XX století // Vopr. filozofie. 1992. č. 8..

Všechny množiny, které neobsahují samy sebe jako svůj prvek. Obsahuje sám sebe jako prvek? Pokud ano, pak by to podle definice neměl být prvek – rozpor. Pokud ne - pak z definice musí jít o prvek - opět rozpor.

Rozpor v Russellově paradoxu vychází z použití vnitřně rozporuplného konceptu v uvažování sady všech sad a představy o možnosti neomezené aplikace zákonů klasické logiky při práci s množinami. Bylo navrženo několik způsobů, jak tento paradox překonat. Nejznámější je prezentace konzistentní formalizace pro teorii množin, ve vztahu k níž by byly přijatelné všechny „skutečně nutné“ (v jistém smyslu) způsoby práce s množinami. V rámci takové formalizace je tvrzení o existenci sady všech sad by bylo neredukovatelné.

Předpokládejme skutečně, že množina všech množin existuje. Pak podle axiomu výběru musí existovat také množina, jejíž prvky jsou ty a pouze ty množiny, které se jako prvek neobsahují. Předpoklad existence množiny však vede k Russellovu paradoxu. Z hlediska konzistence teorie tedy není tvrzení o existenci množiny v této teorii odvoditelné, což bylo nutné dokázat.

Při realizaci popsaného programu „záchrany“ teorie množin bylo navrženo několik jejích možných axiomatizací (Zermelo-Fraenkelova teorie ZF, Neumann-Bernays-Gödelova teorie NBG atd.), ale nebyl nalezen žádný důkaz pro kteroukoli z těchto teorií doposud konzistentnost. Navíc, jak ukázal Gödel rozpracováním řady teorémů o neúplnosti, takový důkaz nemůže (v jistém smyslu) existovat.

Další reakce na objev Russellův paradox objevil se intuicionismus L. E. Ya. Brouwera.

Možnosti formulace

Existuje mnoho populárních formulací tohoto paradoxu. Jeden z nich se tradičně nazývá holičský paradox a vypadá takto:

Byl objednán jeden vesnický holič "holte každého, kdo se neholí sám, a neholi nikoho, kdo se holí sám". Jak by se měl sám se sebou vypořádat?

Jinou možnost:

Jedna země vydala dekret: "Starostové všech měst by neměli žít ve svém vlastním městě, ale ve zvláštním městě starostů". Kde by měl bydlet starosta města?

A ještě jeden:

Jistá knihovna se rozhodla sestavit bibliografický katalog, který by zahrnoval všechny a pouze ty bibliografické katalogy, které neobsahují odkazy na sebe. Měl by takový adresář obsahovat odkaz na sebe?

viz také

Literatura

• Courant R, Robbins G. co je matematika? - Ch. II, § 4.5
• Mirošničenko P. N. Co zničilo Russellův paradox ve Fregeho systému? // Moderní logika: problémy teorie, historie a aplikace ve vědě. - SPb., 2000. - S. 512-514.
• Katrechko S.L. Russellův paradox holiče a dialektika Platóna - Aristotela // Moderní logika: problémy teorie, historie a aplikací ve vědě. - Petrohrad, 2002. - S. 239-242.
• Martin Gardner No hádejte co! = Ach! Mám tě. Paradoxy k hádankám a potěšení. - M .: Mir, 1984. - S. 22-23. - 213 str.

Poznámky

Nadace Wikimedia. 2010 .

Podívejte se, co je „Russell Paradox“ v jiných slovnících:

- (řecky paradoxos nečekaný, podivný) v širokém smyslu: výrok, který je ostře v rozporu s obecně přijímaným, ustáleným názorem, popření toho, co se zdá být „nepochybně správné“; v užším slova smyslu dva protikladné výroky, pro ... ... Filosofická encyklopedie

Russellův paradox, množinově teoretická antinomie objevená v roce 1903 Bertrandem Russellem a později nezávisle znovuobjevená E. Zermelem, demonstrující nedokonalost jazyka naivní teorie množin G. Cantora, nikoli její nekonzistentnost. Antinomie ... ... Wikipedie

paradox- PARADOX (z řečtiny para venku a názor doxa). 1) V širokém (nelogickém) smyslu vše, co je tak či onak v rozporu (rozchází se) s obecně uznávaným názorem, potvrzeným tradicí, zákonem, pravidlem, normou nebo zdravým rozumem. ... ... Encyklopedie epistemologie a filozofie vědy

Pozice, která zprvu ještě není zřejmá, však oproti očekávání vyjadřuje pravdu. V antické logice byl paradoxem výrok, jehož nejednoznačnost odkazuje především na jeho správnost či nesprávnost. V… … Filosofická encyklopedie

- (paradox třídy všech fundovaných tříd) paradox v teorii množin, který je zobecněním paradoxu Buraliho Fortiho. Pojmenováno po ruském matematikovi D. Mirimanovovi. Obsah 1 Formulace ... Wikipedie

Ukazuje, že předpoklad existence množiny všech ordinálních čísel vede k rozporům, a proto je teorie množin, ve které je konstrukce takové množiny možná, rozporuplná. Obsah 1 Znění 2 Historie ... Wikipedie

- (z řeckých paradoxů nečekaný, podivný) nečekaný, neobvyklý (alespoň formou) úsudek (výrok, věta), ostře v rozporu s obecně přijímaným, tradičním názorem na tuto problematiku. V tomto smyslu přídomek „paradoxní“ ... Velká sovětská encyklopedie

Cantorův paradox je paradoxem teorie množin, který demonstruje, že předpoklad existence množiny všech množin vede k rozporům, a proto je nekonzistentní teorie, ve které konstrukce takové množiny ... ... Wikipedia

Tento termín má jiné významy, viz Paradox (významy). Robert Boyle. Schéma důkazu, že perpetum mobile neexistuje Paradox ... Wikipedie

knihy

• Zhroucení metafyzického konceptu univerzality předmětné oblasti v logice. Frege-Schroeder spor, B. V. Biryukov. Tato kniha pojednává o dramatické historii matematické logiky spojené s konceptem „vesmíru uvažování“ – předmět v logice. Konflikt názorů dvou...

Russellův paradox (Russellova antinomie, Taky Russell-Zermelo paradox) je množinový paradox (antinomie) objevený v roce 1901 Bertrandem Russellem, demonstrující nekonzistenci Fregeova logického systému, který byl raným pokusem formalizovat naivní teorii množin Georga Cantora. Dříve objevil, ale nepublikoval Ernst Zermelo.

V neformálním jazyce lze paradox popsat následovně. Dohodněme se, že budeme množinu nazývat „obyčejnou“, pokud není jejím vlastním prvkem. Například množina všech lidí je „obyčejná“, protože množina sama o sobě není osoba. Příkladem „neobvyklé“ množiny je množina všech množin, protože sama je množinou, a proto je sama o sobě vlastním prvkem.

Lze uvažovat o množině skládající se pouze ze všech „obyčejných“ množin, takové množině se říká Sada Russell . Paradox vzniká při snaze zjistit, zda je tato množina „obyčejná“ či nikoli, tedy zda obsahuje sebe jako prvek. Jsou dvě možnosti.

• Na jedné straně, pokud je „obyčejný“, pak musí sám sebe zahrnovat jako prvek, protože podle definice se skládá ze všech „obyčejných“ množin. Ale pak to nemůže být "obyčejné", protože "obyčejné" množiny jsou ty, které nezahrnují samy sebe.
• Zbývá předpokládat, že tato sada je "neobvyklá". Nemůže však zahrnovat sebe jako prvek, protože podle definice se musí skládat pouze z „obyčejných“ množin. Ale pokud nezahrnuje sebe jako prvek, pak je to "obyčejná" množina.

V každém případě z toho vyplývá rozpor.

Encyklopedický YouTube

1 / 5

✪ Přednáška 1. Definice množiny. De Morganovy zákony. Russellův paradox. Weierstrassova věta

✪ 3 Russellův paradox

✪ Bertrand Russell Rady pro budoucí generace

✪ Přednáška 21: Naivní teorie množin a fuzzy logika

✪ Monty Hall Paradox - Numberphile

titulky

Formulace paradoxu

Russellův paradox lze formulovat v naivní teorii množin. Proto je naivní teorie množin nekonzistentní. Rozporuplný fragment naivní teorie množin, který lze definovat jako teorii prvního řádu s binárním vztahem příslušnosti ∈ (\displaystyle \in ) A výběrové schéma: pro každý logický vzorec s jednou volnou proměnnou v naivní teorii množin existuje axiom

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

Toto axiomové schéma říká, že pro jakoukoli podmínku P (x) (\displaystyle P(x)) je jich mnoho y , (\displaystyle y,) skládající se z těch x , (\displaystyle x,) které splňují podmínku P (x) (\displaystyle P(x)) .

To stačí k tomu, abychom Russellův paradox formulovali následovně. Nechat P (x) (\displaystyle P(x)) existuje vzorec x ∉ x . (\displaystyle x\notin x.)(To je P (x) (\displaystyle P(x)) znamená, že mnoho x (\displaystyle x) neobsahuje sám sebe jako prvek, nebo v naší terminologii je „obyčejnou“ množinou.) Pak axiomem výběru existuje množina y (\displaystyle y)(Russelův set) takový, že

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

Protože to platí pro všechny x , (\displaystyle x,) to platí i pro x = y. (\displaystyle x=y.) To znamená

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

Z toho vyplývá, že v naivní teorii množin je vyvozován rozpor.

Paradox by nenastal, pokud bychom předpokládali, že Russellova množina neexistuje. Tento předpoklad sám o sobě je však paradoxní: v Cantorově teorii množin se má za to, že jakákoli vlastnost určuje množinu prvků, které tuto vlastnost splňují. Protože vlastnost množiny být "obyčejná" se zdá být dobře definovaná, musí existovat množina všech "obyčejných" množin. Tato teorie se nyní nazývá naivní teorie množin .

Populární verze paradoxu

Existuje několik verzí Russellova paradoxu. Na rozdíl od samotného paradoxu je zpravidla nelze vyjádřit formálním jazykem.

Lhářský paradox

Russellův paradox souvisí s paradoxem lháře známým od starověku, což je následující otázka. Vzhledem k prohlášení:

Toto tvrzení je nepravdivé.

Je toto tvrzení pravdivé nebo ne? Je snadné ukázat, že toto tvrzení nemůže být ani pravdivé, ani nepravdivé.

Russell napsal o tomto paradoxu:

Sám Russell takto vysvětlil paradox lháře. Abychom mohli říci něco o výpovědích, je třeba nejprve definovat samotný pojem „výmluva“, přičemž nepoužijeme pojmy, které ještě nebyly definovány. Lze tedy definovat příkazy prvního typu, které o příkazech nic neříkají. Potom lze definovat příkazy druhého typu, které hovoří o příkazech prvního typu, a tak dále. Tvrzení „toto tvrzení je nepravdivé“ nespadá pod žádnou z těchto definic, a proto nedává smysl.

Holičský paradox

Russell zmiňuje následující verzi paradoxu, formulovanou jako hádanku, kterou mu někdo navrhl.

Ať žije v určité vesnici holič, který oholí všechny obyvatele vesnice, kteří se neholí sami, a pouze je. Holí se holič sám?

Jakákoli odpověď vede k rozporu. Russell poznamenává, že tento paradox není ekvivalentní jeho paradoxu a lze jej snadno vyřešit. Vskutku, stejně jako Russellův paradox ukazuje, že žádná Russellova množina neexistuje, holičský paradox ukazuje, že žádný takový holič neexistuje. Rozdíl je v tom, že na neexistenci takového holiče není nic překvapivého: pro žádnou vlastnost neexistuje holič, který s touto vlastností holí lidi. Skutečnost, že neexistuje žádná množina prvků daná nějakou přesně definovanou vlastností, však odporuje naivní představě množin a vyžaduje vysvětlení.

Možnost o adresářích

Russellovu paradoxu se nejvíce blíží následující verze jeho prezentace:

Bibliografické katalogy jsou knihy, které popisují jiné knihy. Některé adresáře mohou popisovat jiné adresáře. Některé adresáře se mohou dokonce popsat samy sebe. Je možné katalogizovat všechny katalogy, které samy sebe nepopisují?

Při rozhodování, zda by se tento adresář měl popisovat sám, vzniká paradox. Přes zdánlivou blízkost formulací (jde vlastně o Russellův paradox, kdy se místo souborů používají katalogy), je tento paradox stejně jako holičský paradox vyřešen jednoduše: takový katalog sestavit nelze.

Grelling-Nelsonův paradox

Tento paradox formulovali němečtí matematici Kurt Grelling a Leonard Nelson v roce 1908. Jde ve skutečnosti o překlad původní Russellovy verze paradoxu, kterou uvedl v termínech predikátové logiky (viz dopis Fregemu), do nematematického jazyka.

Nazvěme přídavné jméno reflexní má-li toto přídavné jméno vlastnost definovanou tímto přídavným jménem. Například přídavná jména „ruský“, „víceslabičný“ - mají vlastnosti, které definují (přídavné jméno „ruský“ je ruské a přídavné jméno „víceslabičný“ je víceslabičné), takže jsou reflexivní a přídavná jména „německý“, "jednoslabičné" - jsou nereflexivní. Bude přídavné jméno „nereflexivní“ reflexivní nebo ne?

Jakákoli odpověď vede k rozporu. Na rozdíl od holičského paradoxu není řešení tohoto paradoxu tak jednoduché. Nelze jednoduše říci, že takové přídavné jméno („nereflexivní“) neexistuje, protože jsme ho právě definovali. Paradox vzniká tím, že definice pojmu „nereflexivní“ je sama o sobě nesprávná. Definice tohoto pojmu závisí na hodnoty přídavné jméno, ke kterému se vztahuje. A protože slovo „nereflexivní“ je v definici samo o sobě přídavné jméno, vzniká začarovaný kruh.

Příběh

Russell pravděpodobně objevil svůj paradox v květnu nebo červnu 1901. Podle samotného Russella se snažil najít chybu v Cantorově důkazu paradoxní skutečnosti (známé jako Cantor's Paradox), že neexistuje žádné maximální kardinální číslo (nebo množina všech množin). Výsledkem bylo, že Russell dostal jednodušší paradox. Russell sdělil svůj paradox dalším logikům, zejména Whiteheadovi a Peanovi. Ve svém dopise Fregemu ze dne 16. června 1902 napsal, že našel rozpor v „ Koncepční počet“ - kniha od Frege, vydaná v roce 1879. Svůj paradox vyložil z hlediska logiky a poté z hlediska teorie množin pomocí Fregeovy definice funkce:

Potíže jsem zažil jen na jednom místě. Tvrdíte (str. 17), že funkce může sama fungovat jako neznámá. Kdysi jsem si to také myslel. Ale nyní se mi tento názor zdá pochybný kvůli následujícímu rozporu. Nechat w predikát: "být predikátem, který nelze použít na sebe." Umět w být použitelný sám na sebe? Jakákoli odpověď znamená opak. Proto musíme dojít k závěru, že w není predikát. Podobně neexistuje žádná třída (jako celek) těch tříd, které jako celek nepatří k sobě. Z toho usuzuji, že někdy určitá množina netvoří celistvou formaci.

Původní text (německy)

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 bildet .

Frege obdržel dopis právě v době, kdy dokončil práci na druhém díle Základních zákonů aritmetiky (německy: Grundgesetze der Arithmetik). Frege neměl čas opravit svou teorii množin. Ke druhému dílu přidal pouze dodatek s výkladem a svým rozborem paradoxu, který začal slavnou poznámkou:

Je nepravděpodobné, že by se vědci mohlo stát něco horšího, než když se mu zem vytrhne zpod nohou právě ve chvíli, kdy dokončí své dílo. V této pozici jsem se ocitl, když jsem dostal dopis od Bertranda Russella, když už byla moje práce hotová.

Původní text (německy)

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, als der Druck dieses Bandes sich seinem Ende näherte .

z ∈ ( x: P (x) ) ⟺ P (z) (\displaystyle z\in \(x\dvojtečka P(x)\)\iff P(z)),

který říkal, že je možné sestrojit množinu prvků splňujících vlastnost P (x), (\displaystyle P(x),) navrhl použít následující axiom:

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

čímž se eliminuje možnost, aby množina byla sama sobě členem. Nicméně malý [ který?] modifikace Russellova paradoxu dokazuje, že i tento axiom vede k rozporu.

Russell publikoval svůj paradox ve své knize " Základy matematiky“ v roce 1903.

Níže jsou uvedeny některé z možných přístupů ke konstrukci systému axiomů bez Russellových paradoxů.

Russellova teorie typu

Sám Russell byl první, kdo navrhl teorii bez Russellova paradoxu. Vyvinul teorii typů, jejíž první verze se objevila v knize Russella a Whiteheada Základy matematiky“ v roce 1903. Tato teorie je založena na následující myšlence: jednoduché objekty v této teorii mají typ 0, množiny jednoduchých objektů mají typ 1, množiny množin jednoduchých objektů mají typ 2 a tak dále. Žádná množina tedy nemůže mít sama sebe jako prvek. Ani množina všech množin ani Russellova množina nemohou být v této teorii definovány. Podobná hierarchie je zavedena pro příkazy a vlastnosti. Tvrzení o jednoduchých předmětech patří k typu 1, výroky o vlastnostech výroků typu 1 patří k typu 2 atd. Obecně je funkce podle definice vyššího typu než proměnné, na kterých závisí. Tento přístup vám umožňuje zbavit se nejen Russellova paradoxu, ale i mnoha dalších paradoxů, včetně paradoxu lháře (), Grelling-Nelsonova paradoxu, Buraliho-Fortiho paradoxu. Russell a Whitehead ukázali, jak zredukovat veškerou matematiku na axiomy teorie typů ve své třísvazkové Principia Mathematica, publikované v letech 1910-1913.

Tento přístup se však setkal s obtížemi. Problémy vyvstávají zejména při definování takových pojmů jako nejlepší horní mez pro množiny reálných čísel. Podle definice je nejmenší horní mez nejmenší ze všech horních mezí. Proto se při určování nejmenší horní meze používá množina reálných čísel. Nejmenší horní mez je tedy objektem více než vysoký typ než reálná čísla. To znamená, že to samo o sobě není skutečné číslo. Aby se tomu zabránilo, bylo nutné zavést tzv axiom redukovatelnosti. Kvůli jeho svévoli mnoho matematiků odmítlo přijmout axiom redukovatelnosti a sám Russell to označil za vadu ve své teorii. Teorie se navíc ukázala jako velmi složitá. V důsledku toho nezískal široké uplatnění.

Zermelo-Fraenkelova teorie množin

Nejznámějším přístupem k axiomatizaci matematiky je Zermelo-Fraenkelova (ZF) teorie množin, která vznikla jako rozšíření Zermelovy teorie(1908). Na rozdíl od Russella si Zermelo zachoval logické principy a změnil pouze axiomy teorie množin. Myšlenkou tohoto přístupu je, že je povoleno používat pouze množiny sestavené z již sestavených množin pomocí určité množiny axiomů. Například jeden ze Zermelových axiomů říká, že je možné sestrojit množinu všech podmnožin dané množiny (booleovský axiom). Další axiom ( výběrové schéma) říká, že z každé množiny je možné vybrat podmnožinu prvků, které mají danou vlastnost. Toto je hlavní rozdíl mezi Zermelovou teorií množin a naivní teorií množin: v naivní teorii množin můžete uvažovat množinu všech prvků, které mají danou vlastnost, a v Zermelově teorii množin můžete vybrat pouze podmnožinu z již zkonstruované množiny. . V Zermelově teorii množin je nemožné sestrojit množinu všech množin. Ani tam tedy Russellův set nelze zkonstruovat.

Třídy

Někdy je v matematice užitečné uvažovat všechny množiny jako celek, například uvažovat jako celek všech skupin. Za tímto účelem lze teorii množin rozšířit o pojem třídy, jako například v systému Neumann- Bernays- Gödel (NBG). V této teorii je sbírka všech množin třída. Tato třída však není množinou a není členem žádné třídy, čímž se vyhneme Russellovu paradoxu.

Silnějším systémem, který umožňuje přebírat kvantifikátory nad třídami, a ne pouze nad množinami, je např. Morseova teorie množin - Kelly(MK) . V této teorii je hlavním konceptem koncept třída, ale ne sady. Množiny v této teorii jsou považovány za takové třídy, které jsou samy o sobě prvky některých tříd. V této teorii vzorec z ∈ ( x: P (x) ) (\displaystyle z\in \(x\dvojtečka P(x)\)) se považuje za ekvivalentní vzorci

P (z) & ∃ y. z ∈ y (\displaystyle P(z)\ \&\ \existuje y.z\in y).

Protože ∃ y . z ∈ y (\displaystyle \existuje y.z\in y) v této teorii znamená, že třída z (\displaystyle z) je mnoho, tento vzorec je třeba chápat jako ( x: P (x) ) (\displaystyle \(x\dvojtečka P(x)\)) je třída všech sady(ne třídy) z (\displaystyle z), takové, že P (z) (\displaystyle P(z)). Russellův paradox v této teorii je vyřešen tím, že ne každá třída je množina.

Můžeme jít dále a zvážit sbírky tříd - konglomeráty, sbírky konglomerátů a tak dále.

Vliv na matematiku

Axiomatizace matematiky

Russellův paradox spolu s dalšími matematickými antinomiemi objevenými na počátku 20. století podnítil revizi základů matematiky, která vyústila v konstrukci axiomatických teorií pro ospravedlnění matematiky, z nichž některé jsou zmíněny výše.

Ve všech nově konstruovaných axiomatických teoriích byly paradoxy známé do poloviny 20. století (včetně Russellova paradoxu) eliminovány. Dokázat však, že nové podobné paradoxy nelze v budoucnu objevit (to je problém konzistence konstruovaných axiomatických teorií), se v moderním chápání tohoto problému ukázalo nemožné (viz Gödelovy věty o neúplnosti) .

intuicionismus

Paralelně s tím vznikl nový trend v matematice zvaný intuicionismus, jehož zakladatelem je L. E. Ya. Brouwer. Intuicionismus vznikl nezávisle na Russellově paradoxu a dalších antinomích. Objev antinomií v teorii množin však zvýšil nedůvěru intuicionistů k logickým principům a urychlil vznik intuicionismu. Hlavní teze intuicionismu říká, že k prokázání existence nějakého objektu je nutné předložit metodu pro jeho konstrukci. Intuicionisté odmítají takové abstraktní pojmy, jako je množina všech množin. Intuicionismus popírá zákon vyloučeného středu, nicméně je třeba poznamenat, že zákon vyloučeného středu není potřeba k vyvození rozporu z Russellovy antinomie ani žádné jiné (v každé antinomii je dokázáno, že A (\displaystyle A) znamená negaci A (\displaystyle A) a popření A (\displaystyle A) znamená A , (\displaystyle A,) nicméně od (A ⇒ ¬ A) & (¬ A ⇒ A) (\displaystyle (A\Šipka doprava \neg A)\&(\neg A\Šipka doprava A)) i v intuicionistické logice následuje rozpor). Za zmínku také stojí, že v pozdějších axiomatizacích intuicionistické matematiky byly nalezeny paradoxy podobné Russellovým, jako např. Girardův paradox v původním znění Martin Loef.

Diagonální argument (vlastní použitelnost)

Navzdory skutečnosti, že Russellovo uvažování vede k paradoxu, hlavní myšlenka tohoto uvažování se často používá při důkazu matematických teorémů. Jak již bylo zmíněno výše, Russell získal svůj paradox analýzou Cantorova důkazu o neexistenci největšího kardinálního čísla. Tato skutečnost odporuje existenci množiny všech množin, neboť její mohutnost musí být maximální. Množina všech podmnožin dané množiny má však podle Cantorovy věty větší mohutnost než množina samotná. Důkaz této skutečnosti je založen na následujícím diagonální argument?!:

Nechť existuje korespondence jedna ku jedné , která ke každému prvku x (\displaystyle x) sady X (\displaystyle X) odpovídá podmnožině s x (\displaystyle s_(x)) sady X. (\displaystyle X.) Nechat d (\displaystyle d) bude soubor prvků x (\displaystyle x) takové, že x ∈ s x (\displaystyle x\in s_(x)) (diagonální sada). Pak doplněk této sady s = d ¯ (\displaystyle s=(\overline (d))) nemůže být jedním z s x . (\displaystyle s_(x).) Korespondence tedy nebyla osobní.

Cantor použil diagonální argument, aby dokázal nespočitatelnost reálná čísla v roce 1891. (Není to jeho první důkaz nespočitatelnosti reálných čísel, ale ten nejjednodušší).

Související paradoxy

Samoaplikovatelnost se používá v mnoha jiných paradoxech, než jsou uvedeny výše:

• Paradox všemohoucnosti je středověká otázka: "Může všemohoucí bůh vytvořit kámen, který sám nemůže zvednout?"
• Paradox Burali-Forti (1897) je analogií paradoxu Cantor pro ordinální čísla.
• Mirimanovův paradox (1917) je zobecněním Buraliho-Fortiho paradoxu pro třídu všech fundovaných tříd.
• Richardův paradox (1905) je sémantický paradox ukazující důležitost oddělení jazyka matematiky a metamatematiky.
• Berryho paradox (1906) je zjednodušená verze Richardova paradoxu publikovaná Russellem.
• Kleene-Rosserův paradox(1935) - formulace Richardova paradoxu z hlediska λ-kalkulu.
• Curryho (1941) paradox je zjednodušením Kleene-Rosserova paradoxu.
• Girardův paradox(1972) - formulace Burali-Fortiho paradoxu z hlediska intuicionistická teorie typu .
• je napůl vtipný paradox připomínající Berryho paradox.

Poznámky

1. Godhard Link (2004) Sto let Russellova paradoxu, S. 350, ISBN 9783110174380 , .
2. Russellova antinomie // Slovník logiky. Ivin A. A., Nikiforov A. L.- M.: Tumanit, VLADOS, 1997. - 384 s. - 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. Antinomie- článek z matematické encyklopedie. A. G. Dragalin
5. A. S. Gerasimov. Vypočitatelnost kurzu matematické logiky a teorie. - Třetí vydání, upravené a rozšířené. - Petrohrad: LEMA, 2011. - S. 124-126. - 284 str.

Nejznámějším z paradoxů objevených již v našem století je antinomie objevená B. Russellem. Nápad byl ve vzduchu a jeho zveřejnění vyvolalo dojem explodující bomby. Tento paradox způsobil v matematice podle D. Hilberta „efekt úplné katastrofy“. Nejjednodušší a nejdůležitější logické metody, nejběžnější a nejužitečnější koncepty jsou ohroženy. Okamžitě se ukázalo, že ani v logice, ani v matematice nebylo za celou dlouhou historii jejich existence rozhodně vypracováno nic, co by mohlo sloužit jako základ pro odstranění antinomie. Bylo jasné, že odklon od navyklých způsobů myšlení byl nutný.

Russellův paradox ve své původní podobě souvisí s konceptem množiny, neboli třídy. Můžeme mluvit o množinách různých objektů, například o množině všech lidí nebo o množině přirozených čísel. Prvek první množiny bude každá jednotlivá osoba, prvek druhé - každé přirozené číslo. Za nějaké objekty je možné považovat i samotné množiny a mluvit o množinách. Lze dokonce zavést takové pojmy, jako je množina všech množin nebo množina všech pojmů. S ohledem na jakoukoli libovolně vybranou množinu se zdá rozumné ptát se, zda je jejím vlastním prvkem nebo ne. Množiny, které se neobsahují jako prvek, se budou nazývat běžné. Například množina všech lidí není osoba, stejně jako množina atomů není atom. Sady, které jsou správnými prvky, budou neobvyklé. Například množina, která spojuje všechny množiny, je množinou, a proto obsahuje sebe jako prvek. Je zřejmé, že každá sada je buď obyčejná, nebo neobvyklá.

Uvažujme nyní množinu všech běžných množin. Vzhledem k tomu, že se jedná o sadu, lze se na ni také zeptat, zda je obyčejná nebo neobvyklá. Odpověď je však odrazující. Pokud je obyčejný, pak podle definice musí obsahovat sám sebe jako prvek, protože obsahuje všechny běžné množiny. To ale znamená, že jde o neobvyklou sadu. Předpoklad, že naše množina je obyčejná množina, tak vede k rozporu. Takže to nemůže být normální. Na druhou stranu to nemůže být ani neobvyklé: neobvyklá množina obsahuje sebe jako prvek a prvky naší množiny jsou jen obyčejné množiny. V důsledku toho docházíme k závěru, že množina všech obyčejných množin nemůže být ani obyčejná, ani mimořádná.

Množina všech množin, které nejsou vlastními prvky, je tedy vlastním prvkem právě tehdy, když jím není. To je jasný rozpor.

Rozpor říká, že taková množina prostě neexistuje. Ale proč by nemohl existovat? Skládá se totiž z předmětů, které splňují přesně definovanou podmínku, a samotná podmínka se nezdá být nějak výjimečná nebo nejasná. Jestliže takto jednoduše a jasně definovaná množina nemůže existovat, jaký je tedy ve skutečnosti rozdíl mezi možnými a nemožnými množinami? Závěr, že uvažovaný soubor neexistuje, zní nečekaně a znepokojivě. Díky tomu je naše obecná představa o množině amorfní a chaotická a neexistuje žádná záruka, že z toho nemohou vzniknout nějaké nové paradoxy.

Russellův paradox je pozoruhodný svou extrémní obecností. Pro jeho stavbu nejsou potřeba žádné složité technické koncepce, neboť v případě některých jiných paradoxů stačí pojmy „množina“ a „prvek množiny“. Ale tato jednoduchost jen vypovídá o její základní povaze: dotýká se nejhlubších základů našeho uvažování o množinách, protože nemluví o nějakých speciálních případech, ale o množinách obecně.

Russellův paradox není specificky matematický. Používá koncept množiny, ale nedotýká se žádných speciálních vlastností spojených specificky s matematikou. To se ukáže, když je paradox přeformulován v čistě logických termínech.

U každé vlastnosti se lze se vší pravděpodobností ptát, zda je na ni použitelná nebo ne. Vlastnost být horký, například, se nevztahuje na sebe, protože sám není horký; vlastnost být konkrétní se také nevztahuje k sobě samé, protože je to abstraktní vlastnost. Ale vlastnost být abstraktní, být abstraktní, je aplikovatelný na sebe. Nazvěme tyto vlastnosti nepoužitelné samy o sobě nepoužitelné. Platí vlastnost být neaplikovatelný na sebe? Ukazuje se, že neaplikovatelnost je nepoužitelná pouze tehdy, když tomu tak není. To je samozřejmě paradoxní: Logická verze Russellovy antinomie související s vlastnostmi je stejně paradoxní jako verze matematická, související s množinami.

B. Russell také navrhl následující populární verzi paradoxu, který objevil. „Holič holí všechny a jen ty obyvatele města, kteří se neholí sami. Kdo holí holiče?" Paradox holiče spočívá v tom, že na tuto otázku údajně nelze odpovědět.

Pro pochopení situace rozdělíme obyvatele města do tří skupin. Toto rozdělení je znázorněno na obrázku vlevo: ti, kteří se holí, jsou nahoře; ti, kteří jsou oholení - zdola; ti, co se neholí vůbec (mniši, děti, ženy...) jsou mimo elipsu.

Nejprve zvažte akci podmínky (1). Nechte holič oholit všechny, kteří se neholí sami, tedy celou spodní polovinu elipsy (šrafování značí klienty holiče). Ale podmínka (1) umožňuje oholit se jemu i tomu, kdo se holí, tedy sobě. Podmínka (1) mu umožňuje umístit se do horní poloviny elipsy, kde se obyvatelé sami holí, a oholit se tam. To je znázorněno na prostředním obrázku.

Pokud platí podmínka (2) a holič holí pouze ty, kteří se neholí sami, znamená to, že oholí část spodní poloviny elipsy a neholí se sám, to znamená, že není v horní polovině elipsy. elipsa. Obyvatele dolní poloviny ale možná neoholí holič, ale někdo jiný. A mezi těmito lidmi může být i holič (správná postava). Holič tedy může oholit svého přítele a holič oholí zastíněnou část spodní poloviny elipsy.

Pokud ale platí obě podmínky (1) a (2), pak holič nemá v elipse místo. Vůbec se neholí. A není zde žádný paradox. Je to tedy buď mnich, nebo robot, nebo dítě, nebo žena, nebo nerezident města... A není-li ve městě nikdo kromě holících mužů, a proto vzhled elipsy je prázdný, pak holič, který splňuje podmínky (1) a (2), prostě neexistuje. Ptát se v tomto případě, kdo ho holí, je absurdní. Mnoho takových holičů je prázdných.

A zde si všimneme, že položená otázka: "Kdo holí holič?", byla od samého začátku nesprávná, stejně jako klasická otázka: "Proč biješ svého otce?" Než se zeptáte, kdo holí holiče, musíte získat souhlas, že ho někdo oholí.

Hádku o kadeřnici lze nazvat pseudoparadoxem. Svým průběhem je striktně analogický s Russellovým paradoxem, a právě proto je zajímavý. Ale pořád to není skutečný paradox.

Dalším příkladem stejného pseudoparadoxu je známý katalogový argument.

Jistá knihovna se rozhodla sestavit bibliografický katalog, který by zahrnoval všechny a pouze ty bibliografické katalogy, které neobsahují odkazy na sebe. Měl by takový adresář obsahovat odkaz na sebe? Je snadné ukázat, že myšlenka vytvoření takového katalogu není proveditelná; prostě nemůže existovat, protože musí současně obsahovat odkaz na sebe a nezahrnovat. Je zajímavé poznamenat, že katalogizaci všech adresářů, které na sebe neobsahují odkazy, lze považovat za nekonečný, nikdy nekončící proces.

Řekněme, že v určitém okamžiku byl zkompilován adresář, řekněme K1, který zahrnoval všechny ostatní adresáře, které neobsahovaly odkazy na sebe. S vytvořením K1 se objevil další adresář, který neobsahuje odkaz na sebe. Protože cílem je vytvořit kompletní katalog všech adresářů, které samy o sobě neuvádějí, je zřejmé, že K1 není řešením. O jednom z těch adresářů se nezmiňuje – o sobě. Včetně této zmínky o sobě v K1 získáme katalog K2. Zmiňuje K1, ale ne K2 samotnou. Přidáním takové zmínky ke K2 dostaneme K3, která je opět neúplná kvůli tomu, že se sama o sobě nezmiňuje. A tak dále bez konce.

Majitel holičství v jedné vesnici vyvěsil následující oznámení: "Holím ty a jen ty obyvatele vesnice, kteří se neholí sami." Otázkou je, kdo holí holiče?

Rozvoj matematická logika zvláště intenzivnější ve 20. století v souvislosti s rozvojem výpočetní techniky a programování.

Ø Definice Matematická logika je moderní forma logiky, která zcela spoléhá na formální matematické metody. Studuje pouze úsudky s přesně definovanými objekty a soudy, u nichž je možné jednoznačně rozhodnout, zda jsou pravdivé nebo nepravdivé.

Základním (nedefinovaným) pojmem matematické logiky je pojem „ jednoduché prohlášení". Příkaz, který je jediným příkazem, se obvykle nazývá jednoduchý nebo elementární.

Ø Definiční prohlášení je oznamovací věta, o které lze říci, že je pravdivá nebo nepravdivá.

Výroky mohou být pravdivé I nebo nepravdivé L.

Příklad: Planeta Země Sluneční Soustava. (Skutečný); Každý rovnoběžník je čtverec (nepravda)

Existují výroky, o kterých nelze s jistotou říci, zda jsou pravdivé nebo nepravdivé. "Dnes je dobré počasí" (kdo má rád)

Příklad prohlášení "Prší"- jednoduché a pravdivé nebo nepravdivé závisí na tom, jaké je nyní počasí za oknem. Pokud opravdu prší, pak je tvrzení pravdivé, a pokud je slunečno a je zbytečné čekat na déšť, pak je tvrzení "Prší" bude falešný.

Příklad„ “ není prohlášení (není známo, jaké hodnoty nabývá).

„Sphomore student“ není rčení

Ø DefiniceZákladní výroky nelze vyjádřit jinými výroky.

Ø DefiniceKompozitní výroky jsou výroky, které lze vyjádřit pomocí elementárních výroků.

Příklad„Číslo 22 je sudé“ je základní tvrzení.

Existují dva hlavní přístupy ke stanovení pravdivosti tvrzení: empirický (experimentální) a logický.

Na empirický přístup pravdivost tvrzení se zjišťuje pomocí pozorování, měření, experimentů.

logický přístup spočívá v tom, že pravdivost tvrzení se zjišťuje na základě pravdivosti jiných tvrzení, tedy bez odkazu na fakta, na jejich obsah, tedy formálně. Tento přístup je založen na identifikaci a použití logických souvislostí mezi tvrzeními obsaženými v argumentu.

2.2 Výroková logika

Nejprve je třeba definovat pojmy, protože stejná sekce se často nazývá odlišně: matematická logika, výroková (větná) logika, symbolická logika, dvouhodnotová logika, výroková logika, Booleova algebra ...

Ø Definicevýroková logika- úsek logiky, ve kterém se zvažuje a rozhoduje otázka pravdivosti či nepravdivosti výroků na základě studia metody konstrukce výroků z e. základní(dále nerozložené a neanalyzované) výroky pomocí logických operací spojky ("a"), disjunkce ("nebo"), negace ("ne"), implikace ("pokud...pak...") atd.

Ø Definice výrokového počtu je axiomatický logický systém, jehož interpretací je algebra výroků.

Největší zajímavostí je konstrukce formálního systému, který mezi všemi možnými výroky rozlišuje ty, které jsou logickými zákony (správně postavené úvahy, logické závěry, tautologie, obecně platné výroky).

Formální teorie, které nepoužívají přirozený (hovorový) jazyk, potřebují svůj vlastní formální jazyk, ve kterém jsou psány výrazy, se kterými se v nich setkáváme.

Ø Definice Je volán formální systém, který generuje příkazy, které jsou tautologiemi a pouze ony výrokový kalkul(IV).

Formální systém IoT je definován:

Jaké symboly se nejlépe používají k označení logických spojek?

Zastavme se u následujících označení: negace, konjunkce, disjunkce, implikace a ekvivalence. Obvykle se logické hodnoty výsledků aplikace spojovacích prvků zapisují ve formě tabulek (tzv. pravdivostní tabulky).

2.3 Logické spojky ................................................ ...................

V přirozeném jazyce hrají roli spojovacího výrazu při sestavování složitých vět z jednoduchých tyto gramatické prostředky:

odbory "a", "nebo", "ne";

slova "jestliže ..., pak", "buď ... nebo",

„když a jen když“ atd.

Ve výrokové logice musí být logické spojky používané ke skládání složitých výroků přesně definovány.

Uvažujme logické spojky (operace) na příkazech, ve kterých jsou pravdivostní hodnoty složených příkazů určeny pouze pravdivostními hodnotami jednotlivých příkazů, a nikoli jejich významem.

Existuje pět široce používaných logických spojovacích prostředků.

negace (reprezentovaná znakem),

spojka (znak),

disjunkce (znak v),

implikace (znamení)

ekvivalence (znak).

Ø DefiniceNegace výrok P je výrok, který je pravdivý právě tehdy, když výrok P je nepravdivý.

Ø DefiniceSpojení dva výroky P a Q - výrok, který je pravdivý právě tehdy, když jsou pravdivé oba výroky.

Ø DefiniceDisjunkce dva výroky P a Q - výrok, který je nepravdivý právě tehdy, když jsou oba výroky nepravdivé.

Ø Definiceimplikace dva výroky P a Q - výrok, který je nepravdivý právě tehdy, když P je pravdivé a Q je nepravdivé. Příkaz P se nazývá balíček implikace a prohlášení Q - závěr Dopady.

Ø DefiniceRovnocennost dva výroky P a Q - výrok, který je pravdivý právě tehdy, když pravdivostní hodnoty P a Q jsou stejné.

Použití slov "jestliže ..." "potom ..." v algebře logiky se liší od jejich použití v běžné řeči, kde se zpravidla domníváme, že pokud výrok X je nepravdivé, pak tvrzení „Pokud X, Že na' nedává vůbec smysl. Kromě toho sestavení věty ve tvaru „pokud X, Že na» v běžné řeči máme na mysli vždy větu na vyplývá z návrhu X. Použití slov „jestliže, pak“ v matematické logice to nevyžaduje, protože se v ní nebere v úvahu význam výroků.

2.4Logické operace

Základem digitální techniky jsou tři logické operace, které jsou základem všech počítačových výstupů. Jedná se o tři logické operace: AND, OR, NOT, které se nazývají „tři pilíře strojové logiky“.

Na výroky lze aplikovat logické spojky nebo logické operace známé z kurzu diskrétní matematiky. To má za následek vzorce. Vzorce se stávají návrhy nahrazením všech významů písmen.

Pravdivostní tabulky základních logických operací.

Několik proměnných spojených dohromady logickými operacemi se nazývá logická funkce.

Popis jakéhokoli kalkulu zahrnuje popis symbolů tohoto kalkulu (abecedy), vzorce, které jsou konečnými konfiguracemi symbolů, a definici odvoditelných vzorců.

2.5 Abeceda výrokového počtu

Abeceda kalkulu výpovědi se skládá ze symbolů tří kategorií:

První z nich je znakem disjunkce nebo logického sčítání, druhý je znakem konjunkce nebo logického násobení, třetí je znakem implikace nebo logického důsledku a čtvrtý je znakem negace.

Výrokový kalkul nemá žádné další symboly.

2.6 Vzorce.Tautologie

Výrokové kalkulové formule jsou posloupnosti symbolů z výrokové kalkulové abecedy.

K označení se používají vzorce velká písmena Latinka. Tato písmena nejsou symboly počtu. Jsou to pouze symboly vzorců.

Ø Definiční vzorec – dobře utvořený složený výrok:

1) Každé písmeno je vzorec.

2) Jestliže , jsou formule, pak , , , , jsou také formule.

Je zřejmé, že slova nejsou vzorce: ) (třetí z těchto slov neobsahuje uzavřenou závorku a čtvrté neobsahuje závorky).

Všimněte si, že koncept logických spojek zde není konkretizován. Obvykle jsou do vzorců zavedena určitá zjednodušení. Například v zápisu vzorců se vynechávají závorky podle stejných pravidel jako ve výrokové algebře.

Ø Definice. Vzorec se nazývá tautologie, pokud bere pouze skutečné hodnoty pro jakékoli hodnoty písmen.

Ø Definice Zavolá se vzorec, který je pro jakoukoli hodnotu písmen nepravdivý rozpor

Ø Definice Vzorec se nazývá proveditelné, pokud na nějaké množině rozdělení pravdivostních hodnot proměnných nabývá hodnoty AND.

Ø Definice Vzorec se nazývá vyvratitelné, pokud pro nějaké rozdělení pravdivostních hodnot proměnných nabývá hodnoty L.

Příklad jsou vzorce podle odstavce 2 definice.

Ze stejného důvodu budou slova vzorce:

Současně s pojmem formule, pojem podvzorce nebo část vzorce.

1. podvzorec elementární vzorec je sám sebou.

2. Má-li vzorec tvar , pak jeho podformulemi jsou: sám, vzorec A a všechny podformule vzorce A.

3. Má-li vzorec tvar (A * B) (dále pod symbolem * budeme rozumět kterýkoli ze tří symbolů), pak jeho podformulemi jsou: ona sama, formule A a B a všechny podvzorce vzorců A a B.

Příklad Pro vzorec jeho podvzorce budou:

- podvzorec nulové hloubky,

Podvzorce první hloubky,

Podvzorce druhé hloubky,

Podvzorce třetí hloubky,

Podvzorec čtvrté hloubky.

Když se tedy „noříme hluboko do struktury vzorce“, vybíráme podvzorce s rostoucí hloubkou

Z kurzu diskrétní matematiky jsou známy hlavní logické ekvivalence (ekvivalence), které jsou příklady tautologií. Všechny logické zákony musí být tautologiemi.

Někdy se nazývají zákony pravidla pro výběr, které určují správný závěr z premis.

2.7Zákony výrokové logiky

Algebra logiky má komutativní a asociativní zákony s ohledem na operace konjunkce a disjunkce a distributivní zákon konjunkce s ohledem na disjunkci, stejné zákony platí v algebře čísel.

Proto je možné přes vzorce algebry logiky provádět stejné transformace, jaké se provádějí v algebře čísel (otevírací závorky, závorky, závorky společného činitele).

Zvažte základní zákony výrokové logiky.

1. Komutativnost:

, .

2. Asociativita:

3. Distributivita:

4. Impotence: , .

5. Zákon dvojí negace: .

6. Zákon o vyloučení třetího:.

7. Zákon rozporu: .

8. De Morganovy zákony:

9. Zákony idempotence(vlastnosti operací s logickými konstantami)

V algebře logiky nejsou žádné exponenty a koeficienty. Konjunkce identických „faktorů“ je ekvivalentní jednomu z nich

Zde a jsou všechna písmena.

Příklady. tautologický vzorec.