15,634 reputation
1191146
bio website gowers.wordpress.com
location
age
visits member for 5 years
seen Mar 16 at 23:40
Mathematics professor at Cambridge

Apr
16
comment Pairwise intersecting sets of fixed size
It was meant to be the second or your possibilities, so 2^{k+1} vertices in all.
Apr
10
comment Most 'unintuitive' application of the Axiom of Choice?
Another point I wanted to make was that if your set is chosen using AC, then it's not really clear what it means to choose a random real and ask whether it lands in the set. After all, you haven't said what the set is. So I'm not sure we would get this oscillatory behaviour because I'm not sure it's possible to make mathematical sense of the experiment in the first place. I do like it though ...
Apr
10
comment Most 'unintuitive' application of the Axiom of Choice?
Suppose you construct a non-measurable set of 01-sequences as follows. Call two sequences equivalent if they differ in finitely many places. Choose a sequence from each equivalence class, and then let your set be the set of all sequences that have even symmetric difference with the chosen representative of its equivalence class. It feels as though a random sequence should have probability 1/2 of belonging to the set. And if you change the definition to "symmetric difference has size congruent to 0 mod 100, it feels as though the probability should be 1/100. I'm confused.
Apr
10
comment Most 'unintuitive' application of the Axiom of Choice?
The existence of undetermined games is an easy application of the axiom of choice, and somewhat strange. Another is the existence of a set in the plane that intersects every line exactly twice, though it is not known whether choice is needed for that one.
Apr
8
comment What's a natural candidate for an analytic function that interpolates the tower function?
A smoother way of thinking about the same basic idea would be to define the coefficient a_n to be eta(n)^n, where eta is a function that converges to zero very very slowly. Then the given function will tend to infinity very very quickly. It's then just a question of working out the relationship between the two growth rates and making eta(n) as "nice" as possible.
Apr
6
comment A graph on irrationals where p is adjacent to q if p^q or q^p is rational.
Since the degree of each vertex is at most countable, each component is countable, so the number of components is the cardinality of the continuum.
Apr
1
comment Estimate rate of real correct/wrong from 4 answers quiz.
Without some extra information or hypothesis, the evidence is consistent with everyone who answered "Buzz Lightyear" genuinely believing that, and also consistent with everybody making the "Buzz Aldrin" confusion. But it sounds as though you have some prior distribution in mind, which tells you that if someone answers "Buzz Lightyear" then the probability that they think the answer is a character in Toy Story is almost zero. I don't think you can do without that, so if you really want to understand this example you may need to supplement it with another experiment.
Mar
31
comment Is this a well known NP-complete problem?
AH -- that changes things ...
Mar
31
comment Is this a well known NP-complete problem?
That doesn't quite work if you regard non-edges as having weight zero, but even if you do have that convention you can make them into edges with very large weight instead and then the argument works again.
Mar
31
comment Is this a well known NP-complete problem?
The fact that you don't specify the start and end node is irrelevant since if you can do it in polynomial time with a specific pair of nodes then you can do it in polynomial time by checking all $n^2$ pairs of nodes.
Mar
30
comment How do we recognize an integer inside the rationals?
I find it hard to get my head round this question. How is the rational number presented to us? And why can't we presuppose that we know how to write an arbitrary rational number as a quotient of integers and reduce? I thought I did know how to do that ...
Mar
26
comment Why is a topology made up of 'open' sets?
Here's an example. Suppose I define the product topology on X={0,1}^N. I won't tell you what an open set is. Instead I'll say that the b.o.n. B_n(x) is the set of all sequences that agree with x up to n. Then I can define the continuity at x of a map from X to X without ever having to say what an open set is. So basic open neighourhoods are playing a role similar to balls of radius epsilon in metric-space theory. To relate this definition to metric spaces I don't have to prove that a map between metric spaces is continuous if and only if the inverse image of an open set is open.
Mar
26
comment Why is a topology made up of 'open' sets?
I have no such scruples. I basically agree with Kevin and was trying to put his point in a different way. Here's yet another way of putting it. Open sets have a nice stability property. I think it doesn't really add anything to call them rulers instead, since one is then forced to distort one's intuitive picture of what a ruler does. Probably the best one can do is say that there is a more general notion of stability (roughly, one where if a statement is true then it is robustly true) and that in this context it is captured well by open sets.
Mar
26
comment How has “what every mathematician should know” changed?
After reading Barry Mazur's beautiful five pages, I feel (probably temporarily) as though there is nothing more to say on this topic.
Mar
25
comment Do the empty set AND the entire set really need to be open?
It's not clear to me how much of a problem it is sometimes to have discontinuous constant functions, if the openness of the empty set follows whenever you have two disjoint open sets (and the openness of the whole space follows if every point has a neighbourhood). One could then define a space to be T_{-3} if the empty set and the whole space happen to be open and comment that all reasonable spaces are T_{-3}. But non-T_{-3} spaces are just too silly to be worth considering, so one doesn't do this.
Mar
24
comment Why is a topology made up of 'open' sets?
I think the important point is that there is an idealization going on here. A truly real-world ruler would have the property that some points are definitely in, some definitely out, and there's a fuzzy region in the middle. But an open set is defined to be one where if you're in then you're definitely in (whereas if you're on the boundary then it's very hard to tell that you're not in). We could just as well have closed rulers and define topology via closed sets.
Mar
20
comment How do you motivate a precise definition to a student without much proof experience?
Whether they know what it means is a fascinating question, because at some level they do, even if they can't give a rigorous definition. I think if they understand raising to a rational power, they will sort of feel that 2 to the root 2 is going to be well approximated by 2 to the 1.414, for instance. And from there they will see how in principle you could work out 2 to the root 2 to arbitrary accuracy. But of course they may never have explicitly articulated such thoughts.
Mar
19
comment Triangles, squares, and discontinuous complex functions
I don't want to spoil anyone else's fun, but it's not giving too much away to say that it can also be done without the axiom of choice. In fact, when I've set this question I've tended to get about as many constructions as people who seriously attempted the question.
Mar
19
comment Triangles, squares, and discontinuous complex functions
Incidentally, it's a nice exercise to find a map from the reals to the reals that takes every value in every open interval. Using that it isn't hard to find a map of the kind I'm claiming exists.
Mar
19
comment Triangles, squares, and discontinuous complex functions
Yes. Just pick a single square and then make sure that the image of every open set is equal to that square -- which can be done in many ways.