Il barbiere si rade. Il paradosso di Bertrand Russell

Il più famoso dei paradossi scoperti già nel secolo scorso è l'antinomia scoperta da Bertrand Russell e da lui comunicata in una lettera a G. Ferge. Russell scoprì il suo paradosso relativo al campo della logica e della matematica nel 1902. La stessa antinomia fu discussa simultaneamente a Gottinga dai matematici tedeschi Z. Zermelo (1871-1953) e D. Hilbert. L'idea era nell'aria e la sua pubblicazione ha dato l'impressione di una bomba che esplode Miroshnichenko P.N. Cosa ha distrutto il paradosso di Russell nel sistema di Frege? // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - SPb., 2000. - S. 512-514. . Questo paradosso ha causato in matematica, secondo Hilbert, l'effetto di una catastrofe completa. I metodi logici più semplici e importanti, i concetti più comuni e utili sono minacciati. Si è scoperto che nella teoria degli insiemi di Cantor, accettata con entusiasmo dalla maggior parte dei matematici, ci sono strane contraddizioni che sono impossibili, o almeno molto difficili, da eliminare. Il paradosso di Russell ha portato alla luce queste contraddizioni con particolare chiarezza. I matematici più eminenti di quegli anni lavorarono alla sua risoluzione, così come alla risoluzione di altri paradossi trovati della teoria degli insiemi di Cantor. Divenne subito evidente che né in logica né in matematica, in tutta la lunga storia della loro esistenza, era stato elaborato qualcosa che potesse servire come base per eliminare l'antinomia. Chiaramente era necessario un allontanamento dai modi di pensare abituali. Ma da dove e in che direzione? Courant R., Robbins G. Che cos'è la matematica? - cap. II, § 4.5.

Quanto doveva essere radicale il rifiuto dei metodi consolidati di teorizzazione? Con ulteriori studi sull'antinomia, è cresciuta costantemente la convinzione della necessità di un approccio fondamentalmente nuovo. Mezzo secolo dopo la sua scoperta, gli specialisti dei fondamenti della logica e della matematica L. Frenkel e I. Bar-Hillel hanno già affermato senza alcuna riserva: , finora invariabilmente falliti, sono ovviamente insufficienti a questo scopo. Il moderno logico americano H. Curry scrisse poco dopo su questo paradosso: “Secondo la logica conosciuta nel 19° secolo, la situazione semplicemente sfidava ogni spiegazione, sebbene, ovviamente, nella nostra epoca istruita ci possano essere persone che vedono (o pensano di vedere), qual è l'errore" Miroshnichenko P.N. Cosa ha distrutto il paradosso di Russell nel sistema di Frege? // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - SPb., 2000. - S. 512-514 ..

Il paradosso di Russell nella sua forma originaria è connesso al concetto di insieme, o di classe. Possiamo parlare di insiemi di oggetti diversi, ad esempio, dell'insieme di tutte le persone o dell'insieme dei numeri naturali. Un elemento del primo set sarà una qualsiasi persona, un elemento del secondo - ogni numero naturale. È anche possibile considerare gli insiemi stessi come degli oggetti e parlare di insiemi di insiemi. Si possono anche introdurre concetti come l'insieme di tutti gli insiemi o l'insieme di tutti i concetti. Rispetto a qualsiasi insieme preso arbitrariamente, sembra ragionevole chiedersi se sia o meno un suo elemento. Gli insiemi che non contengono se stessi come elemento saranno chiamati ordinari. Ad esempio, l'insieme di tutte le persone non è una persona, proprio come l'insieme degli atomi non è un atomo. Gli insiemi che sono elementi appropriati saranno insoliti. Ad esempio, un insieme che unisce tutti gli insiemi è un insieme e quindi contiene se stesso come elemento.

Trattandosi di un set, ci si può anche chiedere se è ordinario o insolito. La risposta, tuttavia, è scoraggiante. Se è ordinario, allora per definizione deve contenere se stesso come elemento, poiché contiene tutti gli insiemi ordinari. Ma questo significa che si tratta di un set insolito. L'assunto che il nostro insieme sia un insieme ordinario porta quindi a una contraddizione. Quindi non può essere normale. D'altra parte, non può essere nemmeno insolito: un insieme insolito contiene se stesso come elemento, e gli elementi del nostro insieme sono solo insiemi ordinari. Di conseguenza, giungiamo alla conclusione che l'insieme di tutti gli insiemi ordinari non può essere né ordinario né straordinario.

Pertanto, l'insieme di tutti gli insiemi che non sono elementi propri è un elemento proprio se e solo se non è un tale elemento. Questa è una chiara contraddizione. Ed è stato ottenuto sulla base delle ipotesi più plausibili e con l'ausilio di passaggi apparentemente indiscutibili. La contraddizione dice che un tale insieme semplicemente non esiste. Ma perché non può esistere? Dopotutto, è costituito da oggetti che soddisfano una condizione ben definita e la condizione stessa non sembra essere in qualche modo eccezionale o oscura. Se un insieme così semplicemente e chiaramente definito non può esistere, allora qual è, in effetti, la differenza tra insiemi possibili e impossibili? La conclusione che l'insieme in esame non esiste suona inaspettata e preoccupante. Rende amorfa e caotica la nostra nozione generale di insieme e non vi è alcuna garanzia che non possa dar luogo a nuovi paradossi.

Il paradosso di Russell è notevole per la sua estrema generalità Courant R., Robbins G. Cos'è la matematica? - cap. II, § 4.5. . Per la sua costruzione non sono necessari concetti tecnici complessi, poiché nel caso di alcuni altri paradossi sono sufficienti i concetti di "insieme" ed "elemento dell'insieme". Ma questa semplicità parla solo della sua natura fondamentale: tocca i fondamenti più profondi del nostro ragionamento sugli insiemi, poiché non parla di alcuni casi speciali, ma di insiemi in generale.

Altre varianti del paradosso Il paradosso di Russell non è specificamente matematico. Utilizza il concetto di insieme, ma non tocca alcuna proprietà speciale associata specificamente alla matematica.

Ciò diventa evidente quando il paradosso viene riformulato in termini puramente logici. Di ogni proprietà ci si può, con ogni probabilità, chiedersi se è applicabile a se stessa o meno. La proprietà di essere caldo, per esempio, non si applica a se stesso, poiché non è esso stesso caldo; anche la proprietà di essere concreto non si riferisce a se stessa, perché è una proprietà astratta. Ma la proprietà di essere astratto, di essere astratto, è applicabile a se stessi.

Chiamiamo queste proprietà inapplicabili a se stesse inapplicabili. Vale la proprietà di essere inapplicabili a se stessi? Si scopre che l'inapplicabilità è inapplicabile solo se non lo è. Questo è, ovviamente, paradossale. La varietà logica e correlata alla proprietà dell'antinomia di Russell è paradossale quanto la varietà matematica, correlata agli insiemi.

Russell ha anche proposto la seguente versione popolare del paradosso da lui scoperto Katrechko S.L. Il paradosso di Barber di Russell e la dialettica di Platone-Aristotele // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - SPb., 2002. - S. 239-242 .. Immaginiamo che il consiglio di un villaggio definisse i doveri del barbiere in questo modo: radere tutti gli uomini del villaggio che non si radono da soli, e solo questi uomini. Dovrebbe radersi? Se è così, si riferirà a coloro che si radono da soli, e coloro che si radono da soli, non dovrebbe radersi. In caso contrario, apparterrà a coloro che non si radono da soli, e quindi dovrà radersi. Si arriva così alla conclusione che questo barbiere si rade se e solo se non si rade. Questo, ovviamente, è impossibile.

