## Sometimes a maximality principle is true even if Zorn’s Lemma fails

A famous and straightforward result in general topology says that any compact $T_2$ space is

• maximally compact: any finer topology isn’t compact any more;
• minimally $T_2$: any coarser topoology isn’t $T_2$ any more.

A natural pair of questions that arises from this is the following: Is every compact topology contained in a maximally compact one? (Dually: does every Hausdorff topology contain a minimal Hausdorff topology?).

This short post is only concerned with the former of the two questions. Unfortunately, a direct application of Zorn’s Lemma doesn’t lead us anywhere. Let $\mathbb{N}$ denote the set of positive integers. We define a chain of compact topologies on $\mathbb{N}$ by setting

$\tau_n = \mathcal{P}(\{1,\ldots,n\}) \cup \{\mathbb{N}\}$ for every $n\in \mathbb{N}$. (By $\mathcal{P}(.)$ we denote the power set.)

Now every $\tau_n$ is compact, but the topology generated by the union of this chain is the discrete topology on $\mathbb{N}$, which is not compact. So we cannot apply Zorn’s Lemma for this question.

It turns out that even if we can’t apply ZL, the statement that every compact topology is contained in a maximally compact one is true, which answered an old question. The result can be seen in this paper by Martin Maria Kovar.

## On empty Hom-sets between graphs

In many categories such as Set, Group, Top (topological spaces) there is a morphism between any two objects, usually in both directions. (If one object is “empty”, like the empty space, or the empty set, there is the “empty” morphism from $\emptyset$ to the other object, but not the other way round.)

However in the category Graph it is possible that non-empty graphs $G,H$ have no graph homomorphism between them in either direction:

Let $K_3$ be the complete graph on 3 points and let $H$ be any triangle-free graph with $\chi(H) > 3$, for instance the Grötzsch graph, which has chromatic number 4.

Since $H$ is triangle-free, there is no graph homomorphism $\varphi: K_3 \to H$ and if there were a homomorphism $\eta : H \to K_3$, this map would be an $n$-coloring of $H$ for some $n \leq 3$.

## On the topological closure of the diagonal of a space

When we take a class in general topology and learn about $T_2$-spaces, one of the standard exercises we do is:

Prove that a space $X$ is Hausdorff if and only if the diagonal $\Delta_X = \{(x,x) : x \in X\}$ is closed in the product topology of $X \times X$.

Given any topological space $X$, the closure of the diagonal, that is $cl(\Delta_X)$, is a binary relation, which in the case of Hausdorff spaces is pretty boring. So a natural question to ask is: Which binary relations on a set $X$ arise as the closure of the diagonal for a suitable topology $\tau$ on $X$? We will call those binary relations topologically realizable.

It is easy to see that for any topology, $cl(\Delta_X)$ is reflexive and symmetric, and it turns out that a large class of reflexive and symmetric relations are topologically realizable:

Proposition. Any equivalence relation is topologically realizable.

Proof. Let $X$ be a set and $R \subseteq X\times X$ be an equivalence relation. We set $\textrm{Block}(R)=\{[x]_R : x \in X\}$ — so it is the set of equivalence classes or “blocks” that $R$ induces. Using the Axiom of Choice we pick for each block $B \in$ $\textrm{Block}(R)$ a representative $r(B) \in B$ and we define

$\tau = \{ U\subseteq X :$ for all $B \in$ $\textrm{Block}(R)$ : if $U\cap B \neq \emptyset$ then $r(B)\in U\}$.

It is not hard to verify that $\tau$ is indeed a topology. We need to show that $cl(\Delta_X) = R$.

$cl(\Delta_X) \subseteq R$: Let $(x,y) \in (X\times X)\setminus R$. So $U= [x]_R$ and $V= [y]_R$ are disjoint open sets, therefore $U\times V$ is an open neighborhood of $(x,y)$ that does not intersect $\Delta_X$, so $(x,y)$ is not in $cl(\Delta_X)$.

$cl(\Delta_X) \supseteq R$: Let $(x,y) \in R$ that is $[x]_R = [y]_R$. By construction of the open sets, every open neighborhood of $x$ and every open neighborhood of $y$ contains $z := r([x]_R) = r([y]_R)$. Therefore every open neighborhood of $(x,y)$ in the product space $X\times X$ contains $(z,z) \in \Delta_X$ which implies that  $(x,y) \in cl(\Delta_X)$.

Does the converse hold? We might wonder whether conversely, every topologically realizable relation is transitive. It turns out that this is not true; see Example 4.1. in this paper by Maria-Luisa Colasante and me.

I would like to see the following: Is there a set $X$ and a reflexive, symmetric relation $R \subseteq X\times X$ such that $R$ is not topologically realizable?

## A universal property on groups

Consider the group $\textrm{Sym}(\mathbb{N})$ of all permutations on the set of positive integers, and its subgroup of permutations with finite support, i.e. those permutations $\pi$ of $\mathbb{N}$ such that there is $n \in \mathbb{N}$ such that $\pi(k) = k$ for all $k \geq n$. Let’s call this group $\textrm{Sym}_{\textrm{fin}}(\mathbb{N})$.

