User richard dore - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:35:15Z http://mathoverflow.net/feeds/user/27 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60375/is-r3-the-square-of-some-topological-space Is R^3 the square of some topological space? Richard Dore 2011-04-02T18:42:06Z 2013-01-19T00:12:41Z <p>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.</p> <p>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.</p> <p>So, is there a space $X$ so that $X \times X$ is homeomorphic to $\mathbb{R}^3$?</p> http://mathoverflow.net/questions/400/a-gentleman-never-chooses-a-basis "A gentleman never chooses a basis." Richard Dore 2009-10-13T02:52:28Z 2012-09-18T01:56:14Z <p>Around these parts, the aphorism "A gentleman never chooses a basis," has become popular.</p> <p>Is there a gentlemanly way to prove that the natural map from V to V<sup>**</sup> is surjective if V is finite dimensionsal?</p> <p>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.</p> http://mathoverflow.net/questions/13934/coloring-points-in-the-plane Coloring Points in the Plane Richard Dore 2010-02-03T06:20:29Z 2012-06-15T09:49:51Z <p>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?</p> <p>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-&epsilon;). 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?</p> http://mathoverflow.net/questions/60607/prime-number-theorem-w-o-complex-analysis/69809#69809 Answer by Richard Dore for Prime Number Theorem w/o Complex Analysis Richard Dore 2011-07-08T17:36:12Z 2011-07-08T17:36:12Z <p>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)}$.</p> http://mathoverflow.net/questions/60321/omega-1-categorical-theory/60323#60323 Answer by Richard Dore for Omega_1 Categorical Theory Richard Dore 2011-04-01T21:18:04Z 2011-04-01T21:18:04Z <p>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.</p> http://mathoverflow.net/questions/48299/more-open-problems/59998#59998 Answer by Richard Dore for More open problems Richard Dore 2011-03-29T18:00:51Z 2011-03-29T18:00:51Z <p>Miller has a list of set theory problems <a href="http://www.math.wisc.edu/~miller/res/index.html" rel="nofollow">here</a> (upper right).</p> <p>Schindler also has a list of open problems specifically in inner model theory <a href="http://wwwmath.uni-muenster.de/logik/Personen/rds/list.html" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner Math puzzles for dinner Richard Dore 2010-06-24T04:36:51Z 2011-02-02T11:38:04Z <p>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.</p> <p>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.</p> <p>So: What are your favorite dinner conversation math puzzles?</p> <p>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.</p> <p>One problem per answer.</p> <p>If you post the answer, please obfuscate it with something like <a href="http://www.rot13.com/" rel="nofollow">rot13</a>. Don't spoil the fun for everyone else.</p> http://mathoverflow.net/questions/3219/controlling-ultrapowers Controlling Ultrapowers Richard Dore 2009-10-29T06:19:57Z 2010-10-17T05:16:22Z <p>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&isin;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.</p> <p>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.</p> http://mathoverflow.net/questions/69/complete-theory-with-exactly-n-countable-models Complete theory with exactly n countable models? Richard Dore 2009-10-02T15:47:02Z 2010-10-17T05:05:01Z <p>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)?</p> <p>There's a theorem that says that 2 is impossible.</p> <p>My understanding is this should be doable in a finite language, but I don't know how.</p> <p>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 &lt; c<sub>i</sub>: i &lt; &omega; >. Then the c<sub>i</sub>'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<sub>i</sub>'s can be whatever color you like.) Then, we get one model for each color of the sup plus the two sup-less models.</p> http://mathoverflow.net/questions/26/can-a-vector-space-over-an-infinite-field-be-a-finite-union-of-proper-subspaces/36#36 Answer by Richard Dore for Can a vector space over an infinite field be a finite union of proper subspaces? Richard Dore 2009-09-29T18:50:40Z 2010-10-05T16:25:26Z <p>You can prove by induction on n that:</p> <p>An affine space over an infinite field F is not the union of n proper <em>affine</em> subspaces.</p> <p>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.</p> <p>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|&#8805;n by doing the first step and then applying the affine bound.</p> http://mathoverflow.net/questions/36903/where-does-the-game-theoretic-characterization-of-ph-come-from/36910#36910 Answer by Richard Dore for Where does the game-theoretic characterization of PH come from? Richard Dore 2010-08-27T17:55:06Z 2010-08-27T18:24:48Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/31810/nonconvex-manhole-covers Nonconvex manhole covers Richard Dore 2010-07-14T08:46:37Z 2010-07-22T10:40:50Z <p>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 <a href="http://en.wikipedia.org/wiki/Curve_of_constant_width" rel="nofollow">constant width</a> -- 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.</p> <p>Is it possible to have a nonconvex polygon that cannot be moved through a hole of the same shape?</p> <p>Some Clarifications:</p> <ul> <li>the hole has zero thickness</li> <li>I was thinking of the polygon being simply connected. But if this matters I would like to know the answer both ways.-</li> </ul> http://mathoverflow.net/questions/32070/how-can-i-force-the-continuum-to-be-weakly-compact/32080#32080 Answer by Richard Dore for How can I force the continuum to be weakly compact? Richard Dore 2010-07-15T22:48:50Z 2010-07-15T22:48:50Z <p>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.</p> <p>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.)</p> <p>If you are just interested in getting the continuum to have the tree property, this is done in Mitchell's <a href="http://www.sciencedirect.com/science/article/B6X2C-46V007P-59/2/1ae14176e718107af20fac6b2e72b34b" rel="nofollow">Aronszajn trees and the independence of the transfer property</a> by collapsing a weak compact to $\omega_2$.</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29387#29387 Answer by Richard Dore for Math puzzles for dinner Richard Dore 2010-06-24T14:57:41Z 2010-06-24T14:57:41Z <p>A certain rectangle can be covered by 25 coins of diameter 2. Can it always be covered with 100 coins of diameter 1?</p> http://mathoverflow.net/questions/1924/what-are-some-reasonable-sounding-statements-that-are-independent-of-zfc/2037#2037 Answer by Richard Dore for What are some reasonable-sounding statements that are independent of ZFC? Richard Dore 2009-10-23T04:55:16Z 2010-02-05T21:40:35Z <p>Another example is certain strong forms of Fubini's Theorem.</p> <p>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?</p> <p>(In the actual Fubini's theorem you care about joint measurability, not just measurability on either coordinate.)</p> <p>If you assume CH, it is easy to construct counterexamples. It turns it is also consistent to have models where it is true.</p> <p>I don't have a good reference on this, if you know of one please add it in to my answer.</p> http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/10154#10154 Answer by Richard Dore for Applications of the Chinese remainder theorem Richard Dore 2009-12-30T16:53:48Z 2009-12-30T16:53:48Z <p>In the proof of <a href="http://en.wikipedia.org/wiki/G%F6del%27s%20incompleteness%20theorems%23First%20incompleteness%20theorem" rel="nofollow">Gödel's First Incompleteness Theorem</a>, you need to choose a way to encode formulas and proofs as numbers. The easy way to do this is to take 2<sup>i<sub>0</sub></sup>3<sup>i<sub>1</sub></sup>5<sup>i<sub>3</sub></sup>...p<sub>j</sub><sup>i<sub>j</sub></sup>. However you can instead use the Chinese Remainder Theorem to pick a number congruent to i<sub>0</sub> mod p<sub>0</sub>, congruent to i<sub>1</sub> mod p<sub>1</sub>, 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.</p> http://mathoverflow.net/questions/7025/when-can-we-prove-constructively-that-a-ring-with-unity-has-a-maximal-ideal/7069#7069 Answer by Richard Dore for When can we prove constructively that a ring with unity has a maximal ideal? Richard Dore 2009-11-28T19:02:15Z 2009-11-28T19:02:15Z <p>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.</p> http://mathoverflow.net/questions/4589/is-there-a-non-self-referencing-non-computable-function/5244#5244 Answer by Richard Dore for Is there a non self-referencing non-computable function? Richard Dore 2009-11-12T20:01:07Z 2009-11-22T10:11:32Z <p>If your question is "Are there uncomputable functions which cannot compute Halt?" then the answer is yes. If you take all functions from &#8469; to &#8469;, "can compute each other" is a natural equivalence relation, and the equivalence classes are called <a href="http://en.wikipedia.org/wiki/Turing%20degree" rel="nofollow">Turing degrees</a>. 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'.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Hilbert%27s%20tenth%20problem" rel="nofollow">Hilbert's 10th Problem</a> or <a href="http://en.wikipedia.org/wiki/G%F6del%27s%20incompleteness%20theorems%23Second%20incompleteness%20theorem" rel="nofollow">Gödel's Second Incompleteness Theorem</a>) 20th century logic is a reality of mathematics.</p> http://mathoverflow.net/questions/4994/fundamental-examples/5326#5326 Answer by Richard Dore for Fundamental Examples Richard Dore 2009-11-13T07:59:12Z 2009-11-13T07:59:12Z <p><a href="http://en.wikipedia.org/wiki/G%F6del%27s%20constructible%20universe" rel="nofollow">Gödel's Constructible Universe, L</a>, is the fundamental example of <a href="http://en.wikipedia.org/wiki/Inner%20model" rel="nofollow">inner model theory</a>. 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.</p> http://mathoverflow.net/questions/5116/is-the-existence-of-a-well-ordering-on-r-independent-of-zf/5127#5127 Answer by Richard Dore for Is the existence of a well-ordering on R independent of ZF? Richard Dore 2009-11-12T00:02:04Z 2009-11-12T00:13:08Z <p>Yes. Here's a sketched example:</p> <p>Start in L. Let P be the forcing which adds &omega;<sub>1</sub> many Cohen reals, and let G be an L-generic filter for P. Then L(&#8477;)<sup>L[G]</sup> will model ZF, but will have no well ordering of the reals. The point is that if &sigma; is an automorphism of P, then &sigma; can be extended to an elementary map from L[G] to L[&sigma;[G]], and this extension will fix L(&#8477;)<sup>L[G]</sup>. So if there was a well ordering of &#8477; in L(&#8477;)<sup>L[G]</sup>, it would give a well ordering of G which was fixed by &sigma;. But &sigma; can reorder the elements of G because of the homogeneity of P.</p> http://mathoverflow.net/questions/4901/independence-from-set-theory-axioms/4913#4913 Answer by Richard Dore for Independence from Set Theory Axioms Richard Dore 2009-11-10T19:43:36Z 2009-11-10T19:43:36Z <p>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.</p> <p>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.</p> <p>If you want a book intended for nonlogicians, I would recommend <em>An Introduction to Independence for Analysts</em> by Dales and Woodin. It avoids more of the language of logic, and some assumptions which look strange to nonlogicians, such as standard models.</p> <p>If you want a more standard presentation, Kunen's <em>Set Theory An Introduction To Independence Proofs</em> is a good place to start.</p> http://mathoverflow.net/questions/3528/is-there-a-formula-phi-s-t-phi-and-not-phi-have-a-stronger-consistency/3576#3576 Answer by Richard Dore for Is there a formula phi s.t. phi and not-phi have a stronger consistency? Richard Dore 2009-10-31T18:18:20Z 2009-10-31T20:15:46Z <p>No, it's impossible for any axiom system. If &Sigma; is consistent, then by the Completeness theorem, it has some model M. In M, &phi; is either true or false. So M is a model of either (&Sigma;+&phi;) or (&Sigma;+not &phi;). 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.</p> http://mathoverflow.net/questions/3239/is-no-proof-based-on-tertium-non-datur-sufficient-any-more-after-godel/3258#3258 Answer by Richard Dore for Is no proof based on "tertium non datur" sufficient any more after Gödel? Richard Dore 2009-10-29T13:05:34Z 2009-10-29T13:05:34Z <p>You're missing the distinction between <em>truth</em> and <em>proof</em>. Godel's Theorem says there are statements which are neither <em>provable</em> nor <em>disprovable</em> (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.</p> http://mathoverflow.net/questions/1924/what-are-some-reasonable-sounding-statements-that-are-independent-of-zfc/1926#1926 Answer by Richard Dore for What are some reasonable-sounding statements that are independent of ZFC? Richard Dore 2009-10-22T19:36:07Z 2009-10-22T19:36:07Z <p>If X is a compact Hausdorff space, and f is an algebra homomorphism from C(X) to some Banach Algebra, must f be continuous?</p> <p>This question turns out to be independent. The affirmative answer is referred to as <a href="http://en.wikipedia.org/wiki/Kaplansky%27s%5Fconjecture" rel="nofollow">Kaplansky's Conjecture</a>.</p> http://mathoverflow.net/questions/1083/do-good-math-jokes-exist/1112#1112 Answer by Richard Dore for Do good math jokes exist? Richard Dore 2009-10-19T00:36:41Z 2009-10-19T00:36:41Z <p>Q: How do you tell an extroverted mathematican from an introverted one?</p> <p>A: An extroverted mathematician stares at <em>your</em> shoes when talking to you.</p> http://mathoverflow.net/questions/743/what-do-models-where-the-ch-is-false-look-like/757#757 Answer by Richard Dore for What do models where the CH is false look like? Richard Dore 2009-10-16T16:07:19Z 2009-10-16T16:07:19Z <p>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 <a href="http://en.wikipedia.org/wiki/Martin%27s%5Faxiom" rel="nofollow">Martin's Axiom</a> 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<sub>max</sub> 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).</p> <p>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.</p> http://mathoverflow.net/questions/563/is-the-diagonal-of-a-regular-language-always-context-free/566#566 Answer by Richard Dore for Is the "diagonal" of a regular language always context-free? Richard Dore 2009-10-15T05:05:12Z 2009-10-15T05:11:36Z <p>Yes.</p> <p>There's no reason to have two nonnegative integers, you can just use one integer x<sub>i</sub>-y<sub>i</sub>. 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.</p> <p>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.</p> http://mathoverflow.net/questions/551/does-finite-math-need-the-axiom-of-infinity/555#555 Answer by Richard Dore for Does finite math need the Axiom of Infinity? Richard Dore 2009-10-15T03:53:25Z 2009-10-15T04:11:55Z <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Paris%2DHarrington%5Ftheorem" rel="nofollow">Paris-Harrington Theorem</a>, which proved that a certain Ramsey-like property is independent of PA. Another good example is <a href="http://en.wikipedia.org/wiki/Goodstein%27s%5Ftheorem" rel="nofollow">Goodstein Sequences</a> which Anton mentioned.</p> http://mathoverflow.net/questions/229/is-the-long-line-paracompact/233#233 Answer by Richard Dore for Is the long line paracompact? Richard Dore 2009-10-09T18:56:50Z 2009-10-09T18:56:50Z <p>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):</p> <p>Start with the open covering [0, α) for every ordinal α &lt; ω<sub>1</sub>. Let X be some refinement of that covering. Let S be the limit ordinals below ω<sub>1</sub>. S is a stationary subset of ω<sub>1</sub>. For each β in S, pick a Y<sub>β</sub> in X so that β is in Y<sub>β</sub>. Consider the function f from S to ω<sub>1</sub> which sends β to the least ordinal in Y<sub>β</sub>. For any β in S, f(β) &lt; β since β is a limit ordinal. So by <a href="http://en.wikipedia.org/wiki/Fodor%27s%5Flemma" rel="nofollow">Fodor's Lemma</a>, 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<sub>β</sub> for all β in S'. So the refinement is not finite (or even countable) at γ.</p> http://mathoverflow.net/questions/38/homomorphism-more-than-3-4-the-inverse Homomorphism more than 3/4 the inverse Richard Dore 2009-09-29T23:01:26Z 2009-10-01T19:36:49Z <p>Suppose G is a finite group and f is an automorphism of G. If f(x)=x<sup>-1</sup> for more than 3/4 of the elements of G, does it follow that f(x)=x<sup>-1</sup> for all x in G?</p> <p>I know the answer is "yes," but I don't know how to prove it. <hr> Here is a nice solution posted by administrator, expanded a bit:</p> <p>Let S = { x in G: f(x) = x<sup>-1</sup> }.</p> <p>Claim: For x in S, S&cap;x<sup>-1</sup>S is a subset of C(x), the centralizer of x. <br>Proof: For such y, f(y) = y<sup>-1</sup> and f(xy) = (xy)<sup>-1</sup>. Now x<sup>-1</sup> y<sup>-1</sup> = f(x)f(y) = f(xy) = (xy) <sup>-1</sup> = y<sup>-1</sup>x<sup>-1</sup>. So x and y commute.</p> <p>Since S&cap;x<sup>-1</sup>S 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.</p> http://mathoverflow.net/questions/60321/omega-1-categorical-theory/60323#60323 Comment by Richard Dore Richard Dore 2011-04-06T17:41:38Z 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. http://mathoverflow.net/questions/60375/is-r3-the-square-of-some-topological-space/60389#60389 Comment by Richard Dore Richard Dore 2011-04-04T02:24:49Z 2011-04-04T02:24:49Z I hope no one misses this nice alternative proof because it's behind a link. http://mathoverflow.net/questions/60321/omega-1-categorical-theory/60323#60323 Comment by Richard Dore Richard Dore 2011-04-02T16:06:12Z 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. http://mathoverflow.net/questions/60321/omega-1-categorical-theory/60323#60323 Comment by Richard Dore Richard Dore 2011-04-02T16:06:04Z 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$ http://mathoverflow.net/questions/5497/what-are-the-qualities-of-a-good-math-teacher/5503#5503 Comment by Richard Dore Richard Dore 2010-07-25T21:14:17Z 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 &quot;real&quot; reasoning. http://mathoverflow.net/questions/31810/nonconvex-manhole-covers/32934#32934 Comment by Richard Dore Richard Dore 2010-07-22T19:26:22Z 2010-07-22T19:26:22Z an annulus is not a polygon. http://mathoverflow.net/questions/32626/how-to-shuffle-a-deck-by-parts Comment by Richard Dore Richard Dore 2010-07-20T15:02:30Z 2010-07-20T15:02:30Z Upon reading just the title of your question, I immediately thought of Race for the Galaxy. http://mathoverflow.net/questions/31810/nonconvex-manhole-covers/31816#31816 Comment by Richard Dore Richard Dore 2010-07-19T16:10:42Z 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. http://mathoverflow.net/questions/20219/what-was-godels-real-achievement Comment by Richard Dore Richard Dore 2010-07-14T15:31:47Z 2010-07-14T15:31:47Z I think it is a bit unfair to refer to G&#246;del's incompleteness theorems simply as &quot;G&#246;del's theorem&quot;. To me it trivializes G&#246;del other fundamental contributions to logic (such as his completeness theorem or the development of the constructible hierarchy). http://mathoverflow.net/questions/31810/nonconvex-manhole-covers/31816#31816 Comment by Richard Dore Richard Dore 2010-07-14T14:53:38Z 2010-07-14T14:53:38Z Yes, sorry, I was imagining the hole to have zero thickness. I hadn't even thought of the alternative. http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29330#29330 Comment by Richard Dore Richard Dore 2010-07-08T05:39:15Z 2010-07-08T05:39:15Z Is it impossible if the spiders are the same speed or slower? http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/30979#30979 Comment by Richard Dore Richard Dore 2010-07-08T05:35:49Z 2010-07-08T05:35:49Z One concrete counterexample: $(1-xy)^2+x^2$ http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29519#29519 Comment by Richard Dore Richard Dore 2010-06-25T22:32:08Z 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. http://mathoverflow.net/questions/13934/coloring-points-in-the-plane/13936#13936 Comment by Richard Dore Richard Dore 2010-02-03T06:34:36Z 2010-02-03T06:34:36Z wow, impressively fast answer. http://mathoverflow.net/questions/1083/do-good-math-jokes-exist Comment by Richard Dore Richard Dore 2009-12-10T21:50:14Z 2009-12-10T21:50:14Z I disagree with Tom. I think some levity is desirable, and MO shouldn't all be serious business.