L'argomento sul barbiere si basa sul presupposto che un tale barbiere esista. La contraddizione risultante significa che questo presupposto è falso e non esiste un tale abitante del villaggio che raderebbe tutti coloro e solo quegli abitanti del villaggio che non si radono da soli. I doveri di un barbiere non sembrano contraddittori a prima vista, quindi la conclusione che non può essercene uno suona alquanto inaspettata. Tuttavia, questa conclusione non è paradossale. La condizione che il barbiere del villaggio deve soddisfare è, infatti, contraddittoria e quindi impossibile. Non può esserci un tale parrucchiere nel villaggio per lo stesso motivo per cui non c'è nessuna persona che sia più grande di lui o che sarebbe nata prima della sua nascita Miroshnichenko P.N. Cosa ha distrutto il paradosso di Russell nel sistema di Frege? // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - SPb., 2000. - S. 512-514 ..

L'argomento sul barbiere può essere definito uno pseudo-paradosso. Nel suo corso è strettamente analogo al paradosso di Russell, ed è questo che lo rende interessante. Ma non è ancora un vero paradosso.

Un altro esempio dello stesso pseudo-paradosso è il noto argomento del catalogo. Una certa biblioteca decise di compilare un catalogo bibliografico che comprendesse tutti quei e solo quei cataloghi bibliografici che non contengono riferimenti a se stessi. Una tale directory dovrebbe includere un collegamento a se stessa? È facile dimostrare che l'idea di creare un catalogo del genere non è fattibile; semplicemente non può esistere, perché deve contemporaneamente includere un riferimento a se stesso e non includere.

È interessante notare che la catalogazione di tutte le directory che non contengono riferimenti a se stesse può essere considerata un processo infinito e senza fine. Diciamo che ad un certo punto è stata compilata una directory, diciamo K1, che include tutte le altre directory che non contengono riferimenti a se stesse. Con la creazione di K1, è apparsa un'altra directory che non contiene un collegamento a se stessa. Poiché l'obiettivo è fare un catalogo completo di tutte le directory che non si menzionano, è ovvio che K1 non è la soluzione. Non menziona una di quelle directory -- lui stesso. Includendo questa menzione di se stesso in K1, otteniamo il catalogo K2. Menziona K1, ma non K2 stesso. Aggiungendo una tale menzione a K2, otteniamo KZ, che ancora una volta non è completo a causa del fatto che non si menziona. E via senza fine.

Si può citare un altro paradosso logico: il paradosso dei sindaci olandesi, simile al paradosso del barbiere. Ogni comune in Olanda deve avere un sindaco e due comuni diversi non possono avere lo stesso sindaco. A volte si scopre che il sindaco non abita nel suo comune. Supponiamo che venga approvata una legge con la quale parte del territorio S viene assegnato esclusivamente a tali sindaci che non risiedono nei loro comuni, e che diriga a tutti questi sindaci di stabilirsi in questo territorio. Supponiamo inoltre che ci siano così tanti di questi sindaci che il territorio S stesso formi un comune separato. Dove dovrebbe risiedere il sindaco di questo Comune Speciale S? Un semplice ragionamento mostra che se il sindaco di un Comune Speciale abita in territorio S, allora non deve abitarvi, e viceversa, se non abita nel territorio, allora deve abitare in questo territorio. Che questo paradosso sia analogo al paradosso del barbiere è abbastanza ovvio.

Russell è stato uno dei primi a proporre una soluzione al “suo” paradosso. La soluzione da lui proposta è stata chiamata "teoria dei tipi": un insieme (classe) e i suoi elementi appartengono a tipi logici diversi, il tipo di un insieme è superiore al tipo dei suoi elementi, il che elimina il paradosso di Russell (la teoria dei tipi è stata utilizzata anche da Russell per risolvere il famoso paradosso del "Bugiardo"). Molti matematici, tuttavia, non accettarono la soluzione di Russell, ritenendo che imponga restrizioni troppo severe alle affermazioni matematiche di Katrechko S.L. Il paradosso di Barber di Russell e la dialettica di Platone-Aristotele // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - San Pietroburgo, 2002. - S. 239-242 ..

La situazione è simile con altri paradossi logici. “Le antinomie della logica”, scrive von Wright, “ci hanno lasciato perplessi sin dalla loro scoperta e probabilmente ci confonderanno sempre. Dovremmo, credo, considerarli non tanto come problemi in attesa di essere risolti, ma come materia prima inesauribile per il pensiero. Sono importanti perché pensare a loro tocca le questioni più fondamentali di tutta la logica, e quindi di tutto il pensiero” Wrigt G.Kh. sfondo. Logica e filosofia nel XX secolo // Vopr. filosofia. 1992. N. 8..

Tutti gli insiemi che non contengono se stessi come elemento. Si contiene come elemento? Se è così, allora, per definizione, non dovrebbe essere un elemento, una contraddizione. Se no - allora, per definizione, deve essere un elemento - di nuovo una contraddizione.

La contraddizione nel paradosso di Russell nasce dall'uso nel ragionamento del concetto internamente contraddittorio insiemi di tutti gli insiemi e idee sulla possibilità di un'applicazione illimitata delle leggi della logica classica quando si lavora con gli insiemi. Sono stati proposti diversi modi per superare questo paradosso. La più famosa è la presentazione di una formalizzazione coerente per la teoria degli insiemi, in relazione alla quale sarebbero accettabili tutti i modi “realmente necessari” (in un certo senso) di operare con gli insiemi. Nell'ambito di tale formalizzazione, l'affermazione sull'esistenza insiemi di tutti gli insiemi sarebbe irriducibile.

Supponiamo infatti che esista l'insieme di tutti gli insiemi. Quindi, secondo l'assioma di selezione, deve esistere anche un insieme i cui elementi sono quegli e solo quegli insiemi che non si contengono come elemento. Tuttavia, l'ipotesi dell'esistenza di un insieme porta al paradosso di Russell. Pertanto, vista la coerenza della teoria, l'affermazione circa l'esistenza di un insieme non è derivabile in questa teoria, che doveva essere dimostrata.

Nel corso dell'attuazione del programma descritto di "salvare" la teoria degli insiemi, sono state proposte diverse possibili assiomatizzazioni di essa (teoria ZF di Zermelo-Fraenkel, teoria NBG di Neumann-Bernays-Gödel, ecc.), tuttavia nessuna prova ha stata trovata per una qualsiasi di queste teorie finora coerenza. Inoltre, come ha mostrato Gödel sviluppando una serie di teoremi di incompletezza, una tale dimostrazione non può esistere (in un certo senso).

Un'altra reazione alla scoperta Il paradosso di Russell apparve l'intuizionismo di L. E. Ya. Brouwer.

Opzioni di formulazione

Ci sono molte formulazioni popolari di questo paradosso. Uno di questi è tradizionalmente chiamato il paradosso del barbiere e recita così:

Fu ordinato un barbiere del villaggio "Rasare chi non si rade e non radere chi si rade". Come dovrebbe comportarsi con se stesso?

Un'altra opzione:

Un paese ha emesso un decreto: "I sindaci di tutte le città non dovrebbero vivere nella propria città, ma in una città speciale di sindaci". Dove dovrebbe vivere il Sindaco della Città dei Sindaci?

E un altro:

Una certa biblioteca decise di compilare un catalogo bibliografico che comprendesse tutti quei e solo quei cataloghi bibliografici che non contengono riferimenti a se stessi. Una tale directory dovrebbe includere un collegamento a se stessa?

Guarda anche

Letteratura

