Michał R. Przybyłek

Here is a draft the final version of the first part of the take-home exam .

Sets definable in a first-order theory. Definable graphs and reachability problems.

Bounded and undounded zero-player constraint logic games. Bounded single player constraint logic game (NP-complete). Bounded two-player constraint logic game (PSPACE-complete).

Equivalence between non-deterministic Buchi and both deterministic and non-deterministic Muller automata. Equivalence between deterministic Muller and deterministic parity automata. Finite memory strategies. Finite memory strategy for Muller games.

We learned about inverse image, direct image and dual image functions and how they relate modal operators. We also investigated an infinite variant of Chomp game. The following note gives a proof of the Fundamental Theorem of Chomp Game. Notice that in our notation we implicitly assumed that n is finite, but it is not relevant for the proof.

We recalled some basic information from Set Theory (a poset is complete iff it is cocomplete; general fixed point via transfinite induction, fixed points in finite posets, fixed points of cocontinuous functions). The following note shows that if we assume a very weak form of axiom of determinacy then the space 2^N over the field of characteristic 2 does not have any basis. Moreover, from any basis of 2^N we construct an indetermined word game, whose outcome does not depend on only finite sequence of moves.

During the first lesson we examined simple mathematical games: Chomp, Nim, Hex. Moreover, we investigated winning strategies in Choquet games (over real line, rational line and irrational line).