## Reproducing Kernel Hilbert Spaces

Given that reproducing kernel Hilbert spaces (RKHS) behave more like Euclidean space than more general Hilbert spaces, it is somewhat surprising they are not better known. I have uploaded to arXiv a primer on reproducing kernel Hilbert spaces that differs from other introductory material in a number of ways.

It is perhaps the first to start by considering finite-dimensional spaces rather than jump straight to infinite-dimensional spaces. Surprisingly much can be gained by considering the finite-dimensional case first. It also does not assume any prior knowledge about Hilbert spaces and goes to great lengths to explain clearly about closed and non-closed subspaces and completions of spaces. (e.g., It is explained that a space which is not complete can be thought to have a ‘scratched surface’.)

Whereas other material refers to a RKHS theory as providing a “coordinate-free approach”, I argue that the presence of a Hilbert space already provides a coordinate-free approach, with the added benefit of a *reproducing kernel* Hilbert space being a canonical coordinate system associated to each point in the Hilbert space.

The primer explains that RKHS theory studies the configuration of an inner product space sitting inside a function space; it describes an extrinsic geometry because how the space is oriented inside the larger function space matters. This way of thinking leads to being able to determine when RKHS theory might be relevant to a problem at hand; if the solution of the problem changes continuously as the configuration changes continuously then it is possible the solution might be expressible in terms of the kernel in a nice way.

How RKHS theory can be used to solve linear equations is discussed along with some novel descriptions and extensions, as is the role of RKHS theory in signal detection.

My colleague contributed substantially by describing some of the recent work in the statistical learning theory literature, including explaining how RKHS theory can be used for testing for independence, for nonlinear filtering, and so forth.

## Tensor Products Introduced as Most General Multiplication (and as Lazy Evaluation)

This note is a fresh attempt at introducing tensor products in a simple and intuitive way. The setting is a vector space on which we wish to define a multiplication. Importantly, we do not wish to limit ourselves to a multiplication producing an element of . For example, we would like to think of and as two examples of multiplying elements of . The first multiplication, , is a map from to . The second multiplication, , is a map from to . In fact, since is well-defined even if and have different dimensions, the most general setting is the following.

Let and be fixed vector spaces agreed upon at the start. Assume someone has defined a multiplication rule but has not told us what it is. Here, is a function and is a vector space, both of which are unknown to us. For example, if and , a possible choice might be where .

What does it mean for to be a rule for multiplication? We wish it to have certain properties characteristic of multiplication. In a field, multiplication is involved in a number of axioms, including the distributive law . Since and are vector spaces, potentially distinct from each other, not all the axioms for multiplication in a field make sense in this more general setting. (For instance, commutativity makes no sense if .) The outcome is that is declared to be a rule for multiplication if it is bilinear: , and .

Not knowing does not prevent us from working with it; we simply write it as and are free to manipulate it according to the aforementioned rules. We do the equivalent all the time when we prove general results about a metric; we say “let be a metric” and then make use of only the axioms of a metric, thereby ensuring our derivation is valid regardless of which metric is actually being represented by .

While the tensor product is more than this, in the first instance, it suffices to treat it merely as an unspecified rule for multiplication. (It is specified, but no harm comes from forgetting about this in the first instance.) Rather than write it is more convenient to write , and thinking of as multiplication reminds us that .

The first point is that we can treat as an unspecified multiplication, simplify expressions by manipulating it in accordance with the rules for multiplication, and at the end of the day, if we are eventually told the rule , we can evaluate its simplified expression. In computer science parlance, this can be thought of as lazy evaluation.

Whereas there are many metrics “incompatible” with each other, the rules for multiplication are sufficiently rigid that there exists a “most general multiplication”, and all other multiplications are special cases of it, as explained presently. The tensor product represents this most general multiplication possible.

To consider a specific case first, take and to be . We already know two possible multiplications are and . The claim is that the latter represents the most general multiplication possible. This means, among other things, that it must be possible to write in terms of , and indeed it is: . Note that trace is a linear operator. The precise claim is the following. No matter what is, we can pretend it is , work with this definition, then at the very end, if we are told what actually is, we can obtain the true answer by applying a particular linear transform. At the risk of belabouring the point, if we wish to simplify then we can first pretend is to obtain . Later when we are told we can deduce that the linear map required to convert from to is . Applying this linear map to yields and this is indeed the correct answer because it equals .

Readers wishing to think further about the above example are encouraged to consider that the most general multiplication returning a real-valued number is of the form for some matrix . How can be obtained from ? What about for multiplication rules that return a vector or a matrix?

