Trachtenbrotin lause

Trakhtenbrotin lause on lause äärellisten mallien ensimmäisen asteen logiikkakaavojen totuuden ratkaisemattomuudesta. Sen muotoili B. A. Trakhtenbrot vuonna 1950 [1] Sen seurauksena on rajoittamaton määrä kaavoja, jotka ilmaisevat joukon äärellisyyden ehdon (ja siten määritelmän), ja niiden joukossa on rajoittamaton määrä riippumattomia. yhdet. [2] Lisäksi sen seuraus on äärettömyyden heikoimman aksiooman puuttuminen (millä tahansa äärettömyyden aksioomilla on heikompi äärettömyyden aksiooma) [3] .

Selitykset

On olemassa useita loogisia kaavoja, jotka ilmaisevat joukon äärellisyyden ehdon ja ovat siksi sen määritelmiä, esimerkiksi:

• joukko on äärellinen, jos se on induktiivinen ;
• joukko on äärellinen, jos kaikkien sen osajoukkojen joukko on ei- refleksiivinen [4] ;
• joukko on äärellinen, jos se ei ole refleksiivinen;
• joukko on äärellinen, jos se ei ole kahden disjunktin joukon liitto, joista kukin vastaa tiettyä joukkoa [4] .

Seurauksena Trachtebrotin lauseesta on tällaisten kaavojen rajoittamaton määrä ja heikoimpien ja vahvimpien puuttuminen. [2]

Matemaattisessa logiikassa kaavaa pidetään kaavaa vahvempana, jos se seuraa, mutta ei seuraa kaavasta .

Toinen Trachtenbrotin lauseen seuraus on äärettömyyden heikoimman aksiooman puuttuminen [3] .

Muistiinpanot

1. ↑ Trakhtenbrot B. A. Algoritmin mahdottomuus ratkaista äärellisten luokkien ongelma // Neuvostoliiton tiedeakatemian raportit, - 1950. - V. 70, nro 4. - P. 569-572.
2. ↑ 1 2 Trakhtenbrot B. A. Äärillisen joukon määritelmä ja joukkoteorian deduktiivinen epätäydellisyys // Izv. Neuvostoliiton tiedeakatemia, ser. matto. - 1956. - T. 20, nro 4. - S. 569-582. — URL-osoite: http://mi.mathnet.ru/izv3789
3. ↑ 1 2 Kirkko, 1960 , s. 330.
4. ↑ 1 2 Frenkel, 1966 , s. 87.

Kirjallisuus

• Kirkko A. Johdatus matemaattiseen logiikkaan. - M .: IL, 1960. - 484 s.
• Frenkel A. A. , Bar-Hillel R. Joukkoteorian perusteet. - M .: Mir, 1966. - 555 s.