December 31, 2016

As for the peace that we would preserve, I wonder who among us would like to approach the wife or mother whose husband or son has died in South Vietnam and ask them if they think this is a peace that should be maintained indefinitely. Do they mean peace, or do they mean we just want to be left in peace? There can be no real peace while one American is dying some place in the world for the rest of us. We’re at war with the most dangerous enemy that has ever faced mankind in his long climb from the swamp to the stars, and it’s been said if we lose that war, and in so doing lose this way of freedom of ours, history will record with the greatest astonishment that those who had the most to lose did the least to prevent its happening. Well I think it’s time we ask ourselves if we still know the freedoms that were intended for us by the Founding Fathers.

A time for choosing, Ronald Reagan, 1964.

[E]ven in a season where the incredible blessings that we know as Americans are all around us, even as we enjoy family and friends and are reminded of how lucky we are, we should also be reminded that to be an American involves bearing burdens and meeting obligations to others.

So with respect to Syria, what I have consistently done is taken the best course that I can to try to end the civil war while having also to take into account the long-term national security interests of the United States.

Final presidential press conference, Barack Obama, 16 December 2016.

Genocide has occurred so often and so uncontested in the last fifty years that an epithet more apt in describing recent events than the oft-chanted “Never Again” is in fact “Again and Again.”

Never again. The world’s most unfulfilled promise, Samantha Power.


Article 5

December 11, 2016

The Parties agree that an armed attack against one or more of them in Europe or North America shall be considered an attack against them all and consequently they agree that, if such an armed attack occurs, each of them, in exercise of the right of individual or collective self-defence recognised by Article 51 of the Charter of the United Nations, will assist the Party or Parties so attacked by taking forthwith, individually and in concert with the other Parties, such action as it deems necessary, including the use of armed force, to restore and maintain the security of the North Atlantic area.

Any such armed attack and all measures taken as a result thereof shall immediately be reported to the Security Council. Such measures shall be terminated when the Security Council has taken the measures necessary to restore and maintain international peace and security .

(Article 5 of the North Atlantic Treaty.)


December 2, 2016

From V for Vendetta by Alan Moore, David Lloyd, Tony Weare, Steve Whitaker, Siobhan Dodds, Jenny O’Connor, Steve Craddock, and Elitta Fell.

I don’t know who you are. Please believe. There is no way I can convince you that this is not one of their tricks. But I don’t care. I am me, and I don’t know who you are, but I love you.

I have a pencil. A little one they did not find. I am a woman. I hid it inside me. Perhaps I won’t be able to write again, so this is a long letter about my life. It is the only autobiography I will ever write and oh God I’m writing it on toilet paper.

I was born in Nottingham in 1957, and it rained a lot. I passed my eleven plus and went to girl’s Grammar. I wanted to be an actress.

I met my first girlfriend at school. Her name was Sara. She was fourteen and I was fifteen but we were both in Miss Watson’s class. Her wrists. Her wrists were beautiful. I sat in biology class, staring at the picket rabbit foetus in its jar, listening while Mr. Hird said it was an adolescent phase that people outgrew. Sara did. I didn’t.

In 1976 I stopped pretending and took a girl called Christine home to meet my parents. A week later I enrolled at drama college. My mother said I broke her heart. But it was my integrity that was important. Is that so selfish? It sells for so little, but it’s all we have left in this place. It is the very last inch of us. But within that inch we are free.

London: I was happy in London. In 1981 I played Dandini in Cinderella. My first rep work. The world was strange and rustling and busy, with invisible crowds behind the hot lights and all that breathless glamour. It was exciting and it was lonely. At nights I’d go to Gateways or one of the other clubs, but I was stand-offish and didn’t mix easily. I saw a lot of the scene, but I never felt comfortable: there, so many of them just wanted to be gay. It was their life, their ambition. And I wanted more than that.

Work improved. I got small film roles, then bigger ones. In 1986 I starred in “The Salt Flats.” It pulled in the awards but not the crowds. I met Ruth while working on that. We loved each other. We lived together and on Valentine’s Day she sent me roses and oh God, we had so much. Those were the best three years of my life.

In 1988 there was the war, and after that there were no more roses. Not for anybody.

