You are currently browsing the category archive for the ‘math.GN’ category.

The following question came up in my 245A class today:

Is it possible to express a non-closed interval in the real line, such as [0,1), as a countable union of disjoint closed intervals?

I was not able to answer the question immediately, but by the end of the class some of the students had come up with an answer.  It is actually a nice little test of one’s basic knowledge of real analysis, so I am posing it here as well for anyone else who is interested.  Below the fold is the answer to the question (whited out; one has to highlight the text in order to read it).

Read the rest of this entry »

In topology, a non-empty set {E} is said to be connected if cannot be decomposed into two nontrivial subsets that are both closed and open relative to {E}, and path connected if any two points {x,y} in {E} can be connected by a path (i.e. there exists a continuous map {\gamma: [0,1] \rightarrow E} with {\gamma(0)=x} and {\gamma(1)=y}).

Path-connected sets are always connected, but the converse is not true, even in the model case of compact subsets of a Euclidean space. The classic counterexample is the set

\displaystyle  E := \{ (0,y): -1 \leq y \leq 1 \} \cup \{ (x, \sin(1/x)): 0 < x \leq 1 \}, \ \ \ \ \ (1)

which is connected but not path-connected (there is no continuous path from {(0,1)} to {(1,\sin(1))}).

Looking at the definitions of the two concepts, one notices a difference: the notion of path-connectedness is somehow a “positive” one, in the sense that a path-connected set can produce the existence of something (a path connecting two points {x} and {y}) for a given type of input (in this case, a pair of points {x, y}). On the other hand, the notion of connectedness is a “negative” one, in that it asserts the non-existence of something (a non-trivial partition into clopen sets). To put it another way, it is relative easy to convince someone that a set is path-connected (by providing a connecting path for every pair of points) or is disconnected (by providing a non-trivial partition into clopen sets) but if a set is not path-connected, or is connected, how can one easily convince someone of this fact? To put it yet another way: is there a reasonable certificate for connectedness (or for path-disconnectedness)?

In the case of connectedness for compact subsets {E} of Euclidean space, there is an answer as follows. If {\epsilon > 0}, let us call two points {x, y} in {E} {\epsilon}-connected if one can find a finite sequence {x_0 = x, x_1, \ldots, x_N = y} of points in {E}, such that {|x_{i+1}-x_i| < \epsilon} for all {0 \leq i < N}; informally, one can jump from {x} to {y} in {E} using jumps of length at most {\epsilon}. Let us call {x_0,\ldots,x_N} an {\epsilon}-discrete path.

Proposition 1 (Connectedness certificate for compact subsets of Euclidean space) Let {E \subset {\bf R}^d} be compact and non-empty. Then {E} is connected if and only if every pair of points in {E} is {\epsilon}-connected for every {\epsilon > 0}.

Proof: Suppose first that {E} is disconnected, then {E} can be partitioned into two non-empty closed subsets {F, G}. Since {E} is compact, {F, G} are compact also, and so they are separated by some non-zero distance {\epsilon > 0}. But then it is clear that points in {F} cannot be {\epsilon}-connected to points in {G}, and the claim follows.

Conversely, suppose that there is a pair of points {x,y} in {E} and an {\epsilon > 0} such that {x,y} are not {\epsilon}-connected. Let {F} be the set of all points in {E} that are {\epsilon}-connected to {x}. It is easy to check that {F} is open, closed, and a proper subset of {E}; thus {E} is disconnected. \Box

We remark that the above proposition in fact works for any compact metric space. It is instructive to see how the points {(1,\sin(1))} and {(0,1)} are {\epsilon}-connected in the set (1); the {\epsilon}-discrete path follows the graph of {\sin(1/x)} backwards until one gets sufficiently close to the {y}-axis, at which point one “jumps” across to the {y}-axis to eventually reach {(0,1)}.

It is also interesting to contrast the above proposition with path connectedness. Clearly, if two points {x, y} are connected by a path, then they are {\epsilon}-connected for every {\epsilon > 0} (because every continuous map {\gamma: [0,1] \rightarrow E} is uniformly continuous); but from the analysis of the example (1) we see that the converse is not true. Roughly speaking, the various {\epsilon}-discrete paths from {x} to {y} have to be “compatible” with each other in some sense in order to synthesise a continuous path from {x} to {y} in the limit (we will not make this precise here).