• Courant R, Robbins G. Cos'è la matematica? - cap. II, § 4.5
• Miroshnichenko P.N. Cosa ha distrutto il paradosso di Russell nel sistema di Frege? // Logica moderna: problemi di teoria, storia e applicazione nella scienza. - SPb., 2000. - S. 512-514.
• Katrechko S.L. Il paradosso del barbiere di Russell e la dialettica di Platone - Aristotele // Logica moderna: problemi di teoria, storia e applicazioni nella scienza. - San Pietroburgo, 2002. - S. 239-242.
• Martin Gardner Bene, indovina un po'! = Ah! capito. Paradossi per enigmi e deliziare. - M.: Mir, 1984. - S. 22-23. - 213 pag.

Appunti

Fondazione Wikimedia. 2010.

Guarda cos'è il "paradosso di Russell" in altri dizionari:

- (paradosso greco inaspettato, strano) in senso lato: un'affermazione che contrasta nettamente con l'opinione generalmente accettata e consolidata, la negazione di ciò che sembra essere “indubbiamente corretto”; in senso stretto, due affermazioni opposte, per ... ... Enciclopedia filosofica

Il paradosso di Russell, un'antinomia insiemistica scoperta nel 1903 da Bertrand Russell e successivamente riscoperta indipendentemente da E. Zermelo, dimostrando l'imperfezione del linguaggio dell'ingenua teoria degli insiemi di G. Cantor, e non la sua incoerenza. Antinomia ... ... Wikipedia

paradosso- PARADOX (dal greco para outside e doxa opinion). 1) In senso ampio (non logico), tutto ciò che in un modo o nell'altro contrasta (diverge) dall'opinione generalmente accettata, confermata dalla tradizione, dalla legge, dalla norma, dalla norma o dal buon senso. ... ... Enciclopedia di epistemologia e filosofia della scienza

La posizione, che in un primo momento non è ancora evidente, tuttavia, contrariamente alle aspettative, esprime la verità. Nella logica antica, un paradosso era un'affermazione la cui ambiguità si riferisce principalmente alla sua correttezza o inesattezza. A… … Enciclopedia filosofica

- (il paradosso della classe di tutte le classi fondate) un paradosso nella teoria degli insiemi, che è una generalizzazione del paradosso di Burali Forti. Prende il nome dal matematico russo D. Mirimanov. Sommario 1 Formulazione ... Wikipedia

Dimostra che l'assunzione dell'esistenza di un insieme di tutti i numeri ordinali porta a contraddizioni e, quindi, la teoria degli insiemi, in cui la costruzione di un tale insieme è possibile, è contraddittoria. Sommario 1 Formulazione 2 Storia ... Wikipedia

- (dal greco paradossi inaspettato, strano) inaspettato, insolito (almeno nella forma) giudizio (affermazione, sentenza), nettamente in contrasto con l'opinione tradizionale generalmente accettata su questo tema. In questo senso, l'epiteto "paradossale"... Grande enciclopedia sovietica

Il paradosso di Cantor è un paradosso della teoria degli insiemi, che dimostra che l'assunzione dell'esistenza di un insieme di tutti gli insiemi porta a contraddizioni e, quindi, è inconsistente una teoria in cui la costruzione di un tale insieme ... ... Wikipedia

Questo termine ha altri significati, vedi Paradox (significati). Robert Boyle. Schema di prova che non esiste una macchina a moto perpetuo Paradosso ... Wikipedia

Libri

• Il crollo del concetto metafisico dell'universalità dell'area disciplinare nella logica. Polemica Frege-Schroeder, B.V. Biryukov. Questo libro discute la drammatica storia della logica matematica associata al concetto di "universo ragionante" - l'area tematica della logica. Il conflitto di opinioni tra due...

