I ran last night into the Flickr page for this conference essentially by accident. Couldn’t find who to credit for this picture.
I would like to highlight a cute question in a recent paper,
Recall that W. Ackermann verified what in modern terms we call the bi-interpretability of and , where the latter is (first-order) Peano arithmetic, and the former is finite set theory, the result of replacing in the axiom of infinity with its negation (and with foundation formulated as the schema of -induction). The reference is
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 of hereditarily finite sets and 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 verifies that holds in the translation of and verifies that holds in the translation of . Recall that consists of those sets whose transitive closure is finite, that is, 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 , 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 by
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 that injects (codes) 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 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 . Aczel’s presentation appears in the excellent book
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.
The original paper is
Given a binary relation , its field is the union of its domain and codomain. A decoration of is a function satisfying
for all . When is and the sets in question are well-founded, the only decoration is the identity. Similarly, any well-founded relation admits a unique decoration. Define as the statement that any binary (whether well-founded or not) admits a unique decoration.
In with foundation replaced with one can prove the existence of many non-well-founded sets. One of the appealing aspects of is that the resulting univere is actually quite structured: Other anti-foundation axioms allow the existence of infinitely many Quine atoms, sets such that , for instance. Under , there is exactly one such , usually called . The axiom is sometimes described as saying that it provides solutions to many “equations” among sets. For instance, consider the system of equations and . Under the system has as its unique solution. Note that assuming , is in , 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 instead of foundation. Is there a unique, injective, function satisfying
for all ?
Note that there is a unique such on the well-founded hereditarily finite sets, and it is in fact injective. In general, existence, uniqueness and injectivity of appear to be open. The claim that there is such a function is a statement about solutions of certain equations on the reals, and the claim that is unique requires moreover uniqueness of such solutions. The expectation is that is transcendental for all non-well-founded hereditarily finite but, even assuming this, the injectivity of seems to require additional work.
For example, consider . The function must satisfy
and, indeed is the unique solution of the equation .
I would be curious to hear of any progress regarding this problem.
I had recently learned of the problem through another paper by Zamboni and a collaborator,
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 , whose elements we refer to as letters. A word is a sequence of letters from where is a (not necessarily non-empty, not necessarily proper) initial segment of . If we denote for all , it is customary to write the word simply as
and we will follow the convention. The empty word is typically denoted by or . By we denote the collection of all finite words from , and By we denote the length of the word (that is, the size of the domain of the corresponding function).
We define concatenation of words in the obvious way, and denote by the word resulting from concatenating the words and , where . This operation is associative, and we extend it as well to infinite concatenations.
If a word can be written as the concatenation of words
we refer to the right-hand side as a factorization of . If and is non-empty, we say that is a prefix of . Similarly, if is non-empty, it is a suffix of . By for we denote the word resulting form concatenating copies of . Similarly, is the result of concatenating infinitely many copies.
By a coloring we mean here a function where 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 is an infinite word, and is a coloring. There is then a factorization
where all the have the same color.
Proof. The proof is a straightforward application of Ramsey’s theorem: Assign to the coloring of the set of -sized subsets of given by whenever . Ramsey’s theorem ensures that there is an infinite set such that all with have the same color. We can then take and for all .
In the fact above, the word was arbitrary, and we obtained a monochromatic factorization of a suffix of . However, without additional assumptions, it is not possible to improve this to a monochromatic factorization of itself. For example, consider the word and the coloring
If nothing else, it follows that if is an infinite word that admits a monochromatic factorization for any coloring, then the first letter of must appear infinitely often. The same idea shows that each letter in must appear infinitely often.
Actually, significantly more should be true. For example, consider the word
and the coloring
This example shows that in fact any such must admit a prefixal factorization, a factorization
where each is a prefix of .
Problem. Characterize those infinite words with the property P that given any coloring, there is a monochromatic factorization of .
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 where if is not a prefix of , 1, and otherwise. If
is a monochromatic factorization of , then so and each must be a prefix of of length at least . But it is easy to see that admits no such factorization: For any , consider the first appearance in of and note that none of the first zeros can be the beginning of an , so for some we must have and since , in fact , but this string only appears once in , so actually . Since 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 of finite words given by and where, for , is the result of replacing each letter in with .
This word admits a prefixal factorization, namely
To see this, note that the sequence of letters of can be defined recursively by , and . To see this, note in turn that the sequence given by this recursive definition actually satisfies that is the parity of the number of s in the binary expansion of from which the recursive description above as the limit of the should be clear. The relevance of this observation is that no three consecutive letters in can be the same (since for all ), and from this it is clear that can be factored using only the words , , and .
But it is not so straightforward as in the previous example to check whether admits a factorization into prefixes of length larger than .
Instead, I recall a basic property of and use it to exhibit an explicit coloring for which admits no monochromatic factorization.
I have just posted on my papers page a preprint of a review of
Reflections—the magic, music and mathematics of Raymond Smullyan.
World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. x+213 pp.
ISBN: 978-981-4644-58-7; 978-981-4663-19-9
that I have submitted to Mathematical Reviews.
Mathematical Reviews (MR) and zbMATH cooperate in maintaining the Mathematics Subject Classification (MSC), which is used by these reviewing services, publishers, and others to categorize items in the mathematical sciences literature. The current version, MSC2010, consists of 63 areas classified with two digits refined into over 5000 three- and five-digit classifications. Details of MSC2010 can be found at www.msc2010.org or www.ams.org/msc/msc2010.html and zbmath.org/classification/.
MSC2010 was a revision of the 2000 subject classification scheme developed through the collaborative efforts of the editors of zbMATH and MR with considerable input from the community. zbMATH and MR have initiated the process of revising MSC2010 with an expectation that the revision will be used beginning in 2020. From the perspective of MR and zbMATH, the five-digit classification scheme MSC is an extremely important device that allows editors and reviewers to process the literature. Users of the publications of zbMATH and MR employ the MSC to search the literature by subject area. In the decade since the last revision, keyword searching has become increasingly prevalent, with remarkable improvements in searchable databases. Yet, the classification scheme remains important. Many publishers use the subject classes at either the time of submission of an article, as an aid to the editors, or at the time of publication, as an aid to readers. The arXiv uses author-supplied MSC codes to classify submissions, and as an option in creating alerts for the daily listings. Browsing the MR or zbMATH database using a two- or three-digit classification search is an effective method of keeping up with research in specific areas.
Based in part on some thoughtful suggestions from members of the community, the editors of MR and zbMATH have given preliminary consideration to the scope of the revision of the MSC. We do not foresee any changes at the two-digit level; however, it is anticipated that there will be refinement of the three- and five-digit levels.
At this point, zbMATH and MR welcome additional community input into the process. Comments should be submitted through the Web at msc2020.org. You may also send email to firstname.lastname@example.org. All information about the MSC revision is jointly shared by MR and zbMATH. This input will be of great value as the process moves forward.