Profile

Cover photo
Andres Caicedo
Lives in Ann Arbor
3,632 followers|196,272 views
AboutPostsPhotosVideos

Stream

Andres Caicedo

Shared publicly  - 
 
 
Maths moves at a faster pace these days... only eight days after the breakthrough of Croot, Lev, and Pach obtaining for the first time an exponentially strong upper bound on the cap set problem in (Z/4Z)^n, Jordan Ellenberg has adapted the argument to the original setting of (Z/3Z)^n; we now know that the smallest capset in this space has size between 2.2174^n and 2.756^n asymptotically. (I blogged about the cap set problem in one of my first blog posts way back in 2007: https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/ .) The argument looks like it will also extend to other finite fields than Z/3Z.

Like Dvir's argument solving the finite field Kakeya problem, it ends up being a very short (3 pages) application of the polynomial method. Basically, the point is that if A is a capset (avoiding 3-term progressions), and P(x) is some polynomial that vanishes outside of -A but is nonzero for many values of -A, then the polynomial P(x+y) vanishes on all of A x A except on the diagonal, where it has a lot of nonzeroes. But this forces the rank of the matrix P(x+y) for x,y in A to be large, which in turn forces the degree of P to be large. The usual linear algebra and dimension counting of the polynomial method then finishes off the proof.

The original problem of improving the bounds in Roth's theorem remains open (much as the Euclidean Kakeya problem does), but it at least gives hope that the current logarithmic-type upper bounds for Roth's theorem (based on Fourier methods) can be improved, given that the Fourier methods have finally been dethroned from their long-held title as claimants to the strongest quantitative bounds in the finite field setting.
1 comment on original post
2
Add a comment...

Andres Caicedo

Shared publicly  - 
 
 
From 4888 states to 31

...for a Turing machine that halts if and only if Goldbach's conjecture is false

http://www.scottaaronson.com/blog/?p=2725#comment-1086583

The big question is, though, that this is a custom approach that most likely will not impact so impressively on the Con(ZFC) machines
I've supervised a lot of great student projects in my nine years at MIT, but my inner nerdy teenager has never been as personally delighted by a project as it is right now. Today, I'm proud to announce that Adam Yedidia, a PhD student at MIT (but an MEng student when he did most of this work), ...
1 comment on original post
4
Add a comment...

Andres Caicedo
owner

Discussion  - 
 
 
Von Neumann's axiom of Limitation of Size

Von Neumann had an explosive influence on all the fields he was involved in, sometimes literally. His larger than life persona seems to starkly contrast with one of his major contributions to set theory, the axiom of limitation of size.

In set theory, and to a large extent in category theory, we really want to pretend that there are some collections that we can talk and reason about, despite the fact that they cannot be sets, since they are too large to reason about. We can cheat in the usual ZF framework, and talk about "predicates" which are formulas P(x) with some free variable x, and then we take P(x) to be the class of all objects which satisfy P. This is both a little awkward, since we have to work with formulas themselves instead of actual objects of the theory, and it's a bit unsatisfying, since the whole point of formal logic is to not have to encode all our reasoning mechanisms into the objects of the logic itself.

Luckily, our logical tools are quite well suited to solving these kinds of problems, and there exist some powerful class theories, which extend set theory with a primitive notion of class, which are the "real" collections, of which sets are only a special case. Class theory is quite elegant in it's formulation, with an unrestricted schema of comprehension, which allows classes to be defined for any predicate P(x): {x | P(x)} is always a class, provided the quantifiers in P are restricted to sets. In turn, a set is defined to be anything which is a member of a class! Intuitively, classes can be "large", but their members (which may also have members, etc) must be "small".