In 1992, after the take-over, they started rounding up the gays. They took Ruth while she was out looking for food. Why are they so frightened of us? They burned her with cigarette ends and made her give them my name. She signed a statement saying I’d seduced her. God. I loved her. I didn’t blame her.

But she did. She killed herself in her cell. She couldn’t live with betraying me, with giving up that last inch. Oh Ruth.

They came for me. They told me that all my films would be burned. They shaved off my hair and held my head down a toilet bowl and told jokes about lesbians. They brought me here and gave me drugs. I can’t feel my tongue anymore. I can’t speak.

The other gay women here, Rita, died two weeks ago. I imagine I’ll die quite soon. It’s strange that my life should end in such a terrible place, but for three years I had roses and I apologised to nobody.

I shall die here. Every last inch of me shall perish. Except one.

An inch. It’s small and it’s fragile and it’s the only thing in the world worth having. We must never lose it, or sell it, or give it away. We must never let them take it from us.

I don’t know who you are. Or whether you’re a man or woman. I may never see you. I will never hug you or cry with you or get drunk with you. But I love you.

I hope that you escape this place. I hope that the world turns and that things get better, and that one day people have roses again. I wish I could kiss you.


Bogotá, September 17-20, 2014, 50 años carrera de matemáticas, Universidad de los Andes

September 17, 2016

I ran last night into the Flickr page for this conference essentially by accident. Couldn’t find who to credit for this picture.



The Dalek invasion of MR

September 12, 2016

Maybe they are chasing me, see here.


On anti-foundation and coding the hereditarily finite sets

August 27, 2016

I would like to highlight a cute question in a recent paper,

Giovanna D’Agostino, Alberto Policriti, Eugenio G. Omodeo, and Alexandru I. Tomescu.
Mapping sets and hypersets into numbers.
Fund. Inform. 140 (2015), no. 3-4, 307–328.

Recall that W. Ackermann verified what in modern terms we call the bi-interpretability of \mathsf{ZFfin} and \mathsf{PA}, where the latter is (first-order) Peano arithmetic, and the former is finite set theory, the result of replacing in \mathsf{ZF} the axiom of infinity with its negation (and with foundation formulated as the schema of \in-induction). The reference is

Wilhelm Ackermann.
Die Widerspruchsfreiheit der allgemeinen Mengenlehre.
Math. Ann. 114 (1937), no. 1, 305–315.

I have written about this before. Briefly, one exhibits (definable) translations between the collection \mathsf{HF} of hereditarily finite sets and \mathbb{N}, and verifies that the translation extends to a definable translation of the relations, functions and constants of the language of each structure in a way that \mathsf{PA} verifies that \mathsf{ZFfin} holds in the translation of (\mathsf{HF},\in), and \mathsf{ZFfin} verifies that \mathsf{PA} holds in the translation of {\mathbb N}=(\omega,+,\times,<,0,1). Recall that \mathsf{HF} consists of those sets a whose transitive closure is finite, that is, a is finite, and all its elements are finite, and all the elements of its elements are finite, and so on. Using foundation, one easily verifies that \mathsf{HF}=V_\omega=\bigcup_{n\in\omega}V_n, that is, it is the collection of sets resulting from iterating the power-set operation (any finite number of times) starting from the empty set.

In the direction relevant here, one defines a map h:\mathsf{HF}\to\mathbb{N} by

h(a)=\sum_{b\in a}2^{h(b)}.

One easily verifies, using induction on the set-theoretic rank of the sets involved, that this recursive definition makes sense and is injective (and, indeed, bijective).

Of course this argument uses foundation. In the D’Agostino-Policriti-Omodeo-Tomescu paper they consider instead the theory resulting from replacing foundation with the  anti-foundation axiom, and proceed to describe a suitable replacement for h that injects (codes) \mathsf{HF} into the real numbers. They do quite a bit more in the paper but, for the coding itself, I highly recommend the nice review by Randall Holmes in MathSciNet, linked to above.

The anti-foundation axiom \mathsf{AFA} became known thanks to the work of Peter Aczel, and it is his formulation that I recall below, although it was originally introduced in work of Forti and Honsell from 1983, where they call it X_1. Aczel’s presentation appears in the excellent book