The general situation works as follows. Given vector spaces and , two things can be constructed, both of which use the same symbol for brevity. We need a space for our most general multiplication, and we denote this by . We also need a rule for multiplication and we denote this by . By definition, is an element of . (Just like not all matrices can be written as , there are elements in that cannot be written as . They can, however, be written as linear combinations of such terms.)

At this point, I leave the reader to look up elsewhere the definition of a tensor product and relate it with the above.

## Simple Derivation of Neyman-Pearson Lemma for Hypothesis Testing

This short note presents a very simple and intuitive derivation that explains why the likelihood ratio is used for hypothesis testing.

Recall the standard setup: observed is a realisation of a random variable (or vector or process) generated either with probability density or .

The observation space is to be partitioned into two regions, one region labelled zero and the other unity. If lies in the region labelled zero then is assumed to have been generated under . The rough aim is to choose the partition so that if this “game” is repeated many times — choose to be 0 or 1; repeatedly generate samples from and count how many times they fall in the two regions — then the ratio of “correct outcomes” to “incorrect outcomes” is maximised, regardless of whether or was used. On average, we wish to be correct many more times than we are wrong.

Since there is a trade-off between being correct when and when , Neyman-Pearson’s underlying criterion is to fix the probability of being wrong when and maximise the probability of being correct when . (This part is assumed to be familiar to the reader.)

Mathematically, the region of the observation space must be found such that 1) the probability of the observation lying in under is some fixed (and small) value, while 2) the probability of the observation lying in under is as large as possible. (This region will be the region labelled unity.) This is a constrained optimisation problem involving a region of space. Pleasantly then, there is a simple way of solving it.

**The trick is to imaging the observation space as broken up into many small tiles fitting together to cover the observation space.** (If the observation space is drawn as a square then imagine dividing it into hundreds of small squares.) With this quantisation, finding the region (up to quantisation error) means finding which of the tiles we want to be part of the region .

Think of starting with being the empty set and growing it by adding tiles one at a time. The first tile we add will do two things: it will give us a which we want to keep as small as possible and it will give us a which we want to maximise. (At this point, some readers may wish to re-tile the region with tiles of possibly differing sizes, so that the probability under of landing on any given tile is the same fixed constant regardless of which tile was chosen.) It is intuitively clear (and even clearer after re-tiling) that the very first tile we should pick is the one which will make as large as possible. If has not exceeded the limit then we are allowed to pick another tile, and we pick the next best tile, that is, out of the tiles remaining, we want the tile that maximises the ratio . Each time, we greedily pick the best remaining tile that will help us make as large as possible while not letting grow too quickly.

As the size of the tiles shrinks to zero, the “limit” is the likelihood ratio for the “infinitesimal” tile centred at . Choosing the region for some constant corresponds precisely to choosing the tiles with the largest ratios; every tile with ratio better than is included.

The above is a hand-waving argument and is not the best on which to base a rigorous proof. Often this is the case though: an intuitive derivation is subsequently verified by a less intuitive but more elementary mathematical argument. An elementary proof can be found in the Wikipedia.

## Understanding (real- and complex-valued) Inner Products

This short note addresses two issues.

- How can we intuitively understand a complex-valued inner product?
- If an inner product structure is given to a vector space, how can we understand the resulting geometry?

Since inner products are associated with angles, and since we can understand angles, there is temptation to interpret inner products in terms of angles. I advocate against this being the primary means of interpreting inner products.

An inner product induces the norm . Importantly, the inner product can be recovered from this norm by the polarisation identity. Therefore, understanding the geometry of an inner product is the same as understanding the geometry of the norm, and for the latter, it often suffices to consider what the unit ball looks like. For me, the norm is the primary structure giving the space its geometry.

What then is the purpose of the inner product? Not all norms have the same properties. Under some norms, projection onto a closed subspace may not be unique, for example. When interested in shortest-norm optimisation problems, the most desirable situation to be in is for the square of the norm to be quadratic, since then differentiating it produces a linear equation. In infinite dimensions, what does it mean for the square of a norm to be quadratic?

The presence of an inner product structure means the square of the norm is quadratic. Furthermore, the inner product “decomposes” the norm in a way that gives direct access to the derivative of the norm squared.

The remaining issue is how to understand complex-valued inner products. Given the above, the natural starting place is to consider endowing a complex vector space with a norm. Keeping the axioms of a real-valued normed vector space seems sensible; it implies that scaling a vector by does not change its norm (because ).