Il paradosso di Russell (L'antinomia di Russell, anche Paradosso Russell-Zermelo) è un paradosso (antinomia) della teoria degli insiemi scoperto nel 1901 da Bertrand Russell, che dimostra l'incoerenza del sistema logico di Frege, che fu un primo tentativo di formalizzare l'ingenua teoria degli insiemi di Georg Cantor. Scoperta in precedenza ma non pubblicata da Ernst Zermelo.

Nel linguaggio informale, il paradosso può essere descritto come segue. Accettiamo di chiamare un insieme "ordinario" se non è un suo elemento. Ad esempio, l'insieme di tutte le persone è "ordinario", poiché l'insieme stesso non è una persona. Un esempio di insieme "inusuale" è l'insieme di tutti insiemi, poiché esso stesso è un insieme, e quindi è esso stesso un elemento proprio.

Si può considerare un insieme costituito solo da tutti gli insiemi "ordinari", tale insieme viene chiamato Insieme di Russel . Sorge un paradosso quando si cerca di determinare se questo insieme sia "ordinario" o meno, cioè se contenga se stesso come elemento. Ci sono due possibilità.

• Da un lato, se è "ordinario", allora deve includere se stesso come elemento, poiché per definizione è costituito da tutti gli insiemi "ordinari". Ma allora non può essere "ordinario", poiché gli insiemi "ordinari" sono quelli che non includono se stessi.
• Resta da presumere che questo set sia "insolito". Tuttavia, non può includersi come elemento, poiché per definizione deve consistere solo in insiemi "ordinari". Ma se non include se stesso come elemento, allora è un insieme "ordinario".

In ogni caso ne risulta una contraddizione.

YouTube enciclopedico

1 / 5

✪ Lezione 1. Definizione di un insieme. Le leggi di De Morgan. Il paradosso di Russell. Teorema di Weierstrass

✪ 3 Il paradosso di Russell

✪ Bertrand Russell Consigli alle generazioni future

✪ Lezione 21: Teoria degli insiemi ingenua e logica fuzzy

✪ Monty Hall Paradox - Numerofilo

Sottotitoli

Formulazione del paradosso

Il paradosso di Russell può essere formulato in una teoria ingenua degli insiemi. Pertanto, la teoria ingenua degli insiemi è incoerente. Un frammento contraddittorio della teoria ingenua degli insiemi, che può essere definita come una teoria del primo ordine con una relazione di appartenenza binaria ∈ (\ displaystyle \ in ) e schema di selezione: per ogni formula logica con una variabile libera nella teoria degli insiemi ingenua c'è un assioma

∃ y ∀ X (x ∈ y ⟺ P (x)) (\ displaystyle \ esiste y \ per tutto x (x \ in y \ se P (x))).

Questo schema di assiomi lo dice per qualsiasi condizione P (x) (\ displaystyle P (x)) ci sono molti y , (\ displaystyle y,) composto da quelli x , (\ displaystyle x,) che soddisfano la condizione P (x) (\ displaystyle P (x)) .

Questo è sufficiente per formulare il paradosso di Russell come segue. Permettere P (x) (\ displaystyle P (x)) c'è una formula x ∉ x . (\ displaystyle x \ notin x.)(Questo è P (x) (\ displaystyle P (x)) significa che molti x (\ displaystyle x) non contiene se stesso come elemento o, nella nostra terminologia, è un insieme "ordinario".) Allora, per l'assioma della selezione, c'è un insieme y (\ displaystyle y)(Russell set) tale che

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

Dal momento che questo è vero per qualsiasi x , (\ displaystyle x,) questo vale anche per x = y. (\ displaystyle x=y.) Questo è

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

Ne consegue che nella teoria ingenua degli insiemi si deduce una contraddizione.

Il paradosso non si presenterebbe se assumessimo che l'insieme di Russell non esiste. Tuttavia, questa stessa ipotesi è paradossale: nella teoria degli insiemi di Cantor, si ritiene che qualsiasi proprietà determini l'insieme di elementi che soddisfano questa proprietà. Poiché la proprietà di un insieme di essere "ordinario" sembra ben definita, deve esserci un insieme di tutti gli insiemi "ordinari". Questa teoria è ora chiamata teoria degli insiemi ingenua .

Versioni popolari del paradosso

Esistono diverse versioni del paradosso di Russell. A differenza del paradosso stesso, essi, di regola, non possono essere espressi in un linguaggio formale.

Paradosso del bugiardo

Il paradosso di Russell è legato al paradosso del bugiardo conosciuto fin dall'antichità, che è la seguente domanda. Data una dichiarazione:

Questa affermazione è falsa.

Questa affermazione è vera o no? È facile dimostrare che questa affermazione non può essere né vera né falsa.

Russell ha scritto di questo paradosso:

Lo stesso Russell ha spiegato il paradosso del bugiardo in questo modo. Per dire qualcosa sugli enunciati, bisogna prima definire il concetto stesso di "enunciato", senza utilizzare concetti che non sono stati ancora definiti. Pertanto, si possono definire affermazioni del primo tipo che non dicono nulla sulle affermazioni. Quindi si possono definire affermazioni del secondo tipo che parlano di affermazioni del primo tipo, e così via. L'affermazione "questa affermazione è falsa" non rientra in nessuna di queste definizioni e quindi non ha senso.

Il paradosso del barbiere

Russell cita la seguente versione del paradosso, formulato come un indovinello che qualcuno gli ha suggerito.

In un certo villaggio abiti un barbiere, che rade tutti gli abitanti del villaggio che non si radono se stessi, e solo loro. Il barbiere si rade?

Qualsiasi risposta porta a una contraddizione. Russell osserva che questo paradosso non è equivalente al suo paradosso ed è facilmente risolvibile. Infatti, proprio come il paradosso di Russell mostra che non esiste un set Russell, il paradosso del barbiere mostra che tale barbiere non esiste. La differenza è che non c'è nulla di sorprendente nella non esistenza di un tale barbiere: non per ogni proprietà c'è un barbiere che rade le persone con questa proprietà. Tuttavia, il fatto che non esista un insieme di elementi dato da qualche proprietà ben definita contraddice l'idea ingenua degli insiemi e richiede una spiegazione.

Opzione sulle directory

La formulazione più vicina al paradosso di Russell è la seguente versione della sua presentazione:

I cataloghi bibliografici sono libri che descrivono altri libri. Alcune directory possono descrivere altre directory. Alcune directory possono anche descrivere se stesse. È possibile catalogare tutti i cataloghi che non si descrivono?

Sorge un paradosso quando si cerca di decidere se questa directory debba descriversi. Nonostante l'apparente vicinanza delle formulazioni (questo è in realtà il paradosso di Russell, in cui si usano cataloghi al posto degli insiemi), questo paradosso, come il paradosso del barbiere, si risolve semplicemente: un tale catalogo non può essere compilato.

Paradosso Grelling-Nelson

Questo paradosso è stato formulato dai matematici tedeschi Kurt Grelling e Leonard Nelson nel 1908. Si tratta infatti di una traduzione della versione originale di Russell del paradosso, da lui affermato in termini di logica predicativa (vedi lettera a Frege), in un linguaggio non matematico.

Chiamiamo l'aggettivo riflessivo se questo aggettivo ha la proprietà definita da questo aggettivo. Ad esempio, gli aggettivi "russo", "polisillabico" - hanno le proprietà che definiscono (l'aggettivo "russo" è russo e l'aggettivo "polisillabico" è polisillabico), quindi sono riflessivi e gli aggettivi "tedesco", "monosillabico" - sono non riflessivo. L'aggettivo "non riflessivo" sarà riflessivo o no?

Qualsiasi risposta porta a una contraddizione. A differenza del paradosso del barbiere, la soluzione a questo paradosso non è così semplice. Non si può semplicemente dire che un tale aggettivo ("non riflessivo") non esista, poiché l'abbiamo appena definito. Il paradosso nasce dal fatto che la definizione del termine "non riflessivo" è di per sé errata. La definizione di questo termine dipende da i valori l'aggettivo a cui si applica. E poiché la parola "non riflessivo" è essa stessa un aggettivo nella definizione, ne deriva un circolo vizioso.

Storia

Russell probabilmente scoprì il suo paradosso nel maggio o giugno 1901. Secondo lo stesso Russell, stava cercando di trovare un errore nella dimostrazione di Cantor del fatto paradossale (noto come paradosso di Cantor) che non esiste un numero cardinale massimo (o un insieme di tutti gli insiemi). Di conseguenza, Russell ha ottenuto un paradosso più semplice. Russell ha comunicato il suo paradosso ad altri logici, in particolare Whitehead e Peano. Nella sua lettera a Frege del 16 giugno 1902, scrisse di aver trovato una contraddizione in " Calcolo concettuale” - un libro di Frege, pubblicato nel 1879. Ha esposto il suo paradosso in termini di logica e poi in termini di teoria degli insiemi, utilizzando la definizione di funzione di Frege:

Ho avuto difficoltà in un solo posto. Affermi (p. 17) che una funzione può essa stessa agire come un'incognita. Lo pensavo anch'io. Ma ora questo punto di vista mi sembra dubbio a causa della seguente contraddizione. Permettere w predicato: "essere un predicato che non può essere applicato a se stesso". Può w essere applicabile a se stesso? Qualsiasi risposta implica il contrario. Pertanto, dobbiamo concludere che w non è un predicato. Allo stesso modo, non c'è classe (nel suo insieme) di quelle classi che, nel loro insieme, non appartengono a se stesse. Da ciò concludo che a volte un certo insieme non forma una formazione olistica.

Testo originale (tedesco)

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 (al 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 ha ricevuto la lettera proprio nel momento in cui ha completato il lavoro sul secondo volume delle leggi fondamentali dell'aritmetica (tedesco: Grundgesetze der Arithmetik). Frege non ha avuto il tempo di correggere la sua teoria degli insiemi. Al secondo volume aggiunse solo un'appendice con un'esposizione e la sua analisi del paradosso, iniziata con la famosa osservazione:

È improbabile che a uno scienziato possa succedere qualcosa di peggio che se gli venisse strappata la terra da sotto i piedi proprio nel momento in cui completa il suo lavoro. Fu in questa posizione che mi trovai quando ricevetti una lettera da Bertrand Russell, quando il mio lavoro era già terminato.

Testo originale (tedesco)

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 \ due punti P (x) \) \ se P (z)),

che ha detto che è possibile costruire un insieme di elementi che soddisfano la proprietà P (x) , (\ displaystyle P (x),) ha suggerito di utilizzare il seguente assioma:

z ∈ ( X: P (x) ) ⟺ P (z) & z ≠ ( X: P (x) ) (\ displaystyle z \ in \ (x \ due punti P (x) \) \ se P (z) \ \&\ z\neq \(x\colon P(x)\)),

eliminando così la possibilità per un insieme di essere un membro di se stesso. Tuttavia, un piccolo [ quale?] modifica del paradosso di Russell dimostra che anche questo assioma porta a una contraddizione.

Russell ha pubblicato il suo paradosso nel suo libro " Principi di matematica"nel 1903.

Di seguito sono riportati alcuni dei possibili approcci alla costruzione di un sistema di assiomi libero dai paradossi di Russell.

La teoria dei tipi di Russell

