SQuaREs

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.

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, 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

${}[a,b]=aba^{-1}b^{-1}$.

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:

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.

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