User richard dore - MathOverflow

Is R^3 the square of some topological space?

2011-04-02T18:42:06Z

The other day, I was idly considering when a topological space has a square root. That is, what spaces are homeomorphic to $X \times X$ for some space $X$. $\mathbb{R}$ is not such a space: If $X \times X$ were homeomorphic to $\mathbb{R}$, then $X$ would be path connected. But then $X \times X$ minus a point would also be path connected. But $\mathbb{R}$ minus a point is not path connected.

A next natural space to consider is $\mathbb{R}^3$. My intuition is that $\mathbb{R}^3$ also doesn't have a square root. And I'm guessing there's a nice algebraic topology proof. But that's not technology I'm much practiced with. And I don't trust my intuition too much for questions like this.

So, is there a space $X$ so that $X \times X$ is homeomorphic to $\mathbb{R}^3$?

"A gentleman never chooses a basis."

2009-10-13T02:52:28Z

Around these parts, the aphorism "A gentleman never chooses a basis," has become popular.

Is there a gentlemanly way to prove that the natural map from V to V^** is surjective if V is finite dimensionsal?

As in life, the exact standards for gentlemanliness are a bit vague. Some arguments seem to be implicitly pick basis. I'm hoping there's an argument which is unambigously gentlemanly.

Coloring Points in the Plane

2010-02-03T06:20:29Z

Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed?

I heard this problem when I was a kid. Back then the most I knew was that 3 is impossible and 7 is possible (tile hexagons of diameter 1-ε). I haven't heard about this problem since then and I don't know how to search for it. Is more known? Is this problem well known in certain circles?

Answer by Richard Dore for Prime Number Theorem w/o Complex Analysis

2011-07-08T17:36:12Z

If you just want $\pi(n) = \Omega \left( \frac{n}{\log n} \right)$, good enough for many applications, here is a quick proof: The highest power of a prime $p$ dividing $2n \choose n$ is at most $2n$ -- you get at most one more factor of $p$ in the numerator than denominator for each power $p^i \leq 2n$. This tells you that ${2n \choose n} \leq (2n)^{\pi(2n)}$. So $\pi(2n) \geq \frac{\log_2 {2n \choose n}}{\log_2 (2n)} \geq \frac{n}{\log_2 (2n)}$.

Answer by Richard Dore for Omega_1 Categorical Theory

2011-04-01T21:18:04Z

Let $A$ and $B$ be two models of size $\omega_1$. In both A and B, being in the same cycle is an equivalence relation. Each equivalence class has size $\omega$. So there are $\omega_1$ many equivalence classes in both A and B. Fix a bijection between the equivalence classes in A and B. You can use this to make an isomorphism between A and B because every single equivalence class in either A and B is isomorphic to every other.

Answer by Richard Dore for More open problems

2011-03-29T18:00:51Z

Miller has a list of set theory problems here (upper right).

Schindler also has a list of open problems specifically in inner model theory here.

Math puzzles for dinner

2010-06-24T04:36:51Z

You're hanging out with a bunch of other mathematicians - you go out to dinner, you're on the train, you're at a department tea, et cetera. Someone says something like "A group of 100 people at a party are each receive hats with different prime numbers and ..." For the next few minutes everyone has fun solving the problem together.

I love puzzles like that. But there's a problem -- I running into the same puzzles over and over. But there must be lots of great problems I've never run into. So I'd like to hear problems that other people have enjoyed, and hopefully everyone will learn some new ones.

So: What are your favorite dinner conversation math puzzles?

I don't want to provide hard guidelines. But I'm generally interested in problems that are mathematical and not just logic puzzles. They shouldn't require written calculations or a convoluted answer. And they should be fun - with some sort of cute step, aha moment, or other satisfying twist. I'd prefer to keep things pretty elementary, but a cool problem requiring a little background is a-okay.

One problem per answer.

If you post the answer, please obfuscate it with something like rot13. Don't spoil the fun for everyone else.

Controlling Ultrapowers

2009-10-29T06:19:57Z

