From 5e47a4972076f718dcb1f0766fa7bb8016f8056d Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Thu, 21 Apr 2022 01:23:51 +0200 Subject: Aspell --- lic_malinka.pdf | Bin 386819 -> 386727 bytes lic_malinka.tex | 86 ++++++++++++++++++++++++++++---------------------------- 2 files changed, 43 insertions(+), 43 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 5c50fff..2bd9a82 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/lic_malinka.tex b/lic_malinka.tex index 85541cf..e1a45b3 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -122,7 +122,7 @@ \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 + a complement of a meagre set. Equivalently, a set is comeagre if and only if it contains a countable intersection of open dense sets. \end{definition} @@ -154,7 +154,7 @@ \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 + if and only if $\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. @@ -196,7 +196,7 @@ 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$ + playing any $U_1\subseteq V_0$ and $\textit{II}$ plays unique $V_1$ such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc. \begin{definition} @@ -214,7 +214,7 @@ $G^{\star\star}(A)$. \end{theorem} - In order to prove it we add an auxilary definition and lemma. + In order to prove it we add an auxiliary 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 @@ -227,7 +227,7 @@ \end{definition} \begin{fact} - If $\sigma$ is a winnig strategy for $\mathit{II}$ then + If $\sigma$ is a winning strategy for $\mathit{II}$ then there exists a nonempty comprehensive $S\subseteq\sigma$. \end{fact} @@ -360,7 +360,7 @@ \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 class $\bK$ of all finitely generated structures that embeds into $M$. The age of $M$ is also associated with class of all structures embeddable in $M$ \emph{up to isomorphism}. \end{definition} @@ -411,8 +411,8 @@ \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 + Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogeneous} if every + isomorphism between finitely generated substructures of $M$ extends to an automorphism of $M$. \end{definition} @@ -422,7 +422,7 @@ \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 + the age of a countable, ultrahomogeneous $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} @@ -432,7 +432,7 @@ 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 + We say that an $L$-structure $M$ is \emph{weakly ultrahomogeneous} 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$. @@ -446,8 +446,8 @@ \begin{lemma} \label{lemma:weak_ultrahom} - A countable structure is ultrahomogenous if and only if it is weakly - ultrahomogenous. + A countable structure is ultrahomogeneous if and only if it is weakly + ultrahomogeneous. \end{lemma} This lemma will play a major role in the later parts of the paper. Weak @@ -486,7 +486,7 @@ The concept of the random graph emerges independently in many fields of mathematics. For example, one can construct the graph by choosing at random - for each pair of verticies if they should be connected or not. It turns out + for each pair of vertices if they should be connected or not. It turns out that the graph constructed this way is exactly the random graph we described above. @@ -501,38 +501,38 @@ Take any finite disjoint $X, Y\subseteq\FrGr$. Let $G_{XY}$ be the subgraph of $\FrGr$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$, where $w$ is a new vertex that does not appear in $G_{XY}$. Also, $w$ is connected to - all verticies of $G_{XY}$ that come from $X$ and to none of those that come + all vertices of $G_{XY}$ that come from $X$ and to none of those that come from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$. - Wihtout loss of generality assume that this embedding is simply inclusion. + Without loss of generality assume that this embedding is simply inclusion. Let $f$ be the partial isomorphism from $X\sqcup Y$ to $H$, with $X$ and $Y$ projected to the part of $H$ that come from $X$ and $Y$ respectively. - By the ultrahomogeneity of $\FrGr$ this isomoprhism extends to an automorphism + By the ultrahomogeneity of $\FrGr$ this isomorphism extends to an automorphism $\sigma\in\Aut(\FrGr)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. \end{proof} \begin{fact} If a countable graph $G$ has the random graph property, then it is - isomorhpic to the random graph $\FrGr$. + isomorphic to the random graph $\FrGr$. \end{fact} \begin{proof} - Enumerate verticies of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G + Enumerate vertices of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G = \{b_1, b_2\ldots\}$. We will construct a chain of partial isomorphisms $f_n\colon \FrGr\to G$ such that $\emptyset = f_0\subseteq f_1\subseteq f_2\subseteq\ldots$ and $a_n \in \dom(f_n)$ and $b_n\in\rng(f_n)$. Suppose we have $f_n$. We seek $b\in G$ such that $f_n\cup \{\langle - a_{n+1}, b\rangle\}$ is a partial isomoprhism. Let $X = \{a\in\FrGr\mid + a_{n+1}, b\rangle\}$ is a partial isomorphism. Let $X = \{a\in\FrGr\mid aE_{\FrGr} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are - verticies of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and - $Y$ are those verticies that are not connected with $a_{n+1}$. Let $b$ be - a vertex of $G$ that is connected to all verticies of $f_n[X]$ and to none + vertices of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and + $Y$ are those vertices that are not connected with $a_{n+1}$. Let $b$ be + a vertex of $G$ that is connected to all vertices of $f_n[X]$ and to none $f_n[Y]$ (it exists by the random graph property). Then $f_n\cup \{\langle - a_{n+1}, b\rangle\}$ is a partial isomoprhism. We find $a$ for the + a_{n+1}, b\rangle\}$ is a partial isomorphism. We find $a$ for the $b_{n+1}$ in the similar manner, so that $f_{n+1} = f_n\cup \{\langle a_{n+1}, b\rangle, \langle a, b_{n+1}\rangle\}$ is a partial isomorphism. - $f = \bigcup^{\infty}_{n=0}f_n$ is an isomoprhism between $\FrGr$ + $f = \bigcup^{\infty}_{n=0}f_n$ is an isomorphism between $\FrGr$ and $G$. Take any $a, b\in \FrGr$. Then for some big enough $n$ we have that $aE_{\FrGr}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$ . \end{proof} @@ -576,10 +576,10 @@ a Fraïssé class. \end{proposition} \begin{proof} - Countability and HP are obivous, JEP follows by the same argument as in + Countability and HP are obvious, JEP follows by the same argument as in plain graphs. We need to show that the class has the amalgamation property. - Take any graphs $(A, \alpha), (B, \beta), (C,\gamma)$ such that $A$ embedds + Take any graphs $(A, \alpha), (B, \beta), (C,\gamma)$ such that $A$ embeds into $B$ and $C$. Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in the proof for the plain graphs. We will define the automorphism $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. (TODO: chyba nie @@ -619,9 +619,9 @@ Let $G_{XY}$ be the graph induced by $X\cup Y$. Take $H=G_{XY}\sqcup {v}$ as a supergraph of $G_{XY}$ with one new vertex $v$ connected to all - verticies of $X$ and to none of $Y$. By the proposition + vertices of $X$ and to none of $Y$. By the proposition \ref{proposition:finite-graphs-whp} we can extend $H$ together with its - partial isomoprhism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with + partial isomorphism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with automorphism $\tau$. Once again, without the loss of generality we can assume that $R\subseteq\FrAut$, because $\cH$ is the age of $\FrAut$. But $R\upharpoonright_{G_{XY}}$ together with $\tau\upharpoonright_{G_{XY}}$ @@ -629,7 +629,7 @@ Thus, by ultrahomogeneity of $\FrAut$ this isomorphism extends to an automorphism $\theta$ of $(\FrAut, \sigma)$. Then $\theta(v)$ is the vertex - that is connected to all verticies of $X$ and none of $Y$, because + that is connected to all vertices of $X$ and none of $Y$, because $\theta[R\upharpoonright_X] = X, \theta[R\upharpoonright_Y] = Y$. \end{proof} @@ -712,7 +712,7 @@ player \textit{I} picks functions $f_0, f_1,\ldots$ and player \textit{II} chooses $g_0, g_1,\ldots$ such that $f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify - the coresponding basic open subsets $B_{f_0}\supseteq B_{g_0}\supseteq\ldots$. + the corresponding basic open subsets $B_{f_0}\supseteq B_{g_0}\supseteq\ldots$. Our goal is to choose $g_i$ in such a manner that the resulting function $g = \bigcap^{\infty}_{i=0}g_i$ will be an automorphism of the random graph @@ -721,28 +721,28 @@ By the Fraïssé theorem \ref{theorem:fraisse_thm} it will follow that $(\FrGr, g)\cong (\FrAut, \sigma)$. By the proposition \ref{proposition:graph-aut-is-normal} we can assume without - the loss of generatlity that $\FrAut = \FrGr$ as a plain graph. Hence, + the loss of generality that $\FrAut = \FrGr$ as a plain graph. Hence, by the fact \ref{fact:conjugacy}, $g$ and $\sigma$ conjugate in $G$. Once again, by the Fraïssé theorem \ref{theorem:fraisse_thm} and the \ref{lemma:weak_ultrahom} lemma constructing $g_i$'s in a way such that - age of $(\FrGr, g)$ is exactly $\cH$ and so that it is weakly ultrahomogenous + age of $(\FrGr, g)$ is exactly $\cH$ and so that it is weakly ultrahomogeneous will produce expected result. First, let us enumerate all pairs of finite graphs with automorphism $\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN}$ - such that the first element of the pair embedds by inclusion in the second, + such that the first element of the pair embeds by inclusion in the second, i.e. $(A_n, \alpha_n)\subseteq (B_n, \beta_n)$. Also, it may be that - $A_n$ is an empty graph. We enumerate the verticies of the random graph + $A_n$ is an empty graph. We enumerate the vertices of the random graph $\FrGr = \{v_0, v_1, \ldots\}$. Fix a bijection $\gamma\colon\bN\times\bN\to\bN$ such that for any - $n, m\in\bN$ we have $\gamma(n, m) \ge n$. This bijection naturaly induces + $n, m\in\bN$ we have $\gamma(n, m) \ge n$. This bijection naturally induces a well ordering on $\bN\times\bN$. This will prove useful later, as the main argument of the proof will be constructed as a bookkeeping argument. Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$ and $X_{-1} = \emptyset$. Suppose that player \textit{I} in the $n$-th move chooses a finite partial - isomoprhism $f_n$. We will construct $g_n\supseteq f_n$ and a set $X_n\subseteq\bN^2$ + isomorphism $f_n$. We will construct $g_n\supseteq f_n$ and a set $X_n\subseteq\bN^2$ such that following properties hold: \begin{enumerate}[label=(\roman*)] @@ -757,7 +757,7 @@ is the graph induced by $g_{n-1}$). Let $(i, j) = \min\{(\{0, 1, \ldots\} \times \bN) \setminus X_{n-1}\}$ (with the order induced by $\gamma$). Then $X_n = X_{n-1}\cup\{(i,j)\}$ and - $(B_{n,k}, \beta_{n,k})$ embedds in $(\FrGr_n, g_n)$ so that this diagram + $(B_{n,k}, \beta_{n,k})$ embeds in $(\FrGr_n, g_n)$ so that this diagram commutes: \begin{center} @@ -768,7 +768,7 @@ \end{center} \end{enumerate} - First item makes sure that no inifite orbit will not be present in $g$. The + First item makes sure that no infinite orbit will not be present in $g$. The second item together with the first one are necessary for $g$ to be an automorphism of $\FrGr$. The third item is the one that gives weak ultrahomogeneity. Now we will show that indeed such $g_n$ may be constructed. @@ -778,7 +778,7 @@ $(B_{i,j}, \beta_{i,j})$ to $(\FrGr'_n, g'_n)$. Without the loss of generality we may assume that $f_{i,j}$ is an inclusion and that $A_{i,j} = B_{i,j}\cap\FrGr_{n-1}$. Then let $\FrGr'_n = B_{i,j}\cup\FrGr_{n-1}$ and $g'_n = g_{n-1}\cup \beta_{i,j}$. - Then $(B_{i,j}, \beta_{i,j})$ simply embedds by inclusion in $(\FrGr'_n, g'_n)$, + Then $(B_{i,j}, \beta_{i,j})$ simply embeds by inclusion in $(\FrGr'_n, g'_n)$, i.e. this diagram commutes: \begin{center} @@ -792,9 +792,9 @@ proof of the amalgamation property of $\cH$. It may be also assumed without the loss of generality that $\FrGr'_n\subseteq \FrGr$. - Of course by the recurisve assumption $\FrGr_{n-1}\subseteq\FrGr$. The + Of course by the recursive assumption $\FrGr_{n-1}\subseteq\FrGr$. The $\FrGr'_n \setminus\FrGr_{n-1} = B_{i,j}\setminus A_{i,j}$ can be found in - $\FrGr$ by the random graph property -- we can find verticies of the remaining + $\FrGr$ by the random graph property -- we can find vertices of the remaining part of $B_{i,j}$ each at a time so that all edges are correct. Now, by the WHP of $\bK$ we can extend the graph $\FrGr'_n\cup\{v_n\}$ together @@ -811,9 +811,9 @@ Take any finite graph with automorphism $(B, \beta)$. Then, there are $i, j$ such that $(B, \beta) = (B_{i, j}, \beta_{i,j})$ and $A_{i,j}=\emptyset$. By the bookkeeping there was $n$ such that $(i, j) = \min\{\{0,1,\ldots\}\times\bN\setminus X_{n-1}\}$. - This means that $(B, \beta)$ embedds into $(\FrGr_n, g_n)$, hence it embedds + This means that $(B, \beta)$ embeds into $(\FrGr_n, g_n)$, hence it embeds into $(\FrGr, g)$. With a similar argument we can see that $(\FrGr, g)$ is - weakly ultrahomogenous. + weakly ultrahomogeneous. By this we know that $g$ and $\sigma$ conjugate in $G$. As we stated in the beginning of the proof, the set of possible outcomes of the game (i.e. -- cgit v1.2.3