Then one asks what it means for the square of a norm to be quadratic. From the real-valued case, one guesses that one wants to be able to represent the square of the norm as a bilinear form: , where is linear in each of its arguments. Following the letter of the law, this would mean . In the complex case though, need not equal . This explains why one tweaks the definition and instead considers sesquilinear forms which are linear in one argument and conjugate linear in the other: . Indeed, one then correctly has that . With this tweak, one can verify that the complex-valued case works the same way as the real-valued case.

By treating the norm as the primary structure, one does not have to worry about giving an intuitive meaning to the inner product of two vectors not being a purely real-valued number; the inner product is there merely to expose the square of the norm as being quadratic. A complex-valued inner product is recoverable from its norm and hence no geometric information is lost. (Of course, orthogonality remains an important concept.) If one really wanted, one could play around with examples in to get a better feel for what it means for , for example, however, unless one encounters a particular problem encountering this level of detail, thinking in terms of norms is cleaner and more efficient. (If then , so that by “rotating” a complex-valued vector in the two-dimensional real-valued vector space that it spans, one can always return to thinking about real-valued inner products.)

## Are Humans Smart and Computers Dumb? Can Computers Become Better at Helping Humans Solve Challenging Problems?

Computers are generally seen as “dumb”, unable to think for themselves and therefore unable to solve certain complex tasks that humans, being “smart”, are able to solve relatively easily. Humans outperform computers at speech recognition, many image processing problems, and at real-time control problems such as walking – bipedal robots cannot manoeuvre as well as humans. Some may argue computers will never be able to prove mathematical theorems or engineer complex systems as well as mathematicians or engineers.

From a pragmatic perspective, “being smart” is ill-defined. Roughly speaking, a solution is “smart” if a formulaic solution is not known (or if the solution is obtained much more efficiently than via a formulaic but brute force solution, e.g. one could argue humans are still “smarter” at chess than computers, even though computers can now beat humans).

My current viewpoint is that:-

- we are probably not as smart as we may think;
- computers are dumb primarily because we only know how to program them that way;
- regardless, the future vision should be of challenging problems being solved jointly by humans and computers without the current clunky divide between what humans do and what computers do. We should be aiming for semi-automated design, not fully-automated design.

The following three sections elaborate on the above three points in turn. First a summary though.

**Summary:** We should not dismiss the idea that computers can help us in significantly better ways to solve challenging problems simply because we see a divide: we are smart and computers are not. Ultimately, smartness probably can be recreated algorithmically provided computers (robots?) and humans start to interact extensively. But well prior to this, computers can become better at assisting us solve challenging problems if we start to understand how much ‘intuition’ and ‘problem solving’ boils down to rules and pattern recognition. Certainly not all intuition would be easy to capture, but often challenging problems involve large amounts of fairly routine manipulations interspersed by ingenuity. Semi-automated design aims to have a human and a computer work together, with the computer handling the more routine manipulations and the human providing high-level guidance which is where the ingenuity comes in.

Readers short of time but interested primarily in a suggested research direction can jump immediately to the last section.

As the focus is on solving mathematical and engineering problems, no explicit consideration is given to philosophical or spiritual considerations. Smartness refers merely to the ability to solve challenging (but not completely unconstrained) problems in mathematics and engineering.

## How Smart Are Humans?

A definitive answer is hard to come by, but the following considerations are relevant.

Human evolution traces back to prokaryote cells. At what point did we become “smart”? My favoured hypothesis is that as the brain got more complex and we learnt to supplement our abilities with tools (e.g. by writing things down to compensate for fallible memory), exponential improvement resulted in our capabilities. (I vaguely recall that one theory of how our brain got more complex was by learning to use tools that lead to improved diets, e.g. by breaking bones and accessing the marrow.) It seems much less likely we suddenly picked up an “intelligence gene” that no other creature has. Flies, rats, apes and humans are not that different in terms of basic building blocks.

When comparing humans to computers, one should not forget that humans require 21 or so years of boot-up time. And different humans have different strengths; not all are equally good at solving mathematical problems or engineering systems. An unpleasant a thought as it may be, consider an extraterrestrial who has a choice of building and programming computers or breeding and teaching humans. Which would be a better choice for the extraterrestrial wishing for help in solving problems? (Depending on the initial gene pool and initial population size, it might take 100 years before a human is bred that is good at a particular type of problem. Regardless, if starting from scratch, there is an unavoidable 15-20 year delay.)

