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 nowhere dense 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 $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 $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 $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}\}$. 
    
        By $[T]$ we denote the set of all "infinite branches" of $T$, i.e. infinite sequences $(U_0, V_0, \ldots)$ such that $(U_0, V_0, \ldots U_n, V_n)\in T$ for any $n\in \bN$.
    \end{definition}

    \begin{definition}
        A \emph{strategy} for $II$ in $G^{\star\star}(A)$ is a subtree $\sigma\subseteq T$ such that
        \begin{enumerate}[label=(\roman*)]
            \item $\sigma$ is nonempty,
            \item if $(U_0, V_0, \ldots, V_n)\in\sigma$, then for all open nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, V_n, U_{n+1})\in\sigma$,
            \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for 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 $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 $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 $II$} if for any game $(U_0, V_0\ldots)\in [\sigma]$ (where $[\sigma]$ is defined analogically to $[T]$) player $II$ wins, i.e. $\bigcap_{n}V_n \subseteq A$.
    \end{definition}

    Now we can state the key theorem.

    \begin{theorem}
        \label{theorem:banach_mazur_thm}
        Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is comeagre $\Leftrightarrow$  $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$ be a pruned subtree of a strategy $\sigma$ 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 any $p=(U_0, V_0,\ldots, V_n)\in S$.
    \end{definition}
    
    \begin{lemma}
        \label{lemma:comprehensive_lemma}
        Let $S$ be a comprehensive pruned subtree of a strategy $\sigma$. Then:
        \begin{enumerate}[label=(\roman*)]
            \item For any $V_n$ such that there is $p=(U_0, V_0, \ldots, V_n)\in S$, this $p$ is unique.
            \item Let $W_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$, i.e. $W_n$ is a family of all possible choices player $II$ can make in its $n$-th move. Then $\bigcup W_n$ is open and dense in $X$. 
            \item There exists such $S$.
        \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 W_n}\bigcup\cV_{p_{V_n}}$ ($p_{V_n}$ is given uniquely from (i)) is dense and open in $X$ by the induction hypothesis. But $\bigcup W_{n+1}$ is its superset, thus $\bigcup W_{n+1}$ is dense and open in $X$.

        (iii): 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$, let $U^\star_{n+1}$ be the unique set player $II$ would play by $\sigma$ given that player $I$ played $U_{n+1}\subseteq V_n$. 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 it's maximality -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint from $\bigcup\cU_p$, then the family $\cU_p\cup\{\tilde{U}_{n+1}\}$ violates the maximality of $\cU_p$.
        \end{enumerate}
    \end{proof}

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

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

        $\Leftarrow$: Suppose $II$ has a winning strategy $\sigma$. We will show that $A$ is comeagre. Take a comprehensive $S\subseteq \sigma$. We claim that $\mathcal{W} = \bigcap_n\bigcup W_n \subseteq A$. By \ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup W_n$ are open and dense, thus $A$ must be comeagre. Now we prove the claim. 
        
        (A.a.) Suppose there is $x\in \mathcal{W}$ that is not in $A$. We will prove by induction that for any $n$ there is exactly one $V_n\in W_n$ such that $x\in V_n$. For $n = 0$ this follows trivially by the comprehensiveness of $S$. Now suppose that there is exactly one $V_n\in W_n$ such that $x\in V_n$. By our assumption there is a $V'_{n+1}\in W_{n+1}$ such that $x\in V'_{n+1}$. By \ref{lemma:comprehensive_lemma} we have unique $p_{V'_{n+1}}=(U'_0, V'_0, \ldots, V'_{n+1})\in S$. It must be that $x\in V'_n$, so by the induction hypothesis $V'_n = V_n$, thus $V'_{n+1}\in \cV_{p_{V_{n}}}$. But the family $\cV_{p_{V_{n}}}$ is disjoint, hence $V_{n+1} = V'_{n+1}$ is unique.

        Now the game $(U_0, V_0, U_1, V_1,\ldots) = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ where $x\in V_0, V_1,\ldots$ is not winning for player $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 $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 dodać tytuł do \ref{theorem:banach_mazur_thm}
        \item czy w dowodzie twierdzenia napisać jeszcze raz co to jest $W_n$?
        \item ostatni akapit dowodu twierdzenia, czy taka suma tych $p_{V_n}$ to jest sensowny napis? Jak to inaczej napisać?
    \end{itemize}

    \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 counable $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}