April 27, 2012

The American Institute of Mathematics has a great program for what they call focused collaborative research: SQuaREs, which stands for “Structured Quartet Research Ensembles”. A small group, between 4 and 6 members, applies with a particular research project. The groups that are supported spend a week at AIM working on the project, with the possibility of returning.

I am part of a 6 people SQuaRE group, working on “Descriptive aspects of Inner model theory”. The first meeting took place on May 16-20, 2011, you can see a picture here. This year we met for a follow-up, on April 16-20.

These meetings are fantastic, I think. Of course, they are exhausting and quite intense, but they pay off handsomely.

(Left to right: Grigor Sargsyan, Paul Larson, Ralf Schindler, Martin Zeman, John Steel, and myself.)

I expect I’ll be posting soon on some of our results.

515 – Caratheodory’s characterization of measurability (Homework 3)

April 12, 2012

This set is due Friday, April 27.

The goal of these problems is to prove Carathéodory‘s theorem that “extracts” a measure from any outer measure. In particular, when applied to Lebesgue outer measure, this construction recovers Lebesgue measure.

Read the rest of this entry »

305 – A brief update on n(3)

April 12, 2012

This continues the previous post on A lower bound for n(3).

Only recently I was made aware of a note dated November 22, 2001, posted on Harvey Friedman‘s page, “Lecture notes on enormous integers”. In section 8, Friedman recalls the definition of the function n(k), the length of the longest possible sequence x_1,x_2,\dots,x_n from \{1,2,\dots,k\} with the property that for no i<j\le n/2, the sequence x_i,x_{i+1},\dots,x_{2i} is a subsequence of x_j,x_{j+1},\dots,x_{2j}.

Friedman says that “A good upper bound for n(3) is work in progress”, and states (without proof):

Theorem. n(3)\le A_k(k), where k=A_5(5).

Here, A_1,A_2,\dots are the functions of the Ackermann hierarchy (as defined in the previous post).

He also indicates a much larger lower bound for n(4). We need some notation first: Let A(m)=A_m(m). Use exponential notation to denote composition, so A^3(n)=A(A(A(n))).

Theorem. Let m=A(187196). Then n(4)>A^m(1).

He also states a result relating the rate of growth of the function n(\cdot) to what logicians call subsystems of first-order arithmetic. A good reference for this topic is the book Metamathematics of First-order Arithmetic, by Hájek and Pudlák, available through Project Euclid.

There is a recent question on MathOverflow on this general topic.

305 – Derived subgroups of symmetric groups

April 11, 2012

One of the problems in the last homework set is to study the derived group of the symmetric group S_n.

Recall that if G is a group and a,b\in G, then their commutator is defined as


The derived group G' is the subgroup of G generated by the commutators.

Note that, since any permutation has the same parity as its inverse, any commutator in S_n is even. This means that G'\le A_n.

The following short program is Sage allows us to verify that, for 3\le i\le 6, every element of (S_i)' is actually a commutator. The program generates a list of the commutators of S_i, then verifies that this list is closed under products and inverses (so it is a group). It also lists the size of this group. Note that the size is precisely {}|A_i|, so (S_i)'=A_i in these 4 cases:

Read the rest of this entry »

305 – Cube moves

April 11, 2012

Here is a small catalogue of moves of the Rubik’s cube. Appropriately combining them and their natural analogues under rotations or reflections, allow us to solve Rubik’s cube starting from any (legal) position. I show the effect the moves have when applied to the solved cube.

But, first, some relevant links:

Read the rest of this entry »

Determinacy and Jónsson cardinals

April 9, 2012

It is a well known result of Kleinberg that the axiom of determinacy implies that the \aleph_n are Jónsson cardinals for all n\le\omega. This follows from a careful analysis of partition properties and the computation of ultrapowers of associated measures. See also here for extensions of this result, references, and some additional context.

Using his theory of descriptions of measures, Steve Jackson proved (in unpublished work) that, assuming determinacy, every cardinal below \aleph_{\omega_1} is in fact Rowbottom. See for example these slides: 12. Woodin mentioned after attending a talk on this result that the HOD analysis shows that every cardinal is Jónsson below \Theta.

During the Second Conference on the Core Model Induction and HOD Mice at Münster, Jackson, Ketchersid, and Schlutzenberg reconstructed what we believe is Woodin’s argument.

I have posted a short note with the proof on my papers page. The note is hastily written, and I would appreciate any


you find appropriate. I posted a version of the note in August last year, and Grigor Sargsyan soon emailed me some comments, that I have incorporated in the current version.

[I mentioned this on Twitter last year, but apparently not here. These are the relevant links (while discussing the Münster meeting): 1, 2, 3, 4, 5.]

305 – Homework V

April 9, 2012

This is the last homework set of the term. It is due Friday, April 27, 2012, at the beginning of lecture, but I am fine collecting it during dead week, if that works better.

Read the rest of this entry »


April 9, 2012

This is kind of cool, in its own way.

Reunión de la Junta Consultiva Internacional de la Universidad de los Andes, en 1952 en Princeton (New Jersey). En la foto Mario Laserna, fundador de Los Andes, y miembros de la Junta, entre otros, Albert Einstein. En la parte de atrás, el célebre profesor John Von Neumann (padre de los computadores, pionero de la teoría de juegos y uno de los cerebros más creativos de la historia de la humanidad), quien entró a hacer parte de la Junta en 1952.— at Princeton, New Jersey.

