Basics on maps

Posted on 2012/07/26 by

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 | Leave a comment

Dreaming mathematics

Posted on 2010/10/18 by

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.

Posted in Uncategorized | Leave a comment

(Least) upper bounds for order-preserving maps

Posted on 2010/08/19 by

A map f:P\to Q between non-empty partially ordered sets is said to be order-preserving if x, y \in P, x\leq_P y entails f(x) \leq_Q f(y). The collection Mor(P,Q) of order-preserving maps f:P\to Q can be endowed with an ordering relation in a natural way by setting

f \leq g in Mor(P,Q) iff f(x) \leq g(x) for all x\in P.

When considering any partially ordered set, or poset, for short, a natural question arising is that of the existence of (least) upper bounds, and dually, (greatest) lower bounds. A subset S of a poset (P,\leq) is said to have an upper bound if there exists z \in P such that z \geq s for all s\in S. The collection of upper bounds of S is denoted by S^u.

The basic question of this post is: When do f, g \in Mor(P,Q) have a (least) upper bound?

When you start tinkering with Mor(P,Q) and its elements, you notice that the existence of bounds in the codomain Q is more important than in the domain P. This can be illustrated by two examples:

(1) If f(x) and g(x) have no upper bound in Q for some x \in P, then f,g are not bounded in Mor(P,Q).

(2) If Q is a lattice, then so is Mor(P,Q).

As for the proof of statement (2), let us denote the supremum of a,b \in Q by a\vee b and the infimum by a\wedge b. Let f,g \in Mor(P, Q). Then it is easy to verify that the map h:P \to Q given by

h(x) = f(x) \vee g(x) for all x \in P

is the supremum of f,g; the infimum is constructed in a similar manner.

Let’s have a look at the converse statements of (1) and (2).

The converse of (1) would say that if \{f(x), g(x)\}^u \neq \emptyset for all x\in P, then f, g have an upper bound in Mor(P,Q). We can construct a finite counterexample to this statement by letting V = \{b, 0, 1\} ordered by b < 0, b < 1 and Q = \{0,1\}^2 ordered by (0, j) < (1,k) for j,k \in \{0,1\}. So if we draw V we get a v-shaped figure, and Q looks like a butterfly.

Let f,g: V\to Q be the maps given by f(b) = (0,0) and g(b) = (0,1) and f(0) = g(0) = (1,0) and f(1) = g(1) = (1,1). Then \{f(x), g(x)\}^u \neq \emptyset for all x\in V, but it is easily seen that there is no order-preserving map that is an upper bound of f, g.

The converse of (2), on the other hand, is true. In order to tackle this, we need the concept of a retract. We say that a poset S is a retract of a poset T if there are order-preserving maps i:S\to T and r:T \to S such that r\circ i: S\to S is the identity map.

Lemma 1. Q is a retract of Mor(P,Q).
Proof. Let i:Q \to Mor(P,Q) be defined by i:q \mapsto c_q where c_q:P\to Q is the constant map that maps everything from P to q\in Q. For defining r:Mor(P,Q) \to Q, fix a_0 \in P and for f\in Mor(P,Q) let r(f) = f(a_0). A routine check shows that i, r are order-preserving and r\circ i = \textrm{id}_Q.

Lemma 2. Any retract of a lattice is a lattice.
Proof. Let L be a lattice and P a poset and i:P\to L and r:L \to P such that r\circ i: P\to P is the identity map. For a, b \in P it suffices to check that r(i(a) \vee i(b)) is the least upper bound of a,b. It clearly is an upper bound. Suppose v \in \{a,b\}^u. Then i(v) \in \{i(a), i(b)\}^u since i is order-preserving, therefore i(a)\vee i(b) \leq i(u). Using the fact that r is order-preserving we get that r(i(a) \vee i(b)) \leq r(i(u)) = u, so r(i(a) \vee i(b)) is the least upper bound.

In summary, we get that Mor(P,Q) is a lattice if and only if Q is a lattice. (Note that this equivalence only works for P \neq \emptyset).

We gave partial answers, but are still lacking a full one, to the main question of this post: When do f, g \in Mor(P,Q) have a (least) upper bound?

Posted in Order theory | Leave a comment

T_2 and compactness

Posted on 2010/08/17 by

Any compact T_2 (= Hausdorff) space (X, \tau)  is on the brink of being compact and being T_2:

(1) If we endow X with a topology \tau' distinct from \tau such that \tau' \supseteq \tau, then (X, \tau') is not compact any more; and
(2) if we endow X with a topology \tau' distinct from \tau such that \tau' \subseteq \tau, we lose the the Hausdorff property.

More concisely, these statements say: compact T_2 spaces are maximal compact and minimal T_2. They are both quite straightforward to prove.

Which leads to the question about the converse of these statements, i.e.

(1) Is every maximal compact space T_2?
(2) Is every minimal T_2 space compact?

As for the first question, the answer is No. One example is the Alexandroff compactification \mathbb{Q}^* of the rationals with the Euclidean topology. Recall that the Alexandroff compactification of a Hausdorff space (X, \tau) is formed by setting X^* = X \cup \{\infty\} where \infty \notin X and endowing X^* with the topology generated by \tau \cup \{X^* \setminus F: F \textrm{ is compact in }X\}.

The key to showing that \mathbb{Q}^* is maximal compact is the following
Lemma. A space is maximal compact if and only if every compact subset is closed.

Moreover, we cannot separate any q \in \mathbb{Q} from \infty \in \mathbb{Q}^* by disjoint neighborhoods, so \mathbb{Q}^* is not Hausdorff.

The lemma above characterizes maximal compact spaces. On the other hand I lack a tool for tackling minimal Hausdorffness. So I can answer Question (1) above, but for its ”dual” question whether minimal T_2 implies compactness, I don’t have a clue. Any hints are appreciated!

Posted in Point-set topology | Leave a comment