But this leaves two (somewhat imprecise) questions, which I do not know how to satisfactorily answer:

Question 1: Is there a good certificate for path disconnectedness, say for compact subsets {E} of {{\bf R}^d}? One can construct lousy certificates, for instance one could look at all continuous paths in {{\bf R}^d} joining two particular points {x, y} in {E}, and verify that each one of them leaves {E} at some point. But this is an “uncountable” certificate – it requires one to check an uncountable number of paths. In contrast, the certificate in Proposition 1 is basically a countable one (if one describes a compact set {E} by describing a family of {\epsilon}-nets for a countable sequence of {\epsilon} tending to zero). (Very roughly speaking, I would like a certificate that can somehow be “verified in countable time” in a suitable oracle model, as discussed in my previous post, though I have not tried to make this vague specification more rigorous.)

It is tempting to look at the equivalence classes of {E} given by the relation of being connected by a path, but these classes need not be closed (as one can see with the example (1)) and it is not obvious to me how to certify that two such classes are not path-connected to each other.

Question 2: Is there a good certificate for connectedness for closed but unbounded closed subsets of {{\bf R}^d}? Proposition 1 fails in this case; consider for instance the set

\displaystyle  E := \{ (x,0): x \in {\bf R} \} \cup \{ (x,\frac{1}{x}): x > 0 \}. \ \ \ \ \ (2)

Any pair of points {x,y \in E} is {\epsilon}-connected for every {\epsilon > 0}, and yet this set is disconnected.

The problem here is that as {\epsilon} gets smaller, the {\epsilon}-discrete paths connecting a pair of points such as {(1,0)} and {(1,1)} have diameter going to infinity. One natural guess is then to require a uniform bound on the diameter, i.e. that for any pair of points {x, y}, there exists an {R>0} such that there is an {\epsilon}-discrete path from {x} to {y} of diameter at most {R} for every {\epsilon > 0}. This does indeed force connectedness, but unfortunately not all connected sets have this property. Consider for instance the set

\displaystyle  E := \{ (x,y,0): x \in {\bf R}, y \in \pm 1 \} \cup \bigcup_{n=1}^\infty (E_n \cup F_n) \ \ \ \ \ (3)

in {{\bf R}^3}, where

\displaystyle E_n := \{ (x,y,0): \frac{x^2}{n^2} + \frac{y^2}{(1-1/n)^2} = 1\}

is a rectangular ellipse centered at the origin with minor diameter endpoints {(0,1/n-1), (0,1-1/n)} and major diameter endpoints {(-n,0), (n,0)}, and

\displaystyle F_n := \{ (n,y,z): (y-1/2)^2+z^2=1/4 \}

is a circle that connects the {(n,0)} endpoint of {E_n} to the point {(n,1)} in {E}. One can check that {E} is a closed connected set, but the {\epsilon}-discrete paths connecting {(0,-1)} with {(0,+1)} have unbounded diameter as {\epsilon \rightarrow 0}.

Currently, I do not have any real progress on Question 1. For Question 2, I can only obtain the following strange “second-order” criterion for connectedness, that involves an unspecified gauge function {\delta}:

Proposition 2 (Second-order connectedness certificate) Let {E} be a closed non-empty subset of {{\bf R}^d}. Then the following are equivalent:

  • {E} is connected.
  • For every monotone decreasing, strictly positive function {\delta: {\bf R}^+ \rightarrow {\bf R}^+} and every {x,y \in E}, there exists a discrete path {x_0=x,x_1,\ldots,x_N=y} in {E} such that {|x_{i+1}-x_i| < \delta(|x_i|)}.

Proof: This is proven in almost the same way as Proposition 1. If {E} can be disconnected into two non-trivial sets {F, G}, then one can find a monotone decreasing gauge function {\delta: {\bf R}^+ \rightarrow {\bf R}^+} such that for each ball {B_R := \{ x \in {\bf R}^d: |x| \leq R \}}, {F \cap B_R} and {G} are separated by at least {\delta(R)}, and then there is no discrete path from {F} to {G} in {E} obeying the condition {|x_{i+1}-x_i| < \delta(|x_i|)}.

