Analysis · Mathematics

Banach Fix Point Theorem

Banach fix point theorem is a very powerful tool in mathematics, in particular, in functional analysis and in operator theory. I was studying for functional analysis earlier this weekend and came across it once again, even though I did not see it coming. We will first look at a few definitions, and then the theorem itself.

Let (X,d) be a metric space. A map T:X \to X is called a contraction if  d(T(x),T(y)) \le d(x,y); it is called a strict contraction the inequality is strict, or equivalently, if there exists k \in [0,1) such that d(T(x),T(y)) = k d(x,y).

As the name suggest, Banach fixed point theorem is a tool to find fix points for contraction mappings in complete metric space, and hence Banach spaces. The statement of the theorem is as follows:

Suppose (X,d) is a complete metric space. If T:X \to X is a strict contraction, then there exists a unique x^* \in X such that T(x^*) = x^*. Furthermore, for any $x_0 \in X$, if we set x_n = T(x_{n-1}) for all n \in \mathbb{N}, then \lim_{n \in \mathbb{N}} x_n = x^*.

The proof on Wikipedia is pretty concise, so we will not talk about it here.  It is often used in differential equations to find fixed points of the equation itself. There is yet another clever application that I encounter earlier this weekend, it is used in a theorem by Stampacchia in functional analysis. Maybe we will talk about it next time.

Mathematics · Topology

Dense and Nowhere Dense Sets

Found a neat properties for dense and nowhere dense sets in functional analysis assignments recently. Suppose (X,\tau) is a topological space, and A \subseteq X is an arbitrary subset. We say that A is dense if the closure is the whole space itself, i.e. \bar{A} = X; we say that A is nowhere dense if the interior of its closure is empty, i.e. \mathring{\bar{A}} = \emptyset.

Now, we can also think about closures and interiors in terms of their complement. We shall denote by X \setminus A to be the complement of A instead of the usual A^C; the reason is obvious once we get to the main part, I promise.

Usually in topology, the interior and closure of a set A, are defined to be the union of all open sets contained in A, and the intersection of all closed sets containing A respectively; in other words, they are the largest open set contained in A, and the smallest closed set that contains A respectively. In terms of complement, we have the interior \mathring{A} = X \setminus \bar{A} and \bar{A} = (X \setminus A)^{\circ}, this is not hard to prove.

If A is dense, then the complement has empty interior. We have

\bar{A} = X \iff X \setminus \bar{A} = \emptyset \iff (X \setminus A)^{\circ} = \emptyset

This is not surprising and is pretty standard. On the other hand, we claim that A is nowhere dense if and only if its complement contains an open dense subset of X. This is slightly more work, we have

\mathring{\bar{A}} = \emptyset \iff \bar{X \setminus \bar{A}} = X \iff \bar{(X \setminus A)^{\circ}} = X \iff  (X \setminus A)^{\circ} = X

And since the interior itself is an open set, hence (X \setminus A)^{\circ} is the open dense subset we desired.

This is pretty useful result when trying to prove Baire Category’s Theorem, or for an application of the Baire’s Category Theorem. All the best doing your assignments!

Game Theory · Information Theory

The Devil’s Chessboard (Problem)


The Devil’s Chessboard is an information theory problem in game theoretic setting. As one may or may not have  heard before, the Devil’s Chessboard is a rather intimidating problem, or at least when one first learns about the problem. If one attempts to play the game (with the Devil) without any kind of strategy or by using pure luck, it is rather impossible to win the game as the probability of choosing the correct move is \frac{1}{64} (or about 1.56\%).

Furthermore, the problem can be extended to larger grids, which decreases the chance of choosing the correct move exponentially, if we choose to play the game by using only luck. In fact, some of these game theoretic problems does not even have a winning strategy (Note: Simply put, a winning strategy is a strategy in which the player(s) is(are) guaranteed to win.); in case a winning strategy exists, what is it; if the winning strategy does not exists, what is the best strategy to tackle the problem. In this article, we are going to examine the Devil’s Chessboard, and come up with the best strategy to play the game.

The Game Setting

Imagine this. You and a friend both studies mathematics in your undergraduate studies.  Envying your ability to reason, God decided to send both of you to the Devil. Contrary to the legend, the Devil did not send both of you to burn for eternity immediately. Instead, he would like to play a game with you. If both of you win the game, then you will be released and proceed with life. Otherwise, you will suffer for the rest of the eternity.