Then there is the issue of what precisely smartness is. Smartness is defined by a social phenomenon. At a small scale, one just has to look at review committees and promotion panels to realise there is not always agreement on what is smart and what is not. More striking though, smartness is relative – humans compare with each other and with the world around them. There are infinitely more problems we cannot solve than we can solve, yet no one seems to conclude that we are therefore not smart. We look at what we *can* do and compare that with what others can do. In a similar vein, a computer can effortlessly produce millions and millions of theorems and proofs in that it could systematically piece axioms together to form true sentences, recording each new sentence as a “theorem” and the trail leading to it as a “proof”. Yet this would be dismissed immediately as not useful. So ‘usefulness to humans’ plays a role in defining smartness.

How do humans solve problems? Following again the principle of Occam’s Razor, the simplest hypothesis that comes to my mind involves the following factors. Most of our abilities come from having to compete in the world (think back thousands of years). Image processing is crucial, and as over half the brain is involved to some extent with vision, a large part of how we reason is visual. (Even if we do not explicitly form images in our minds, our subconscious is likely to be using similar circuitry.) We also need to be able to understand cause and effect — if I stand next to that lion, I will get eaten — which leads to the concept of thinking systematically. So my current hypothesis is that systematic thinking (including understanding cause and effect) and pattern recognition are the main players when it comes to reasoning. The mathematics and engineering we have developed, largely fits into this mould. Rigorous systemisation and writing down and sharing of results have lead to ‘amazing’ results that no single human could achieve (insufficient time!) but at each little step, ideas come from experience and nowhere else. Those that can calculate faster, are more perceptive, are more inquisitive, tend to find the “right” types of patterns, have greater focus and stamina, and are more attuned to what others may find interesting, have significant competitive advantages, but to rule a line and say computers can never do mathematics or engineering is unjustified. (The issue of creativity will be discussed in the next section.)

A final point before moving on. Speech recognition is very challenging for computers. Yet are we smart because we can understand speech? Speech was something created over time by humans for humans. Presumably grunts turned into a small vocabulary of words which grew into phrases and more complicated structures. The point though is that at no time could the process evolve to produce something humans couldn’t understand, because by definition, the aim was to communicate, and if communication was not working, another approach would be taken. If we could learn the languages of all extraterrestrials, perhaps we really are smart, but I’m skeptical.

## How can Computers be Made Smarter?

The three main characteristics of a computer system (i.e., something built to do speech recognition or solve mathematical problems) are its size (raw processing power), architecture (e.g., what parts can communicate with what other parts) and the software running on it.

Since humans tend to set the benchmark at what humans can do, a minimum amount of raw processing power is required before a computer can even hope to do something “smart”. Yet the architecture is even more important. Engineers currently do not build computers anything like the way nature builds brains. It is very likely that current computational architectures are ineffective for the types of pattern recognition the human brain engages in.

More interestingly, the architecture of the human brain evolves over time. In simple terms, it learns by changing its architecture. There are two obvious components; via DNA, natural selection increases the chances that a human is born with a ‘good’ architecture to start with. Then there is the long process of refining this architecture through everyday experiences and targeted learning (e.g., attending school).

There is nothing stopping us from building reconfigurable computers that are massively interconnected, thereby very crudely approximating the architecture of a brain. (I suspect this may involve a shift away from ‘reliable’ logic gates to logic gates (or equivalent) that work some but not all of the time, for there is a trade-off between density and reliability.)

With remarkable advances in technology, the real challenge looking forwards is the software side. Because we don’t understand precisely the sort of pattern recognition the brain uses to solve problems, and because until recently the technology was not there to build massively interconnected reconfigurable computers, no one has seriously tried to make a computer “smart” in the way I have been referring to in this essay. (This is not overlooking Artificial Intelligence whose approach was partly hampered by the available technology of the day, and which I suspect never delved deeper and deeper into how the brain does pattern recognition — once artificial neural networks came on the scene, there were sufficiently many research questions for AI researchers to chase that they did not continuously return to the biology to understand better and better how the brain does pattern recognition. And in fairness, as they lacked the computational power for hypothesis testing, it would most likely have been a futile endeavour anyway.)

Summarising this section, several points can be made. Current computing systems (which nevertheless serve the majority of their intended purposes extremely well) seem to be a ‘mismatch’ for doing what humans are good at doing, therefore, they come across as “dumb”. There is no evidence yet to suggest there is a barrier to building (this century) a computing system that is “smart” in some respects, but it will require a whole new approach to computing. It is not clear whether imitating the architecture of the human brain is the best thing to do, or if there is an even more efficient approach waiting to be discovered. Nevertheless, if smartness is being measured against what humans can do, a good starting point is starting with similar resources to what a human has.