Lo stesso Russell fu il primo a proporre una teoria libera dal paradosso di Russell. Ha sviluppato una teoria dei tipi, la cui prima versione è apparsa nel libro di Russell e Whitehead Principi di matematica"nel 1903. Questa teoria si basa sulla seguente idea: gli oggetti semplici in questa teoria hanno il tipo 0, gli insiemi di oggetti semplici hanno il tipo 1, gli insiemi di oggetti semplici hanno il tipo 2 e così via. Pertanto, nessun insieme può avere se stesso come elemento. Né l'insieme di tutti gli insiemi né l'insieme di Russell possono essere definiti in questa teoria. Una gerarchia simile viene introdotta per le istruzioni e le proprietà. Le proposizioni sugli oggetti semplici appartengono al tipo 1, le proposizioni sulle proprietà delle proposizioni di tipo 1 appartengono al tipo 2 e così via. In generale, una funzione, per definizione, è di tipo superiore rispetto alle variabili da cui dipende. Questo approccio consente di eliminare non solo il paradosso di Russell, ma anche molti altri paradossi, tra cui il paradosso bugiardo (), il paradosso Grelling-Nelson, il paradosso Burali-Forti. Russell e Whitehead hanno mostrato come ridurre tutta la matematica agli assiomi della teoria dei tipi nei loro tre volumi Principia Mathematica, pubblicati nel 1910-1913.

Tuttavia, questo approccio ha incontrato difficoltà. In particolare, sorgono problemi nel definire tali concetti come il miglior limite superiore per insiemi di numeri reali. Per definizione, un limite superiore minimo è il limite superiore più piccolo di tutti. Pertanto, quando si determina il limite superiore minimo, viene utilizzato l'insieme dei numeri reali. Quindi, il limite superiore minimo è un oggetto di tipo superiore rispetto ai numeri reali. Ciò significa che non è di per sé un numero reale. Per evitare ciò, è stato necessario introdurre il cosiddetto assioma di riducibilità. A causa della sua arbitrarietà, molti matematici rifiutarono di accettare l'assioma della riducibilità e lo stesso Russell lo definì un difetto nella sua teoria. Inoltre, la teoria si è rivelata molto complessa. Di conseguenza, non ha ricevuto ampia applicazione.

Teoria degli insiemi di Zermelo-Fraenkel

L'approccio più noto all'assiomatizzazione della matematica è la teoria degli insiemi di Zermelo-Fraenkel (ZF), nata come estensione di Le teorie di Zermelo(1908). A differenza di Russell, Zermelo mantenne i principi logici e cambiò solo gli assiomi della teoria degli insiemi. L'idea di questo approccio è che è consentito utilizzare solo insiemi costruiti da insiemi già costruiti utilizzando un determinato insieme di assiomi. Ad esempio, uno degli assiomi di Zermelo dice che è possibile costruire un insieme di tutti sottoinsiemi di un dato insieme (l'assioma booleano). Un altro assioma ( schema di selezione) dice che da ogni insieme è possibile selezionare un sottoinsieme di elementi che hanno una determinata proprietà. Questa è la principale differenza tra la teoria degli insiemi di Zermelo e la teoria degli insiemi ingenua: nella teoria degli insiemi ingenua, puoi considerare l'insieme di tutti gli elementi che hanno una determinata proprietà, e nella teoria degli insiemi di Zermelo, puoi selezionare solo un sottoinsieme da un insieme già costruito . Nella teoria degli insiemi di Zermelo, è impossibile costruire un insieme di tutti insiemi. Pertanto, anche l'insieme di Russell non può essere costruito lì.

Classi

A volte in matematica è utile considerare tutti gli insiemi nel loro insieme, ad esempio, considerare la totalità di tutti i gruppi. Per fare ciò, la teoria degli insiemi può essere estesa alla nozione di classe , come, ad esempio, nel sistema Neumann- Bernays- Gödel (NBG). In questa teoria, la raccolta di tutti gli insiemi è classe. Tuttavia, questa classe non è un insieme e non è un membro di nessuna classe, evitando così il paradosso di Russell.

Un sistema più forte che consente di prendere i quantificatori sulle classi, e non solo sugli insiemi, è, ad esempio, Teoria degli insiemi Morse - Kelly(MK). In questa teoria, il concetto principale è il concetto classe, ma no imposta. Gli insiemi in questa teoria sono considerati classi che sono esse stesse elementi di alcune classi. In questa teoria, la formula z ∈ ( x: P (x) ) (\ displaystyle z \ in \ (x \ due punti P (x) \))è considerato equivalente alla formula

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

Perché ∃ y . z ∈ y (\ displaystyle \ esiste y. z \ in y) in questa teoria significa che la classe z (\ displaystyle z)è molti, questa formula dovrebbe essere intesa come ( x: P (x) ) (\ displaystyle \ (x \ due punti P (x) \))è la classe di tutti imposta(non classi) z (\ displaystyle z), tale che P (z) (\ displaystyle P (z)). Il paradosso di Russell in questa teoria è risolto dal fatto che non tutte le classi sono un insieme.

Si può andare oltre e considerare raccolte di classi - conglomerati, raccolte di conglomerati e così via.

Impatto sulla matematica

Assiomatizzazione della matematica

Il paradosso di Russell, insieme ad altre antinomie matematiche scoperte all'inizio del XX secolo, ha stimolato una revisione dei fondamenti della matematica, che ha portato alla costruzione di teorie assiomatiche per giustificare la matematica, alcune delle quali sono state menzionate sopra.