Conversely, if there exists a gauge function {\delta} and two points {x,y \in E} which cannot be connected by a discrete path in {E} that obeys the condition {|x_{i+1}-x_i| < \delta(|x_i|)}, then if one sets {F} to be all the points that can be reached from {x} in this manner, one easily verifies that {F} and {E \backslash F} disconnect {E}. \Box

It may be that this is somehow the “best” one can do, but I am not sure how to quantify this formally.

Anyway, I was curious if any of the readers here (particularly those with expertise in point-set topology or descriptive set theory) might be able to shed more light on these questions. (I also considered crossposting this to Math Overflow, but I think the question may be a bit too long (and vague) for that.)

(The original motivation for this question, by the way, stems from an attempt to use methods of topological group theory to attack questions in additive combinatorics, in the spirit of the paper of Hrushovski studied previously on this blog. The connection is rather indirect, though; I may discuss this more in a future post.)

One way to study a general class of mathematical objects is to embed them into a more structured class of mathematical objects; for instance, one could study manifolds by embedding them into Euclidean spaces. In these (optional) notes we study two (related) embedding theorems for topological spaces:

Read the rest of this entry »

A key theme in real analysis is that of studying general functions {f: X \rightarrow {\bf R}} or {f: X \rightarrow {\bf C}} by first approximating them by “simpler” or “nicer” functions. But the precise class of “simple” or “nice” functions may vary from context to context. In measure theory, for instance, it is common to approximate measurable functions by indicator functions or simple functions. But in other parts of analysis, it is often more convenient to approximate rough functions by continuous or smooth functions (perhaps with compact support, or some other decay condition), or by functions in some algebraic class, such as the class of polynomials or trigonometric polynomials.

In order to approximate rough functions by more continuous ones, one of course needs tools that can generate continuous functions with some specified behaviour. The two basic tools for this are Urysohn’s lemma, which approximates indicator functions by continuous functions, and the Tietze extension theorem, which extends continuous functions on a subdomain to continuous functions on a larger domain. An important consequence of these theorems is the Riesz representation theorem for linear functionals on the space of compactly supported continuous functions, which describes such functionals in terms of Radon measures.

Sometimes, approximation by continuous functions is not enough; one must approximate continuous functions in turn by an even smoother class of functions. A useful tool in this regard is the Stone-Weierstrass theorem, that generalises the classical Weierstrass approximation theorem to more general algebras of functions.

As an application of this theory (and of many of the results accumulated in previous lecture notes), we will present (in an optional section) the commutative Gelfand-Neimark theorem classifying all commutative unital {C^*}-algebras.

Read the rest of this entry »

A normed vector space {(X, \| \|_X)} automatically generates a topology, known as the norm topology or strong topology on {X}, generated by the open balls {B(x,r) := \{ y \in X: \|y-x\|_X < r \}}. A sequence {x_n} in such a space converges strongly (or converges in norm) to a limit {x} if and only if {\|x_n-x\|_X \rightarrow 0} as {n \rightarrow \infty}. This is the topology we have implicitly been using in our previous discussion of normed vector spaces.

However, in some cases it is useful to work in topologies on vector spaces that are weaker than a norm topology. One reason for this is that many important modes of convergence, such as pointwise convergence, convergence in measure, smooth convergence, or convergence on compact subsets, are not captured by a norm topology, and so it is useful to have a more general theory of topological vector spaces that contains these modes. Another reason (of particular importance in PDE) is that the norm topology on infinite-dimensional spaces is so strong that very few sets are compact or pre-compact in these topologies, making it difficult to apply compactness methods in these topologies. Instead, one often first works in a weaker topology, in which compactness is easier to establish, and then somehow upgrades any weakly convergent sequences obtained via compactness to stronger modes of convergence (or alternatively, one abandons strong convergence and exploits the weak convergence directly). Two basic weak topologies for this purpose are the weak topology on a normed vector space {X}, and the weak* topology on a dual vector space {X^*}. Compactness in the latter topology is usually obtained from the Banach-Alaoglu theorem (and its sequential counterpart), which will be a quick consequence of the Tychonoff theorem (and its sequential counterpart) from the previous lecture.