Bringing in points from the preceding section, one must not forget though that humans have been ‘trained’ over centuries (natural selection), that each individual then takes an additional 21 years of training, during which time they are communicating with and learning from other individuals, and even then, we tend to work on the problems we believe we can solve and ignore the rest. This suggests we have a narrow definition of “smartness” and perhaps the only real way for a computer to be “smart” in our eyes is if it were to ‘grow up’ with humans and ‘learn’ (through daily feedback over 21 years) what humans value.

Indeed, smartness is usually linked with creativity and being able to solve “completely new” problems. (I would argue though that the problems we can solve are, by definition, not as distant from other problems we have solved before as we would like to think. Who knows how much the subconscious remembers that our conscious mind does not.) Creativity, even more than smartness, is linked to how humans perceive themselves relative to others. A random number generator is not creative. An abstract artist is. Some computer generated pictures coming from fractals or other mathematical constructs can be aesthetically pleasing to look at but is creativity involved once one realises a formulaic pattern is being followed? When it comes to problem solving, creativity and smartness come back largely to usefulness, or more generally, to some notion of value. We solve problems by instinctively knowing which of the thousands of possible approaches are most likely not to work, thereby leaving a manageable few options to work our way through. When we “create” a new theorem or engineer a new system, we are credited with creativity if it is both potentially useful (“sensible”?) and different from what has been done before. A random number generator succeeds at being different; the challenge is teaching a computer a sense of value; I suspect this is achievable by having computers interact with humans as described above (it is all just pattern recognition refined by external feedback!), and perhaps humans can even learn to write down systematically not just an algebraic proof of a mathematical result but also the “intuition” behind the proof, thereby enabling computers to learn like humans by studying how others solve problems.

## A Future Vision of Semi-automated Design

Although arguing that if we wanted computers to be smart then we are most likely going to be able to achieve that goal eventually, the more important question is whether we should be trying to head directly there. Personally, a more useful and more easily achievable goal is to work towards semi-automation and not full automation. At the moment there is essentially no way to guide a computer towards a goal; we run something, we wait, we get a result. Often we make a modification and try again. But we are not really interacting with the computer, just using it to shorten the time it takes for us to calculate something. By comparison, two people can work together on a design problem or a mathematical proof; there are periods when they work alone, but there are periods when they come together to discuss and get ideas from each other before going off to think on their own again. Semi-automation lies somewhere between these two extremes: the computer need not be “smart” like a human, but it should come across as being more than just a dumb calculator (even if, at the end of the day, all it is doing are calculations!).

Efficient exchange of information is vital. Computers can store more data than a brain can, but we can probe someone else’s brain for information much more efficiently than we can probe a computer’s memory banks. Largely this is because exchange of information is more efficient when there is shared knowledge that need not be explicitly transmitted.

### Semi-automated Theorem Proving

There are so many mistakes, both big and small, in the published literature (even the top journals) that it seems not only highly desirable but inevitable we will ultimately have all mathematical works stored on and verified by computers. This is certainly not a new dream, so how far are we from achieving it?

Although proof verification systems exist, otherwise simple proofs become excessively long when translated into a suitable form for the computer to check. Exchange of information is far from efficient! At the other extreme, automated theorem provers exist, but are yet to prove any theorems of substance. I propose the following stages of research.

1) Choose an area (e.g. basic set theory, or basic set theory and finite-dimensional linear algebra). Work towards devising a notation so that humans can enter a theorem and proof using a similar amount of effort to typing up the theorem and proof for a formal set of lecture notes. To improve efficiency, the notation does not need to be unambiguous since the computer can always ask for clarification if it cannot figure out the correct meaning. Similarly, the gaps between each step of the proof may not always be sufficiently small for the computer to be able to fill in, nevertheless, the computer should have a go, and ask for help (e.g., ask for a sub-step to be inserted) if it fails.

2) Enhance stage one above by having the computer give a list of suggestions whenever it gets stuck; it is easier for the user to click on the correct suggestion than to type in the answer, and if none of the suggestions are correct, the user can always fall back to entering the answer. Here, some method of ranking the suggestions is required (for otherwise there might be too many suggestions). Initially, this can be based on the computer determining “what we already know” and “what we want to find out”, then searching through the axioms and existing theorems to find something that relates either to “what we already know” (a possible ‘starting move’) or “what we want to find out” (a possible ending move).

