\documentclass[portrait,notes]{seminar}
\usepackage{fancybox,amssymb}
\slideframe{oval}
\usepackage{color}

\definecolor{brightred}{rgb}{0,1,0.2}
% \definecolor{halfred}{rgb}{1,0,0}


\usepackage{mathrsfs}
 
\def\xx#1:{\medskip\noindent{\bf #1:} } 
\def \yy#1\par{\centerline{\bf #1}}


\newcommand{\brightred}{\textcolor{brightred}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\A}{{\mathscr A}}
\renewcommand{\P}{{\mathscr P}}
\newcommand{\Rel}{{\rm Rel}}
\newcommand{\rel}{{\rm Rel}}
\newcommand{\sinv}{{\rm sInv}}
\newcommand{\aut}{{\rm Aut}}
\newcommand{\Sym}{{\rm Sym}}
\newcommand{\sym}{{\rm Sym}}
\newcommand{\on}{{\upharpoonright}}
 
\begin{document}
\renewcommand{\theslide}{\arabic{slide}/10}


\begin{slide*}   % erste Folie

\begin{center}
{
\Large\bf
 The Galois Connection\\[4mm]
between\\[4mm]
 relations and automorphisms\\[4mm]
\
}

\bigskip
\bigskip

{\bf  Ferdinand B\"orner\\
Martin Goldstern*\\
Saharon Shelah
}


\end{center}

\end{slide*}
\begin{slide*}
  
\xx Setup:  $A$ \dots  \ an infinite set

 $
\textcolor{brightred}{\Rel_k(A)}
 = \P(A^k) = $
\textcolor{brightred}{ $k$-ary relations}
 on $A$

$\Rel(A) =  \bigcup_{k\in \N} \Rel_k(A)$.

$
\textcolor{brightred}{\Sym(A)}
 = $ all 
\textcolor{brightred}{permutations }
of~$A$: 


\bigskip


Every $f\in \Sym A$ acts also on $A^k$ (pointwise).  

 For $\rho \subseteq A^k$ we define $f[\rho] $ naturally.  


\bigskip
\yy  The  Galois connection $\sinv$-$\aut$ 

For $f\in \sym A$, $\rho \in\Rel A$ we write 
$$
\textcolor{brightred}{ f \in \aut(\rho)}
 \mbox{ \ or \ } 
\textcolor{brightred}{\rho\in \sinv (f)}
$$
iff
 $
\textcolor{brightred}{f[\rho] = \rho}
$.  We say 

\begin{center}
``$f$ is an automorphism of $\rho$''

``$\rho$ is strongly invariant under $f$''
\end{center}

\end{slide*}
\begin{slide*}

\xx Definition: 
$ f \in \aut(\rho)  \Leftrightarrow \rho\in \sinv (f) 
\Leftrightarrow f[\rho] = \rho$. 


\bigskip

For  $F \subseteq \Sym(A)$  we let 
%  $ \aut(P):= \bigcap_{\rho\in P}\aut(\rho)$.
 $
\textcolor{brightred}{ \aut(F)}
:= \bigcap_{f \in F}\sinv(f )$

Dually: 
$ 
\textcolor{brightred}{\aut(P)}
:= \bigcap_{\rho\in P}\aut(\rho)$
for $P \subseteq \Rel(A)$.

\bigskip 



\xx The Problem:
{\it  Characterize the \\\null \qquad \qquad
\textcolor{brightred}{ Galois closed}
 sets of relations.}

in other words: 

\begin{itemize}
\item Which subsets of $\Rel(A)$ are of the form $\sinv(F)$ for some~$F$? 
\item {\em (rephrased:)} describe the 
\textcolor{brightred}{closure operator}
$$ P \mapsto \sinv\aut (P)$$
\end{itemize}




\end{slide*}

\begin{slide*}
\sl
\yy Aside


The dual closure operator is easy to describe:  For any set
 $F \subseteq \sym(A)$,  the set~$\aut\,\sinv(F)$ is the smallest 
subset of $\sym(A)$
\begin{itemize}
\item containing $F$
\item closed under the group operations\\ (composition, inverse)
\item closed under  finite interpolability.     \\
{\sl \small (= closed in the Tychonoff topology on $A^A$. 
``$f\notin\aut(\rho)$'' is an open=finitary property.)}

\end{itemize}

Thus, for infinite sets $A$ (of any cardinality) we have to 
combine an algebraic(=finitary) closure operator with
a topological(=infinitary) closure operator. 

\textcolor{brightred}{So we have to expect that the description of
$P \mapsto \sinv\,\aut (P)$ also involves finitary and infinitary closure.}

\end{slide*}

\begin{slide*}
\yy Closure properties of $\sinv(F)$


\xx Example 1:   if $\rho_1$, $\rho_2$ are both in $\sinv(F)$ (for some $F$), and are of the same arity~$k$, then also $\rho_1\cup \rho_2$ and
$A^k\setminus \rho_1$ 
must be in $\sinv(F)$. 

\xx Example 2:  
  if $\rho \subseteq A\times A$ is in $\sinv(F)$, then also the 
projection of $\rho$, 
$$ \exists \rho := \{ x\in A : \exists y\in A\, (x,y)\in \rho\}$$
is in $ \sinv(F)$. 

\xx Conclusion:  $\sinv(F)$ is closed under all 
\textcolor{brightred}{{\em logical operations}. }
(=operations of first order logic).    This is also called a 
``Krasner algebra'' (of the second kind). 