MR0940014 (89j:03039)
Peter Aczel.
Non-well-founded sets. With a foreword by Jon Barwise.
CSLI Lecture Notes, 14. Stanford University, Center for the Study of Language and Information, Stanford, CA, 1988. xx+137 pp.
ISBN: 0-937073-22-9.

The original paper is

MR0739920 (85f:03054)
Marco Forti, Furio Honsell.
Set theory with free construction principles.
Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 10 (1983), no. 3, 493–522.

Given a binary relation R, its field \mathrm{fld}(R) is the union of its domain and codomain. A decoration of R is a function d:\mathrm{fld}(R)\to V satisfying

d(x)=\{d(y)\mid y\mathrel{R}x\}

for all x,y\in\mathrm{fld}(R). When R is \in and the sets in question are well-founded, the only decoration is the identity. Similarly, any well-founded relation R admits a unique decoration. Define \mathsf{AFA} as the statement that any binary R (whether well-founded or not) admits a unique decoration.

In \mathsf{ZF} with foundation replaced with \mathsf{AFA} one can prove the existence of many non-well-founded sets. One of the appealing aspects of \mathsf{AFA} is that the resulting univere is actually quite structured: Other anti-foundation axioms allow the existence of infinitely many Quine atoms, sets x such that x=\{x\}, for instance. Under \mathsf{AFA}, there is exactly one such x, usually called \Omega. The axiom is sometimes described as saying that it provides solutions to many “equations” among sets. For instance, consider the system of equations x=\{y\} and y=\{x\}. Under \mathsf{AFA} the system has x=y=\Omega as its unique solution. Note that assuming \mathsf{AFA}, \Omega is in \mathsf{HF}, as are many other non-well-founded sets.

Here is the open question from the D’Agostino-Policriti-Omodeo-Tomescu paper: Work in set theory with \mathsf{AFA} instead of foundation. Is there a unique, injective, function h:\mathsf{HF}\to \mathbb{R}  satisfying

h(x)=\sum_{y\in x}2^{-h(y)}

for all x,y\in\mathsf{HF}?

Note that there is a unique such h on the well-founded hereditarily finite sets, and it is in fact injective. In general, existence, uniqueness and injectivity of h appear to be open. The claim that there is such a function h is a statement about solutions of certain equations on the reals, and the claim that h is unique requires moreover uniqueness of such solutions. The expectation is that h(x) is transcendental for all non-well-founded hereditarily finite x but, even assuming this, the injectivity of h seems to require additional work.

For example, consider x=\Omega. The function h must satisfy


and, indeed h(\Omega)=0.6411857\dots is the unique solution x of the equation x=2^{-x}

I would be curious to hear of any progress regarding this problem.

Monochromatic colorings

August 20, 2016

Caïus Wojcik and Luca Zamboni recently posted a paper on the arXiv solving an interesting problem in combinatorics on words.
Monochromatic factorisations of words and periodicity.
Caïus Wojcik, Luca Q. Zamboni.

I had recently learned of the problem through another paper by Zamboni and a collaborator,

Aldo de Luca, Luca Q. Zamboni
On prefixal factorizations of words.
European J. Combin. 52 (2016), part A, 59–73.

It is a nice result and I think it may be enjoyable to work through the argument here. Everything that follows is either straightforward, standard, or comes from these papers.

1. The problem

To make the post reasonably self-contained, I begin by recalling some conventions, not all of which we need here.

By an alphabet we simply mean a set A, whose elements we refer to as letters. A word w is a sequence w:N\to A of letters from A where N is a (not necessarily non-empty, not necessarily proper) initial segment of \mathbb N. If we denote w_i=w(i) for all i\in N, it is customary to write the word simply as


and we will follow the convention. The empty word is typically denoted by \Lambda or \varepsilon. By A^* we denote the collection of all finite words from A, and A^+=A^*\setminus \{\varepsilon\}. By |x| we denote the length of the word x (that is, the size of the domain of the corresponding function).

We define concatenation of words in the obvious way, and denote by x_0x_1 the word resulting from concatenating the words x_0 and x_1, where x_0\in A^*. This operation is associative, and we extend it as well to infinite concatenations.

If a word w can be written as the concatenation of words x_0,x_1,\dots,


