On Games on Non-Wellfounded Sets and Stationary Sets

In this thesis we study a few games related to non-wellfounded and stationary sets. Games have turned out to be an important tool in mathematical logic ranging from semantic games defining the truth of a sentence in a given logic to for example games on real numbers whose determinacies have important effects on the consistency of certain large cardinal assumptions. The equality of non-wellfounded sets can be determined by a so called bisimulation game already used to identify processes in theoretical computer science and possible world models for modal logic. Here we present a game to classify non-wellfounded sets according to their branching structure. We also study games on stationary sets moving back to classical wellfounded set theory. We also describe a way to approximate non-wellfounded sets with hereditarily finite wellfounded sets. The framework used to do this is domain theory. In the Banach-Mazur game, also called the ideal game, the players play a descending sequence of stationary sets and the second player tries to keep their intersection stationary. The game is connected to precipitousness of the corresponding ideal. In the pressing down game first player plays regressive functions defined on stationary sets and the second player responds with a stationary set where the function is constant trying to keep the intersection stationary. This game has applications in model theory to the determinacy of the Ehrenfeucht-Fraisse game. We show that it is consistent that these games are not equivalent.

Väitöskirja kuuluu joukko-opin alaan ja sen lähestymistapa aiheeseen on peliteoreettinen. Tutkimus koostuu kolmesta erillisestä artikkelista. Kaksi ensimmäistä artikkelia käsittelee ei-hyvinperustettujen joukkojen teoriaa. Normaalisti ymmärrettynä joukon alkiot pitää muodostaa ennen kuin niistä voidaan muodostaa itse joukko. Esimerkiksi joukko, joka on itsensä alkio rikkoo tätä käsitystä. Normaalisti joukko-opin perusolettamuksiin kuuluu perustusaksiooma, joka kieltää tällaisten ei-hyvinperustettujen joukkojen olemassaolon. Voidaan kuitenkin osoittaa, että ilman perustusaksioomaa saadaan ristiriidaton joukko-opin teoria. Ei-hyvinnperusteuilla joukoilla voidaan mallintaa monia esimerkiksi tietojenkäsittelytieteessä ja filosofiassa esiintyviä ilmiöitä. Tutkimuksissa kuvataan eräs tapa saada ei-hyvinperustettuja joukkoja aikaiseksi klassisten verkkoihin ja yhtälöihin perustuvien tapojen rinnalle. Lisäksi määritellään peli, jonka avulla ei-hyvinperustun joukon haarautumisrakennetta voidaan kuvata. Toisessa artikkelissa näytetään miten ei-hyvinperustettuja joukkoja voidaan approksimoida hyvin perustettujen joukkojen avulla. Kolmas artikkeli käsittelee ns. stationaaristen joukkojen ominaisuuksia klassisen joukko-opin viitekehyksessä. Artikkelissa kuvataan kaksi erilaista peliä, joista ensimmäinen nk. Banachin-Mazurin peli liittyy suurten äärettömien lukujen ominaisuuksiin. Osoitamme että nämä pelit voidaan tietyissä olosuhteissa erottaa toisistaan.