Say I start with some a transitive model of a large fragment of ZFC (say enough to run Łoś' Theorem externally) and a specific set x∈M. Now let's say I'm going to pick some M-ultrafilter U on x. By M-ultrafilter, I mean that U measures the subsets of x which are in M.

My question is, by varying U, how much can I affect the ultrapower of M by U? Let's say I limit myself to a U which are countably complete, so that the ultrapower will be wellfounded. If this question is too vague or broad, I'd welcome any interesting examples of things that are possible or impossible.

Complete theory with exactly n countable models?

2009-10-02T15:47:02Z

For n an integer greater than 2, Can one always get a complete theory over a finite language with exactly n models (up to isomorphism)?

There's a theorem that says that 2 is impossible.

My understanding is this should be doable in a finite language, but I don't know how.

If you switch to a countable language, then you can do it as follows. To get 3 models, take the theory of unbounded dense linear orderings together with a sequence of increase constants < c_i: i < ω >. Then the c_i's can either have no upper bound, an upper bound but no sup, or have a sup. This gives exactly 3 models. To get a number bigger than 3, we include a way to color all elements, and require that each color is unbounded and dense. (The c_i's can be whatever color you like.) Then, we get one model for each color of the sup plus the two sup-less models.

Answer by Richard Dore for Can a vector space over an infinite field be a finite union of proper subspaces?

2009-09-29T18:50:40Z

You can prove by induction on n that:

An affine space over an infinite field F is not the union of n proper affine subspaces.

The inductive step goes like this: Pick one of the affine subspaces V. Pick an affine subspace of codimension one which contains it, W. Look at all the translates of W. Since F is infinite, some translate W' of W is not on your list. Now restrict all other subspaces down to W' and apply the inductive hypothesis.

This gives the tight bound that an F affine space is not the union of n proper subspaces if |F|>n. For vector spaces, one can get the tight bound |F|≥n by doing the first step and then applying the affine bound.

Answer by Richard Dore for Where does the game-theoretic characterization of PH come from?

2010-08-27T17:55:06Z

Whenever you have quantifier alternation, you can think of it as a sort of game: one player picks what happens at each universal quantifier, and the other player picks the values at each existential quantifier. The existential player wins if the inner formula at the end is true, the universal player wins if it is false. The whole formula will be true exactly when the existential player has a winning strategy.

Different complexity classes correspond to different types of formulas. For example, any language in NP can be represented as the strings y so the $\exists x. \phi(x,y)$, where the length of $x$ is polynomial in the length of $y$ and $\phi$ can be computed in polynomial time. So NP corresponds to the games where the existential player can make a move that wins immediately. Working up the polynomial hierarchy, you get games (determined by the input) where the existential player always wins in 2 moves, 3 moves, etc., (where each move still has to be polynomial in size). And a language in the whole polynomial hierarchy is the collection of games where there is some fixed n, so that the game is always won by the existential player in n moves. In contrast, PSPACE is the games where the number of move can vary as long as it is polynomial in the length of y. (And the different formulas have to arise in some reasonably uniform way). This is how I usually understand why PH is contained in PSPACE, but then, I am a logician.

Nonconvex manhole covers

2010-07-14T08:46:37Z

One common reason given for the circularity of manhole covers is so they can't fall through the manhole. For convex manhole covers, this property is equivalent to having constant width -- if you have different widths, just orient the cover so that the shorter width slides through the larger one. Since convex polygons can't have constant width, this rules them out for manhole covers. However, for nonconvex shapes, a longer width does not necessarily give you a longer hole.

Is it possible to have a nonconvex polygon that cannot be moved through a hole of the same shape?

Some Clarifications:

the hole has zero thickness
I was thinking of the polygon being simply connected. But if this matters I would like to know the answer both ways.-

Answer by Richard Dore for How can I force the continuum to be weakly compact?

2010-07-15T22:48:50Z

The continuum can't be weak compact. The continuum can't be a strong limit (basically by definition of a strong limit) and weak compact cardinals are always strong limits.

You could start with a weakly compact cardinal in the ground model and make it the continuum by your favorite way of changing the continuum, but by the above you'll destroy the weak compactness. (Under the assumption that weak compacts are consistent, of course.)

If you are just interested in getting the continuum to have the tree property, this is done in Mitchell's Aronszajn trees and the independence of the transfer property by collapsing a weak compact to $\omega_2$.

Answer by Richard Dore for Math puzzles for dinner

2010-06-24T14:57:41Z