The strong and weak topologies on normed vector spaces also have analogues for the space {B(X \rightarrow Y)} of bounded linear operators from {X} to {Y}, thus supplementing the operator norm topology on that space with two weaker topologies, which (somewhat confusingly) are named the strong operator topology and the weak operator topology.

Read the rest of this entry »

One of the most useful concepts for analysis that arise from topology and metric spaces is the concept of compactness; recall that a space {X} is compact if every open cover of {X} has a finite subcover, or equivalently if any collection of closed sets with the finite intersection property (i.e. every finite subcollection of these sets has non-empty intersection) has non-empty intersection. In these notes, we explore how compactness interacts with other key topological concepts: the Hausdorff property, bases and sub-bases, product spaces, and equicontinuity, in particular establishing the useful Tychonoff and Arzelá-Ascoli theorems that give criteria for compactness (or precompactness).

Exercise 1 (Basic properties of compact sets)

  • Show that any finite set is compact.
  • Show that any finite union of compact subsets of a topological space is still compact.
  • Show that any image of a compact space under a continuous map is still compact.

Show that these three statements continue to hold if “compact” is replaced by “sequentially compact”.

Read the rest of this entry »

The notion of what it means for a subset E of a space X to be “small” varies from context to context.  For instance, in measure theory, when X = (X, {\mathcal X}, \mu) is a measure space, one useful notion of a “small” set is that of a null set: a set E of measure zero (or at least contained in a set of measure zero).  By countable additivity, countable unions of null sets are null.  Taking contrapositives, we obtain

Lemma 1. (Pigeonhole principle for measure spaces) Let E_1, E_2, \ldots be an at most countable sequence of measurable subsets of a measure space X.  If \bigcup_n E_n has positive measure, then at least one of the E_n has positive measure.

Now suppose that X was a Euclidean space {\Bbb R}^d with Lebesgue measure m.  The Lebesgue differentiation theorem easily implies that having positive measure is equivalent to being “dense” in certain balls:

Proposition 1. Let E be a measurable subset of {\Bbb R}^d.  Then the following are equivalent:

  1. E has positive measure.
  2. For any \varepsilon > 0, there exists a ball B such that m( E \cap B ) \geq (1-\varepsilon) m(B).

Thus one can think of a null set as a set which is “nowhere dense” in some measure-theoretic sense.

It turns out that there are analogues of these results when the measure space X = (X, {\mathcal X}, \mu)  is replaced instead by a complete metric space X = (X,d).  Here, the appropriate notion of a “small” set is not a null set, but rather that of a nowhere dense set: a set E which is not dense in any ball, or equivalently a set whose closure has empty interior.  (A good example of a nowhere dense set would be a proper subspace, or smooth submanifold, of {\Bbb R}^d, or a Cantor set; on the other hand, the rationals are a dense subset of {\Bbb R} and thus clearly not nowhere dense.)   We then have the following important result:

Theorem 1. (Baire category theorem). Let E_1, E_2, \ldots be an at most countable sequence of subsets of a complete metric space X.  If \bigcup_n E_n contains a ball B, then at least one of the E_n is dense in a sub-ball B’ of B (and in particular is not nowhere dense).  To put it in the contrapositive: the countable union of nowhere dense sets cannot contain a ball.

Exercise 1. Show that the Baire category theorem is equivalent to the claim that in a complete metric space, the countable intersection of open dense sets remain dense.  \diamond

Exercise 2. Using the Baire category theorem, show that any non-empty complete metric space without isolated points is uncountable.  (In particular, this shows that Baire category theorem can fail for incomplete metric spaces such as the rationals {\Bbb Q}.)  \diamond