Set theory proceeds from here relatively unchanged, with axioms asserting that certain classes are actually sets, instead of directly asserting existence. The usual suspects of "large" classes, ordinals, the class of groups, the class of all sets can be proven to not be sets, using some kind of Russel or Burali-Forti paradox. It turns out that (if Choice is assumed) all of these classes can be put into bijection with the class of all sets (it's actually non-trivial to show this for the class of ordinals). It's pretty natural to wonder if this is the case for all non-set classes. But it's intuitively rather clear that, at least, the most intuitive way of building such classes, e.g. by taking the "power class" of the class of sets, are not available. So a pretty natural axiom to take is: "There are no classes larger (in cardinality) than the class of all sets".

Since the class of all sets is supposed to contain, well, all the "small" sets, one might be naturally driven to the Axiom of Limitation of Size (ALS):

"Every class is either a set, or in bijection with the class of all sets"

But contrary to it's name, this axiom enables proving the existence of all sorts of objects! In particular: class theory without union, replacement, or choice, but with the ALS implies all these principles! For instance, every set can be well ordered by the fact that the class of ordinals is not a set: there is by ALS a bijection with the class of all sets, and so every set is well ordered by it's image in the bijection. Similarly, if the image of a functional relation with domain a set is not a set, then that image must be in bijection with the class of all sets, and so is in bijection with some (pre-image) set, which is impossible! This implies foundation.

The ALS even allows us to limit class comprehension to a set of finite instances. At the time, this was a somewhat significant result, since for some reason people were more comfortable with finite axiomatizations than with schemas (even though it's pretty trivial to conservatively extend any theory with shemas into a theory with a finite number of axioms), which dispelled the notion that set theory needed "something infinite" in its axiomatization.

On the face of it, the ALS seems therefore somewhat miraculous. We have a very simple set of axioms which not only formalizes a very handy set theory, but implies all the nastier set theory axioms like choice and replacement, that mathematicians would rather not get their hands dirty with. This is the set theorists' ontological dream: simple, intuitive axioms with rich, and hopefully consistent consequences.

Unfortunately, I think this dream is an illusion. One clue is that despite the nice formulation of the axioms, mathematicians tend to actually use choice and replacement rather than the alternative. Also, it's actually disturbing to have such a simple axiom with such rich consequences. This is usually the sign of an inconsistency or at least a mis-match with our intuition. The fact that the name "limitation of size" is so off the mark is also not reassuring. The axiom also has suspicious hints of GCH: every class is either small or exactly "class of sets" sized. No room for "intermediate" sizes.

In fact, the reason we really think this axiom is consistent at all is because it is of equal "strength" as ZFC + there exists a strongly inaccessible cardinal! The "explanation" goes in the opposite direction (from ZFC + stuff -> class theory + ALS). It goes without saying as well that set theorists and logicians in general are interested in models of set theory where choice does not hold, and so ALS is right out, and we need foundation and comprehension again.

So despite it's a priori elegance, the ALS is simply not very useful in building an intuitive picture of the world of sets, which is the ultimate goal of the set theory community. Still though, it's fun to work with, and the proofs of the implications of the standard ZFC rules are really cute. I wonder what other "deceptively simple" axioms or postulates appear in different fields. Being "complex continuous" springs to mind, since it implies being analytical, an astronomically stronger condition in the reals. Maybe I'll ask on mathoverflow (or find a pre-existing post about this...)
12 comments on original post
4
Add a comment...

Andres Caicedo

Shared publicly  - 
 
A couple of days ago I received by mail a copy of what seems to be Hugh's first (unpublished) paper (this is [28] in the quotes below). The title page reads "Discontinuous homomorphisms from C(Ω) and the partially ordered set ω^ω", Hugh Woodin, Fall 1976.

Together with Paul Larson and two other colleagues, I am in the process of editing a volume of proceedings to appear in Contemporary Mathematics, to celebrate Hugh's 60th birthday. There was a meeting in Harvard last year in his honor.
https://plus.google.com/+AndresCaicedo0/posts/NmUBxppwoxy
https://andrescaicedo.wordpress.com/2015/04/01/woodin-meeting/

One of the papers is a lovely survey by Garth Dales on "Norming infinitesimals of large fields". Dales uses the opportunity to recall a couple of anecdotes regarding Hugh.

He says in the introduction: "I first met Hugh in the year 1983-84 when he was one of my TAs for a calculus class that I was teaching at Berkeley. (As a TA, Hugh was initially quite puzzled that there were students at Berkeley who did not understand concepts that were very obvious to him, but he quickly learned about reality.) Subsequently we worked together on two books, and this meant that Hugh came to our house in England quite a few times. This was great pleasure for us. It was something of a shock to my wife and myself to receive an invitation to come to Harvard for a conference to mark Hugh's 60th birthday: how could this charming young man have reached so mature a level?"

He adds some historical remarks at the end: "The paper [5] was mainly worked out in the year 1973-74, whilst I was at UCLA; I thank Phil. Curtis for inviting me to UCLA and for much support. I gave lectures on this at the inaugural conference on Banach algebras in July, 1974. The work was mostly written in the year 1974-75." He proceeds to explain his result (obtained independently at about the same time by Jean Esterle), namely that, under the continuum hypothesis (CH), given any infinite compact space Ω, there is a discontinuous homomorphism from C(Ω) into some Banach algebra.

He continues: "The paper [5] was submitted in May, 1976.

"I then thought how one could remove `(CH)' from the theorem, but could not do this; with some trepidation I wrote in June 1976 to Professor Robert Solovay at Berkeley, and asked for his help in this. (Young colleagues might like to know that one wrote by hand on paper in those distant days; but we did have airmail.) This letter eventually reached Solovay at Caltech, where he was on leave.

"The next part of the story is based on information from Frederick Dashiell, then a Bateman Research Instructor at Caltech; I am grateful to Fred for this.

"Hugh Woodin, then a junior at Caltech, approached Fred in January 1976 for a topic for his senior thesis. Fred suggested that Hugh organize what was known about Kaplansky's problem up to that point, and explain the heart of the open question on homomorphisms from C( βℕ). Hugh ignored the survey part of the suggestion, and immediately started trying to construct a model of NDH ["no discontinuous homomorphisms"]; he was learning about forcing at that time, and discussed the question with Solovay, the leading expert on forcing. Hugh produced a type-written document [28] that I have
in `Fall 1976'; by that time Hugh had seen the preprint of [5]. It seems that this document was not submitted as a senior thesis, and that it has not been published, but results from it are contained in Hugh's thesis [29] and in [8]. The paper [28] seems to be Hugh's first contribution to mathematics.

"In fact, Hugh proved in [28,§5] that it is consistent with ZFC that there is an ultrafi lter U such that ℓ^∞/U does not admit a non-zero algebra semi-norm, and, in [28,§6], he gave a set-theoretic condition, now `Woodin's condition', which, if satisfied, implies NDH. Subsequently Solovay showed that this condition was consistent with ZFC, and lectured on this on 26 October 1976; this argument was never published because Hugh himself soon gave a shorter proof of the same result. ...

"After some time Solovay kindly replied to my letter, saying that `Woodin' had shown that there are models of set theory in which NDH is true. I wrote to the person that I took to be `Professor Woodin' at Caltech to ask about this, and received [28] in response."

A short while back there were a post or two here on Woodin's "cryptic marks", 
https://plus.google.com/+DavidRoberts/posts/TtiW4dMiFcF
and
https://plus.google.com/+DavidRoberts/posts/P7oxqv8nhxL

Dales also has something to say in this regard: "It will be apparent that the original insights into the theorems of the second half of [9], including all theorems that involve forcing, were due to Hugh Woodin.
My comment on his method of proof is the following: first, there were discussions on the likelihood that one class was contained in another class, and possible counter-examples were considered; the questions were clari fied and the undergrowth cleared away; then Hugh thought about the matter for some time, and drew a large number of squiggly lines on a sheet of white paper; then he opined, using remarkable insight on what would be true in certain models of set theory, that a particular containment would be relatively consistent with ZFC + GCH. These insights were almost always completely correct in the end; but it took many days and many pages to craft a careful proof."

The references mentioned above are

[5] H. G. Dales, A discontinuous homomorphism from C(X), American J. Math., 101 (1979), 647-734.

[8] H. G. Dales and W. H. Woodin, An introduction to independence for analysts, London Mathematical Society Lecture Note Series 115, Cambridge University Press, 1987.

[9] H. G. Dales and W. H. Woodin, Super-real fields: totally ordered fields with additional structure, London Mathematical Society Monographs, Volume 14, Clarendon Press, Oxford, 1996.

[29] W. H. Woodin, Discontinuous homomorphisms of C(Ω) and set theory, Thesis, University of California, Berkeley, 1984.
6
Andres Caicedo's profile photoYemon Choi's profile photo
4 comments
 
+Andres Caicedo Oops. Well, I'm sure my "correction" was still in the vein of Dales...
Add a comment...
In his circles
879 people
Have him in circles
3,632 people
James Macgill's profile photo
Neuralice morena sodre's profile photo
Harold Ray's profile photo
Christian Egeberg's profile photo
Américo Tavares's profile photo
Negin Motamedi's profile photo
Rafael Menendez-Barzanallana Asensio's profile photo
Hendri Awan's profile photo
Mariano Nalin's profile photo

Andres Caicedo

Shared publicly  - 
 
 
Remember that 4888-state Turing machine that halts iff Golbach's conjecture is false? Here's an explicit 27-state TM that does the same

https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6

Notation is from the Aaronson-Yedidia paper announced at http://www.scottaaronson.com/blog/?p=2725

(Permalink to 27-state TM announcement: http://www.scottaaronson.com/blog/?p=2725#comment-1088811)

#openscience  
7 comments on original post
2
Add a comment...

Andres Caicedo

Shared publicly  - 
 
 
The Canadian Conference on Computational Geometry (CCCG 2016) has a web site set up in such a way that I can't produce any kind of useful link here, but after some fits and starts it's online at http://www.sfu.ca/~shermer/CCCG2016/ with a submission deadline on May 10 (a little over one week) and the conference itself to be held at Simon Fraser University in Vancouver in early August. It's always a fun conference, so I'd encourage those of you interested in this subject to participate.
View original post
1
Add a comment...

Andres Caicedo

Shared publicly  - 
 
 
A new journal seen via Prof. Mark Sapir on Facebook: 

"Journal of Combinatorial Algebra is devoted to publication of research articles of the highest level. Its domain is the rich and deep area of interplay between combinatorics and algebra. Its scope includes combinatorial aspects of group, semigroup  and ring theory, representation theory, commutative algebra, algebraic geometry and dynamical systems. Exceptionally strong research papers from all parts of mathematics related to these fields are also welcome."
Journal of Combinatorial Algebra European Mathematical Society. Editorial Board · Aims and Scope · Instructions for Authors.
View original post
5
Add a comment...

Andres Caicedo

Shared publicly  - 
 
 
The Foundations of mathematics (FOM) mailing list, which I left a while ago due to unfair moderating practices, seems to have gone crazy with infinite discussions of "Set theory versus Homotopy Type Theory".

I find the whole activity ridiculous and based on the false premise that the two foundations are in opposition (as attested by the titles of discussion threads), or that they cannot co-exist, or that all foundations of mathematics need to be linearly ordered. These are all childish and false motivations.

The discussions are further hampered by the fact that no expert in homotopy type theory is taking part. This might partly be a consequence of the lessons learned in the 1990's when FOM was extremely hostile to category theorists, although I suspect (and can affirm for myself personally) that the questions asked and the issues raised by Harvey Friedman are simply not relevant to the HoTT crowd. There seems to be a very fundamental difference in perception of what foundations of mathematics are, ought to be, and what purpose they serve.

Supplemental: I have deleted the extremely long comments that appeared under this post without reading them and have disabled further comments. I also deleted one paragraph of my post which was arguably something that required a reply. I am simply not in the business of prolonging discussions with titles like "HoTT vs. ZFC" that present "challenges to HoTT" or "challenges to ZFC", etc. They are counter-productive and do not serve any purpose that would warrant them appearing on my posts. If anyone feels like producing yet more discussions, they are welcome to do so under their own G+ account. It is easy enough to reference this post. But do not expect me to participate, I simply wanted to express publicly my disappointment with the FOM contracting a very common Internet sickness.
April 2016 Archives by thread. Messages sorted by: [ subject ] [ author ] [ date ] · More info on this list... Starting: Fri Apr 1 01:23:14 EDT 2016. Ending: Wed Apr 13 19:14:11 EDT 2016. Messages: 79. [FOM] Philosophical coherence and foundational role of set and type theory Astor, Eric P.
View original post
3
Add a comment...

Andres Caicedo
owner

Discussion  - 
 
From Nam Trang and Martin Zeman:

"Dear colleagues,

the next Core Model Induction + Hod Mice meeting will be held at UC Irvine during July 18 -- July 29, 2016. The format of the meeting will be the same as that of previous meetings in Muenster and Palo Alto. That is, the second week is expected to be more informal with more emphasis on interaction between the participants."

For details, in particular regarding funding, please contact Martin or Nam at UC Irvine.
1
Add a comment...

Andres Caicedo

Shared publicly  - 
 
 
Dear Colleagues: The Journal of Number Theory is delighted to publish a special issue in honor of the work of Winnie Li! The papers will be freely available till the end of May. For more information, please visit
http://www.journals.elsevier.com/journal-of-number-theory/news/honoring-of-the-lifelong-work-of-wen-ching-winnie-li/
Elsevier is a world-leading provider of scientific, technical and medical information products and services
View original post
1
Timothy Gowers's profile photoDavid Roberts's profile photo
2 comments
 
Thanks, Tim. Much more constructive than the comment I was tempted to make.
Add a comment...
People
In his circles
879 people
Have him in circles
3,632 people
James Macgill's profile photo
Neuralice morena sodre's profile photo
Harold Ray's profile photo
Christian Egeberg's profile photo
Américo Tavares's profile photo
Negin Motamedi's profile photo
Rafael Menendez-Barzanallana Asensio's profile photo
Hendri Awan's profile photo
Mariano Nalin's profile photo
Work
Occupation
Mathematician
Employment
  • Math Reviews, 2015 - present
Basic Information
Gender
Male
Story
Introduction
Mathematician.  Associate editor at Math Reviews. Father of two.
Places
Map of the places this user has livedMap of the places this user has livedMap of the places this user has lived
Currently
Ann Arbor
Previously
Boise, ID - Bogotá, Colombia - Oakland, CA - El Cerrito, CA - Vienna - Pasadena, CA - Ann Arbor