A certain rectangle can be covered by 25 coins of diameter 2. Can it always be covered with 100 coins of diameter 1?

Answer by Richard Dore for What are some reasonable-sounding statements that are independent of ZFC?

2009-10-23T04:55:16Z

Another example is certain strong forms of Fubini's Theorem.

If you have a real value function on the product of two closed intervals which is bounded, and which is measurable in either coordinate when you fix the other, are the two iterated integrals equal?

(In the actual Fubini's theorem you care about joint measurability, not just measurability on either coordinate.)

If you assume CH, it is easy to construct counterexamples. It turns it is also consistent to have models where it is true.

I don't have a good reference on this, if you know of one please add it in to my answer.

Answer by Richard Dore for Applications of the Chinese remainder theorem

2009-12-30T16:53:48Z

In the proof of Gödel's First Incompleteness Theorem, you need to choose a way to encode formulas and proofs as numbers. The easy way to do this is to take 2^i₀3^i₁5^i₃...p_j^i_j. However you can instead use the Chinese Remainder Theorem to pick a number congruent to i₀ mod p₀, congruent to i₁ mod p₁, etc. (Of course, you need to pick big enough primes then.) The advantage of doing this is you no longer need exponentiation in your theory, just multiplication and adition.

Answer by Richard Dore for When can we prove constructively that a ring with unity has a maximal ideal?

2009-11-28T19:02:15Z

Unlike full choice, you probably use countable choice all over the place without even recognizing it. Every time you do something iteratively and then take some sort of limit to your construction, you're using countable choice. In many cases, if you do very careful bookkeeping, you can eliminate it on a case by case basis. But you have to be very careful. Without countable choice, the countable union of countable sets isn't necessarily countable.

Answer by Richard Dore for Is there a non self-referencing non-computable function?

2009-11-12T20:01:07Z

If your question is "Are there uncomputable functions which cannot compute Halt?" then the answer is yes. If you take all functions from ℕ to ℕ, "can compute each other" is a natural equivalence relation, and the equivalence classes are called Turing degrees. The computable functions form the minimal degree, 0. The Turing degree of Halt is called 0', pronounced zero jump. (For any degree A, the degree of Halt with A as an oracle is written A'). There are lots of degrees which are strictly between 0 and 0'.

The question as phrased, suggests that logic constructions are unnatural or abnormal. This attitude is flatly wrong. Offhandedly rejecting such arguments is as quackish as claiming the real numbers are "morally countable". Computation, definability, and diagonalization are embedded deeply in a wide range of mathematical systems. (See Hilbert's 10th Problem or Gödel's Second Incompleteness Theorem) 20th century logic is a reality of mathematics.

Answer by Richard Dore for Fundamental Examples

2009-11-13T07:59:12Z

Gödel's Constructible Universe, L, is the fundamental example of inner model theory. L was the first inner model, and is the minimal one. One could argue that the point of inner model theory is to build L-like models that do things L cannot.

Answer by Richard Dore for Is the existence of a well-ordering on R independent of ZF?

2009-11-12T00:02:04Z

Yes. Here's a sketched example:

Start in L. Let P be the forcing which adds ω₁ many Cohen reals, and let G be an L-generic filter for P. Then L(ℝ)^L[G] will model ZF, but will have no well ordering of the reals. The point is that if σ is an automorphism of P, then σ can be extended to an elementary map from L[G] to L[σ[G]], and this extension will fix L(ℝ)^L[G]. So if there was a well ordering of ℝ in L(ℝ)^L[G], it would give a well ordering of G which was fixed by σ. But σ can reorder the elements of G because of the homogeneity of P.

Answer by Richard Dore for Independence from Set Theory Axioms

2009-11-10T19:43:36Z

It's important to distinguish between the theory you're proving something about (say ZFC) and the metatheory you're working in. For a metatheory, people usually talk like they're using ZFC, but are only using a much weaker fragment of it.

The basic idea is that you start with a structure M with some binary relation E, so that E satisfies the ZFC axioms, just like, say, a group satisfying the group axioms. Then you modify this structure in some controlled way to get a new structure M' with a new relation E'. If you've done things right, (M', E') is a model of what you were trying to build. Typical M' is a subset or superset of M, and E and E' agree where appropriate.

