The first edition of Bourbaki's General Topology (chapter I, §9, p. 56) contains the following theorem.
Proposition 3. Soient $E$, $F$ deux espaces topologiques, $R$ une relation d'équivalence dans $E$, $S$ une relation d'équivalence dans $F$. L'application canonique de l'espace produit $(E/R) \times (F/S)$ sur l'espace quotient $(E\times F)/(R\times S)$ est un homéomorphisme.
It is followed by a very convincing proof. However, the theorem is wrong. The subsequent editions give an example where the spaces are not homeomorphic, even when one of the equivalence relation is equality.
I finally understood where the mistake is. It is in the very statement! Indeed, there is a canonical map, say $h$, between those two spaces, but it goes the other way round, namely from $(E\times F)/(R\times S)$ to $(E/R)\times (F/S)$. This map is continuous, as it should be. But Bourbaki, assuming that the natural canonical map goes the other way round, pretended that $h^{-1}$ is continuous, and embarked in proving that its reciprocal bijection, $h$, is also continuous, what it is...
There are cases where one would like this theorem to holds, for example when one discusses topologies on the fundamental group. Indeed, the fundamental group of a pointed space $(X,x)$ is a quotient of the space of loops based at $x$ on $X$ for the pointed-homotopy relation, hence can be endowed with the quotient of the topology of compact convergence (roughly, uniform convergence on compact sets). Multiplication of loops is continuous. However, the resulting group law on $\pi_1(X,x)$ need not be.
The mistake appears in the recent litterature, see for example this paper, or that one (which has been even featured as «best AMM paper of the year» in 2000...). MathScinet is not aware of the flaws in those papers... Fortunately, MathOverflow is!
Wednesday, December 5, 2012
Tuesday, November 27, 2012
Finite choices
Libellés :
combinatorics
,
set theory
The axiom of choice says that an arbitrary product $\prod_{i\in I} A_i$ of non-empty sets $A_i$ indexed by a set $I$ is non-empty. It is well known that this axiom does not follow from the other axioms of Zermelo-Fraenkel theory. Even finite choices, that is, this statement restricted to the case where all sets are finite, is not a consequence. Even 2-choices, when one assumes that $A_i$ has two elements!
Tarski proved the funny following fact: ${\rm AC}(2) \Rightarrow {\rm AC}(4)$—if you know how to choose between 2 elements, you can choose between 4.
For each integer $n$, call ${\rm AC}(n)$ the axiom of choice restricted to families $(A_i)$ where $A_i$ has $n$ elements.
Tarski proved the funny following fact: ${\rm AC}(2) \Rightarrow {\rm AC}(4)$—if you know how to choose between 2 elements, you can choose between 4.
The proof is in fact quite easy. Consider a family $(A_i)$ of sets with 4 elements. I will use choice functions furnished by ${\rm AC}(2)$ to pick-up one preferred element from $A_i$. For simplicity, label the elements of $A_i$ as $\{a,b,c,d\}$ and remove the index $i$. Then, consider the set $\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}$ of all pairs of elements of $A_i$. The hypothesis ${\rm AC}(2)$ allows to choose, for each of those pairs, one preferred element. Call $n_a,n_b,n_c,n_d$ the number of times $a,b,c,d$ has been chosen; one thus has $n_a+n_b+n_c+n_d=6$ and consider those elements which have been chosen the most often, those for which $n_?$ is maximal.
- If there is only one, let's choose it. (This happens in repartitions like $(3,1,1,1)$, etc.)
- If there are three such elements (the repartition must be $(2,2,2,0)$), let's choose the unique one which has never been chosen.
- There can't be four such elements because 4 does not divides 6.
- If there are two (repartition $(2,2,1,1)$), then use your 2-choice function on this pair!
The other funny, but more difficult, thing, is that ${\rm AC}(2)$ does not imply ${\rm AC}(3)$! Why? because the group $\{\pm1\}$ can act without fixed points on a 2-elements set but cannot on a 3-elements set. I hope to be able to say more on this another day.
Wednesday, November 21, 2012
Misconceptions about $K_X$
Libellés :
algebraic geometry
This is the title of a very short paper by Steven Kleiman published in L'enseignement mathématique, and which should be studied by every young student in scheme theory.
Here, $X$ is a scheme and $K_X$ is the sheaf of rational functions on $X$.
The misconceptions are the following, where we write $\mathop{Frac}(A)$ for the total ring of fractions of a ring $A$, namely the localized ring with respect to all element which are not zero divisors.
Here, $X$ is a scheme and $K_X$ is the sheaf of rational functions on $X$.
The misconceptions are the following, where we write $\mathop{Frac}(A)$ for the total ring of fractions of a ring $A$, namely the localized ring with respect to all element which are not zero divisors.
- $K_X$ is not the sheaf associated to the presheaf $U\mapsto \mathop{Frac}(\Gamma(U,O_X))$; indeed, that map may not be a presheaf.
- The germ $K_{X,x}$ of $K_X$ at a point $x$ may not be the total ring of fractions of the local ring $O_{X,x}$, it may be smaller.
- If $U=\mathop{Spec}(A)$ is an affine open subset of $X$, then $\Gamma(U,K_X)$ is not necessarily equal to $\mathop{Frac}(A)$.
These mistakes can be found in the writings of very good authors, even Grothendieck's EGA IV...
By chance, the first one is corrected in a straightforward way, and the other two work when the scheme $X$ is locally noetherian.
Thanks to Antoine D. for indicating to me this mistake, and to Google for leading me to Kleiman's paper.
The category of sets and its opposite
Libellés :
category theory
,
set theory
In the book Categories and sheaves by Kashiwara and Shapira, I found a nice argument for the fact that the category of sets is not equivalent to its opposite: they write « every morphism to the initial object is an isomorphism ». Of course!
In the category Sets, the initial object is the empty set, which means that for every set $A$, there is a unique map from $\emptyset$ to $A$. Now, if we reverse the process, namely, if we consider a set $A$ and a map $f\colon A\to \emptyset$, we see that $A$ must be empty and $f$ is a bijection, hence an isomorphism in the category of sets.
In the opposite category, all arrows are reversed, the initial object becomes the terminal object, etc. Isomorphisms are (reversed) maps which have an inverse, so isomorphisms are still given by bijections. A terminal object of Sets is one-element set, $\{x\}$ (you could take the set $1=\{\emptyset\}$ if, like von Neumann, you believe that numbers are sets). Indeed, there is a unique map from any set to a one-element set. Reverse the process again and consider a set $A$ and a map $f\colon \{x\} \to A$. This amounts to choosing an element of $A$, but such maps are not bijections in general, unless $A$ has itself only one element.
In the category Sets, the initial object is the empty set, which means that for every set $A$, there is a unique map from $\emptyset$ to $A$. Now, if we reverse the process, namely, if we consider a set $A$ and a map $f\colon A\to \emptyset$, we see that $A$ must be empty and $f$ is a bijection, hence an isomorphism in the category of sets.
In the opposite category, all arrows are reversed, the initial object becomes the terminal object, etc. Isomorphisms are (reversed) maps which have an inverse, so isomorphisms are still given by bijections. A terminal object of Sets is one-element set, $\{x\}$ (you could take the set $1=\{\emptyset\}$ if, like von Neumann, you believe that numbers are sets). Indeed, there is a unique map from any set to a one-element set. Reverse the process again and consider a set $A$ and a map $f\colon \{x\} \to A$. This amounts to choosing an element of $A$, but such maps are not bijections in general, unless $A$ has itself only one element.
Sunday, November 18, 2012
The van Kampen Theorem
Libellés :
fundamental group
,
topology
Let me recall the statement of this theorem.
Theorem. Let $X$ be a topological space, let $U,V$ be connected open subsets of $X$ such that $W=U\cap V$ is connected and let $x$ be a point of $U\cap V$. Then, the fundamental group $\pi_1(X,x)$ is the amalgamated product $\pi_1(U,x) *_{\pi_1(W,x)} \pi_1(V,x)$, that is, the quotient of the free product of the groups $\pi_1(U,x)$ and $\pi_1(V,x)$ by the normal subgroup generated by the elements of the form $i_U(c)i_V(c)^{-1}$, where $i_U$ and $i_V$ are the natural injections from the groups $\pi_1(U,x)$ and $\pi_1(V,x)$ respectively in their free product.
The classical proof of this result in topology books relies decomposes a loop at $x$ as a product of loops at $x$ which are either contained in $U$, or in $V$.
(In fact, van Kampen proves a theorem which is quite different at first sight.)
It has been long recognized that there is a completely different approach is possible, from which all loops are totally absent. For this proof we make a supplementary assumption, namely that our spaces are « semi-locally simply connected » : Any point $a$ of $X$ has a neighborhood $A$ such that the morphism $\pi_1(A,a)\to \pi_1(X,a)$ is trivial.
When $X$ is a connected slsc space together with a point $x$, the theory of the fundamental group is related to the theory of coverings,under the form of an equivalence of categories between coverings of $X$ and sets with an action of $\pi_1(X,x)$. The equivalence of categories is explicit; it maps a covering $p\colon Y\to X$ to the fiber $p^{-1}(x)$ on which $\pi_1(X,x)$ acts naturally via the path-lifting property of coverings (given $y\in p^{-1}(x)$, any loop $c$ at $x$ lifts uniquely to a path with origin $y$, the endpoint of which is $c\cdot y$).
Given this equivalence, one can prove the van Kampen Theorem very easily in two steps. First of all, one observes that it is equivalent to have a covering of $X$ as to have a covering of $U$ and a covering of $V$ together with an identification of these coverings above $W$. A covering of $U$ corresponds to a set $A$ with an action of $\pi_1(U,x)$; a covering of $V$ corresponds to a set $B$ with an action of $\pi_1(V,x)$; an identification of these coverings above $W$ corresponds to a bijection from $A$ to $B$ which is compatible with the two actions of $\pi_1(W,x)$ acting on $A$ via the morphism $\pi_1(W,x)\to \pi_1(U,x)$ and on $B$ via the morphism $\pi_1(W,x)\to \pi_1(V,x)$. It is harmless to assume that $A=B$ and that the bijection from $A$ to $B$ is the identity. Now, a covering of $X$ corresponds to a set $A$ together with two actions of the groups $\pi_1(U,x)$ and $\pi_1(V,x)$ such that the two actions of $\pi_1(W,x)$ are equal. This is precisely the same as a set $A$ together with an action of the amalgamated product $\pi_1(U,x)*_{\pi_1(W,x)}\pi_1(V,x)$. CQFD.
The same proof applies and allows to describe the fundamental group of an union of spaces in more general contexts. For example, let us use the same method to understand the fundamental group of the circle $\mathbf S_1$. It is clear that a circle is nothing but an interval $ [0,1]$ of which the two endpoints are glued, and a covering of the circle corresponds to a covering $p\colon X\to [0,1]$ of the interval $[0,1]$ together with an identification of the fibers at $0$ and~$1$. Now, a covering of the interval can be written as a product $A\times [0,1]$ (where $A$ is the fiber at $0$, say). Consequently, identifying the fibers at $0$ and $1$ means giving yourself a bijection of $A$ to $A$. In other words, a covering of the circle « is » a set $A$ together with a permutation of $A$, in other words, a set $A$ with an action of the additive group $\mathbf Z$. Moreover, the obvious loop is the image by the glueing map $[0,1]\to\mathbf S_1$ of the obvious path joining $0$ to $1$ so that this loop is the generator of $\pi_1(\mathbf S_1,p(0))$.
Observe that the latter example is not an instance of the van Kampen Theorem. One could get it via a groupoid-version of van Kampen.
All of this is more or less explained in the following texts:
The classical proof of this result in topology books relies decomposes a loop at $x$ as a product of loops at $x$ which are either contained in $U$, or in $V$.
(In fact, van Kampen proves a theorem which is quite different at first sight.)
It has been long recognized that there is a completely different approach is possible, from which all loops are totally absent. For this proof we make a supplementary assumption, namely that our spaces are « semi-locally simply connected » : Any point $a$ of $X$ has a neighborhood $A$ such that the morphism $\pi_1(A,a)\to \pi_1(X,a)$ is trivial.
When $X$ is a connected slsc space together with a point $x$, the theory of the fundamental group is related to the theory of coverings,under the form of an equivalence of categories between coverings of $X$ and sets with an action of $\pi_1(X,x)$. The equivalence of categories is explicit; it maps a covering $p\colon Y\to X$ to the fiber $p^{-1}(x)$ on which $\pi_1(X,x)$ acts naturally via the path-lifting property of coverings (given $y\in p^{-1}(x)$, any loop $c$ at $x$ lifts uniquely to a path with origin $y$, the endpoint of which is $c\cdot y$).
Given this equivalence, one can prove the van Kampen Theorem very easily in two steps. First of all, one observes that it is equivalent to have a covering of $X$ as to have a covering of $U$ and a covering of $V$ together with an identification of these coverings above $W$. A covering of $U$ corresponds to a set $A$ with an action of $\pi_1(U,x)$; a covering of $V$ corresponds to a set $B$ with an action of $\pi_1(V,x)$; an identification of these coverings above $W$ corresponds to a bijection from $A$ to $B$ which is compatible with the two actions of $\pi_1(W,x)$ acting on $A$ via the morphism $\pi_1(W,x)\to \pi_1(U,x)$ and on $B$ via the morphism $\pi_1(W,x)\to \pi_1(V,x)$. It is harmless to assume that $A=B$ and that the bijection from $A$ to $B$ is the identity. Now, a covering of $X$ corresponds to a set $A$ together with two actions of the groups $\pi_1(U,x)$ and $\pi_1(V,x)$ such that the two actions of $\pi_1(W,x)$ are equal. This is precisely the same as a set $A$ together with an action of the amalgamated product $\pi_1(U,x)*_{\pi_1(W,x)}\pi_1(V,x)$. CQFD.
The same proof applies and allows to describe the fundamental group of an union of spaces in more general contexts. For example, let us use the same method to understand the fundamental group of the circle $\mathbf S_1$. It is clear that a circle is nothing but an interval $ [0,1]$ of which the two endpoints are glued, and a covering of the circle corresponds to a covering $p\colon X\to [0,1]$ of the interval $[0,1]$ together with an identification of the fibers at $0$ and~$1$. Now, a covering of the interval can be written as a product $A\times [0,1]$ (where $A$ is the fiber at $0$, say). Consequently, identifying the fibers at $0$ and $1$ means giving yourself a bijection of $A$ to $A$. In other words, a covering of the circle « is » a set $A$ together with a permutation of $A$, in other words, a set $A$ with an action of the additive group $\mathbf Z$. Moreover, the obvious loop is the image by the glueing map $[0,1]\to\mathbf S_1$ of the obvious path joining $0$ to $1$ so that this loop is the generator of $\pi_1(\mathbf S_1,p(0))$.
Observe that the latter example is not an instance of the van Kampen Theorem. One could get it via a groupoid-version of van Kampen.
All of this is more or less explained in the following texts:
- Adrien and Régine Douady, Algèbre et théories galoisiennes, Cassini 2005.
- Ronald Brown, Topology and Groupoids, Booksurge Publishing, 2006.
- I remember having read an old Bourbaki Tribu from the 50sby Cartan, Eilenberg and/or Weil explaining this, but I cannot find it anymore on the archive. :-(
Thursday, October 18, 2012
Cardinality of ultraproducts (an update)
Libellés :
algebra
,
set theory
,
topology
I thought a little more about the proof that an ultraproduct of finite sets is either finite (if the family of cardinals is bounded with respect to the chosen ultrafilter) or has the power of the continuum. I believe that I can now state things in a neater, albeit longer, way.
Let me recall the notation: $(A_x)$ be a family of sets indexed by a set $X$, $A=\prod A_x$ is the product of the sets $A_x$, $\cal U$ be a nonprincipal ultrafilter on a set $X$, and $A^*$ is the ultraproduct of the $A_x$ with respect to $\cal U$.
I then recall the notion of convergence with respect to the ultrafilter $\cal U$. Let $V$ be a topological space and let $(v_x)$ be a family of points of $V$.
Last reminding. The set of nonnegative integers $\mathbf N$ is dense in the Hausdorff and compact set $\mathbf Z_2$ of $2$-adic integers endowed with the $2$-adic distance.
For every $x\in X$, choose a surjection $f_x$ from $A_x$ to the interval of integers $[0,\mathrm{Card}(A_x))$, viewed as a subset of $\mathbf Z_2$. For any family $a=(a_x)$ where $a_x\in A_x$ for every $x\in X$, the family $(f_x(a_x))$ has a unique $\cal U$-limit in $\mathbf Z_2$, denoted $f(a)$. This defines a map $f\colon A\to \mathbf Z_2$.
Let $a=(a_x)$ and $b=(b_x)$ be two such families and assume that $f(a)\neq f(b)$. It follows from the fact that $\mathbf Z_2$ is Hausdorff that the set of $x\in X$ such that $a_x\neq b_x$ belongs to $\cal U$. Said the other way round, if $a$ and $b$ are $\cal U$-equivalent, then $f(a)=f(b)$, so that $f$ defines a map $f^*\colon A^*\to\mathbf Z_2$.
We now show that if the cardinalities $\mathrm{Card}(A_x)$ are not bounded (with respect to $\cal U$), this map $f^*$ is surjective. Let $v\in\mathbf Z_2$; for any $x\in X$, let $v_x$ be the integer in $[0,\mathrm{Card}(A_x))$ which is the closest to $v$ with respect to the $2$-adic distance and let $a_x\in A_x$ be such that $f_x(a_x)=v_x$. I claim that $d(v,v_x)$ $\cal U$-converges to $0$; indeed, for any $k$, the set $X_k$ of $x\in X$ such that $\mathrm{Card}(A_x)\geq 2^k$ belongs to $\cal U$ (this is what it means to be unbounded with respect to $\cal U$) and for $x\in X_k$, $d(v,v_x)\leq 2^{-k}$. By construction, $(f_x(a_x))=(v_x)$, hence $f((a_x))=v$; if $a^*$ is the class in $A^*$ of the family $(a_x)$, we thus have $f^*(a^*)=v$.
Finally, $\mathrm{Card}(A^*) \geq \mathrm{Card}(\mathbf Z_2)=2^{\mathbf N}$, as was to be shown.
(This proof is longer, but only because I needed to recall—I mean, to recall to myself—the topological apparatus of convergence for ultrafilters.)
Let me recall the notation: $(A_x)$ be a family of sets indexed by a set $X$, $A=\prod A_x$ is the product of the sets $A_x$, $\cal U$ be a nonprincipal ultrafilter on a set $X$, and $A^*$ is the ultraproduct of the $A_x$ with respect to $\cal U$.
I then recall the notion of convergence with respect to the ultrafilter $\cal U$. Let $V$ be a topological space and let $(v_x)$ be a family of points of $V$.
- Say $(v_x)$ $\cal U$-converges to $v$ if for any neighborhood $W$ of $v$, the set of $x\in X$ such that $v_x\in W$ belongs to $\cal U$.
- If $V$ is Hausdorff, then $(v_x)$ has at most one limit. In particular, if $(w_x)$ is another family of points of $V$ indexed by $X$ which converges to a point $w\neq v$, the set of $x\in X$ such that $v_x\neq w_x$ belongs to $\cal U$.
- Moreover, if $V$ is compact, then any family $(v_x)$ has a $\cal U$-limit in $V$. This is essentially the definition of compactness in terms of ultrafilters, but it does no harm recalling the proof. If, by contradiction, $(v_x)$ has no $\cal U$-limit, any point $v\in V$ has a neighborhood $W_v$ such that the set $X_v$ $x\in X$ with $x\not\in W_v$ belongs to $\cal U$. Since $V$ is compact, there exists a finite set $T$ in $V$ such that the $W_v$, for $v\in T$, cover $V$. This implies that the intersection of the $X_v$, for $v\in T$, is empty. However, this is a finite intersection of elements of $\cal U$, hence belongs to $\cal U$, hence is non-empty.
Last reminding. The set of nonnegative integers $\mathbf N$ is dense in the Hausdorff and compact set $\mathbf Z_2$ of $2$-adic integers endowed with the $2$-adic distance.
For every $x\in X$, choose a surjection $f_x$ from $A_x$ to the interval of integers $[0,\mathrm{Card}(A_x))$, viewed as a subset of $\mathbf Z_2$. For any family $a=(a_x)$ where $a_x\in A_x$ for every $x\in X$, the family $(f_x(a_x))$ has a unique $\cal U$-limit in $\mathbf Z_2$, denoted $f(a)$. This defines a map $f\colon A\to \mathbf Z_2$.
Let $a=(a_x)$ and $b=(b_x)$ be two such families and assume that $f(a)\neq f(b)$. It follows from the fact that $\mathbf Z_2$ is Hausdorff that the set of $x\in X$ such that $a_x\neq b_x$ belongs to $\cal U$. Said the other way round, if $a$ and $b$ are $\cal U$-equivalent, then $f(a)=f(b)$, so that $f$ defines a map $f^*\colon A^*\to\mathbf Z_2$.
We now show that if the cardinalities $\mathrm{Card}(A_x)$ are not bounded (with respect to $\cal U$), this map $f^*$ is surjective. Let $v\in\mathbf Z_2$; for any $x\in X$, let $v_x$ be the integer in $[0,\mathrm{Card}(A_x))$ which is the closest to $v$ with respect to the $2$-adic distance and let $a_x\in A_x$ be such that $f_x(a_x)=v_x$. I claim that $d(v,v_x)$ $\cal U$-converges to $0$; indeed, for any $k$, the set $X_k$ of $x\in X$ such that $\mathrm{Card}(A_x)\geq 2^k$ belongs to $\cal U$ (this is what it means to be unbounded with respect to $\cal U$) and for $x\in X_k$, $d(v,v_x)\leq 2^{-k}$. By construction, $(f_x(a_x))=(v_x)$, hence $f((a_x))=v$; if $a^*$ is the class in $A^*$ of the family $(a_x)$, we thus have $f^*(a^*)=v$.
Finally, $\mathrm{Card}(A^*) \geq \mathrm{Card}(\mathbf Z_2)=2^{\mathbf N}$, as was to be shown.
(This proof is longer, but only because I needed to recall—I mean, to recall to myself—the topological apparatus of convergence for ultrafilters.)
Wednesday, October 17, 2012
Ultrafilters
Libellés :
algebra
,
combinatorics
,
math
,
set theory
Ultrafilters won't make american coffee better, but they have nice applications in mathematics. In fact, the last three (working) days, I happened to hear about them with three different colleagues, in three different directions.
Let me recall that an ultrafilter $\cal U$ on a set $X$ is a subset of $\mathfrak P(X)$ satisfying the following axioms:
Here is an example of an ultrafilter. Fix a point $x\in X$ and decree that a set $A\subset X$ is large iff it contains $x$. Such ultrafilters are called principal and they do not quite respect the intuition of elements of an ultrafilter being a large set. Unfortunately, there is no explicit construction of an ultrafilter which is not principal. Fortunately, choice-like axioms imply the existence of non principal ultrafilters.
1) Cardinality of ultraproducts of countable sets.
If there is a large subset of $X$ on which $\mathrm{Card}(A_x)$ is bounded, then $A^*$ is finite. Otherwise, $A^*$ is infinite, and has in fact at least the power of the continuum.
Here is a classical proof in the case $X=\mathbf N$, with some twists that helped me understand it.
We want to construct a map from $2^{\mathbf N}$ to $A^*$. Here, $2^{\mathbf N}$ is the set of subsets of $\mathbf N$, but can be almost viewed as the set of $2$-adic integers, a subset of $\mathbf N$ corresponding to a $2$-adic integer whose nonzero digits are exactly those belonging to the given subset. In formula, $S\subset\mathbf N$ corresponds to the $2$-adic integer $f(S)=\sum_{n=0}^\infty \chi_S(n) 2^n$. If we sum only $n$ terms, we get an approximation $f_n(S)$ modulo $(2^n)$ which is an element of $\{0,\dots,2^n-1\}$. In particular, $f_n(S)\rightarrow f(S)$. This shows that if $S\neq T$ are two distincts subsets of $B$, then $f_n(S)\neq f_n(T)$ for all but finitely many integers~$n$.
Enumerate a large subset $X_1=\{x_0,\dots\} $ of $X$ such that $A_{x_n}$ has at least $2^n$ elements and enumerate those elements. For any $S\in 2^{\mathbf N}$, consider the family $a(S)=(a_x)$ of $\prod A_x$ such that for every $n$, $a_{x_n}$ is the $f_n(S)$th element of $A_{x_n}$, and $a_x$ is any fixed element of $A_x$ otherwise. Let $a^*(S)$ be the class of this family in $A^*$. If $S\neq T$, then $f_S(n)\neq f_T(n)$ for all but finitely many $n$, so that $a(S)$ and $a(T)$ differ in a large set (the complement to a finite set in a large set), hence $a^*(S)\neq a^*(T)$. We have thus constructed an injective map from $2^{\mathbf N}$ to $A^*$, hence $\mathrm{Card}(A^*)\geq 2^{\mathbf N}$.
2) An “ultrafilter proof” of the infinite Ramsey theorem
Any infinite graph contains an infinite subset which is either a complete subgraph (any two vertices are linked by an edge) or a discrete subgraph (no two vertices are linked by an edge). In this statement, a graph is assumed to have no loop.
Let $V$ be the set of vertices of your graph $G$. Choose a non principal ultrafilter on $V$. Say a vertex $v\in V$ is social if the set of its neighbors (those linked to $v$ by an edge of $G$) is large; otherwise, say it is lonely. Now, assuming that the set of social vertices is large, we will construct an infinite complete subgraph of $G$. Otherwise, the set of lonely vertices is large and the same construction (or the consideration of the opposite graph) gives an infinite discrete subgraph.
Fix a social vertex $v_0$. The set of social neighbors of $v_0$ is large, because it is the intersection of the large set of social vertices with the large set of neighbors of $v_0$; so $v_0$ has a social neighbor $v_1$. Assume we have constructed social vertices $v_0,\dots,v_{n-1}$ which are pairwise linked by an edge, the set of social vertices of $V$ which are linked to all of the $v_i$ is large, again because it is the intersection of the large set of social vertices with finitely many large sets of neighbors of each $v_i$. So there is a social vertex $v_n$ which is a neighbor of $v_0,\dots,v_{n-1}$. Go on.
This infinite Ramsey theorem implies the finite one: For any integer $n$, there is an integer $r(n)$ such that each graph with at least $r(n)$ vertices possesses a subgraph of cardinality $n$ which is either complete or discrete. The proof uses ultrafilters again, but in a different way. Assume by contradiction that the finite Ramsey theorem is false. So there is an integer $n$ and a family $(G_i)$ of finite graphs with an increasing number of vertices, none of which contains a complete or discrete subgraph with $n$ vertices. Take the ultraproduct $G$ of the graphs $G_i$, namely the product graph $\prod G_i$ modulo the equivalence relation $(g_i)\sim (g'_i)$ iff the set of $i$ such that $g_i=g'_i$
is large, for some given non principal ultraproduct on the set $I$ of indices. Write $[g_i]$ for the class of a family $(g_i)$; say that $[g_i]$ is linked to $[g'_i]$ if the set of indices $i$ for which $g_i$ is linked to $g'_i$ in $G_i$ is large. Then $G$ is a graph, an infinite graph (by the result on cardinalities of ultraproducts).
3) Ax's proof of Hilbert's Nullstellensatz
Let $k$ be an algebraically closed field, let $f_1,\dots,f_m$ be polynomials in $d$ variables with coefficients in $k$. Assume that the system of polynomial equations
\[ f_1(x_1,\dots,x_d)=\dots=f_m(x_1,\dots,x_d)=0 \]
has a solution in some extension $K$ of $k$. Then, it already has a solution in $k$.
The following proof is given by Ax in the surprising paper A Metamathematical Approach to some Problems in Number Theory, published in the proceedings of a conference (Proc. Symp. Pure Math., 20, Amer. Math. Soc). I say surprising, because the main part of this 30-pages paper is about 6 pages, the rest is an appendix providing a beautiful introduction the theory of valuations!
I basically copy Ax. One may assume that both fields $k$ and $K$ are countable and algebraically closed (first replace $k$ by the algebraic closure of the subfield generated by the coefficients
Let me recall that an ultrafilter $\cal U$ on a set $X$ is a subset of $\mathfrak P(X)$ satisfying the following axioms:
- The empty set does not belong to $\cal U$;
- If $A\in\cal U$ and $B\supset A$, then $B\in\cal U$;
- If $A,B\in \cal U$, then $A\cap B\in\cal U$;
- For any subset $A\subset X$, either $A$ or $\complement A$ belongs to $\cal U$ (but not both).
Here is an example of an ultrafilter. Fix a point $x\in X$ and decree that a set $A\subset X$ is large iff it contains $x$. Such ultrafilters are called principal and they do not quite respect the intuition of elements of an ultrafilter being a large set. Unfortunately, there is no explicit construction of an ultrafilter which is not principal. Fortunately, choice-like axioms imply the existence of non principal ultrafilters.
Ultrafilters are used to construct ultraproducts.
Take a family $(A_x)$ of non-empty sets indexed by the set $X$ and fix a nonprincipal ultrafilter on $X$. (The definition below is not the correct one when some sets $A_x$ may be empty; the correct one is slightly more elaborate. I learnt it from Laurent Moret-Bailly, see Section 2 of his beautiful paper An extension of Greenberg's theorem to general valuation rings, arXiv:1106.0984v3.) Define an equivalence relation on the product set $A=\prod A_x$ by saying that two families $(a_x)$ and $(b_x)$ are equivalent iff the set of $x$ such that $a_x=b_x$ is large. Let $A^*$ be the quotient of $A$ by this equivalence relation; it is called the ultraproduct of the $A_x$. When the $A_x$ have some extra-structure (relations, operations, etc.) on can transport them to the ultraproduct $A^*$. For example, if, for each $x$, $R_x$ is a binary relation on $A_x$, $a,b\in A^*$ are classes of $(a_x)$ and $(b_x)$, say that $R(a,b)$ iff the set of $x$ such that $R_x(a_x,b_x)$ is large. We shall see some specific examples below.
There are many nice bits of mathematics where ultrafilters are involved. Here are three of them which I would like not to forget.
1) Cardinality of ultraproducts of countable sets.
If there is a large subset of $X$ on which $\mathrm{Card}(A_x)$ is bounded, then $A^*$ is finite. Otherwise, $A^*$ is infinite, and has in fact at least the power of the continuum.
Here is a classical proof in the case $X=\mathbf N$, with some twists that helped me understand it.
We want to construct a map from $2^{\mathbf N}$ to $A^*$. Here, $2^{\mathbf N}$ is the set of subsets of $\mathbf N$, but can be almost viewed as the set of $2$-adic integers, a subset of $\mathbf N$ corresponding to a $2$-adic integer whose nonzero digits are exactly those belonging to the given subset. In formula, $S\subset\mathbf N$ corresponds to the $2$-adic integer $f(S)=\sum_{n=0}^\infty \chi_S(n) 2^n$. If we sum only $n$ terms, we get an approximation $f_n(S)$ modulo $(2^n)$ which is an element of $\{0,\dots,2^n-1\}$. In particular, $f_n(S)\rightarrow f(S)$. This shows that if $S\neq T$ are two distincts subsets of $B$, then $f_n(S)\neq f_n(T)$ for all but finitely many integers~$n$.
Enumerate a large subset $X_1=\{x_0,\dots\} $ of $X$ such that $A_{x_n}$ has at least $2^n$ elements and enumerate those elements. For any $S\in 2^{\mathbf N}$, consider the family $a(S)=(a_x)$ of $\prod A_x$ such that for every $n$, $a_{x_n}$ is the $f_n(S)$th element of $A_{x_n}$, and $a_x$ is any fixed element of $A_x$ otherwise. Let $a^*(S)$ be the class of this family in $A^*$. If $S\neq T$, then $f_S(n)\neq f_T(n)$ for all but finitely many $n$, so that $a(S)$ and $a(T)$ differ in a large set (the complement to a finite set in a large set), hence $a^*(S)\neq a^*(T)$. We have thus constructed an injective map from $2^{\mathbf N}$ to $A^*$, hence $\mathrm{Card}(A^*)\geq 2^{\mathbf N}$.
2) An “ultrafilter proof” of the infinite Ramsey theorem
Any infinite graph contains an infinite subset which is either a complete subgraph (any two vertices are linked by an edge) or a discrete subgraph (no two vertices are linked by an edge). In this statement, a graph is assumed to have no loop.
Let $V$ be the set of vertices of your graph $G$. Choose a non principal ultrafilter on $V$. Say a vertex $v\in V$ is social if the set of its neighbors (those linked to $v$ by an edge of $G$) is large; otherwise, say it is lonely. Now, assuming that the set of social vertices is large, we will construct an infinite complete subgraph of $G$. Otherwise, the set of lonely vertices is large and the same construction (or the consideration of the opposite graph) gives an infinite discrete subgraph.
Fix a social vertex $v_0$. The set of social neighbors of $v_0$ is large, because it is the intersection of the large set of social vertices with the large set of neighbors of $v_0$; so $v_0$ has a social neighbor $v_1$. Assume we have constructed social vertices $v_0,\dots,v_{n-1}$ which are pairwise linked by an edge, the set of social vertices of $V$ which are linked to all of the $v_i$ is large, again because it is the intersection of the large set of social vertices with finitely many large sets of neighbors of each $v_i$. So there is a social vertex $v_n$ which is a neighbor of $v_0,\dots,v_{n-1}$. Go on.
This infinite Ramsey theorem implies the finite one: For any integer $n$, there is an integer $r(n)$ such that each graph with at least $r(n)$ vertices possesses a subgraph of cardinality $n$ which is either complete or discrete. The proof uses ultrafilters again, but in a different way. Assume by contradiction that the finite Ramsey theorem is false. So there is an integer $n$ and a family $(G_i)$ of finite graphs with an increasing number of vertices, none of which contains a complete or discrete subgraph with $n$ vertices. Take the ultraproduct $G$ of the graphs $G_i$, namely the product graph $\prod G_i$ modulo the equivalence relation $(g_i)\sim (g'_i)$ iff the set of $i$ such that $g_i=g'_i$
is large, for some given non principal ultraproduct on the set $I$ of indices. Write $[g_i]$ for the class of a family $(g_i)$; say that $[g_i]$ is linked to $[g'_i]$ if the set of indices $i$ for which $g_i$ is linked to $g'_i$ in $G_i$ is large. Then $G$ is a graph, an infinite graph (by the result on cardinalities of ultraproducts).
While I write this proof, I realize that this proof prompts naturally the question of the Ramsey theorem for cardinals: Assuming $V$ has some (infinite) cardinality, what is the smallest cardinality for which
there may not exist an either complete or discret subgraph of that cardinality? For the previous proof to work, one needs transfinite induction, so one needs the ultrafilter to be stable by possibly infinite intersections.
there may not exist an either complete or discret subgraph of that cardinality? For the previous proof to work, one needs transfinite induction, so one needs the ultrafilter to be stable by possibly infinite intersections.
3) Ax's proof of Hilbert's Nullstellensatz
Let $k$ be an algebraically closed field, let $f_1,\dots,f_m$ be polynomials in $d$ variables with coefficients in $k$. Assume that the system of polynomial equations
\[ f_1(x_1,\dots,x_d)=\dots=f_m(x_1,\dots,x_d)=0 \]
has a solution in some extension $K$ of $k$. Then, it already has a solution in $k$.
The following proof is given by Ax in the surprising paper A Metamathematical Approach to some Problems in Number Theory, published in the proceedings of a conference (Proc. Symp. Pure Math., 20, Amer. Math. Soc). I say surprising, because the main part of this 30-pages paper is about 6 pages, the rest is an appendix providing a beautiful introduction the theory of valuations!
I basically copy Ax. One may assume that both fields $k$ and $K$ are countable and algebraically closed (first replace $k$ by the algebraic closure of the subfield generated by the coefficients
of the polynomials $f_1,\dots,f_m$; then replace $K$ by the algebraic closure of the subfield generated over $k$ by the coordinates $(x_1,\dots,x_d)$ of some solution).
Consider a nonprincipal ultrafilter on the set $\mathbf N$ of integers and look at the ultraproducts $k^*$ and $K^*$ of the families $(k_n)$ and $(K_n)$, where $k_n=k$ and $K_n=K$ for each $K$. These are algebraically closed fields; moreover, $k^*$ contains $k$ (the set of classes of all families $(a_n)$ where $a_n\equiv a$ for some $a\in k$). From a solution $(x_1,\dots,x_d)$ in $K$ and considering the class of the constant family, one gets a solution $(x^*_1,\dots,x^*_d)$ in $(K^*)^d$ of the system of equations $f_1(x^*)=\dots=f_m(x^*)=0$.
By set theory, $\mathrm{Card}(k^*)\leq {\mathbf N}^{\mathbf N}=2^{\mathbf N}$, while we have shown that $\mathrm{Card}(k^*)\geq 2^{\mathbf N}$, so that $k^*$ has the cardinality of the continuum. Likewise, $K^*$ has the cardinality of the continuum. Consequently (by set theory again), $k^*$ and $K^*$ both have a transcendence basis over $k$ of cardinality the continuum; since they are algebraically closed, they are isomorphic as extensions of $k$. The image of the solution $x^*$ by a $k$-isomorphism from $K^*$ to $k^*$ is a solution $y^*$ of our system in $k^*$. By definition, $y^*=(y^*_1,\dots,y^*_d)$ where for each $i$, $y^*_i$ is the class of a sequence $(y_{i,n})$ of elements of $k$. Since $f_j(y^*)=0$, the set of integers $n$ such that $f_j(y_{1,n},\dots,y_{d,n})=0$ is large. Consequently, there is a large set of integers $n$ such that $(y_{1,n},\dots,y_{d,n})$ is a solution of our system. Any such integer $n$ is a proof that this system already has a solution in $k$. Q.E.D.
I do no know whether this proof is really easier than the ones usually given in an algebra course, for all the set theory involved is rather delicate, but I found it rather appealing.
Tuesday, October 16, 2012
Birth of a new blog
It may have been like when you take care of a friend's pet for a week-end: you get used to it and eventually want to have your own. I had run a familial blog for one year, when we all left Rennes to Princeton, but we went back home, and left Rennes again to Paris. So this old blog I cherish couldn't really host the sequel of our adventures. I am not sure I am willing to discuss that kind of adventures publicly neither. It's okay to chat about your life when your 6000km away, but it's slightly more problematic when you live next to the one you would chat about.
So I needed fresh ideas, for a fresh blog, and today, here it is !
So what will this blog be about ?
Sorry for some of you, primarily math.
But I will probably use it to store some computer tricks (the kind of recipes you don't want
to forget but have no convenient place to keep in).
And I'll certainly talk about music too. In fact, finding a title for this blog has been a sad experience.
The first three names I tried were already used, namely Garden of Eden, Lost in a Dream and Mumbo Jumbo. These are three beautiful songs of the revered drummer Paul Motian — a musical poet among all. The New York Times said of him he was a “composer of grace and abstraction”. The fourth try has been taken from a Eddie Harris song I know from a duet by Motian and Enrico Pieranunzi, Freedom Jazz Dance; it lead to the actual title of this new blog.
I hope this title convey the kind of things I want to discuss here, the way I expect to discuss it: freely, as a math dance.
In fact, and this was not intended, this title reminds me of the envoi of a beautiful collective small book on transcendental number theory : et que commence la transe en danse !
So I needed fresh ideas, for a fresh blog, and today, here it is !
So what will this blog be about ?
Sorry for some of you, primarily math.
But I will probably use it to store some computer tricks (the kind of recipes you don't want
to forget but have no convenient place to keep in).
And I'll certainly talk about music too. In fact, finding a title for this blog has been a sad experience.
The first three names I tried were already used, namely Garden of Eden, Lost in a Dream and Mumbo Jumbo. These are three beautiful songs of the revered drummer Paul Motian — a musical poet among all. The New York Times said of him he was a “composer of grace and abstraction”. The fourth try has been taken from a Eddie Harris song I know from a duet by Motian and Enrico Pieranunzi, Freedom Jazz Dance; it lead to the actual title of this new blog.
I hope this title convey the kind of things I want to discuss here, the way I expect to discuss it: freely, as a math dance.
In fact, and this was not intended, this title reminds me of the envoi of a beautiful collective small book on transcendental number theory : et que commence la transe en danse !
Subscribe to:
Posts
(
Atom
)