Riippumattomuus matemaattisessa logiikassa: määritelmä

Määritelmä ja tarkennus

Muodollisemmin: olkoon T ensimmäisen kertaluvun teoria (joukko lauseita) ja φ lause ilman vapaita muuttujia. Sanomme, että φ on riippumaton teoriasta T, jos ei päde T ⊢ φ eikä T ⊢ ¬φ. Toisin sanoen φ:tä ei voida todistaa T:n aksiomien avulla eikä myöskään sen kieltävää lausetta.

Semanttinen tulkinta ja täydellisyys

Gödelin täydellisyysteoreeman nojalla syntaktinen ja semanttinen määritelmä vastaavat toisiaan: φ on riippumaton T:stä tarkalleen silloin, kun sekä T ∪ {φ} että T ∪ {¬φ} ovat satisfioitavia eli niille on olemassa malli. Käytännössä riippumattomuus ilmaisee siis, että T ei päätä φ:n totuutta siinä mielessä, että sekä φ että ¬φ voidaan liittää teoriaan ilman ristiriitaa (olettaen, että T itsessään on konsistentti).

Miksi riippumattomuutta tutkitaan ja miten se todistetaan

Riippumattomuutta tutkitaan, koska se kertoo, mitkä väitteet ovat ratkaistavissa valituilla aksioomilla ja mitkä vaativat lisäaksioomia tai uusia periaatteita. Tavallisimmat menetelmät riippumattomuuden osoittamiseen ovat:

• malliteoreettinen konstruktio: rakennetaan malli, jossa φ on tosi, ja toinen malli, jossa ¬φ on tosi;
• sisäiset mallit ja L-universumi (esim. Gödelin tulokset) sekä Cohenin forcing-menetelmä, joita käytetään erityisesti joukko-opin aksioomien, kuten kontinuumin hypoteesin, riippumattomuuden näyttämiseksi;
• relatiiviset konsistenssitulokset: näytetään, että jos T on konsistentti, niin myös T ∪ {φ} ja T ∪ {¬φ} ovat konsistentteja.

Esimerkkejä

• Joukko-opissa Continuum Hypothesis (CH) on klassinen esimerkki: Gödel ja Cohen osoittivat, että CH on riippumaton ZF-aksioomistosta (ja myös ZFC:stä), eli ZF ei pysty päättämään CH:n totuutta.
• Aksiooma valinnasta (AC) on riippumaton ZF:stä — voidaan rakentaa mallijärjestelmiä, joissa AC pätee ja mallijärjestelmiä, joissa se ei päde.
• Peano-aritmetiikassa Gödelin epätäydellisyystulokset tarkoittavat, että jos PA on konsistentti, niin on olemassa lauseita, joita PA ei voi todistaa eikä kumota; nämä lauseet ovat PA:lle riippumattomia.

Riippumattomuuden ja "päättelemättömyyden" ero

On tärkeää erottaa kaksi eri merkitystä, joita termi "päättelemätön" voi kantaa:

• Riippumattomuus (kuten yllä määritelty): lausetta ei voida todistaa tai kumota annetusta teoriasta.
• Algoritminen päätöksettömyys (usein nimellä "päättelemättömyys" tai "epäpääteltävyys" laskennallisessa mielessä): päätösongelman yhteydessä tarkoitetaan, että ei ole yleistä algoritmia, joka päättää, ovatko satunnaisesti annettuja lauseita todistettavissa teoriassa (ks. päätösongelma). Tämä on eri käsite kuin yksittäisen lauseen riippumattomuus.

Lisätutkimus ja huomioitavaa

Riippumattomuus on aina suhteessa valittuun teoriamalliin ja todistusjärjestelmään: sama lause voi olla riippumaton yhdestä teoriasta mutta todistettavissa laajemmassa teoriassa. Lisäksi riippumattomuus ei itsessään kerro, onko lause "totta" intuitiivisessa tai oletetussa mallissa — ainoastaan sen, että teoria ei ratkaise lausetta.

Yhteenvetona: riippumattomuus ensimmäisen kertaluvun teoriasta tarkoittaa, että teoria ei päätä tiettyä lausetta. Sen osoittaminen perustuu yleensä mallien rakentamiseen tai relativisiin konsistenssituloksiin, ja käsite on keskeinen mm. kouluttavissa kysymyksissä, kuten joukko-opin ja aritmetiikan perusongelmissa.