In tutte le nuove teorie assiomatiche costruite, i paradossi conosciuti dalla metà del XX secolo (compreso il paradosso di Russell) sono stati eliminati. Tuttavia, dimostrare che nuovi paradossi simili non possono essere scoperti in futuro (questo è il problema della coerenza delle teorie assiomatiche costruite), si è rivelato, nella moderna comprensione di questo problema, impossibile (vedi teoremi di Gödel sull'incompletezza) .

intuizionismo

Parallelamente, sorse una nuova tendenza in matematica, chiamata intuizionismo, il cui fondatore è L. E. Ya. Brouwer. L'intuizionismo sorse indipendentemente dal paradosso di Russell e da altre antinomie. Tuttavia, la scoperta delle antinomie nella teoria degli insiemi ha aumentato la sfiducia degli intuizionisti nei confronti dei principi logici e ha accelerato la formazione dell'intuizionismo. La tesi principale dell'intuizionismo afferma che per provare l'esistenza di un oggetto, è necessario presentare un metodo per la sua costruzione. Gli intuizionisti rifiutano concetti astratti come l'insieme di tutti gli insiemi. L'intuizionismo nega la legge del mezzo escluso, tuttavia, va notato che la legge del mezzo escluso non è necessaria per derivare una contraddizione dall'antinomia di Russell o da qualsiasi altra (in ogni antinomia è dimostrato che A (\ displaystyle A) comporta la negazione A (\ displaystyle A) e negazione A (\ displaystyle A) comporta A , (\ displaystyle A,) tuttavia, da (LA ⇒ ¬ LA) & (¬ LA ⇒ LA) (\displaystyle (A\Freccia destra\neg A)\&(\neg A\Freccia destra A)) anche nella logica intuizionista segue una contraddizione). Vale anche la pena notare che nelle successive assiomatizzazioni della matematica intuizionistica sono stati trovati paradossi simili a quelli di Russell, come, ad esempio, Il paradosso di Girard nella formulazione originale Martin Loef.

Argomento diagonale (autoapplicabilità)

Nonostante il fatto che il ragionamento di Russell porti a un paradosso, l'idea principale di questo ragionamento viene spesso utilizzata nella dimostrazione di teoremi matematici. Come accennato in precedenza, Russell ha ottenuto il suo paradosso analizzando la prova di Cantor della non esistenza del numero cardinale più grande. Questo fatto contraddice l'esistenza di un insieme di tutti gli insiemi, poiché la sua cardinalità deve essere massima. Tuttavia, secondo il teorema di Cantor, l'insieme di tutti i sottoinsiemi di un dato insieme ha una cardinalità maggiore dell'insieme stesso. La prova di questo fatto si basa su quanto segue diagonal argomento?!:

Lascia che ci sia una corrispondenza uno a uno, che a ciascun elemento x (\ displaystyle x) imposta X (\ displaystyle X) corrisponde a un sottoinsieme s x (\ displaystyle s_ (x)) imposta X. (\ displaystyle X.) Permettere d (\ displaystyle d) sarà un insieme di elementi x (\ displaystyle x) tale che x ∈ s x (\ displaystyle x \ in s_ (x)) (serie diagonale). Quindi il complemento di questo set s = d ¯ (\ displaystyle s = (\ overline (d))) non può essere uno di sx. (\ displaystyle s_(x).) Pertanto, la corrispondenza non era uno a uno.

Cantor ha usato l'argomento diagonale per dimostrare l'innumerevolezza numeri reali nel 1891. (Questa non è la sua prima prova della non numerabilità dei numeri reali, ma la più semplice).

Paradossi correlati

L'autoapplicabilità è usata in molti paradossi diversi da quelli discussi sopra:

• Il paradosso dell'onnipotenza è una domanda medievale: "Può un dio onnipotente creare una pietra che lui stesso non può sollevare?"
• Il paradosso Burali-Forti (1897) è un analogo del paradosso Cantor per i numeri ordinali.
• Il paradosso di Mirimanov (1917) è una generalizzazione del paradosso Burali-Forti per la classe di tutte le classi ben fondate.
• Il paradosso di Richard (1905) è un paradosso semantico che mostra l'importanza di separare il linguaggio della matematica e della metamatematica.
• Il paradosso di Berry (1906) è una versione semplificata del paradosso di Richard pubblicata da Russell.
• Paradosso di Kleene-Rosser(1935) - formulazione del paradosso di Richard in termini di λ-calcolo.
• Il paradosso di Curry (1941) è una semplificazione del paradosso di Kleene-Rosser.
• Il paradosso di Girard(1972) - formulazione del paradosso Burali-Forti in termini di teoria di tipo intuizionista .
• è un paradosso semi-scherzoso che ricorda il paradosso di Berry.

Appunti

1. Godhard Link (2004) Cento anni di paradosso di Russell, Insieme a. 350, ISBN 9783110174380 , .
2. Antinomia di Russell // Dizionario della logica. Ivin A.A., Nikiforov A.L.- M.: Tumanit, VLADOS, 1997. - 384 pag. - ISBN 5-691-00099-3.
3. Andrew David Irvine, Harry Deutsch. Russell "s Paradox // The Stanford Encyclopedia of Philosophy / Edward N. Zalta. - 01-01-2014.
4. Antinomia- articolo dall'Enciclopedia matematica. AG Dragalin
5. AS Gerasimov. Corso matematico logico e teorico calcolabile. - Terza edizione, riveduta e ampliata. - San Pietroburgo: LEMA, 2011. - S. 124-126. - 284 pag.

Il più famoso dei paradossi scoperti già nel nostro secolo è l'antinomia scoperta da B. Russell. L'idea era nell'aria e la sua pubblicazione ha prodotto l'impressione di una bomba che esplode. Questo paradosso ha causato in matematica, secondo D. Hilbert, "l'effetto di una catastrofe completa". I metodi logici più semplici e importanti, i concetti più comuni e utili sono minacciati. Divenne subito evidente che né in logica né in matematica, in tutta la lunga storia della loro esistenza, era stato elaborato qualcosa che potesse servire come base per eliminare l'antinomia. Chiaramente era necessario un allontanamento dai modi di pensare abituali.

Il paradosso di Russell nella sua forma originaria è connesso al concetto di insieme, o di classe. Possiamo parlare di insiemi di oggetti diversi, ad esempio, dell'insieme di tutte le persone o dell'insieme dei numeri naturali. Un elemento del primo set sarà una qualsiasi persona, un elemento del secondo - ogni numero naturale. È anche possibile considerare gli insiemi stessi come degli oggetti e parlare di insiemi di insiemi. Si possono anche introdurre concetti come l'insieme di tutti gli insiemi o l'insieme di tutti i concetti. Rispetto a qualsiasi insieme preso arbitrariamente, sembra ragionevole chiedersi se sia o meno un suo elemento. Gli insiemi che non contengono se stessi come elemento saranno chiamati ordinari. Ad esempio, l'insieme di tutte le persone non è una persona, proprio come l'insieme degli atomi non è un atomo. Gli insiemi che sono elementi appropriati saranno insoliti. Ad esempio, un insieme che unisce tutti gli insiemi è un insieme e quindi contiene se stesso come elemento. Ovviamente, ogni set è ordinario o insolito.

Consideriamo ora l'insieme di tutti gli insiemi ordinari. Trattandosi di un set, ci si può anche chiedere se è ordinario o insolito. La risposta, tuttavia, è scoraggiante. Se è ordinario, allora per definizione deve contenere se stesso come elemento, poiché contiene tutti gli insiemi ordinari. Ma questo significa che si tratta di un set insolito. L'assunto che il nostro insieme sia un insieme ordinario porta quindi a una contraddizione. Quindi non può essere normale. D'altra parte, non può essere nemmeno insolito: un insieme insolito contiene se stesso come elemento, e gli elementi del nostro insieme sono solo insiemi ordinari. Di conseguenza, giungiamo alla conclusione che l'insieme di tutti gli insiemi ordinari non può essere né ordinario né straordinario.

Pertanto, l'insieme di tutti gli insiemi che non sono elementi propri è un elemento proprio se e solo se non è un tale elemento. Questa è una chiara contraddizione.

La contraddizione dice che un tale insieme semplicemente non esiste. Ma perché non può esistere? Dopotutto, è costituito da oggetti che soddisfano una condizione ben definita e la condizione stessa non sembra essere in qualche modo eccezionale o oscura. Se un insieme così semplicemente e chiaramente definito non può esistere, allora qual è, in effetti, la differenza tra insiemi possibili e impossibili? La conclusione sulla non esistenza dell'insieme considerato suona inaspettata e ispira ansia. Rende amorfa e caotica la nostra nozione generale di insieme e non vi è alcuna garanzia che non possa dar luogo a nuovi paradossi.

Il paradosso di Russell è notevole per la sua estrema generalità. Per la sua costruzione non sono necessari concetti tecnici complessi, poiché nel caso di alcuni altri paradossi sono sufficienti i concetti di "insieme" ed "elemento dell'insieme". Ma questa semplicità parla solo della sua natura fondamentale: tocca i fondamenti più profondi del nostro ragionamento sugli insiemi, poiché non parla di alcuni casi speciali, ma di insiemi in generale.

Il paradosso di Russell non è specificamente matematico. Utilizza il concetto di insieme, ma non tocca alcuna proprietà speciale associata specificamente alla matematica. Ciò diventa evidente quando il paradosso viene riformulato in termini puramente logici.

Di ogni proprietà ci si può, con ogni probabilità, chiedersi se è applicabile a se stessa o meno. La proprietà di essere caldo, per esempio, non si applica a se stesso, poiché non è esso stesso caldo; anche la proprietà di essere concreto non si riferisce a se stessa, perché è una proprietà astratta. Ma la proprietà di essere astratto, di essere astratto, è applicabile a se stessi. Chiamiamo queste proprietà inapplicabili a se stesse inapplicabili. Vale la proprietà di essere inapplicabili a se stessi? Si scopre che un'inapplicabilità è inapplicabile solo se non lo è. Questo è, ovviamente, paradossale: la varietà logica e correlata alla proprietà dell'antinomia di Russell è paradossale quanto la varietà matematica, correlata agli insiemi.

B. Russell ha anche proposto la seguente versione popolare del paradosso che ha scoperto. “Il barbiere rade tutti coloro e solo quei residenti della città che non si radono da soli. Chi rade il barbiere?" Il paradosso del barbiere sta nel fatto che, presumibilmente, è impossibile rispondere a questa domanda.

Per capire la situazione, divideremo gli abitanti della città in tre gruppi. Questa ripartizione è mostrata nella figura a sinistra: quelli che si radono da soli sono in cima; coloro che sono rasati - dal basso; quelli che non si radono affatto (monaci, bambini, donne...) sono fuori dall'ellisse.

Consideriamo prima l'azione della condizione (1). Lascia che il barbiere radi tutti coloro che non si radono da soli, cioè l'intera metà inferiore dell'ellisse (il tratteggio segna i clienti del barbiere). Ma la condizione (1) permette a lui di radersi ea chi si rade, cioè se stesso. La condizione (1) gli consente di posizionarsi nella metà superiore dell'ellisse, dove gli abitanti stessi si radono, e lì si radono. Questo è mostrato nell'immagine centrale.

Se si applica la condizione (2) e il barbiere rade solo coloro che non si radono da soli, ciò significa che rade parte della metà inferiore dell'ellisse e non si rade, cioè non è nella metà superiore dell'ellisse . Ma gli abitanti della metà inferiore potrebbero non essere rasati da un barbiere, ma da qualcun altro. E un barbiere può essere tra queste persone (figura a destra). Quindi il barbiere può radere il suo amico e il barbiere raderà la parte ombreggiata della metà inferiore dell'ellisse.

Ma se si applicano entrambe le condizioni (1) e (2), allora il barbiere non ha posto nell'ellisse. Non si rade affatto. E qui non c'è nessun paradosso. Egli, quindi, o è un monaco, o un robot, o un bambino, o una donna, o un non residente della città... E se non c'è nessuno in città se non uomini che fanno la barba, e, quindi, il l'aspetto dell'ellisse è vuoto, quindi un barbiere che soddisfa le condizioni (1) e (2) semplicemente non esiste. È assurdo chiedere in questo caso chi lo rade. Molti di questi barbieri sono vuoti.

E qui noteremo che la domanda posta, "Chi rade il barbiere?", era errata fin dall'inizio, proprio come la classica domanda: "Perché picchi tuo padre?" Prima di chiedere chi rade il barbiere, bisogna ottenere il consenso che qualcuno lo rade.

L'argomento sul parrucchiere può essere definito uno pseudo-paradosso. Nel suo corso è strettamente analogo al paradosso di Russell, ed è questo che lo rende interessante. Ma non è ancora un vero paradosso.

Un altro esempio dello stesso pseudo-paradosso è il noto argomento del catalogo.

Una certa biblioteca decise di compilare un catalogo bibliografico che comprendesse tutti quei e solo quei cataloghi bibliografici che non contengono riferimenti a se stessi. Una tale directory dovrebbe includere un collegamento a se stessa? È facile dimostrare che l'idea di creare un catalogo del genere non è fattibile; semplicemente non può esistere, perché deve contemporaneamente includere un riferimento a se stesso e non includere. È interessante notare che la catalogazione di tutte le directory che non contengono riferimenti a se stesse può essere considerata un processo infinito e senza fine.

Diciamo che ad un certo punto è stata compilata una directory, diciamo K1, includendo tutte le altre directory che non contengono riferimenti a se stesse. Con la creazione di K1 è apparsa un'altra directory che non contiene un riferimento a se stessa. Poiché l'obiettivo è fare un catalogo completo di tutte le directory che non si menzionano, è ovvio che K1 non è la soluzione. Non menziona una di quelle directory: lui stesso. Includendo questa menzione di se stesso in K1, otteniamo il catalogo K2. Menziona K1 ma non K2 stesso. Aggiungendo una tale menzione a K2, otteniamo K3, che è ancora una volta incompleto a causa del fatto che non si menziona. E così via senza fine.

Il proprietario di un barbiere in un villaggio ha pubblicato il seguente avviso: "Rado quelli e solo quei residenti del villaggio che non si radono da soli". La domanda è: chi rade il barbiere?

Sviluppo logica matematica particolarmente intensificato nel XX secolo in connessione con lo sviluppo della tecnologia informatica e della programmazione.

Ø Definizione Logica matematicaè una moderna forma di logica che si basa interamente su metodi matematici formali. Studia solo inferenze con oggetti e giudizi rigorosamente definiti per i quali è possibile decidere inequivocabilmente se sono vere o false.

Il concetto di base (non definito) della logica matematica è il concetto di " semplice affermazione". Un'affermazione, che è una singola affermazione, è generalmente chiamata semplice o elementare.

Ø Dichiarazione di definizioneè una frase dichiarativa che può dirsi vera o falsa.

Le affermazioni possono essere vere I o false L.

Esempio: Pianeta Terra sistema solare. (Vero); Ogni parallelogramma è un quadrato (Falso)

Ci sono affermazioni di cui è impossibile dire con certezza se siano vere o false. "Oggi fa bel tempo" (piace a tutti)

Esempio dichiarazione "Piove"- semplice, vero o falso dipende da che tempo fa ora fuori dalla finestra. Se piove davvero, allora l'affermazione è vera, e se c'è il sole ed è inutile aspettare la pioggia, allora l'affermazione è "Piove" sarà falso.

Esempio“ ” non è un'affermazione (non si sa quali valori assuma).

"Studente del secondo anno" non è un modo di dire

Ø DefinizioneElementare gli enunciati non possono essere espressi in termini di altri enunciati.

Ø DefinizioneComposito le proposizioni sono proposizioni che possono essere espresse usando proposizioni elementari.

Esempio"Il numero 22 è pari" è un'affermazione elementare.

Esistono due approcci principali per stabilire la verità delle affermazioni: empirico (sperimentale) e logico.

In approccio empirico la verità dell'affermazione è stabilita con l'aiuto di osservazioni, misurazioni, esperimenti.

approccio logico sta nel fatto che la verità di un'affermazione si stabilisce sulla base della verità di altre affermazioni, cioè senza riferirsi ai fatti, al loro contenuto, cioè formalmente. Questo approccio si basa sull'identificazione e sull'uso di connessioni logiche tra le affermazioni incluse nell'argomento.

2.2 Logica proposizionale

Prima di tutto, è necessario definire i concetti, perché la stessa sezione è spesso chiamata in modo diverso: logica matematica, logica proposizionale (frase), logica simbolica, logica a due valori, logica proposizionale, algebra booleana ...

Ø Definizioneproposizione logica- una branca della logica in cui la questione della verità o falsità delle affermazioni viene considerata e decisa sulla base dello studio del metodo di costruzione delle affermazioni da e elementare(ulteriormente non scomposte e non analizzate) affermazioni con l'ausilio di operazioni logiche di congiunzione ("e"), disgiunzione ("o"), negazione ("non"), implicazione ("se...allora...") , ecc.

Ø Definizione Calcolo proposizionaleè un sistema logico assiomatico, la cui interpretazione è l'algebra delle proposizioni.

Di maggiore interesse è la costruzione di un sistema formale, che, tra tutti gli enunciati possibili, distingua quelli che sono leggi logiche (ragionamenti correttamente costruiti, conclusioni logiche, tautologie, enunciati generalmente validi).

Le teorie formali, che non utilizzano il linguaggio naturale (colloquiale), hanno bisogno di un proprio linguaggio formale in cui siano scritte le espressioni che vi si incontrano.

Ø Definizione Viene chiamato il sistema formale che genera enunciati che sono tautologie e solo loro calcolo proposizionale(IV).

Il sistema IoT formale è definito da:

Quali simboli sono meglio usati per denotare i connettivi logici?

Soffermiamoci sulle seguenti notazioni: negazione, congiunzione, disgiunzione, implicazione ed equivalenza. Di solito, i valori logici dei risultati dell'applicazione dei connettivi sono scritti sotto forma di tabelle (le cosiddette tavole di verità).

2.3 Connettivi logici.................................................. ................ ...

Nel linguaggio naturale, i seguenti mezzi grammaticali svolgono il ruolo di connettivi nella compilazione di frasi complesse da quelle semplici:

unioni "e", "o", "non";

le parole "se ..., allora", "o ... o",

“se e solo se”, ecc.

Nella logica proposizionale, i connettivi logici utilizzati per comporre proposizioni complesse devono essere definiti con precisione.

Consideriamo i connettivi logici (operazioni) sulle affermazioni, in cui i valori di verità delle affermazioni composte sono determinati solo dai valori di verità delle affermazioni costituenti e non dal loro significato.

Esistono cinque connettivi logici ampiamente utilizzati.

negazione (rappresentata da un segno),

congiunzione (segno),

disgiunzione (segno v),

implicazione (segno)

equivalenza (segno).

Ø DefinizioneNegazione affermazioni P è un'affermazione che è vera se e solo se l'affermazione P è falsa.

Ø DefinizioneCongiunzione due proposizioni P e Q - una proposizione che è vera se e solo se entrambe le proposizioni sono vere.

Ø DefinizioneDisgiunzione due proposizioni P e Q - una proposizione che è falsa se e solo se entrambe le proposizioni sono false.

Ø Definizionecoinvolgimento due affermazioni P e Q - un'affermazione che è falsa se e solo se P è vera e Q è falsa. Si chiama l'istruzione P pacco implicazioni, e l'affermazione Q - conclusione implicazioni.

Ø DefinizioneEquivalenza due proposizioni P e Q - una proposizione che è vera se e solo se i valori di verità di P e Q sono gli stessi.

L'uso delle parole "se ..." "allora ..." nell'algebra della logica differisce dal loro uso nel linguaggio quotidiano, dove, di regola, riteniamo che se l'affermazione Xè falsa, allora l'affermazione "Se X, poi a' non ha affatto senso. Inoltre, costruendo una frase della forma "se X, poi a» nel linguaggio di tutti i giorni, intendiamo sempre che la frase a nasce dalla proposta X. L'uso delle parole "se, allora" nella logica matematica non lo richiede, poiché in essa non viene considerato il significato delle proposizioni.

2.4 Operazioni logiche

Le basi della tecnologia digitale sono tre operazioni logiche che stanno alla base di tutti i risultati del computer. Si tratta di tre operazioni logiche: AND, OR, NOT, che vengono chiamate “tre pilastri della logica della macchina”.

Connettivi logici o operazioni logiche note dal corso di matematica discreta possono essere applicati alle affermazioni. Questo risulta in formule. Le formule diventano proposizioni sostituendo tutti i significati delle lettere.

Tavole di verità delle operazioni logiche di base.

Diverse variabili collegate tra loro da operazioni logiche sono chiamate funzione logica.

La descrizione di qualsiasi calcolo include una descrizione dei simboli di questo calcolo (alfabeto), formule, che sono le configurazioni finali dei simboli e la definizione di formule derivabili.

2.5 Alfabeto del calcolo proposizionale

L'alfabeto del calcolo delle espressioni è costituito da simboli di tre categorie:

Il primo è il segno della disgiunzione o dell'addizione logica, il secondo è il segno della congiunzione o della moltiplicazione logica, il terzo è il segno dell'implicazione o della conseguenza logica e il quarto è il segno della negazione.

Il calcolo proposizionale non ha altri simboli.

2.6 Formule Tautologia

Le formule del calcolo proposizionale sono sequenze di simboli dell'alfabeto del calcolo proposizionale.

Le lettere maiuscole dell'alfabeto latino sono usate per designare le formule. Queste lettere non sono simboli di calcolo. Sono solo simboli di formule.

Ø Formula di definizione– affermazione composta ben formata:

1) Ogni lettera lo è formula.