we refer to the right-hand side as a factorization of w. If w=xy and x is non-empty, we say that x is a prefix of w. Similarly, if y is non-empty, it is a suffix of w. By x^n for n\in\mathbb N we denote the word resulting form concatenating n copies of x. Similarly, x^{\mathbb N} is the result of concatenating infinitely many copies.

By a coloring we mean here a function c:A^+\to C where C is a finite set of “colors”.

Apparently the problem I want to discuss was first considered by T.C. Brown around 2006 and, independently, by Zamboni around 2010. It is a question about monochromatic factorizations of infinite words. To motivate it, let me begin with a cute observation.

Fact. Suppose w=w_0w_1\dots is an infinite word, and c is a coloring. There is then a factorization 


where all the x_i\in A^+ have the same color.

Proof. The proof is a straightforward application of Ramsey’s theorem: Assign to c the coloring of the set [\mathbb N]^2 of 2-sized subsets of \mathbb N given by d(\{i,j\})=c(w_iw_{i+1}\dots w_{j-1}) whenever i<j. Ramsey’s theorem ensures that there is an infinite set I=\{n_0<n_1<\dots\} such that all w_{n_i}w_{n_i+1}\dots w_{n_j-1} with i<j have the same color. We can then take p=w_0\dots w_{n_0-1} and x_i=w_{n_i}\dots w_{n_{i+1}-1} for all i. \Box

In the fact above, the word w was arbitrary, and we obtained a monochromatic factorization of a suffix of w. However, without additional assumptions, it is not possible to improve this to a monochromatic factorization of w itself. For example, consider the word w=01^{\mathbb N} and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }0\mbox{ appears in }x,\\ 1&\mbox{otherwise.}\end{array}\right.

If nothing else, it follows that if w is an infinite word that admits a monochromatic factorization for any coloring, then the first letter of w must appear infinitely often. The same idea shows that each letter in w must appear infinitely often.

Actually, significantly more should be true. For example, consider the word

w=010110111\dots 01^n0 1^{n+1}\dots,

and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }x\mbox{ is a prefix of }w,\\1&\mbox{otherwise.}\end{array}\right.

This example shows that in fact any such w must admit a prefixal factorization, a factorization


where each x_i is a prefix of w.

Problem. Characterize those infinite words w with the property P that given any coloring, there is a monochromatic factorization of w.

The above shows that any word with property P admits a prefixal factorization. But it is easy to see that this is not enough. For a simple example, consider


Consider the coloring c where c(x)=0 if x is not a prefix of w, c(0)=1, and c(x)=2 otherwise. If


is a monochromatic factorization of w, then x_0=01\dots so c(x_0)=2 and each x_i must be a prefix of w of length at least 2. But it is easy to see that w admits no such factorization: For any n>2, consider the first appearance in w of 0^{n+1} and note that none of the first n zeros can be the beginning of an x_i, so for some j we must have x_j=01\dots 10^n and since n>2, in fact x_j=01\dots 10^n10^n, but this string only appears once in w, so actually j=0. Since n was arbitrary, we are done.

Here is a more interesting example: The Thue-Morse word


was defined by Axel Thue in 1906 and became known through the work of Marston Morse in the 1920s. It is defined as the limit (in the natural sense) of the sequence x_0,x_1,\dots of finite words given by x_0=0 and x_{n+1}=x_n\bar{x_n} where, for x\in\{0,1\}^*, \bar x is the result of replacing each letter i in x with 1-i.

This word admits a prefixal factorization, namely


To see this, note that the sequence of letters of t can be defined recursively by t_0=0, t_{2n}=t_n and t_{2n+1}=1-t_n. To see this, note in turn that the sequence given by this recursive definition actually satisfies that t_n is the parity of the number of 1s in the binary expansion of n, from which the recursive description above as the limit of the x_n should be clear. The relevance of this observation is that no three consecutive letters in t can be the same (since t_{2n+1}=1-t_{2n} for all n), and from this it is clear that t can be factored using only the words 0, 01, and 011.

But it is not so straightforward as in the previous example to check whether t admits a factorization into prefixes of length larger than 1.

Instead, I recall a basic property of t and use it to exhibit an explicit coloring for which t admits no monochromatic factorization.

Read the rest of this entry »