If you want a book intended for nonlogicians, I would recommend An Introduction to Independence for Analysts by Dales and Woodin. It avoids more of the language of logic, and some assumptions which look strange to nonlogicians, such as standard models.

If you want a more standard presentation, Kunen's Set Theory An Introduction To Independence Proofs is a good place to start.

Answer by Richard Dore for Is there a formula phi s.t. phi and not-phi have a stronger consistency?

2009-10-31T18:18:20Z

No, it's impossible for any axiom system. If Σ is consistent, then by the Completeness theorem, it has some model M. In M, φ is either true or false. So M is a model of either (Σ+φ) or (Σ+not φ). So at least one of them is consistent. It might be that your metatheory doesn't know which one is consistent, but it knows that at least one of them is.

Answer by Richard Dore for Is no proof based on "tertium non datur" sufficient any more after Gödel?

2009-10-29T13:05:34Z

You're missing the distinction between truth and proof. Godel's Theorem says there are statements which are neither provable nor disprovable (from a given set of axioms). Those statements are still either true or false in a given universe. Godel just says your axioms aren't good enough to tell which one.

Answer by Richard Dore for What are some reasonable-sounding statements that are independent of ZFC?

2009-10-22T19:36:07Z

If X is a compact Hausdorff space, and f is an algebra homomorphism from C(X) to some Banach Algebra, must f be continuous?

This question turns out to be independent. The affirmative answer is referred to as Kaplansky's Conjecture.

Answer by Richard Dore for Do good math jokes exist?

2009-10-19T00:36:41Z

Q: How do you tell an extroverted mathematican from an introverted one?

A: An extroverted mathematician stares at your shoes when talking to you.

Answer by Richard Dore for What do models where the CH is false look like?

2009-10-16T16:07:19Z

Usually it is difficult to prove something from just not CH, much like if the parallel postulate fails, you want to distinguish between hyperbolic and elliptic geometries. There are lots of interesting models of ZFC where CH is false. One common example is a model where Martin's Axiom holds. Not CH + Martin's Axiom does lots of interesting things like provide a counterexample to the Whitehead Problem, or prove Kaplansky's Conjecture. Woodin's P_max forcing produces a model in which CH is false in an "effective" way. The model produced also has absoluteness properties similar to Godel's constructible universe L (the canonical model where CH is true).

Also, I would say most people (at least set theorists) who think CH has an answer (whatever that means) think that it is probably false.

Answer by Richard Dore for Is the "diagonal" of a regular language always context-free?

2009-10-15T05:05:12Z

Yes.

There's no reason to have two nonnegative integers, you can just use one integer x_i-y_i. Then you care about whether the sum is zero. The language K of things which sum to zero is recognized by a push down automata -- the stack is always just a bunch of +1 tokens or -1 tokens corresponding to the current sum. Since K is recognized by a push down automata, it is context free.

The language you are interested in is L intersect K. The intersection of a regular language and a context free language is always context free.

Answer by Richard Dore for Does finite math need the Axiom of Infinity?

2009-10-15T03:53:25Z

ZF - infinity + not infinity is bi-interpretable with Peano Arithmetic. Bi-interpretable means that a model of either one can view a subset of itself as a model of the other (all in a definable way). So ZF - infinity can't prove anything that PA wouldn't prove.

There are some fairly natural statements which are independent of PA but provable in ZF. In fact, they're provable in theories much weaker than ZF. The first convincing example was the Paris-Harrington Theorem, which proved that a certain Ramsey-like property is independent of PA. Another good example is Goodstein Sequences which Anton mentioned.

Answer by Richard Dore for Is the long line paracompact?

2009-10-09T18:56:50Z

The wikipedia article states that the long line is not paracompact. Here is a proof that the long ray is not paracompact (so neither is the long line):

Start with the open covering [0, α) for every ordinal α < ω₁. Let X be some refinement of that covering. Let S be the limit ordinals below ω₁. S is a stationary subset of ω₁. For each β in S, pick a Y_β in X so that β is in Y_β. Consider the function f from S to ω₁ which sends β to the least ordinal in Y_β. For any β in S, f(β) < β since β is a limit ordinal. So by Fodor's Lemma, There is a stationary subset of S, call it S', so that f is constant on S'. Let γ be the value of f on S'. Then γ is in Y_β for all β in S'. So the refinement is not finite (or even countable) at γ.