2) Se , sono formule, allora , , , , sono anche formule.

Ovviamente, le parole non sono formule: ) (la terza di queste parole non contiene parentesi chiuse e la quarta non contiene parentesi).

Si noti che il concetto di connettivi logici non è qui concretizzato. Di solito, nelle formule vengono introdotte alcune semplificazioni. Ad esempio, le parentesi sono omesse nella notazione delle formule secondo le stesse regole dell'algebra proposizionale.

Ø Definizione. La formula è chiamata tautologia, se prende solo valori veri per qualsiasi valore di lettere.

Ø Definizione Viene chiamata una formula falsa per qualsiasi valore delle lettere contraddizione

Ø Definizione La formula è chiamata fattibile, se su qualche insieme di distribuzione dei valori di verità delle variabili assume il valore AND.

Ø Definizione La formula è chiamata confutabile, se per qualche distribuzione dei valori di verità delle variabili assume il valore L.

Esempio sono formule secondo la clausola 2 della definizione.

Per lo stesso motivo, le parole saranno formule:

Contemporaneamente al concetto di formula, il concetto sottoformule o parte di una formula.

1. sottoformula la formula elementare è essa stessa.

2. Se la formula ha la forma , le sue sottoformule sono: stessa, formula A e tutte le sottoformule di formula A.

