Argumentul diagonal

Argumentul diagonal ( metoda diagonală a lui Cantor ) este o dovadă a teoremei lui Cantor că mulțimea tuturor submulțimii unei mulțimi date are mai multă cardinalitate decât mulțimea în sine. În special, mulțimea tuturor submulților din seria naturală are o cardinalitate mai mare decât aleph -0 și, prin urmare, nu este numărabilă [1] . Dovada acestui fapt se bazează pe următorul argument diagonal:

Să existe o corespondență unu-la-unu , care atribuie fiecărui element al mulțimii o submulțime a mulțimii Fie o mulțime formată din elemente astfel încât ( mulțime diagonală ). Atunci complementul acestui set nu poate fi oricare dintre A, prin urmare, corespondența nu a fost unu-la-unu.

Cantor a folosit argumentul diagonală pentru a demonstra nenumărabilitatea numerelor reale în 1891. (Aceasta nu este prima sa dovadă a nenumărabilității numerelor reale, ci cea mai simplă) [2] .

Argumentul diagonal a fost folosit în multe domenii ale matematicii. Astfel, de exemplu, este argumentul central în teorema de incompletitudine a lui Gödel , în demonstrarea existenței unei mulțimi enumerabile indecidabile , și, în special, în demonstrarea indecidibilității problemei opririi [3] .

Note

  1. ↑ Metoda diagonală a lui Cantor . studfiles.net .
  2. ↑ Gray, Robert (1994), Georg Cantor and Transcendental Numbers , American Mathematical Monthly vol. 101: 819–832, doi : 10.2307/2975129 , < http://www.maa.org/sites/default/files/pdf/ upload_library/22/Ford/Gray819-832.pdf > Arhivat 21 ianuarie 2022 la Wayback Machine 
  3. ↑ John B. Bacon, Michael Detlefsen, David Charles McCarty. Argument diagonal // Logic from A to Z: The Routledge Encyclopedia of Philosophy Glosar de termeni logici și matematici . — Routledge, 2013-09-05. — 126 p. — ISBN 9781134970971 .