3) Stage two will eventually prove inefficient as the number of theorems grows and the proofs become more complicated. Some sort of ‘learning’ and ‘intuition’ on behalf of the computer is unavoidable if humans and computers are to interact significantly more efficiently. Perhaps ultimately pattern recognition, as discussed in previous sections, becomes unavoidable, but one should not be too hasty in ruling out the possibility that a fair amount of intuition is more formulaic than we think. Stage three then is supplementing theorems and proofs with basic intuition. The first example that comes to mind is working with bounds, e.g., the triangle inequality. A computer can be taught that if it wants to prove x and y are close, then it can do this if it can find a point z that is close to x and also close to y. Or in another form (i.e., ), if the computer wants to show x and y are some distance apart, it can endeavour to do so by comparing the norm of x with the norm of y.

Certainly some proofs require deep intuition and ingenuity, but even then, a large part of the proof is generally fairly routine. Once a human has specified the “stepping stones”, the routine parts can be filled in (semi-)automatically by the computer working its way through its collection of routine moves and supplemented by basic intuition to rank the order in which it should try the moves.

Stages 1 to 3 are within our grasp and would already have a tremendous impact if they work as expected.

4) Stages 1 to 3 were concerned with a user stating a theorem and sketching a proof, with the aim that the computer can fill in the missing steps of the proof and thereby verify the correctness of the theorem, falling back to asking for more information if it gets stuck. Stage 4 is for the computer to work with a user in proving or disproving a theorem. That is, the user states a conjecture, then through a series of interactions with the computer, the user either finds a proof or a counterexample in a shorter time than if the user were to proceed unassisted. Refinement of the “intuition engine” may or may not be necessary. Some way for the user to suggest efficiently (minimum of keystrokes) to the computer what to try next is required. Some way for the computer to make suggestions to the user as to what to (and what not to) try next is required. [I omit my ideas for how to do this because they will most likely be superseded by the insight gained by anyone working through stages 1 to 3.]

5) The fifth stage is for computers to propose theorems of their own. In the first instance, they can look for repeated patterns used in proofs stored in its database. The examples that come to mind immediately are category theory and reproducing kernel Hilbert spaces. In part, these areas came into existence because mathematicians observed the same types of manipulations being carried out in different situations, identified the common threads and packaged them up into their own theory or “toolbox”.

### Semi-automated Chip Design

Engineers have long had the dream of being able to specify what they would like a software program or an electronic circuit to do, push a button, and have a computer generate the software or the circuit. Even more significant than saving time, if done properly, this would ensure the software (and possibly the circuit, although this is a bit harder to guarantee in more complicated situations when extra considerations such as EM interactions must be taken into account) is guaranteed to work correctly. There is a staggering amount of buggy software and hardware out there that this dream is becoming more and more desirable to achieve.

Basically, all the ideas discussed earlier are relevant here. Instead of a library of mathematical theorems, proofs and accompanying intuition being built up, a library of software or a library of electronic circuits is built up. Humans will always be part of the design loop, but more and more of the routine work can be carried out by a computer. Brute force algorithms and heuristics must be replaced by a way of encoding “intuition” and “lessons from past experience”, thereby allowing humans and computers to interact much more efficiently.

## Why does Compactness ensure a Bijective Map is a Homeomorphism?

The motivation for this exposition is threefold:

- It helps illustrate the mantra that intuition is as equally important as algebraic manipulation.
- It relates to a fundamental concept in mathematics, namely morphisms (from category theory).
- It helps explain why compact spaces and Hausdorff spaces are important.

The following facts are readily found in textbooks; the tenet of this exposition is that it is impossible, without further thought, to appreciate any of these facts.

A topological space is compact if every open cover has a finite subcover.

A topological space is Hausdorff if every two points can be separated by neighbourhoods.

A map (i.e., a continuous function) between topological spaces and is a homeomorphism if it is bijective and its inverse is continuous.

If is compact and is Hausdorff then a bijective map is automatically a homeomorphism.

Questions:

- How can a bijective map not be a homeomorphism?
- How can compactness possibly have any relevance to whether a map is a homeomorphism?
- Why the Hausdorff assumption on ?
- How does this relate to “morphisms”, as mentioned at the start of this exposition?

Before addressing these questions, a standard proof of the above result is given, the purpose being to emphasise that the proof, on its own, does not directly answer any of these questions. Memorising the proof is essentially worthless. (Important are being able to derive the proof from scratch and being able to understand why the result should indeed be true.)

