path: root/lic_malinka.tex

\documentclass[11pt, a4paper, final]{amsart}
\setlength{\emergencystretch}{2em}


\usepackage[T1]{fontenc}
\usepackage{mathtools}
\usepackage[activate={true,nocompatibility},final,tracking=true,kerning=true,spacing=true,stretch=10,shrink=10]{microtype}
\microtypecontext{spacing=nonfrench}
% \usepackage[utf8]{inputenc}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{XCharter}
\usepackage[charter,expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage[utf8]{inputenc}
\usepackage{tikz-cd}
\usepackage{tikz}

\usepackage{etoolbox}


\usepackage{xcolor}
\definecolor{green}{RGB}{0,127,0}
\definecolor{redd}{RGB}{191,0,0}
\definecolor{red}{RGB}{105,89,205}
\usepackage[colorlinks=true]{hyperref}

\usepackage[notref, notcite]{showkeys}
\usepackage[cmtip,arrow]{xy}
%\usepackage[backend=biber,
%url=false,
%isbn=false,
%backref=true,
%citestyle=alphabetic,
%bibstyle=alphabetic,
%autocite=inline,
%maxnames=99,
%minalphanames=4,
%maxalphanames=4,
%sorting=nyt,]{biblatex}
%\addbibresource{linear_strucures.bib}

\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\Flim}{FLim}
\DeclareMathOperator{\Int}{{Int}}

\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
\newcommand{\cC}{\mathcal C}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\bN}{\mathbb N}
\newcommand{\bR}{\mathbb R}
\newcommand{\bZ}{\mathbb Z}
\newcommand{\bQ}{\mathbb Q}

\DeclareMathOperator{\im}{{Im}}
\DeclareMathOperator{\lin}{{Lin}}
\DeclareMathOperator{\Th}{{Th}}

\newtheorem{theorem}{Theorem}
\numberwithin{theorem}{section}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{question}[theorem]{Question}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{theorem2}{Theorem}
\newtheorem*{claim2}{Claim}
\newtheorem*{corollary2}{Corollary}
\newtheorem*{question2}{Question}
\newtheorem*{conjecture2}{Conjecture}


\newtheorem{clm}{Claim}
\newtheorem*{clm*}{Claim}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition2}{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark2}{Remark}


