aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2022-07-17 14:16:41 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2022-07-17 14:16:41 +0200
commit2b830cb2d9c2237fcb7809bab7c64966098ea6fb (patch)
tree08948249884fbb75fb0a1424cacf0a05e57d56ad
parentae1c456f6467a50427fc485ec5ae163495ea0e52 (diff)
Oby ostatnie poprawki
-rw-r--r--lic_malinka.pdfbin483781 -> 480986 bytes
-rw-r--r--licmalinka.bib10
-rw-r--r--sections/conj_classes.tex72
-rw-r--r--sections/fraisse_classes.tex11
-rw-r--r--sections/introduction-pl.tex4
-rw-r--r--sections/introduction.tex6
-rw-r--r--sections/preliminaries.tex1
7 files changed, 32 insertions, 72 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf
index 0529e44..6354005 100644
--- a/lic_malinka.pdf
+++ b/lic_malinka.pdf
Binary files differ
diff --git a/licmalinka.bib b/licmalinka.bib
index 6c1237c..26dd13f 100644
--- a/licmalinka.bib
+++ b/licmalinka.bib
@@ -53,13 +53,14 @@
year = {2007}
},
@article{extending_iso_graphs,
- title={http://math.univ-lyon1.fr/~milliet/grapheanglais.pdf},
+ title={Extending partial isomorphisms of finite graphs},
url={http://math.univ-lyon1.fr/~milliet/grapheanglais.pdf},
author={Cédric Milliet},
year={2004}
},
@article{hrushovski_extending_iso,
author={Ehud Hrushovski},
+ title={Extending partial isomorphisms of graphs},
year={1992},
journal={Combinatorica},
volume={12},
@@ -68,13 +69,6 @@
},
@book{siniora2017automorphism,
title={Automorphism Groups of Homogeneous Structures},
- author={Siniora, D.N.},
- url={https://books.google.pl/books?id=-qiZtAEACAAJ},
- year={2017},
- publisher={University of Leeds (Department of Pure Mathematics)}
-}
-@book{siniora2017automorphism,
- title={Automorphism Groups of Homogeneous Structures},
author={Daoud Nasri Siniora},
url={https://core.ac.uk/download/pdf/83934818.pdf},
year={2017},
diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex
index c0120d3..9ec4b0c 100644
--- a/sections/conj_classes.tex
+++ b/sections/conj_classes.tex
@@ -46,7 +46,7 @@
$\Aut(M)$: take any finite $\gamma\colon M\to M$ such that $[\gamma]_{\Aut(M)}$
is nonempty. Then also
$\bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}\cap[\gamma]_{\Aut(M)}\neq\emptyset$,
- one can easily construct a permutation that extends $\gamma$ and have at least
+ one can easily construct a permutation that extends $\gamma$ and has at least
$k$ many $n$-cycles.
Now we see that $A = \bigcap_{n=1}^{\infty} A_n$ is a comeagre set consisting
@@ -97,21 +97,21 @@
generated by $\dom(g)$ and $\rng(g)$ respectively. Of course, in our
case, $g$ is good
if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (because of ultrahomogeneity
- of $\Gamma$.
+ of $\Gamma$).
Also it is important to mention that an isomorphism between two finitely
generated structures is uniquely given by a map from generators of one structure
to the other. This allow us to treat a finite function as an isomorphism
- of finitely generated structure.
+ of finitely generated structures.
\begin{proof}
Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. First, by the Theorem
\ref{theorem:isomorphic_fr_lims}, we may assume without the loss of generality
that $\Pi = \Gamma$. Let $G = \Aut(\Gamma)$,
i.e. $G$ is the automorphism group of $\Gamma$.
- We will construct a strategy for the second player in the Banach-Mazur game
- on the topological space $G$. This strategy will give us a subset
- $A\subseteq G$ and as we will see a subset of the $\sigma$'s conjugacy class.
+ We will construct a winning strategy for the second player in the Banach-Mazur game
+ (see \ref{definition:banach-mazur-game})
+ on the topological space $G$ with $A$ being $\sigma$'s conjugacy class.
By the Banach-Mazur theorem (see \ref{theorem:banach_mazur_thm}) this will prove
that this class is comeagre.
@@ -129,15 +129,6 @@
chooses $g_0, g_1,\ldots$ such that
$f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify
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 Fraïssé limit
- % $\Gamma$ such that $(\Gamma, g) = \Flim{\cD}$.
- % Precisely, we will find $g_i$'s such that
- % $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$ and by
- % the Fraïssé theorem \ref{theorem:fraisse_thm}
- % it will follow that $(\Gamma, g)\cong (\Pi, \sigma)$. Hence,
- % by the fact \ref{fact:conjugacy}, $g$ and $\sigma$ conjugate in $G$.
Our goal is to choose $g_i$ in such a manner that
$\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$ and $(\Gamma, g)$ is ultrahomogeneous
@@ -145,24 +136,14 @@
that $(\Gamma, \sigma)\cong (\Gamma, g)$, thus by the Fact \ref{fact:conjugacy}
we have that $\sigma$ and $g$ conjugate.
- % Once again, by the Fraïssé theorem and by Lemma
- % \ref{lemma:weak_ultrahom} constructing $g_i$'s in a way such that
- % age of $(\Gamma, g)$ is exactly $\cD$ and so that it is weakly ultrahomogeneous
- % will produce expected result.
- First, let us enumerate all pairs of structures
- $\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN},\in\cD$
- 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. We enumerate the elements of the Fraïssé limit
- $\Gamma = \{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 naturally induces
a well ordering on $\bN\times\bN$. This will prove useful later, as the
main ingredient of the proof will be a bookkeeping argument.
For technical reasons, let $g_{-1} = \emptyset$ and
- $X_{-1} = \emptyset$.
+ $X_{-1} = \emptyset$. Enumerate the elements of the Fraïssé limit
+ $\Gamma = \{v_0, v_1, \ldots\}$.
Suppose that player \textit{I} in the $n$-th move chooses a finite partial
automorphism $f_n$. We will construct a finite partial automorphism
$g_n\supseteq f_n$ together with a finitely generated substructure
@@ -204,26 +185,13 @@
\end{center}
\end{enumerate}
- % First item makes sure that no infinite orbit will be present in $g$. The
- % second item together with the first one are necessary for $g$ to be an
- % automorphism of $\Gamma$. The third item is the one that gives weak
- % ultrahomogeneity. Now we will show that indeed such $g_n$ may be constructed.
-
First, we will satisfy the item (iii). Namely, we will construct $\Gamma'_n, g'_n$
such that $g_{n-1}\subseteq g'_n$, $\Gamma_{n-1}\subseteq\Gamma'_n$,
$g'_n$ gives an automorphism of $\Gamma'_n$
and $f_{i,j}$ extends to an embedding of
$(B_{i,j}, \beta_{i,j})$ to $(\Gamma'_n, g'_n)$. But this can be easily
- done by the fact, that $\cD$ has the amalgamation property. Moreover, without
- the loss of generality we can assume that all embeddings are inclusions.
+ done by the fact, that $\cD$ has the amalgamation property.
- \begin{center}
- \begin{tikzcd}
- & (\Gamma'_n, g'_n) & \\
- (B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\subseteq"] & & (\Gamma_{n-1}, g_{n-1}) \arrow[ul, dashed, "\subseteq"'] \\
- & (A_{i,j}, \alpha_{i,j}) \arrow[ur, "\subseteq"'] \arrow[ul, "\subseteq"]
- \end{tikzcd}
- \end{center}
It is important to note that $g'_n$ should be a finite function and once
again, as it is an automorphism of a finitely generated structure, we may
@@ -231,14 +199,7 @@
others. By the weak ultrahomogeneity of $\Gamma$, we may assume that
$\Gamma'_n\subseteq \Gamma$.
- % \begin{center}
- % \begin{tikzcd}
- % B_{i,j}\cup\Gamma_{n-1} \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Gamma \\
- % \Gamma'_{n}\arrow[ur, dashed, "f"']
- % \end{tikzcd}
- % \end{center}
-
- Now, by the WHP of $\cK$ we can extend $\langle\Gamma'_n\cup\{v_n\}\rangle$ together
+ Now, by the WHP of $\cC$ we can extend $\langle\Gamma'_n\cup\{v_n\}\rangle$ together
with its partial isomorphism $g'_n$ to a finitely generated structure $\Gamma_n$
together with its
automorphism $g_n\supseteq g'_n$ and (again by weak ultrahomogeneity)
@@ -247,7 +208,7 @@
that has all desired properties.
Now we need to see that $g = \bigcap^{\infty}_{n=0}g_n$ is indeed an automorphism
- of $\Gamma$ such that $(\Gamma, g)$ has the age $\cH$ and is weakly ultrahomogeneous.
+ of $\Gamma$ such that $(\Gamma, g)$ has the age $\cD$ and is weakly ultrahomogeneous.
It is of course an automorphism of $\Gamma$ as it is defined for every $v\in\Gamma$
and is an union of an increasing chain of automorphisms of finitely generated
substructures.
@@ -257,7 +218,8 @@
By the bookkeeping there was $n$ such that
$(i, j) = \min\{\{0,1,\ldots n-1\}\times\bN\setminus X_{n-1}\}$.
This means that $(B, \beta)$ embeds into $(\Gamma_n, g_n)$, hence it embeds
- into $(\Gamma, g)$. Hence, the age of $(\Gamma, g)$ is $\cH$.
+ into $(\Gamma, g)$. Thus, $\cD$ is a subclass of the age of $(\Gamma, g)$.
+ The other inclusion is obvious. Hence, the age of $(\Gamma, g)$ is $\cH$.
It is also weakly ultrahomogeneous. Having $(A,\alpha)\subseteq(B,\beta)$,
and an embedding $f\colon(A,\alpha)\to(\Gamma,g)$, we may find $n\in\bN$
@@ -267,11 +229,9 @@
$(\Gamma_n, g_n)$, which means we can also embed it into $(\Gamma, g)$.
Hence, $(\Gamma,g)\cong(\Gamma,\sigma)$.
- By this we know that $g$ and $\sigma$ conjugate in $G$. As we stated in the
- beginning of the proof, the set $A$ of possible outcomes of the game (i.e.
- possible $g$'s we end up with) is comeagre in $G$, thus $\sigma^G$ is also
- comeagre and $\sigma$ is a generic automorphism, as it contains a comeagre
- set $A$.
+ By this we know that $g$ and $\sigma$ are conjugate in $G$, thus player \textit{II}
+ have a winning strategy in the Banach-Mazur game with $A=\sigma^G$,
+ thus $\sigma^G$ is comeagre in $G$ and $\sigma$ is a generic automorphism.
\end{proof}
\begin{theorem}
diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex
index 87647c6..1126dee 100644
--- a/sections/fraisse_classes.tex
+++ b/sections/fraisse_classes.tex
@@ -283,13 +283,14 @@
\end{tikzcd}
\end{center}
+ and $A\sqcup_C B\in\cC$.
$A\sqcup_C B$ here is an $L$-structure with domain $A\cup B$ such that
for every $n$-ary symbol $R$ from $L$, $n$-tuple $\bar{a}\subseteq A\cup B$,
- we have that $A\sqcup B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and
+ we have that $A\sqcup_C B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and
$A\models R(\bar{a})$] or [$\bar{a}\subseteq B$ and $B\models R(\bar{a})$].
\end{definition}
- Actually we did already implicitly worked with free amalgamation in the
+ Actually we did already implicitly work with free amalgamation in the
Proposition \ref{proposition:finite-graphs-fraisse-class}, showing that
the class of finite graphs is indeed a Fraïssé class.
@@ -298,7 +299,7 @@
Recall, $\Cospan(\cC)$, $\Pushout(\cC)$ are the categories of cospan
and pushout diagrams of the category $\cC$. We have also denoted the notion
of cospans and pushouts with a fixed base structure $C$ denoted
- as $\Cospan_C(\cC)$ and $Pushout_C(\cC)$.
+ as $\Cospan_C(\cC)$ and $\Pushout_C(\cC)$.
\begin{definition}
\label{definition:canonical_amalgamation}
@@ -346,6 +347,10 @@
\end{itemize}
\end{definition}
+ \begin{remark}
+ Free amalgamation is canonical.
+ \end{remark}
+
From now on in the paper, when $A$ is an $L$-structure and $\alpha$ is
an automorphism of
$A$, then by $(A, \alpha)$ we mean the structure $A$ expanded by the
diff --git a/sections/introduction-pl.tex b/sections/introduction-pl.tex
index bd6e2f1..1b06733 100644
--- a/sections/introduction-pl.tex
+++ b/sections/introduction-pl.tex
@@ -38,6 +38,6 @@
grami Banacha-Mazura, które są dobrze znanym narzędziem w deskryptywnej
teorii mnogości.
- Opisana konstrukcja generycznego automorfizmu okazuje się pomocna w dowodzeniu
- niektórych własności tego automorfizmu (patrz \ref{proposition:fixed_points}).
+ % Opisana konstrukcja generycznego automorfizmu okazuje się pomocna w dowodzeniu
+ % niektórych własności tego automorfizmu (patrz \ref{proposition:fixed_points}).
\end{document}
diff --git a/sections/introduction.tex b/sections/introduction.tex
index 655cba7..6cb432e 100644
--- a/sections/introduction.tex
+++ b/sections/introduction.tex
@@ -36,7 +36,7 @@
this by using the Banach-Mazur games, a well known method in the descriptive
set theory, which proves useful in the study of comeagre sets.
- Finally, we show how this construction of the generic automorphism can be
- used to deduce some properties of generic automorphisms
- (see \ref{proposition:fixed_points}, (COŚ JESZCE)).
+ % Finally, we show how this construction of the generic automorphism can be
+ % used to deduce some properties of generic automorphisms
+ % (see \ref{proposition:fixed_points}, (COŚ JESZCE)).
\end{document}
diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex
index 0a1b202..b27cd69 100644
--- a/sections/preliminaries.tex
+++ b/sections/preliminaries.tex
@@ -76,6 +76,7 @@
\end{definition}
\begin{definition}
+ \label{definition:banach-mazur-game}
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