To quickly illustrate an application of the Baire category theorem, observe that it implies that one cannot cover a finite-dimensional real or complex vector space {\Bbb R}^n, {\Bbb C}^n by a countable number of proper subspaces.  One can of course also establish this fact by using Lebesgue measure on this space.  However, the advantage of the Baire category approach is that it also works well in infinite dimensional complete normed vector spaces, i.e. Banach spaces, whereas the measure-theoretic approach runs into significant difficulties in infinite dimensions.  This leads to three fundamental equivalences between the qualitative theory of continuous linear operators on Banach spaces (e.g. finiteness, surjectivity, etc.) to the quantitative theory (i.e. estimates):

  1. The uniform boundedness principle, that equates the qualitative boundedness (or convergence) of a family of continuous operators with their quantitative boundedness.
  2. The open mapping theorem, that equates the qualitative solvability of a linear problem Lu = f with the quantitative solvability.
  3. The closed graph theorem, that equates the qualitative regularity of a (weakly continuous) operator T with the quantitative regularity of that operator.

Strictly speaking, these theorems are not used much directly in practice, because one usually works in the reverse direction (i.e. first proving quantitative bounds, and then deriving qualitative corollaries); but the above three theorems help explain why we usually approach qualitative problems in functional analysis via their quantitative counterparts.

Read the rest of this entry »

To progress further in our study of function spaces, we will need to develop the standard theory of metric spaces, and of the closely related theory of topological spaces (i.e. point-set topology).  I will be assuming that students in my class will already have encountered these concepts in an undergraduate topology or real analysis course, but for sake of completeness I will briefly review the basics of both spaces here.

Read the rest of this entry »

A (concrete) Boolean algebra is a pair (X, {\mathcal B}), where X is a set, and {\mathcal B} is a collection of subsets of X which contain the empty set \emptyset, and which is closed under unions A, B \mapsto A \cup B, intersections A, B \mapsto A \cap B, and complements A \mapsto A^c := X \backslash A. The subset relation \subset also gives a relation on {\mathcal B}. Because the {\mathcal B} is concretely represented as subsets of a space X, these relations automatically obey various axioms, in particular, for any A,B,C \in {\mathcal B}, we have:

  1. \subset is a partial ordering on {\mathcal B}, and A and B have join A \cup B and meet A \cap B.
  2. We have the distributive laws A \cup (B \cap C) = (A \cup B) \cap (A \cup C) and A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
  3. \emptyset is the minimal element of the partial ordering \subset, and \emptyset^c is the maximal element.
  4. A \cap A^c = \emptyset and A \cup A^c = \emptyset^c.

(More succinctly: {\mathcal B} is a lattice which is distributive, bounded, and complemented.)

We can then define an abstract Boolean algebra {\mathcal B} = ({\mathcal B}, \emptyset, \cdot^c, \cup, \cap, \subset) to be an abstract set {\mathcal B} with the specified objects, operations, and relations that obey the axioms 1-4. [Of course, some of these operations are redundant; for instance, intersection can be defined in terms of complement and union by de Morgan’s laws. In the literature, different authors select different initial operations and axioms when defining an abstract Boolean algebra, but they are all easily seen to be equivalent to each other. To emphasise the abstract nature of these algebras, the symbols \emptyset, \cdot^c, \cup, \cap, \subset are often replaced with other symbols such as 0, \overline{\cdot}, \vee, \wedge, <.]

Clearly, every concrete Boolean algebra is an abstract Boolean algebra. In the converse direction, we have Stone’s representation theorem (see below), which asserts (among other things) that every abstract Boolean algebra is isomorphic to a concrete one (and even constructs this concrete representation of the abstract Boolean algebra canonically). So, up to (abstract) isomorphism, there is really no difference between a concrete Boolean algebra and an abstract one.

Now let us turn from Boolean algebras to \sigma-algebras.

A concrete \sigma-algebra (also known as a measurable space) is a pair (X,{\mathcal B}), where X is a set, and {\mathcal B} is a collection of subsets of X which contains \emptyset and are closed under countable unions, countable intersections, and complements; thus every concrete \sigma-algebra is a concrete Boolean algebra, but not conversely. As before, concrete \sigma-algebras come equipped with the structures \emptyset, \cdot^c, \cup, \cap, \subset which obey axioms 1-4, but they also come with the operations of countable union (A_n)_{n=1}^\infty \mapsto \bigcup_{n=1}^\infty A_n and countable intersection (A_n)_{n=1}^\infty \mapsto \bigcap_{n=1}^\infty A_n, which obey an additional axiom:

5. Any countable family A_1, A_2, \ldots of elements of {\mathcal B} has supremum \bigcup_{n=1}^\infty A_n and infimum \bigcap_{n=1}^\infty A_n.

As with Boolean algebras, one can now define an abstract \sigma-algebra to be a set {\mathcal B} = ({\mathcal B}, \emptyset, \cdot^c, \cup, \cap, \subset, \bigcup_{n=1}^\infty, \bigcap_{n=1}^\infty ) with the indicated objects, operations, and relations, which obeys axioms 1-5. Again, every concrete \sigma-algebra is an abstract one; but is it still true that every abstract \sigma-algebra is representable as a concrete one?

The answer turns out to be no, but the obstruction can be described precisely (namely, one needs to quotient out an ideal of “null sets” from the concrete \sigma-algebra), and there is a satisfactory representation theorem, namely the Loomis-Sikorski representation theorem (see below). As a corollary of this representation theorem, one can also represent abstract measure spaces ({\mathcal B},\mu) (also known as measure algebras) by concrete measure spaces, (X, {\mathcal B}, \mu), after quotienting out by null sets.

In the rest of this post, I will state and prove these representation theorems. They are not actually used directly in the rest of the course (and they will also require some results that we haven’t proven yet, most notably Tychonoff’s theorem), and so these notes are optional reading; but these theorems do help explain why it is “safe” to focus attention primarily on concrete \sigma-algebras and measure spaces when doing measure theory, since the abstract analogues of these mathematical concepts are largely equivalent to their concrete counterparts. (The situation is quite different for non-commutative measure theories, such as quantum probability, in which there is basically no good representation theorem available to equate the abstract with the classically concrete, but I will not discuss these theories here.)

Read the rest of this entry »

We now begin the study of recurrence in topological dynamical systems (X, {\mathcal F}, T) – how often a non-empty open set U in X returns to intersect itself, or how often a point x in X returns to be close to itself. Not every set or point needs to return to itself; consider for instance what happens to the shift x \mapsto x+1 on the compactified integers \{-\infty\} \cup {\Bbb Z} \cup \{+\infty\}. Nevertheless, we can always show that at least one set (from any open cover) returns to itself:

Theorem 1. (Simple recurrence in open covers) Let (X,{\mathcal F},T) be a topological dynamical system, and let (U_\alpha)_{\alpha \in A} be an open cover of X. Then there exists an open set U_\alpha in this cover such that U_\alpha \cap T^n U_\alpha \neq \emptyset for infinitely many n.

Proof. By compactness of X, we can refine the open cover to a finite subcover. Now consider an orbit T^{\Bbb Z} x = \{ T^n x: n \in {\Bbb Z} \} of some arbitrarily chosen point x \in X. By the infinite pigeonhole principle, one of the sets U_\alpha must contain an infinite number of the points T^n x counting multiplicity; in other words, the recurrence set S := \{ n: T^n x \in U_\alpha \} is infinite. Letting n_0 be an arbitrary element of S, we thus conclude that U_\alpha \cap T^{n_0-n} U_\alpha contains T^{n_0} x for every n \in S, and the claim follows. \Box

Exercise 1. Conversely, use Theorem 1 to deduce the infinite pigeonhole principle (i.e. that whenever {\Bbb Z} is coloured into finitely many colours, one of the colour classes is infinite). Hint: look at the orbit closure of c inside A^{\Bbb Z}, where A is the set of colours and c: {\Bbb Z} \to A is the colouring function.) \diamond

Now we turn from recurrence of sets to recurrence of individual points, which is a somewhat more difficult, and highlights the role of minimal dynamical systems (as introduced in the previous lecture) in the theory. We will approach the subject from two (largely equivalent) approaches, the first one being the more traditional “epsilon and delta” approach, and the second using the Stone-Čech compactification \beta {\Bbb Z} of the integers (i.e. ultrafilters).

Read the rest of this entry »