Showing is continuous means showing the preimage of every open set is open, or equivalently, showing the preimage of every closed set is closed. Since is bijective, the preimage under of a set is simply . Hence it suffices to prove that is closed (the image of every closed set is closed). Let be closed. Since is compact, must be compact. The image of a compact set under a continuous function is itself compact, that is, is compact. A compact subset of a Hausdorff space must be closed, that is, is a closed subset of , proving is closed and therefore that is continuous, as required.

While basing topology on open sets works very well from the perspective of being able to give concise proofs such as the one above, it is perhaps the worst way of introducing topology. It is noteworthy that when topology was being developed, it took decades for the importance of “open sets” to be recognised.

Let’s start from scratch and try to understand things intuitively. One approach (but certainly not the only approach) to understanding a topological space is understanding what converges to what. In special cases, such as when the topology comes from a metric, it suffices to consider sequences (the curious reader may wish to read about sequential spaces). In general, nets must be considered instead of sequences, nevertheless, for the purposes of answering the questions above, it suffices to restrict attention to sequences. (It is often enough to understand intuitively why a result is true in special cases, leaving the proof to justify the result in full generality.)

## Why a Bijective Map need not be a Homeomorphism

By restricting attention to sequences (and therefore to nice topological spaces), the definition of continuity becomes: is continuous if, whenever , it holds that . Therefore, a bijective map is a homeomorphism if and only if implies .

Whereas bijectivity just tests whether distinct points are mapped to distinct points, being a homeomorphism means nearby points must be mapped to nearby points, in both directions, from to and from to . (That is, a homeomorphism preserves the topology.)

This suggests the following example. Let be the interval and let be the unit circle . Let be the function sending to . Then is continuous because it sends nearby points in to nearby points in . But is not continuous because the point is sent to the point but a point just below , say for just less than , is sent to a point far away from . (The reader should pause to understand this fully; drawing a picture may help.)

The above example is quintessential; an injective map is a homeomorphism only if it is not possible to map a “line ” to a “loop “. In detail, let be a sequence of points that either does not have a limit point, or that converges to a point that is different from . Such a sequence can be obtained by considering the location at regularly spaced intervals of an ant walking along a path in that does not eventually return to where it started. It is therefore referred to loosely as a “line”. Let it loosely be said that this “line” gets mapped to a “loop” if . If it is possible for a line to be mapped to a loop, then cannot be a homeomorphism. (Draw some pictures!)

To summarise, injectivity of means that if then . For to be a homeomorphism requires more: if then it must be that . Whereas injectivity just means the preimages of distinct points are distinct, a homeomorphism means *the preimages of convergent sequences with distinct limits are convergent sequences with distinct limits.* Perhaps the best way of visualising this though is asking whether a “line” can be mapped to a “loop”.

Relevance of the Domain being Compact and the Codomain being Hausdorff

Let be a “line”, as defined above. There are two cases to consider: either does not have a limit point, in which case it will be seen that compactness of is relevant, or has a limit, in which case it will be seen that being Hausdorff is significant.

When dealing with sequences, the role of compactness is guaranteeing every sequence has a limit point (or equivalently, that a convergent subsequence exists). Therefore, if is compact, it is not possible for to lack a limit point, and this option is immediately off the table.

If it is possible for a “line” to be mapped to a “loop” despite being compact then it is possible to achieve this assuming has a limit (by considering a convergent subsequence if necessary). Henceforth, assume yet . Continuity of implies . When dealing with sequences, the role of the Hausdorff requirement is to ensure limits are unique. (Prove this for yourself, or look up a proof that limits are unique in Hausdorff spaces.) Therefore, being Hausdorff means since converges to both and . Since is injective, this means , contradicting being a “line”. Therefore, it is impossible for a “line” to be mapped to a “loop”; every injective map from a compact space to a Hausdorff space is automatically a homeomorphism.

The above has hopefully taken away a bit of the mystery of why compactness and the Hausdorff condition enter into the picture.

- An injective map (on a nice topological space where it suffices to reason with sequences) is a homeomorphism if and only if it is not possible for a “line ” to be mapped to a “loop “. (A line and a loop are topologically distinct whereas the purpose of a homeomorphism is to preserve topological structure.)
- If is a loop in , that is, , then consider its preimage . Unless there is some reason for to converge, the fact that is injective is powerless to prevent from being a “line”, i.e., it may well be the case that is not a homeomorphism.
- If is compact then has a limit point. By considering a subsequence if necessary, assume without loss of generality that . Continuity of implies .
- If is Hausdorff then limits are unique, therefore, . Therefore, the preimage of a loop is a loop, not a line. The topology has been preserved, hence is a homeomorphism.
- The above is “intuitively” why the result holds, yet the formal proof based on open sets is shorter, more general but devoid of intuition (at least for beginners); this is the joy of mathematics.