The game is as follows: there is an isolated room in which no communication to the outside realm is possible. In the center, there is a table, and on top of the table there is a 8 \times 8 chessboard. You and your friend are to follow the Devil one at a time into the room, where further actions will be taken. For simplicity, we will refer to A and B as first and second person that enters the room respectively.

Once A and the Devil are in the room, the Devil will perform the following steps:

  1. Seal the door (presumably with magic) so that no communication to the outside world is possible.
  2. Make 64 coins identical in colour, weight, etc magically appear on top each square of the chessboard; since it is done by magic, you cannot interfere with this process.
  3. The Devil then points at a square at random, and mark the position of the square on the chessboard as a proof; of course, the mark is invisible to human naked eye until the game is over.
  4. A is allowed to flip one coin on the chessboard, should s/he chooses to.
  5. A will be lead out of the room to avoid any form of collusion with $B$.

During this whole process, A is to remain silent, otherwise both of the players will be sent to Hell for eternity immediately.

Now B will enter the room with the Devil. After the Devil seals the room (again, with magic), B will get a chance to examine the board and then to pick a square on the board. If s/he choose the exact same square the Devil did, then both players are released immediately. Otherwise, both of you go to Hell. Finally, the Devil agrees that he will not cheat by manipulating the marked square; hoping that you succeed and to annoy God, the Devil allows you and your friend to have a discussion to come up with a strategy before the game starts.

Is there a winning strategy in which you and your friend will be guaranteed freedom? If there is, can you find out what the strategy is? If not, what would be the best strategy to maximize the probability of escaping Hell? The solutions will be posted next time.

Mathematics · Topology

Cocountable Topology

Given a space X, there are many ways to define a topology. More common methods are one of the following:

  • explicitly list out all the open sets
  • define the rules for a subset U \subseteq X to be open
  • define the basis/subbasis of the topology (Note: The basis here refers to topological basis, this is different than a vector space basis that we have learnt in linear algebra.)

More often than not, we will work with topological spaces that has infinitely many open sets. In this case it will be hard to explicitly list out all the open sets in the topological space. In this post, we will look at a topology call cocountable topology, and luckily, we can describe the open set of this topology, thus we do not need to describe a topological basis.

Given a ground set X, the cocountable topology \tau on X is the empty set together with the collection of subsets U \subseteq X such that X \setminus U is countable, namely the complement of U is countable. For example, if X = \{1,2,3\}, then under the cocountable topology, none of the subsets of X is open.

Now let’s assume that X is an uncountable set.  By definition, \emptyset, X \in \tau. Then, let \{U_{\lambda}\}_{\lambda \in \Lambda} \subseteq \tau be a collection of open sets in X for some index set \Lambda. Thus X \setminus U_{\lambda} is countable for all \lambda \in \Lambda. Now consider

X \setminus \bigcup_{\lambda \in \Lambda} U_{\lambda} = \bigcap_{\lambda \in \Lambda} [X \setminus U_{\lambda}] \subseteq X \setminus U_{\lambda_0}

by De Morgan’s law, where \lambda_0 \in \Lambda is arbitrary. Since X \setminus U_{\lambda} is countable for all $\lambda \in \Lambda$ and intersections will only result in smaller set, therefore X \setminus \bigcup_{\lambda \in \Lambda} U_{\lambda} must be countable. Thus we may conclude that \bigcup_{\lambda \in \Lambda} U_{\lambda} \in \tau.

Finally, let \{U_i\}_{i=1}^{n} \subseteq X be a finite collection. Then by De Morgan’s law, we have X \setminus \bigcap_{i=1}^{n} U_i = \bigcup_{i=1}^{n} (X \setminus U_i). Notice that finite union of countable sets is still countable (in fact, countable union of countable sets is countable), thus X \setminus \bigcap_{i=1}^{n} U_i is countable and \bigcap_{i=1}^{n} U_i \in \tau.

Therefore \tau is indeed a topology.


Mathematics · Topology

The Intersection of Topologies result in a Topology

Topology is the study of invariant properties of mathematical objects. Through the study of topology, mathematicians to translate properties between mathematical objects. There are many different subfields of topology, e.g. general topology (a.k.a. point-set topology), algebraic topology, etc. Unfortunately (or fortunately?), I have only encountered general topology in my undergraduate degree.

Perhaps one interesting (basic) result in topology is as follows

Given a space X and a collection of topologies \tau_i, where i \in I and I is an index set, the intersection \bigcap_{i \in I} \tau_i is also a topology on X.