Homomorphism more than 3/4 the inverse

2009-09-29T23:01:26Z

Suppose G is a finite group and f is an automorphism of G. If f(x)=x^-1 for more than 3/4 of the elements of G, does it follow that f(x)=x^-1 for all x in G?

I know the answer is "yes," but I don't know how to prove it.

Here is a nice solution posted by administrator, expanded a bit:

Let S = { x in G: f(x) = x^-1 }.

Claim: For x in S, S∩x^-1S is a subset of C(x), the centralizer of x.
Proof: For such y, f(y) = y^-1 and f(xy) = (xy)^-1. Now x^-1 y^-1 = f(x)f(y) = f(xy) = (xy) ^-1 = y^-1x^-1. So x and y commute.

Since S∩x^-1S is more than half of G, so is C(x). So by Lagrange's Theorem, C(x) = G, and x is in the center of G. Thus S is a subset of the center, and it is more than half of G. So the center must be all of G, that is G is commutative. Once G is commutative the problem is easy.

Comment by Richard Dore

2011-04-06T17:41:38Z

If you don't have onto, you can get nonisomorphic models based on the number of cycles with a starting point. I don't understand what you mean by $f^i(x)$ if $i$ is a limit.

Comment by Richard Dore

2011-04-04T02:24:49Z

I hope no one misses this nice alternative proof because it's behind a link.

Comment by Richard Dore

2011-04-02T16:06:12Z

You can't have an uncountable cycle. Let f be your function, and x some point in your cycle. Then the cycle is exactly $\{ f^n (x) : n \in \mathbb{Z}\}$, which is a countable set.

Comment by Richard Dore

2011-04-02T16:06:04Z

David's point is just that cycle keeps going in the direction of repeated applications of f: $f(x), f(f(x)), f(f(f(x))), \ldots$ and in the direction of repeated applications of $f^{-1}$: $f^{-1}(x), f^{-1}(f^{-1}(x)), f^{-1}(f^{-1}(f^{-1}(x))), \ldots$

Comment by Richard Dore

2010-07-25T21:14:17Z

I agree (to a point) with Anton. The goal should be for students to reason precisely. More fine, detailed steps should be a means to that end. Demanding justification can add or subtract from this goal. You want justification where being ambiguous or unclear affects the reasoning. But demanding every minute justification may undermine the cause -- students might view such steps as symbol pushing disconnected from the "real" reasoning.

Comment by Richard Dore

2010-07-22T19:26:22Z

an annulus is not a polygon.

Comment by Richard Dore

2010-07-20T15:02:30Z

Upon reading just the title of your question, I immediately thought of Race for the Galaxy.

Comment by Richard Dore

2010-07-19T16:10:42Z

Maybe I'm misunderstanding, but this seems to rely on all the inner diagonals of the whole being the same length. That will stop being true after you approximate with a polygon.

Comment by Richard Dore

2010-07-14T15:31:47Z

I think it is a bit unfair to refer to Gödel's incompleteness theorems simply as "Gödel's theorem". To me it trivializes Gödel other fundamental contributions to logic (such as his completeness theorem or the development of the constructible hierarchy).

Comment by Richard Dore

2010-07-14T14:53:38Z

Yes, sorry, I was imagining the hole to have zero thickness. I hadn't even thought of the alternative.

Comment by Richard Dore

2010-07-08T05:39:15Z

Is it impossible if the spiders are the same speed or slower?

Comment by Richard Dore

2010-07-08T05:35:49Z

One concrete counterexample: $(1-xy)^2+x^2$

Comment by Richard Dore

2010-06-25T22:32:08Z

Nate: Nal fbyhgvba pbhyq gnxr n juvyr. Vs gur obk vf irel ovnfrq, rnpu syvc whfg vfa'g cebqhpvat gung zhpu ragebcl. V nz abj phevbhf, ubjrire, vs gurer vf n fbzrjung zber rssvpvrag fbyhgvba.

Comment by Richard Dore

2010-02-03T06:34:36Z

wow, impressively fast answer.

Comment by Richard Dore

2009-12-10T21:50:14Z

I disagree with Tom. I think some levity is desirable, and MO shouldn't all be serious business.