Moreover, $\sinv(F) $ is closed under
\textcolor{brightred}{ arbitrary intersections.}
\end{slide*}

\begin{slide*}
\yy Countable base sets


\xx Theorem:  If $A$ is countable, $P\subseteq \Rel(A)$, 
 then $\sinv \aut (P)$ is the closure of $P$ under 
\textcolor{brightred}{logical operations and
 arbitrary intersections}.

{\bf 
However, this is not true for uncountable sets: }


E.g., if $\rho\subseteq A \times A$, then the relation
\brightred{$ \exists^{>\aleph_0} \rho $},
 defined as
$$ \{ x : 
\mbox{ there are uncountably many~$y$:}  (x,y)\in \rho\}$$
is  in $\sinv\aut(\rho)$, but can in general not be
 obtained from $\rho$ with logical operations and arbitrary intersections.

\end{slide*}

\begin{slide*}
\yy 
\brightred{Invariant operations}


The problem is that first order logic cannot distinguish different 
infinite cardinalities.   So we add {\em all} operations from 
all higher order logics. 

\xx Definition:  A map $h: \rel_{k_1}(A)\times \cdots
 \times \rel_{k_\ell}(A)
\to \rel(A)$ is called an {\em invariant operation}, if: 

\begin{quote}
For all $ f\in \Sym(A)$ and all $\rho_1\in \rel_{k_1}$, \dots,
$ \rho_\ell\in \rel_{k_\ell}$ we have 
$$ h[ f(\rho_1,\ldots, \rho_\ell) ] = 
 f(h[\rho_1],\ldots, h[\rho_\ell]) ] $$
\end{quote}



All logical operations, and all operations 
\brightred{definable}
 in higher 
order logic such as $\exists^{>\aleph_0}$ are 
\brightred{invariant.}

\end{slide*}

\begin{slide*}
\yy A plausible conjecture

We are looking for an internal description of the closure 
operator $P \mapsto \aut\,\sinv P$.   In many cases --- in particular
if the base set~$A$ is at most countable, or if the set~$P$ is finite --- 
we have:  
\begin{quote}\sl

$\aut(\sinv (P))$  is the smallest set containing $P$ which is closed 
under
\begin{itemize}
\item [--] 
\brightred{all invariant operations}
\item[--] 
\brightred{arbitrary intersections.}
\end{itemize}
\end{quote}

{\bf Is this true in general?}

\bigskip 
\bigskip 

\xx Answer:  No! 

\end{slide*}
\begin{slide*}
\yy A counterexample



There is an uncountable structure $
\brightred{\A }
= (A, \rho_1,\rho_2, \ldots)$ such 
that, letting
{\advance\leftmargini0.8cm
\begin{enumerate}
\item[$P := $] the first order definable relations of $\A$ (without 
parameters)
\item[ $ \A\on n := $] $(A, \rho_1,\ldots, \rho_n) $
\end{enumerate}
}
we have
\begin{enumerate} 
\item  $\A$ is 
\brightred{$\aleph_0$-categorical.}
  {\small Hence:
\begin{enumerate}
\item [--] $P$ is {\bf small} (countable)
\item [--] $P$ is closed under arbitrary $\bigcap$
\end{enumerate}
}
\item $\forall n:$  $\A\on n$ is 
\brightred{homogeneous }
(every finite partial 
automorphism extends)
\\
{\small This implies:  $P$ is closed under all invariant operations.}


\item  $\A$ is 
\brightred{rigid.}
 \\
Hence, $\aut(P) = \{ {\rm id} \}$, and $\sinv\,\aut P = 
\sym(A) $ is {\bf large} . 

\end{enumerate}

 

\end{slide*}
% \begin{slide*}
% To achieve property 3, we use the following lemma: 
% 
% 
% \xx Lemma:    If a set~$R$ of relations on $A$ is {\em homogeneous}  ,
% 
% \begin{quote}{\small\sl(That is:  if every finite partial automorphism of
% $(A,R)$ extends to a total automorphism)}
% \end{quote}
% then the closure of $R$ under logical operations is already the 
% closure under invariant operations. 
% 
% So it is enough to construct  a structure $(A, \rho_1,\rho_2,\ldots)$
% as above such that 
% 
% \begin{itemize}
% \item 
% each  reduct $(A, \rho_1,\ldots, \rho_k)$ has very many
% automorphisms (is homogeneous)
% \item The whole structure  $(A, \rho_1,\ldots\, )$ is rigid. 
% 
% \end{itemize}
% 
% \end{slide*}
\begin{slide*}
\yy Characterization of $\sinv\,\aut$ 



\xx Definition:  A map $$h: \prod_{n\in \omega} \rel_{k_n}(A)
\to \rel(A)$$ is called an 
\brightred{{\em $\sigma$-invariant operation}},
 if: 
\begin{quote}
For all $ f\in \Sym(A)$ and all countable sequences 
$(\rho_1,\ldots) $ with $\rho_1\in \rel_{k_1}$, \dots,
we have 
$$ h[ f(\rho_1,\ldots, \rho_\ell, \ldots ) ] = 
 f(h[\rho_1],\ldots, h[\rho_\ell], \ldots ) ] $$
\end{quote}

Then we have for any (even uncountable) set~$A$: 
\begin{quote}
\brightred{
For any set~$P$ of relations on~$A$, \\
$\aut\,\sinv P$  is the smallest set containing $P$ which is closed 
under all invariant operations, and arbitrary intersections.}
\end{quote}


\end{slide*}
\end{document}