Given a collection of objects that share property a property, let’s say property a, we do not expect the union and intersection of this collection to share the same properties. For instance, the set \{n\}, where n is an integer, is finite. But when you take the union of all singleton set (namely \{n\}), we have an infinite set.

So why is the above statement true? To prove this, we need need at least the definition of a topology, so here it goes:

Let X be a set, and \mathcal{P}(X) be its power set. A subset \tau \subseteq \mathcal{P}(X) is called a topology if the following conditions hold:

  1. \emptyset, X \in \tau
  2. Arbitrary union of elements of \tau is also an element of \tau, i.e. \bigcup_{\lambda \in \Lambda} U_{\lambda} \in \tau where U_{\lambda} \in \tau is arbitrarily chosen.
  3. Finite intersection of elements of \tau is also an element of \tau, i.e. if n \in \mathbb{Z}, then \bigcap_{i=1}^n U_{i} \in \tau where U_{i} \in \tau is arbitrarily chosen

So far so good. Now that we know the definition of a topology, we can easily see that the union of topologies is NOT a topology; consider X = \{a,b,c\}, and we have two topologies \tau_1 = \{\emptyset, \{a\}, X\} and \tau_2 = \{\emptyset, \{b\}, X\}, then the union is

\tau_1 \cup \tau_2 = \{\emptyset, \{a\},\{b\},X\}

This violates the arbitrary union property; \{a\} and \{b\} are elements of the union, but \{a\} \cup \{b\} = \{a,b\} is not. Note that this is not to say that all unions of topologies does not result in a topology; it is only the counterexample to the claim that all unions of topologies gives a topology.

We have shown above that the union of topologies itself need not be a topology. So why is the intersection of of topologies is itself a topology? Clearly, by definition of topology, each topology includes the sets \emptyset and X, thus the empty set \emptyset and X is in the intersection. Now let I be an index set, and for i \in I, U_{i} \in \bigcap_{\lambda \in \Lambda} \tau_{\lambda} be an arbitrary family of elements in the intersection of the topologies. Then by definition of topology, arbitrary unions of elements in \{U_i\}_{i \in I} is also in \tau_{\lambda} for all \lambda \in \Lambda. Thus the arbitrary union is also an element of \bigcap_{\lambda \in \Lambda} \tau_{\lambda}. By similar reasoning, we can also conclude that finite intersection of elements in \bigcap_{\lambda \in \Lambda} \tau_{\lambda} is also an element of \bigcap_{\lambda \in \Lambda} \tau_{\lambda} itself. Thus \bigcap_{\lambda \in \Lambda} \tau_{\lambda} is a topology.

Graph Theory · Mathematics

Hypergraphs: Introduction

Graph theory is the study of graphs, which can be used to model relationships, routes, etc. People understands a lot about graphs. However, there is a generalisation of graph theory that we can talk about – the hypergraphs!
Like graph theory, hypergraphs contains vertices, denoted by V, and edges which we call hyperedges, denoting E. Instead of connecting two vertices u,v \in V, a hyperedge e \in E connects any subset of V, i.e. e is an element of the power set of the vertices.

Intuitively, hypergraphs are just a set of vertices, and hyperedges are lines that connects some vertices together. For instance, the n \times n grid is a hyper graph, with n^2 vertices and 2n hyperedges. In the n \times n grid, each pair of hyperedges, e,e' \in E intersects at a vertex v \in V uniquely. Another example of a hypergraph is the Fano plane, which is the hypergraph below

Fano Plane

As we can see, there are seven vertices in total in the hypergraph above. There are also seven hyperedges in the hypergraph above, each hyperedge is represented by a unique colour itself.

We can also talk about the properties of a hypergraph just as we do in normal graphs. Recall that in a graph, we say that a graph is k-regular if each vertex has exactly degree k. Similarly, a hypergraph is k-regular if for each vertex in the hypergraph, the degree of the vertex (number of lines that pass through a vertex) is exactly degree k. So a n \times n-grid is 2-regular, and the Fano plane is 3-regular.

Another interesting property that we want to inherit from graph theory is the dual. Amazingly, basic properties of duality that we learn from normal graph theory is also true for hypergraphs. Perhaps the most important such property is that G^{**} \cong G for any hypergraph G, where G^* denotes the dual graph of the graph G. This is another post for another time.

There are many other types of hypergraphs, and they are used in many ways. Hopefully this post helps you with some intuition in hypergraphs.