From e79d66fdd62e06bff773562daa7c29c1cba91bcc Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sat, 19 Mar 2022 21:02:59 +0100 Subject: Definicje wkolo freissego --- lic_malinka.pdf | Bin 317628 -> 345258 bytes lic_malinka.tex | 750 ++++++++++++++++++++++++++++++++++---------------------- licmalinka.bib | 10 + update-pdf.sh | 24 ++ 4 files changed, 494 insertions(+), 290 deletions(-) create mode 100644 licmalinka.bib create mode 100644 update-pdf.sh diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 45f4de6..5663434 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/lic_malinka.tex b/lic_malinka.tex index 62d1f7b..0dde9cd 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -1,96 +1,88 @@ -\documentclass[11pt, a4paper, final]{amsart} -\setlength{\emergencystretch}{2em} +\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em} +\usepackage[backend=biber]{biblatex} +\addbibresource{licmalinka.bib} -\usepackage[T1]{fontenc} -\usepackage{mathtools} + +\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{amsfonts} +\usepackage{amsmath} \usepackage{amssymb} -\usepackage{amsthm} -\usepackage{XCharter} -\usepackage[charter,expert, greekuppercase=italicized, greekfamily=didot]{mathdesign} -\usepackage{mathtools} -\usepackage{enumitem} +\usepackage{amsthm} +\usepackage{XCharter} +\usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign} +\usepackage{mathtools} +\usepackage{enumitem} \usepackage[utf8]{inputenc} -\usepackage{tikz-cd} +\usepackage{tikz-cd} \usepackage{tikz} +\usetikzlibrary{arrows,arrows.meta} +\tikzcdset{arrow style=tikz, diagrams={>=latex}} -\usepackage{etoolbox} +\usepackage{etoolbox} -\usepackage{xcolor} +\usepackage{xcolor} \definecolor{green}{RGB}{0,127,0} -\definecolor{redd}{RGB}{191,0,0} +\definecolor{redd}{RGB}{191,0,0} + \definecolor{red}{RGB}{105,89,205} \usepackage[colorlinks=true]{hyperref} -\usepackage[notref, notcite]{showkeys} +\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{\Aut}{Aut} \DeclareMathOperator{\Hom}{Hom} -\DeclareMathOperator{\Stab}{Stab} +\DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\st}{st} -\DeclareMathOperator{\Flim}{FLim} +\DeclareMathOperator{\Flim}{FLim} \DeclareMathOperator{\Int}{{Int}} -\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} -\newcommand{\cC}{\mathcal C} -\newcommand{\cV}{\mathcal{V}} +\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} +\newcommand{\cC}{\mathcal C} +\newcommand{\cV}{\mathcal{V}} \newcommand{\cU}{\mathcal{U}} -\newcommand{\bN}{\mathbb N} +\newcommand{\bN}{\mathbb N} \newcommand{\bR}{\mathbb R} -\newcommand{\bZ}{\mathbb Z} +\newcommand{\bZ}{\mathbb Z} \newcommand{\bQ}{\mathbb Q} +\newcommand{\bK}{\mathbb K} -\DeclareMathOperator{\im}{{Im}} +\DeclareMathOperator{\im}{{Im}} \DeclareMathOperator{\lin}{{Lin}} \DeclareMathOperator{\Th}{{Th}} -\newtheorem{theorem}{Theorem} +\newtheorem{theorem}{Theorem} \numberwithin{theorem}{section} -\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} -\newtheorem{fact}[theorem]{Fact} +\newtheorem{fact}[theorem]{Fact} \newtheorem{proposition}[theorem]{Proposition} -\newtheorem{conjecture}[theorem]{Conjecture} +\newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{question}[theorem]{Question} -\newtheorem{corollary}[theorem]{Corollary} +\newtheorem{corollary}[theorem]{Corollary} \newtheorem*{theorem2}{Theorem} -\newtheorem*{claim2}{Claim} +\newtheorem*{claim2}{Claim} \newtheorem*{corollary2}{Corollary} -\newtheorem*{question2}{Question} +\newtheorem*{question2}{Question} \newtheorem*{conjecture2}{Conjecture} -\newtheorem{clm}{Claim} -\newtheorem*{clm*}{Claim} +\newtheorem{clm}{Claim} \newtheorem*{clm*}{Claim} -\theoremstyle{definition} +\theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} -\newtheorem*{definition2}{Definition} +\newtheorem*{definition2}{Definition} \newtheorem{example}[theorem]{Example} -\theoremstyle{remark} +\theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem*{remark2}{Remark} @@ -98,248 +90,426 @@ \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}}} +\newcommand{\xqed}[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill + \quad\hbox{\ensuremath{#1}}} -\title{Tytuł} +\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} \ No newline at end of file + \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've chosen $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} + + \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 occurrence + 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. + + \section{Fraïssé classes} + + In this section we will take a closer look at classes of finitely + generated structures with some characteristic properties. More + specifically, we will describe a concept developed by a French + mathematician Roland Fraïssé called Fraïssé limit. + + \subsection{Definitions} + \begin{definition} + Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is + the class $\bK$ of all finitely generated structures that embedds into $M$. + The age of $M$ is also associated with class of all structures embeddable in + $M$ \emph{up to isomorphism}. + \end{definition} + + \begin{definition} + We say that $M$ has \emph{countable age} when its age has countably many + isomorphism types of finitely generated structures. + \end{definition} + + \begin{definition} + Let $\bK$ be a class of finitely generated structures. $\bK$ has + \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated + substructure $B$ of $A$ it holds that $B\in\bK$. + \end{definition} + + \begin{definition} + Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has + \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a + structure $C\in\bK$ such that both $A$ and $B$ embed in $C$. + \end{definition} + + Fraïssé has shown fundamental theories regarding age of a structure, one of + them being the following one: + + \begin{fact} + \label{fact:age_is_hpjep} + Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set + of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if + and only if $\bK$ is the age of some finite or countable structure. + \end{fact} + + Beside the HP and JEP Fraïssé has distinguished one more property of the + class $\bK$, namely amalgamation property. + + \begin{definition} + Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$ + has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and + embeddings $f\colon A\to B, g\colon A\to C$ there exists $D\in\bK$ together + with embeddings $h\colon B\to D$ and $j\colon C\to D$ such that + $h\circ f = j\circ g$. + \begin{center} + \begin{tikzcd} + & D & \\ + B \arrow[ur, dashed, "h"] & & C \arrow[ul, dashed, "j"'] \\ + & A \arrow[ur, "g"'] \arrow[ul, "f"] + \end{tikzcd} + \end{center} + \end{definition} + + \begin{definition} + Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogenous} if every + isomorphism between finitely generated substrucutres of $M$ extends to an + automorphism of $M$. + \end{definition} + + Having those definitions we can provide the main Fraïssé theorem. + + \begin{theorem}[Fraïssé theorem] + \label{theorem:fraisse_thm} + Let L be a countable language and let $\bK$ be a nonempty countable set of + finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is + the age of a countable, ultrahomogenous $L$-structure $M$. Moreover, $M$ is + unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$ + and denote this by $M = \Flim(\bK)$. + \end{theorem} + + This is a well known theorem. One can read a proof of this theorem in Wilfrid + Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof + of this theorem appears another, equally important \ref{lemma:weak_ultrahom}. + + \begin{definition} + We say that an $L$-structure $M$ is \emph{weakly ultrahomogenous} if for any + $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and + an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which + extends $f$. + \begin{center} + \begin{tikzcd} + A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\ + B \arrow[ur, dashed, "g"'] + \end{tikzcd} + \end{center} + \end{definition} + + \begin{lemma} + \label{lemma:weak_ultrahom} + A countable structure is ultrahomogenous if and only if it is weakly + ultrahomogenous. + \end{lemma} + + This lemma will play a major role in the later parts of the paper. Weak + ultrahomogenity is an easier and more intuitive property and it will prove + useful when recursively constructing the generic automorphism of a Fraïssé + limit. + + + % \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} + \printbibliography +\end{document} diff --git a/licmalinka.bib b/licmalinka.bib new file mode 100644 index 0000000..4c4c881 --- /dev/null +++ b/licmalinka.bib @@ -0,0 +1,10 @@ +@book{hodges_1993, + place={Cambridge}, + series={Encyclopedia of Mathematics and its Applications}, + title={Model Theory}, + DOI={10.1017/CBO9780511551574}, + publisher={Cambridge University Press}, + author={Hodges, Wilfrid}, + year={1993}, + collection={Encyclopedia of Mathematics and its Applications} +} \ No newline at end of file diff --git a/update-pdf.sh b/update-pdf.sh new file mode 100644 index 0000000..8d1534a --- /dev/null +++ b/update-pdf.sh @@ -0,0 +1,24 @@ +if [[ $# != 1 ]] +then + echo "Usage: $0 [.tex file]" + exit 1 +fi + +PRACA=$1 +if ! [[ -f $PRACA ]] +then + echo "No such file: $PRACA" + exit 1 +fi + +threshold=1 +while true +do + if (($(date +"%s")- $(stat --format="%Y" $PRACA) < $threshold)) + then + echo "updating" + pdflatex $PRACA + else + sleep 0.2 + fi +done -- cgit v1.2.3