3. Se la formula ha la forma (A * B) (di seguito, sotto il simbolo * capiremo uno qualsiasi dei tre simboli), allora le sue sottoformule sono: essa stessa, le formule A e B e tutte le sottoformule delle formule A e B.

Esempio Per formula le sue sottoformule saranno:

- sottoformula di profondità zero,

Sottoformule della prima profondità,

Sottoformule della seconda profondità,

Sottoformule di terza profondità,

Sottoformula della quarta profondità.

Pertanto, mentre "immergiamoci in profondità nella struttura della formula", individuiamo sottoformule di profondità crescente

Dal corso di matematica discreta si conoscono le principali equivalenze logiche (equivalenze), che sono esempi di tautologie. Tutte le leggi logiche devono essere tautologie.

A volte si chiamano leggi regole di prelievo, che determinano la corretta conclusione dalle premesse.

2.7 Leggi della logica proposizionale

L'algebra della logica ha leggi commutative e associative rispetto alle operazioni di congiunzione e disgiunzione e una legge distributiva di congiunzione rispetto alla disgiunzione, le stesse leggi hanno luogo nell'algebra dei numeri.

Pertanto, sulle formule dell'algebra della logica, è possibile eseguire le stesse trasformazioni che si eseguono nell'algebra dei numeri (parentesi aperte, parentesi quadre, parentesi del fattore comune).

Considera le leggi fondamentali della logica proposizionale.

1. Commutatività:

, .

2. Associatività:

3. Distributività:

4. Idempotenza: , .

5. Legge della doppia negazione: .

6. La legge dell'esclusione dei terzi:.

7. Legge di contraddizione: .

8. Leggi di de Morgan:

9. Leggi di idempotenza(proprietà di operazioni con costanti logiche)

Non ci sono esponenti e coefficienti nell'algebra della logica. La congiunzione di "fattori" identici è equivalente a uno di essi

Qui , e ci sono tutte le lettere.

Esempi. formula di tautologia.