On Effective Banach-Mazur Games and an application to the Poincaré Recurrence Theorem for Category

Technische Samenvatting: Over Effectieve Banach-Mazur Spelen en een Toepassing op de Poincaré Recurrentie-stelling voor Categorie

Probleemstelling
Klassieke wiskunde steunt vaak op niet-constructieve existentiebewijzen (bijv. via het Axioma van Keuze of Zorns Lemma) om aan te tonen dat objecten met bepaalde eigenschappen bestaan door te laten zien dat de verzameling van dergelijke objecten "groot" is in een topologische zin (Baire-categorie). Specifiek biedt het Banach-Mazur spel een speltheoretische karakterisering van verzamelingen van de eerste categorie (meager verzamelingen): een verzameling is van de eerste categorie indien en slechts indien de tweede speler een winnende strategie heeft.

Echter, in het domein van de berekenbaarheidstheorie en de effectieve analyse zijn existentiële argumenten onvoldoende. Er is een behoefte om de "effectieve inhoud" van klassieke stellingen te extraheren, wat expliciete, algoritmische constructies vereist. Hoewel de effectieve Baire-categoriestelling en effectieve maattheoretische versies van de Poincaré Recurrence-stelling bekend zijn, was de effectieve topologische versie van de Poincaré Recurrence-stelling nog niet volledig gevestigd voor alle verzamelingen van effectieve eerste categorie. De auteurs beogen deze kloof te overbruggen door het Banach-Mazur spel te effectiveren en toe te passen op dynamische systemen.

Methodologie
De auteurs ontwikkelen een raamwerk voor Effectieve Topologische Ruimten en Effectieve Banach-Mazur Spelen binnen de context van Berekenbare Analyse.

1. Effectieve Topologische Ruimten: Het werk opereert primair binnen berekenbare $T_0$-ruimten (specifiek sterk berekenbare $T_0$-ruimten voor de eerste spelversie en volledige berekenbare metrieke ruimten voor de tweede). Deze ruimten zijn uitgerust met een aftelbare basis en een representatie van basisopen verzamelingen via partiële berekenbare surjecties. Kerndefinities zijn onder meer:

   • c.e. open verzamelingen: Verenigingen van basisopen verzamelingen die berekenbaar opsombaar (computably enumerable) zijn.
   • Effectieve nergens dicht lichte verzamelingen: Verzamelingen $A$ waarbij een berekenbare functie elke basisopen verzameling kan afbeelden op een kleinere basisopen verzameling die disjunct is met $A$.
   • Effectieve eerste categorie verzamelingen: Aftelbare verenigingen van effectieve nergens dicht lichte verzamelingen.

2. Effectieve Banach-Mazur Spelen: De auteurs definiëren twee versies van het spel om effectieve meagerness te karakteriseren:

   • Versie 1: Speler 2 (P2) wordt beperkt tot een effectieve strategie (berekenbare respons), terwijl Speler 1 (P1) over onbegrensde middelen beschikt. Het spel wordt gespeeld op een sterk berekenbare $T_0$-ruimte.
   • Versie 2: P1 heeft een effectieve strategie, terwijl P2 over onbegrensde middelen beschikt. Deze versie vereist dat de ruimte een volledige berekenbare metrieke ruimte is om gebruik te maken van de Cantor-snijverzamelingstelling voor convergentie.

3. Speltheoretische Bewijzen: In plaats van Zorns Lemma (dat niet-constructief is) te gebruiken, bieden de auteurs expliciete, constructieve strategieën voor de spelers. Zij demonstreren dat indien een verzameling van de effectieve eerste categorie is, P2 een berekenbare winnende strategie bezit. Omgekeerd, indien P2 een berekenbare winnende strategie heeft, is de doelverzameling van de effectieve eerste categorie.

Belangrijkste Bijdragen en Resultaten

1. Karakterisering van Effectieve Eerste Categorie Verzamelingen:
   De primaire theoretische bijdrage is Stelling 4.3, die vaststelt dat in een sterk berekenbare $T_0$-ruimte, een verzameling $M$ van de effectieve eerste categorie is dan en slechts dan als Speler 2 een effectieve winnende strategie heeft in het Banach-Mazur spel $BM(M, M^c)$. Dit biedt een zuiver speltheoretische, constructieve karakterisering van effectieve meagerness, waarbij niet-constructieve existentiële argumenten worden vermeden.

2. Toepassing op Liouville-getallen:
   De auteurs passen hun raamwerk toe op de verzameling van Liouville-getallen ($E$). Zij bewijzen (Stelling 4.12) dat het complement van de verzameling van Liouville-getallen ($E^c$) een effectieve eerste categorie verzameling is. Bijgevolg is de verzameling van Liouville-getallen effectief co-meager. Dit resultaat benadrukt dat hoewel Liouville-getallen "klein" zijn in termen van Lebesgue-maat en Hausdorff-dimensie, zij "groot" zijn in de effectieve topologische zin.

3. Effectieve Poincaré Recurrence-stelling voor Categorie:
   De centrale toepassing van het artikel is Stelling 5.5, de Effectieve Poincaré Recurrence-stelling voor Categorie.

   • Context: Voor een begrensde berekenbaar opseembare (c.e.) open regio $X \subseteq \mathbb{R}^n$ uitgerust met een berekenbare homeomorfisme $T$ die geen niet-lege open wandering sets toelaat.
   • Resultaat: De verzameling van niet-recurrente punten in $X$ is een verzameling van de effectieve eerste categorie.
   • Methode: De auteurs definiëren de verzameling van niet-recurrente punten $N(E)$ en construeren een effectieve winnende strategie voor Speler 2 in het spel $BM(N(E), X \setminus N(E))$. Door aan te tonen dat voor elke open verzameling gekozen door P1, P2 effectief een deelverzameling kan kiezen die disjunct is van de niet-recurrente punten (door het niet-bestaan van wandering sets te benutten), bewijzen zij dat de intersectie van het spelspel de niet-recurrente verzameling volledig vermijdt.

Significantie
Het artikel claimt significantie door een speltheoretisch bewijs te leveren van de effectieve topologische Poincaré Recurrence-stelling. In tegenstelling tot eerdere benaderingen die mogelijk leunen op effectieve ergodische stellingen (die maattheoretisch zijn), opereert dit werk strikt binnen het topologische raamwerk van de Baire-categorie.

Door het Banach-Mazur spel te effectiveren, demonstreren de auteurs dat de "grootte" van de verzameling van niet-recurrente punten niet alleen topologisch klein (meager) is, maar ook effectief klein (effectieve eerste categorie). Dit betekent dat de verzameling van niet-recurrente punten gedekt kan worden door een berekenbaar opseembare vereniging van effectieve nergens dicht lichte verzamelingen, en dat een berekenbare strategie bestaat om deze punten te vermijden. Dit lost het probleem op van het vaststellen van de topologische Poincaré-stelling voor alle verzamelingen van de effectieve eerste categorie, en biedt een constructief perspectief op recurrentie in berekenbare dynamische systemen.