\AtEndEnvironment{proof}{\setcounter{clm}{0}}
\newenvironment{clmproof}[1][\proofname]{\proof[#1]\renewcommand{\qedsymbol}{$\square$(claim)}}{\endproof}

\newcommand{\xqed}[1]{%
    \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill
    \quad\hbox{\ensuremath{#1}}}


\title{Tytuł}
\author{Franciszek Malinka}

\begin{document}

    \begin{abstract}
        Abstract
    \end{abstract}
    \section{Introduction}

    \section{Preliminaries}
    \subsection{Descriptive set theory}
    \begin{definition}
        Suppose $X$ is a topological space and $A\subseteq X$. We say that $A$ is \emph{meagre} in $X$ if $A = \bigcup_{n\in\bN}A_n$, where $A_n$ are nowhere dense subsets of $X$ (i.e. $\Int(\bar{A_n}) = \emptyset$). 
    \end{definition}

    \begin{definition}
        We say that $A$ is \emph{comeagre} in $X$ if it is a complement of a meagre set. Equivalently, a set is comeagre iff it contains a countable intersection of open dense sets.
    \end{definition}
    
    % \begin{example}
    Every countable set is meagre in any $T_1$ space, so, for example, $\bQ$ is meagre in $\bR$ (though being dense), which means that the set of irrationals is comeagre. Another example is...
    % \end{example}

    \begin{definition}
        We say that a topological space $X$ is a \emph{Baire space} if every comeagre subset of $X$ is dense in $X$ (equivalently, every meagre set has empty interior).
    \end{definition}

    \begin{definition}
        Suppose $X$ is a Baire space. We say that a property $P$ \emph{holds generically} for a point in $x\in X$ if $\{x\in X\mid P\textrm{ holds for }x\}$ is comeagre in $X$.
    \end{definition}
    
    \begin{definition}
        Let $X$ be a nonempty topological space and let $A\subseteq X$. The \emph{Banach-Mazur game of $A$}, denoted as $G^{\star\star}(A)$ is defined as follows: Players $I$ and $\textit{II}$ take turns in playing nonempty open sets $U_0, V_0, U_1, V_1,\ldots$ such that $U_0 \supseteq V_0 \supseteq U_1 \supseteq V_1 \supseteq\ldots$. We say that player $\textit{II}$ wins the game if $\bigcap_{n}V_n \subseteq A$.
    \end{definition}

    There is an important theorem on the Banach-Mazur game: $A$ is comeagre
    iff $\textit{II}$ can always choose sets $V_0, V_1, \ldots$ such that it wins. Before we prove it we need to define notions necessary to formalise and prove the theorem.
    
    \begin{definition}
        $T$ is \emph{the tree of all legal positions} in the Banach-Mazur game $G^{\star\star}(A)$ when $T$ consists of all finite sequences $(W_0, W_1,\ldots, W_n)$, where $W_i$ are nonempty open sets such that $W_0\supseteq W_1\supseteq\ldots\supseteq W_n$. In another words, $T$ is a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$. 
    
    \end{definition}
    
    \begin{definition}
        We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal positions $T$ if $\sigma\subseteq T$ and for any $(W_0, W_1, \ldots, W_n)\in\sigma, n\ge 0$ there is a $W$ such that $(W_0, W_1,\ldots, W_n, W)\in\sigma$ (it simply means that there's no finite branch in~$\sigma$). 
    \end{definition}

    \begin{definition}
        Let $\sigma$ be a pruned subtree of the tree of all legal positions $T$. By $[\sigma]$ we denote \emph{the set of all infinite branches of $\sigma$}, i.e. infinite sequences $(W_0, W_1, \ldots)$ such that $(W_0, W_1, \ldots W_n)\in \sigma$ for any $n\in \bN$.
    \end{definition}

    \begin{definition}
        A \emph{strategy} for $\textit{II}$ in $G^{\star\star}(A)$ is a pruned subtree $\sigma\subseteq T$ such that
        \begin{enumerate}[label=(\roman*)]
            \item $\sigma$ is nonempty,
            \item if $(U_0, V_0, \ldots, U_n, V_n)\in\sigma$, then for all open nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, U_n, V_n, U_{n+1})\in\sigma$,
            \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for a unique $V_n$, $(U_0, V_0, \ldots,  U_{n}, V_n)\in\sigma$. 
        \end{enumerate}
    \end{definition}

    Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing $U_0$ as any open subset of $X$, then $\textit{II}$ plays unique (by (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by playing any $U_1\subseteq V_0$ and $\textit{II}$ plays uniqe $V_1$ such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc.

    \begin{definition}
        A strategy $\sigma$ is a \emph{winning strategy for $\textit{II}$} if for any game $(U_0, V_0\ldots)\in [\sigma]$ player $\textit{II}$ wins, i.e. $\bigcap_{n}V_n \subseteq A$.
    \end{definition}

    Now we can state the key theorem.

    \begin{theorem}[Banach-Mazur, Oxtoby]
        \label{theorem:banach_mazur_thm}
        Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is comeagre $\Leftrightarrow$  $\textit{II}$ has a winning strategy in $G^{\star\star}(A)$.
    \end{theorem}

    In order to prove it we add an auxilary definition and lemma.
    \begin{definition}
        Let $S\subseteq\sigma$ be a pruned subtree of tree of all legal positions $T$ and let $p=(U_0, V_0,\ldots, V_n)\in S$. We say that S is \emph{comprehensive for p} if the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ (it may be that $n=-1$, which means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in $V_n$ (where we think that $V_{-1} = X$).

        We say that $S$ is \emph{comprehensive} if it is comprehensive for each $p=(U_0, V_0,\ldots, V_n)\in S$.
    \end{definition}
    
    \begin{fact}
        If $\sigma$ is a winnig strategy for $\mathit{II}$ then there exists a nonempty comprehensive $S\subseteq\sigma$.
    \end{fact}

    \begin{proof}
        We construct $S$ recursively as follows:
        \begin{enumerate}
            \item $\emptyset\in S$,
            \item if $(U_0, V_0, \ldots, U_n)\in S$, then $(U_0, V_0, \ldots, U_n, V_n)\in S$ for the unique $V_n$ given by the strategy $\sigma$,
            \item let $p = (U_0, V_0, \ldots, V_n)\in S$. For a possible player $I$'s move $U_{n+1}\subseteq V_n$ let $U^\star_{n+1}$ be the unique set player $\mathit{II}$ would respond with by $\sigma$. Now, by Zorn's Lemma, let $\cU_p$ be a maximal collection of nonempty open subsets $U_{n+1}\subseteq V_n$ such that the set $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$ is pairwise disjoint. Then put in $S$ all $(U_0, V_0, \ldots, V_{n}, U_{n+1})$ such that $U_{n+1} \in \cU_p$. This way $S$ is comprehensive for $p$: the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ is exactly $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$, which is pairwise disjoint and $\bigcup\cV_p$ is obviously dense in $V_n$ by the maximality of $\cU_p$ -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint from $\bigcup\cV_p$, then $\tilde{U}^{\star}_{n+1}\subseteq \tilde{U}_{n+1}$ would be also disjoint from $\bigcup\cV_p$, so the family $\cU_p\cup\{\tilde{U}_{n+1}\}$ would violate the maximality of $\cU_p$ .
            \qedhere
        \end{enumerate}
    \end{proof}

    \begin{lemma}
        \label{lemma:comprehensive_lemma}
        Let $S$ be a nonempty comprehensive pruned subtree of a strategy $\sigma$. Then:
        \begin{enumerate}[label=(\roman*)]
            \item For any open $V_n\subseteq X$ there is at most one $p=(U_0, V_0, \ldots, U_n, V_n)\in S$.
            \item Let $S_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$ for $n\in\bN$ (i.e. $S_n$ is a family of all possible choices player $\textit{II}$ can make in its $n$-th move according to $S$). Then $\bigcup S_n$ is open and dense in $X$.
            \item $S_n$ is a family of pairwise disjoint sets.
        \end{enumerate}
    \end{lemma}

    \begin{proof}
        (i): Suppose that there are some $p = (U_0, V_0,\ldots, U_n, V_n)$, $p'=(U'_0, V'_0, \ldots, U'_n, V'_n)$ such that $V_n = V'_n$ and $p \neq p'$. Let $k$ be the smallest index such that those sequences differ. We have two possibilities:
        \begin{itemize}
            \item $U_k = U'_k$ and $V_k\neq V'_k$ -- this cannot be true simply by the fact that $S$ is a subset of a strategy (so $V_k$ is unique for $U_k$).
            \item $U_k\neq U'_k$: by the comprehensiveness of $S$ we know that for $q =(U_0, V_0, \ldots, U_{k-1}, V_{k-1})$ the set $\cV_q$ is pairwise disjoint. Thus $V_k\cap V'_k=\emptyset$, because $V_k, V'_k\in \cV_q$. But this leads to a contradiction -- $V_n$ cannot be a nonempty subset of both $V_k, V'_k$.
        \end{itemize}

        (ii): The lemma is proved by induction on $n$. For $n=0$ it follows trivially from the definition of comprehensiveness. Now suppose the lemma is true for $n$. Then the set $\bigcup_{V_n\in S_n}\bigcup\cV_{p_{V_n}}$ (where $p_{V_n}$ is given uniquely from (i)) is dense and open in $X$ by the induction hypothesis. But $\bigcup S_{n+1}$ is exactly this set, thus it is dense and open in $X$.

        (iii): We will prove it by induction on $n$. Once again, the case $n = 0$ follows from the comprehensiveness of $S$. Now suppose that the sets in $S_n$ are pairwise disjoint. Take some $x \in V_{n+1}\in S_{n+1}$. Of course $\bigcup S_n \supseteq \bigcup S_{n+1}$, thus by the inductive hypothesis $x\in V_{n}$ for the unique $V_n\in S_n$. It must be that $V_{n+1}\in \cV_{p_{V_n}}$, because $V_n$ is the only superset of $V_{n+1}$ in $S_n$. But $\cV_{p_{V_n}}$ is disjoint, so there is no other $V'_{n+1}\in \cV_{p_{V_n}}$ suc h that $x\in V'_{n+1}$. Moreover, there is no such set in $S_{n+1}\setminus\cV_{p_{V_n}}$, because those sets are disjoint from $V_{n}$. Hence there is no $V'_{n+1}\in S_{n+1}$ other than $V_n$ such that $x\in V'_{n+1}$. We chosed $x$ and $V_{n+1}$ arbitrarily, so $S_{n+1}$ is pairwise disjoint.
    \end{proof}

    Now we can move to the proof of the Banach-Mazur theorem.

    \begin{proof}[Proof of theorem \ref{theorem:banach_mazur_thm}]
        $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with $\bigcap_n A_n\subseteq A$. The simply $\textit{II}$ plays $V_n = U_n\cap A_n$, which is nonempty by the denseness of $A_n$.

        $\Leftarrow$: Suppose $\textit{II}$ has a winning strategy $\sigma$. We will show that $A$ is comeagre. Take a comprehensive $S\subseteq \sigma$. We claim that $\mathcal{S} = \bigcap_n\bigcup S_n \subseteq A$. By the lemma~\ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup S_n$ are open and dense, thus $A$ must be comeagre. Now we prove the claim towards contradiction. 
        
        Suppose there is $x\in \mathcal{S}\setminus A$. By the lemma \ref{lemma:comprehensive_lemma}, (iii) for any $n$ there is unique $x\in V_n\in S_n$. It follows that $p_{V_0}\subset p_{V_1}\subset\ldots$. Now the game $(U_0, V_0, U_1, V_1,\ldots) = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ is not winning for player $\textit{II}$, which contradicts the assumption that $\sigma$ is a winning strategy.
    \end{proof}

    % Pytania:
    % \begin{itemize}
    %     \item Czy da się coś zrobić, żeby $\mathcal{V}$ nie było takie brzydkie?
    %     \item Jak to napisać, że się zrzyna z książki?
    %     \item Dodatkowy przykład pod def 2.2
    %     \item DONE W/E $G^{\star\star}(A)$ czy $G^{**}(A)$? Czy może $G^{**}(X, A)?$ Jakiś skrót na to?
    %     \item w \ref{lemma:comprehensive_lemma} (i), jak to ładniej sformułować?
    %     \item w \ref{lemma:comprehensive_lemma} (iii), może to wyodrębnić? Może to dać jako pierwsze, a pierwsze dwa później?
    %     \item DONE dodać tytuł do \ref{theorem:banach_mazur_thm}
    %     \item czy w dowodzie twierdzenia napisać jeszcze raz co to jest $W_n$?
    %     \item DONE TAK ostatni akapit dowodu twierdzenia, czy taka suma tych $p_{V_n}$ to jest sensowny napis? Jak to inaczej napisać?
    % \end{itemize}

    % Odpowiedzi:
    % \begin{itemize}
    %     % \item dodać osobną definicję na $[\sigma]$ (tzn dla dowolnego poddrzewa).
    %     \item $II$ -> $\mathit{II}$
    %     \item w ogóle dodać def poddrzewa (co to znaczy pruned?)
    %     \item w \ref{lemma:comprehensive_lemma} (i) zmienić na "dla każdego otwartego podzbioru X jest co najwyżej jedno takie p"
    %     \item powiedzieć że S musi być niepuste
    %     \item w \ref{lemma:comprehensive_lemma} zamienić kolejność w pierwszym zdaniu gwiazdki z nie-gwiazdką
    %     \item zmienić $W_n -> S_n$
    %     \item rozwinąć \ref{lemma:comprehensive_lemma} (ii), poza tym $W_{n+1}$ jest dokładnie równy, a nie tylko superset, dodać kwantyfikator na n, a może wplecić jeszcze to że te rodziny $W_n$ też są rozłączne?
    % \end{itemize}

    \begin{corollary}
        \label{corollary:banach-mazur-basis}
        If we add a constraint to the Banach-Mazur game such that players can only choose basic open sets, then the theorem \ref{theorem:banach_mazur_thm} still suffices.
    \end{corollary}

    \begin{proof}
        If one adds the word \textit{basic} before each occurance of word \textit{open} in previous proofs and theorems then they all will still be valid (except for $\Rightarrow$, but its an easy fix -- take $V_n$ a basic open subset of $U_n\cap A_n$).  
    \end{proof}

    This corollary will be important in using the theorem in practice -- it's much easier to work with basic open sets rather than any open sets.

    \subsection{Fraïssé classes}
    \begin{fact}[Fraïssé theorem]
        \label{fact:fraisse_thm}
        % Suppose $\cC$ is a class of finitely generated $L$-structures such that...

        Then there exists a unique up to isomorphism countable $L$-structure $M$ such that...
    \end{fact}

    \begin{definition}
        For $\cC$, $M$ as in Fact~\ref{fact:fraisse_thm}, we write $\Flim(\cC)\coloneqq M$.
    \end{definition}

    \begin{fact}
        If $\cC$ is a uniformly locally finite Fraïssé class, then $\Flim(\cC)$ is $\aleph_0$-categorical and has quantifier elimination.
    \end{fact}

    \section{Conjugacy classes in automorphism groups}

    \subsection{Prototype: pure set}
    In this section, $M=(M,=)$ is an infinite countable set (with no structure beyond equality).
    \begin{proposition}
        If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are conjugate if and only if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$ and $f_2$ have the same number of orbits of size $n$.
    \end{proposition}

    \begin{proposition}
        The conjugacy class of $f\in \Aut(M)$ is dense if and only if...
    \end{proposition}
    \begin{proposition}
        If $f\in \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is meagre.
    \end{proposition}

    \begin{proposition}
        An automorphism $f$ of $M$ is generic if and only if...
    \end{proposition}

    \begin{proof}

    \end{proof}

    \subsection{More general structures}


    \begin{proposition}
        Suppose $M$ is an arbitrary structure and $f_1,f_2\in \Aut(M)$. Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong (M,f_2)$.
    \end{proposition}

    \begin{definition}
        We say that a Fraïssé class $\cC$ has \emph{weak Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and partial automorphism $p\colon A\to A$, there is some $B\in \cC$ such that $p$ can be extended to an automorphism of $B$, i.e.\ there is an embedding $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following diagram commutes:
        \begin{center}
            \begin{tikzcd}
                B\ar[r,"\bar p"]&B\\
                A\ar[u,"i"]\ar[r,"p"]&A\ar[u,"i"]
            \end{tikzcd}
        \end{center}
    \end{definition}

    \begin{proposition}
        Suppose $\cC$ is a Fraïssé class in a relational language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$, all orbits of $f$ are finite.
    \end{proposition}
    \begin{proposition}
        Suppose $\cC$ is a Fraïssé class in an arbitrary countable language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$ ...
    \end{proposition}

    \subsection{Random graph}
    \begin{definition}
        The \emph{random graph} is...
    \end{definition}

    \begin{fact}
        The
    \end{fact}

    \begin{proposition}
        Generically, the set of fixed points of $f\in \Aut(M)$ is isomorphic to $M$ (as a graph).
    \end{proposition}

\end{document}