Because of Cayley’s Theorem it turns out that every finite group can be embedded into $\textrm{Sym}_{\textrm{fin}}(\mathbb{N})$. I strongly believe that $\textrm{Sym}_{\textrm{fin}}(\mathbb{N})$ is the “smallest” such group, that is I think that the following statement is true:

(S) If $G$ is any group such that every finite group can be embedded into $G$ then $G$ contains a subgroup isomorphic to $\textrm{Sym}_{\textrm{fin}}(\mathbb{N})$.

Statement (S) is one of the things that I think have a natural and easy proof  – but I am unable to find it. Any help would be appreciated.

Things are less clear to me when we turn the question “upside down”: Consider the class $\mathcal{C}$ of groups $G$ such that every for every finite group $F$ there is a surjective group homomorphism $e: G\to F$. Is there a group $G^*$ belonging to the class $latex \mathcal{C}$  such that for every $G\in \mathcal{C}$ there is a surjective group homomorphism $e : G \to G^*$? I suspect that would be some quotient of the free group on $\mathbb{N}$

Posted in Uncategorized | 6 Comments

## Two definitions of connectedness in graphs

In this short post, we are only dealing with simple graphs $G = (V,E)$ where $V$ is a non-empty set and $E \subseteq {\cal P}_2(V) := \{\{a,b\} \subseteq V: a \neq b\}$.

When talking about connected graph, one usually has the following definition in mind:

Definition 1. A graph $G=(V,E)$ is said to be connected if for any distinct vertices $a,b \in V$ there is a path connecting $a$ and $b$. (A  path from $a$ to $b$ is an injective map $p: \{0,...n\} \to V$ for some positive integer $n$, such that $\{p(k), p(k+1)\} \in E$ for all $0 \leq k < n$.)

Note the similarity to path connectedness in topology.

Definition 2. A graph $G=(V,E)$ is said to be connected if for any subset $S$ of $V$ with $\emptyset \neq S \neq V$ there is $e \in E$ such that $S \cap e \neq \emptyset \neq (V\setminus S) \cap e$.

Again, there is a topological equivalent: we say that a topological space $(X,\tau)$ is connected if no subset $S$ of $X$ with $\emptyset \neq S \neq X$ is both open and closed (“clopen”).

But the analogy of the connectedness in topological spaces and in graphs only goes so far. Recall that every path-connected topological space is connected, but not vice versa. However, and possibly a bit surprisingly even for infinite graphs, we have:

Lemma.  The definitions 1 and 2 above agree.

Proof. It is quite straightforward to show that path-connectedness as in definition 1 implies connectedness as in definition 2. Suppose that $G = (V,E)$ is connected in the sense of definition 2 but not 1. Pick any $x \in V$ and let $C = \{x\} \cup \{ v\in V: \textrm{ there is a path from } x \textrm{ to } v\}$. ($C$ is the pathwise connected component of $x$.) It is easy to see that $C$ is a proper subset of $V$ because of our assumption. However, since $G$ is connected in the 2nd sense, there is an edge connecting a point $c \in C$ to some point $y \in V\setminus C$. But since there is a path from $x$ to $c$ and also $\{c, y\} \in E$ we can extend the path so that it leads from $x$ to $y$. So $y \in C$, contradicting $y \in V\setminus C$.

## Basics on maps

Recently I was trying to prove the following statement found as an exercise in a topology book by Arkhangel’skii (I forget the title):

Let $X$ be a set and let $A, B$ be subsets such that there are bijections $\varphi_A: A \to (X \setminus A)$ and $\varphi_B: B \to (X \setminus B)$. Show without using the Axiom of Choice that there is a bijection from $A$ to $B$.

It turns out that you can construct an injection from $A$ into $B$ (and, by symmetry, an injection from $B$ into $A$). So the theorem of Cantor-Schroeder-Bernstein (CSB) comes in usefully (which can be proved without AC): It says that whenever you have injective maps between two sets, then there is a bijection between them.

There are several proofs to CSB, none of which was simple or elegant enough that it would stick to my memory. So, with the aid of Google and Wikipedia, I tried to find a proof that I would remember. On the German-speaking wiki page of CSB I was pointed to an astonishing generalisation of CSB, called Banach’s mapping theorem, which is purely set-theoretical and has nothing to do with contractions, Banach spaces, or whatever you would associate with Stefan Banach. Here is the statement of that theorem.

Banach’s mapping theorem: If $X, Y$ are sets and $f: X \to Y$ and $g: Y \to X$ are maps, then there are subsets $A \subseteq X$ and $B \subseteq Y$ such that

(1) $f(A) = B$, and
(2) $g(Y\setminus B) = X \setminus A$.

