There are two natural arithmetic operations on the class of linear orders: the sum + and lexicographic product x. These operations generalize the sum and product of ordinals. 

The arithmetic laws obeyed by the sum were uncovered in the pre-forcing days of set theory and are surprisingly nice. For example, while the left cancellation law A + X \cong B + X => A \cong B is not true in general, its failure can be completely characterized: a linear order X fails to cancel in some such isomorphism if and only if there is a non-empty order R such that R + X \cong X. Right cancellation is symmetrically characterized. 

Tarski and Aronszajn characterized the commuting pairs of linear orders, i.e. the pairs X and Y such that X + Y \cong Y + X.

Lindenbaum showed that X + X \cong Y + Y implies X \cong Y for linear orders X and Y. More generally, the finite cancellation law nX \cong nY => X \cong Y holds. Lindenbaum showed that the sum even satisfies the Euclidean algorithm! 

On the other hand, the arithmetic of the lexicographic product is much less well understood. The lone totally general classical result is due to Morel, who characterized when the right cancellation law A x X \cong B x X => A \cong B holds. Morel showed that an order X fails to cancel in some such isomorphism if and only if there is a non-singleton order R such that R x X \cong X, in analogy with the additive case. 

In this talk we focus on the question of whether Morel’s cancellation theorem is true on the left. We’ll show that, while the literal left-sided version of Morel’s theorem is false, an appropriately reformulated version is true. Our results suggest that a complete characterization of left cancellation in lexicographic products is possible. We’ll also discuss how our work might help in proving multiplicative versions of Tarski’s, Aronszajn’s, and Lindenbaum’s additive laws.

This is joint work with Eric Paul.  

Abstract: The notions of measure hyperfiniteness and measure reducibility of countable Borel equivalence relations are variants of the usual notions of hyperfiniteness and Borel reducibility. Conley and Miller proved that every basis for the countable Borel equivalence relations strictly above E_0 under measure reducibility is uncountable and asked whether there is a "measure successor of E_0"—i.e. a countable Borel equivalence relation E such that E is not measure reducible to E_0 and any F which is measure reducible to E is either equivalent to E or measure reducible to E_0. In an ongoing work with Patrick Lutz, we have isolated a combinatorial condition on a Borel group action (a strong form of expansion that we call "lossless expansion" after a similar property which is studied in computer science and finite combinatorics) which implies that the associated orbit equivalence relation is a measure successor of E_0. We have also found several examples of group actions which are plausible candidates for satisfying this condition. In this talk, I will explain the context for Conley and Miller's question, the condition that we have isolated and discuss some of the candidate examples we have identified.

All of this is joint work with Patrick Lutz.

At and above the level of measurability, large cardinal notions are typically characterized by the existence of certain elementary embeddings of the universe into an inner model. We may contrast this with smaller large cardinal notions, whose characterizations tend to be strictly combinatorial. In this series of talks, we survey results from Magidor's thesis, in which he shows that the large notion of supercompactness can also be viewed combinatorially, and in this light supercompactness is seen to be a natural strengthening of ineffability. We will also survey modern results which show how these strong combinatorial principles can be forced to hold at small successor cardinals.

NOTE: Tuesday meeting

This is the last lecture in an introductory survey of the theory of algorithmic randomness. The primary question we wish to answer is: what does it mean for a set of natural numbers, or equivalently an infinite binary sequence, to be random? We will focus on three intuitive paradigms of randomness: (i) a random sequence should be hard to describe, (ii) a random sequence should have no rare properties, and (iii) a random sequence should be unpredictable, in the sense that we should not be able to make large amounts of money by betting on the next bit of the sequence. Using ideas from computability theory, we will make each of these three intuitive notions of randomness precise and show that the three define the same class of sets.

We give an introductory survey of the theory of algorithmic randomness. The primary question we wish to answer is: what does it mean for a set of natural numbers, or equivalently an infinite binary sequence, to be random? We will focus on three intuitive paradigms of randomness: (i) a random sequence should be hard to describe, (ii) a random sequence should have no rare properties, and (iii) a random sequence should be unpredictable, in the sense that we should not be able to make large amounts of money by betting on the next bit of the sequence. Using ideas from computability theory, we will make each of these three intuitive notions of randomness precise and show that the three define the same class of sets.