## Morphisms

Very briefly, it is remarked that structure-preserving functions are called morphisms (in category theory). Two sets are equivalent if there exists a bijective function between them. As more structure is given to these sets, requirements stronger than just bijectivity are necessary if the structure is to be preserved.

In linear algebra, two vector spaces are the same if there exists a bijective function between them that is linear and whose inverse is linear; the linearity of and is what preserves the structure. Interestingly, if is linear and bijective then its inverse is automatically linear.

In topology, a continuous function preserves structure in one direction, therefore, to preserve structure in both directions requires a bijective that is continuous and whose inverse is also continuous; as introduced earlier, such a function is called a homeomorphism. Unlike the linear case, being bijective and continuous is not enough to imply is continuous.

## Countable Intersections and Unions of Sets: A Discussion on an Example in Williams “Probability with Martingales”

As homework for students, I recently set the task of understanding the Example/Warning in Section 1.11 of Williams’ book “Probability with Martingales“. I provide here my own ‘solution’ to this homework exercise. There is no need to refer to Williams’ book as the following is self-contained.

Let be the set of rational numbers between 0 and 1 inclusive; because the rational numbers are countable, they can be enumerated as . Define the sets . Here, is the open interval of width centred at the rational number , and intersecting it with the closed interval simply eliminates any “end effects” by keeping all sets within . For a fixed , note that monotonically decreases to as . In particular, .

Of interest is what the set looks like. A straightforward calculation shows , but do you think , or , or something else? Is ?

For any finite and , . Believing this to continue to hold in the limit as is a flawed argument for . (Note: normally, union and intersection cannot be interchanged, but here, the sets are decreasing in . In particular, .) To see the difference between the finite and infinite cases, note that being an element of means precisely that , such that . Here, a subscript adorns to emphasise that the choice of is allowed to depend on . That is an element of means precisely that , , . The key difference is that here, a single must work for all . In the finite case, the choice works for all . If is infinite though, there is no such thing as that could serve in place of .

A flawed argument for can be based on the denseness of rationals: every is the limit of a sequence of rational numbers, and since contains not only every rational number, but also a neighbourhood of every rational number, it “must” therefore contain all numbers in . It is insightful to understand where the flaw is. Let be an irrational number. Let be an increasing sequence of indices such that . **Whether depends on which is faster: the convergence of , or the convergence of .** To illustrate, assume that . (For pedants, interpret this equality as approximate equality; the difference between a rational and irrational number cannot exactly equal a rational number.) Then even though , the convergence is sufficiently slow that for all . (Note because .)

The pendulum swings back: perhaps then because no sequence can converge sufficiently quickly to an irrational number? To demonstrate that this is false, consider the following procedure for choosing to ensure that . It suffices to construct a sequence that converges quickly to because the remaining rational numbers can be assigned (in arbitrary order) to . Simply choose , for odd, to be a rational number within of . (This can always be arranged by taking sufficiently many terms in the decimal expansion of .) Then, no matter how large is chosen, when is an odd number greater than , hence .

The above has already demonstrated that limits cannot be interchanged; a sequence of rational numbers was constructed such that is in and hence . This is not the argument used by Williams, but being constructive in nature might mean it is a more transparent argument.

The higher-level argument in Williams’ book reveals more information about . Williams uses the Baire category theorem to deduce that must be uncountable, hence regardless of how are chosen. Furthermore, the Lebesgue measure of is easily shown to be zero, therefore, does not contain any open intervals, and in particular . (Proof: the Lebesgue measure of is at most . Since , the Lebesgue measure of is at most . As , this goes to zero, hence the measure of must be zero.)

For completeness, the fact that is uncountable will be derived. The trick is to consider the complement . If it can be shown that the complement is “too small” then must be uncountable. De Morgan’s law implies that . (Exercise: prove from first principles that .) Let . Since contains all the rational numbers, can contain only irrational numbers. In particular, does not contain any open interval. Each is open and hence is open. Thus, is a closed set not containing any open intervals. Such sets are called nowhere dense. Since is the countable union of nowhere dense sets, it is a meagre set. If is countable then it too would be meagre, and hence would be meagre. Yet , and is a Baire space, meaning meagre sets are “small”. In particular, the whole space cannot be meagre, a contradiction. Therefore, must be uncountable.

The conclusion then is that depends on the actual ordering of the rationals, yet regardless of how the rationals are ordered, will be an uncountable set of Lebesgue measure zero. In particular, .