Roughly: “Meeting of the International Advisory Board of the University of the Andes in 1952 in Princeton (New Jersey). In the photo Mario Laserna, founder of Los Andes, and members of the Board, among others, Albert Einstein. In the back, the celebrated Professor John von Neumann (the father of computers, a pioneer of game theory and one of the most creative minds in the history of mankind), who joined the Board in 1952. – at Princeton, New Jersey.”

(Found at the Facebook thing. I was an undergrad at the Andes ages ago.)

[Now to make this more than perfect, I would only need a picture of the meeting of Leonel Parra, my first Calculus teacher, with Borges. They talked about infinity, of course.]

Downward transference of mice and universality of local core models

April 4, 2012

Martin Zeman and I have just submitted our paper Downward transference of mice and universality of local core models to the Journal of Symbolic Logic, downloadable from my papers page. We have also uploaded it on the ArXiv. (I should have been doing this for years; this is the first time I post there.)

It is a nice observation that goes back to Friedman that if 0^\sharp exists and {\mathbf M} is an inner model that correctly computes \omega_2, then 0^\sharp\in {\mathbf M}. Looking at a completely different problem, from the theory of forcing axioms, we were led to the question of how much this result can be generalized.

Our main result is that there is a significant transfer of structure going on, simply due to the agreement of cardinals. (The statement of the result and, of course, the argument, require familiarity with fine structure theory, as developed in Steel’s or Martin’s books.)

Theorem. Assume that {\mathbf M} is a proper class inner model, and that \delta is regular in {\mathbf V}.

  1. If there are no inner models of {\mathbf V} with Woodin cardinals, \delta>\omega_1, and

    \{x\in{\mathcal P}_\delta(\delta^+)\cap{\mathbf M}\mid{\rm cf}^{\mathbf M}(x\cap\delta)>\omega\}

    is stationary, then {\mathbf K}^{\mathbf M}\|\delta is universal for all iterable 1-small premice in {\mathbf V} of cardinality less than \delta.

  2. If, in {\mathbf M}, 0^\P does not exist, and {\mathcal P}_\delta(\delta^+)\cap{\mathbf M} is stationary, and \delta>\omega_1, then the same conclusion holds. If \delta=\omega_1, then {\mathbf K}^{\mathbf M}\|\omega_2 is universal for all countable iterable premice in {\mathbf V}.

Here, as usual, {\mathcal P}_\kappa(\lambda) denotes the collection of subsets of \lambda of size less than \kappa. It is easy to check that {\mathcal P}_{\omega_1} (\omega_2)\cap{\mathbf M} is stationary if {\mathbf M} computes \omega_2 correctly, so this result generalizes the statement about 0^\sharp mentioned above.

In fact, it follows that, if \omega_2 is computed correctly in {\mathbf M}, then any sound mouse in {\mathbf V} projecting to \omega and below 0^\P, is in {\mathbf M}. Beyond 0^\P, the argument becomes more complicated, and we need to assume a global anti-large cardinal assumption, namely, that there are no inner models in {\mathbf V} with Woodin cardinals.

We expect that this restriction can be weakened, perhaps even dispensed with.

(This paper is the second in a series, aiming to explore the structure of inner models for which some agreement of cardinals holds. I briefly mentioned the first paper here.)

On CH (After Hamkins)

April 2, 2012

(Wherein I quote from Twitter.)

This is my excuse to put this page to use. It all started, more or less, around here:

Moreno, Javier (bluelephant). “Es muy bueno este artículo de Hamkins sobre algo así como sociología de la teoría de conjuntos: http://arxiv.org/abs/1203.4026” 2 April 2012, 3:39 p.m. Tweet.

Villaveces, Andrés (gavbenyos). “@bluelephant lo siento bastante crudo – me parece que Joel simplemente pone en versión impresa cierto consenso, pero falta argumentar” 2 April 2012, 4:32 p.m. Tweet.

(Loosely translated: “This is a very good article by Hamkins on something akin to sociology of set theory” “I find it weak — I think that Joel is simply putting in writing a known consensus, but needs to argue for it more”) Long story short, I feel Andrés is right, but I thought I should elaborate my view, at least somewhat. Originally I considered writing a blog entry, but it quickly became apparent it would grow longer than I can afford time-wise. So, I used twitter instead.

(But there is a serious caveat, namely, it seems that the paper is intended for a general mathematical and philosophical audience, so the omission of technical issues is most likely intentional. Javier even remarked as much.)

What follows is the series of Tweets I posted. It is not a transcription; to ease reading, I have added a couple of links, reformatted the posts rather than continuing with the MLA suggested approach, very lightly edited the most obvious typos, and added a couple of phrases where I felt more clarity was needed. [Edit, April 22: I also removed a line on MM^{++} vs Woodin’s (*), as the proof of the underlying claim has been withdrawn.]

I started at 10:44 p.m., with a warning: “(Technical pseudo-philosophical thoughts for a few posts.)”

Read the rest of this entry »