That struck me as a truly remarkable statement: You can dissect $X$ and $Y$ so that you get two “matching pairs” of subsets so that $f,g$ “respect” the pairings. No restrictions are made on the nature of the maps $f, g$! If we take $f, g$ to be injections, it is clear how CSB can be proved from this: just define $\varphi : X \to Y$ to be $f$ on $A$ and $g^{-1}$ on $X \setminus A$, and so $\varphi$ is our bijection.

How would we go to prove Banach’s little gem? It turns out that it is a consequence from the Knaster-Tarski fixed point theorem:

Knaster-Tarski fixed point theorem: If $(P, \leq)$ is a complete lattice and $f:L \to L$ is an order-preserving function, then $f$ has a fixed point. — The proof of this fixed point theorem is remarkably straightforward: Just consider the supremum $s^*$ of the set $M = \{l \in L : l \leq f(l)\}$ and verify that $f(s^*) = s^*$.

As to why Knaster-Tarski is helpful for proving Banach’s theorem, let $P(X)$ be the powerset of $X$ and note that $P(X)$ is a complete lattice, ordered by set inclusion $\subseteq$. Consider

$\Phi: P(X) \to P(X)$ defined by $S \mapsto X \setminus (g(Y\setminus f(S))$.

We verify that $\Phi$ is order-preserving, therefore it has a fixed point $A \in P(X)$. Set $B:= f(A)$. So we get item (1) of Banach’s theorem for free, and item (2) is easy too, because $A = X \setminus (g(Y\setminus B)$ since $A$ is a fixed point of $\Phi$, and therefore $X\setminus A = g(Y \setminus B)$.

For me, seeing how you get Banach’s theorem out of Knaster’s and Tarski’s well-known fixed-point theorem was a real wow moment!

Posted in Uncategorized | 1 Comment

## Dreaming mathematics

This post is more of a psychological or philosophical musing, only loosely connected to mathematics. Last night I had a peculiar dream that I remember quite precisely. I was sitting in my point-set topology class, and the teacher introduced ultrafilters. (For some reason I knew in the dream that they would play a crucial role in proving Tychonoff’s theorem.) Then she gave us the following (slightly weird, but easy) assignment:

Let $X$ be an infinite set and let ${\cal U}$ be a non-principal ultrafilter on $X$. Then show that $(X, {\cal U}\cup \{\emptyset\})$ is a topological space.

I am quite sure that I was never given this assignment in real life. In hindsight, I find the following points remarkable:

$(X,{\cal U}\cup \{\emptyset\})$ is indeed a topological space;
$(X,{\cal F}\cup \{\emptyset\})$ is a topological space for every filter ${\cal F}\cup \{\emptyset\}$, you don’t need the filter to be maximal or non-principal, so in the real world such a problem would not be stated in terms of non-principal ultrafilters;
– I’m pretty certain I haven’t looked at (ultra)filters as a topology in their own right.

In the dream I feverishly tried to show that distinct elements $x,y\in X$ could be separated by disjoint members of ${\cal U}$ thereby committing at least two mistakes on different levels:

(1) in order to show that a collection of subsets of a set $X$ you don’t need to prove the separation property (Hausdorff-ness) and
(2) no two members of any filter are disjoint.

I realised both points immediately upon my awakening (in a double sense), and in real life it would never have occurred to me to try the weird and fruitless approach that I took in my dream.

The reason why I found this dream interesting is the following. Many of us experience (and remember for some time afterwards) very awkward dreams dealing with situation that are physically impossible (e.g. allowing you to hover above the ground without further aid) or otherwise highly implausible, or that memory plays tricks on us within the dream and we even notice it within the dream. Dreams are a radically different experience compared to our waking hours; but for the first time I noticed that also there are some interesting distortions of formal thinking that may accompany dreams. I have had quite implausible and buggy thinking in other dreams, but never before have I been able to pin it down in a formal and precise setting.

These were the thoughts that passed my mind when I was laying awake this morning. Also, I was reminded of a fellow student that I met in my first year calculus class. At some point he claimed that he was sure he had found a bijection between $\mathbb{N}$ and $\mathbb{R}$. This alone wasn’t noteworthy — such mistakes can happen in the beginning of your studies. I pointed him to Cantor’s diagonal argument showing that the reals are uncountable. But he told me I was only cunningly tricked into believing $\mathbb{R}$ was uncountable. In truth, he claimed, there was an intricate and deep bijection between the natural numbers and the reals, and this knowledge was deliberately hidden by our calculus professor (and the math books). This claim struck me as really odd, but I shrugged it off and got on with my studies. (Later, my fellow student was diagnosed with schizophrenia and had to discontinue his studies).

Interestingly, schizophrenia is characterised by distorted perception, disruptive formal thinking, memory distortions and generally holding severely implausible beliefs. All of those symptoms can be a part of dreams as well. When reflecting on my dream, I was so strongly reminded of the episode of my fellow student that I felt there must be some underlying mechanism or phenomenon connecting dreams and schizophrenia. But since I am not medically trained, I should be careful with such hypotheses.