Reputation
16,887
Next privilege 20,000 Rep.
Access 'trusted user' tools
Badges
17 107 153
Impact
~1.1m people reached

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.
Mar
13
comment Is the ratio Perimeter/Area for a finite union of unit squares at most 4?
Suppose you have an arbitrary union U of unit squares and another unit square S. Is it possible that the ratio of the length of the part of the boundary of S that is not in U to the area of S\U is greater than 4? I presume it is, or else there would be an easy inductive proof. Or is it that this is essentially the question one wants to answer?
Mar
9
comment Prime numbers with given difference
If you could solve the case N_1=1, N_2=3 I'd be very interested ...
Mar
9
comment Best way to teach concept of real numbers using a hands-on activity?
I too was going to suggest calculating square roots by means of successive approximation. I wouldn't go as far as to discuss the subtleties of the real number system, but this would allow them to feel it at an intuitive level.
Mar
8
comment Examples of inequality implied by equality.
It's Cauchy-Schwarz applied to the scalar product of X and the constant function 1.
Mar
8
comment Are there any important mathematical concepts without discrete analog?
I'd say the discrete analogue of a continuous function is one that is continuous in some quantitative way (such as being Lipschitz) on a finite metric space. If the finite metric space is one of a sequence of spaces with unbounded size, this can be very useful.
Mar
8
comment Are there any important mathematical concepts without discrete analog?
It amuses me that this answer has been accepted when discrete mathematicians would use analogues of every single one of these. I recommend a look at this post of Terry Tao: terrytao.wordpress.com/2007/05/23/…
Mar
8
comment Examples of inequality implied by equality.
It's hard to formalize Pete's question, since if A is always at most B then B-A=C for some C that is always non-negative. One needs a notion of "obviously non-negative", which is often provided by a number's being a sum of squares.
Mar
7
comment Criteria for accepting an invitation to become an editor of a scientific journal
How busy are you, how many journals are you already on, and how serious is this journal?
Mar
7
comment How many ways can we characterize gamma function?
I disagree. A characterization would be a set of properties that turned out to be uniquely satisfied by the gamma function. It's like the difference between defining the reals as Dedekind cuts and characterizing them as the unique complete ordered field. There is a characterization of the gamma function as the unique function that satisfies f(n)=(n-1)f(n-1) and has some other smoothness property. Unfortunately, I can't remember what that other property is.