User chad groft - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T16:35:05Z http://mathoverflow.net/feeds/user/4133 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82769/is-it-consistent-with-zfc-that-for-all-ordinals-alpha-beta-omega-it-holds/82771#82771 Answer by Chad Groft for Is it consistent with ZFC that for all ordinals $\alpha, \beta < \omega$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$? Chad Groft 2011-12-06T05:24:17Z 2011-12-06T05:24:17Z <p>Yes. Start with a model of GCH and add $\aleph_{\omega+1}$ Cohen reals. Then $2^{\aleph_n}=\aleph_{\omega+1}$ for all $n&lt;\omega$. You can get the bound $\gamma$ arbitrarily high within the ordinal hierarchy by adding $\kappa$ Cohen reals instead, where $\kappa$ is a regular cardinal greater than $\aleph_\gamma$. (I think that's all correct.)</p> http://mathoverflow.net/questions/17152/when-2a-2b-implies-ab-a-b-cardinals/17155#17155 Answer by Chad Groft for When 2^a = 2^b implies a=b (a,b cardinals) Chad Groft 2010-03-05T03:01:14Z 2011-10-14T01:35:02Z <p>François's and Joel's answers to the general question are correct.</p> <p>As for the "dimension of a free group is uniquely determined, even if it's infinite", there's a better argument. Let <em>G</em> be a free group on two sets of generators <em>x</em> and <em>y</em>; we wish to show |<em>x</em>| = |<em>y</em>|. First let <em>A</em> = <em>G<sub>ab</sub></em> be the free abelian group on generators <em>x</em> and <em>y</em>; then let <em>V</em> = <em>A</em> &otimes;<sub><em>Z</em></sub> <em>F</em><sub>2</sub> be the vector space over <em>F</em><sub>2</sub> with bases <em>x</em> and <em>y</em>, <strike>so that |<em>V</em>| = 2<sup>|<em>x</em>|</sup> = 2<sup>|<em>y</em>|</sup></strike> (strike that, it's false for infinite cardinalities). (We could use any field here<strike>, but the argument is more intricate</strike>.)</p> <p>If |<em>V</em>| is finite, then |<em>x</em>| = |<em>y</em>| follows immediately. So suppose |<em>V</em>| is infinite, so that |<em>x</em>| and |<em>y</em>| are infinite. Each element of <em>x</em> is the sum of finitely many elements of <em>y</em>, and every element of <em>y</em> must show up in at least one such sum (why?). This means |<em>y</em>| ≤ |<em>x</em>|•&alefsym;<sub>0</sub> = |<em>x</em>| (cardinal arithmetic). Similarly |<em>x</em>| ≤ |<em>y</em>|, so |<em>x</em>| = |<em>y</em>|.</p> http://mathoverflow.net/questions/54981/is-the-closedness-of-the-image-of-operator-needed-in-the-defintion-of-fredholm/54984#54984 Answer by Chad Groft for Is the "closedness of the image of operator" needed in the defintion of Fredholm operators? Chad Groft 2011-02-10T03:57:38Z 2011-02-10T03:57:38Z <p>No, the proof is correct, and it's taking $\mathrm{coker}\ T = H_2/\mathrm{im}\ T$. The essence of the argument is that $V\oplus\mathbb{C}^n$ contains $V$ as a closed subspace, regardless of the norm on $V$, and that $H_2$ is "close enough" to $(\mathrm{im}\ T)\oplus\mathbb{C}^n$.</p> <p>The full argument goes like this: Let $T: H_1\to H_2$ be Fredholm (the $H_i$ are Hilbert spaces). WLOG $T$ is injective, otherwise replace $H_1$ with $(\mathrm{ker}\ T)^\perp$. Choose $v_1,\dots, v_n\in H_2$ which represent a basis of $\mathrm{coker}\ T$, and use them to define a linear function $\mathbb{C}^n\to H_2$. Combine this with $T$ to get a linear map $\overline{T}: H_1\oplus\mathbb{C}^n\to H_2$.</p> <p>Now $\overline{T}$ is a linear isomorphism, so its inverse $\widetilde{T}$ is also a linear isomorphism. $\overline{T}$ is also continuous, so the graph of $\overline T$ is a closed subset of $H_1\oplus\mathbb{C}^n\oplus H_2$, so the graph of $\widetilde T$ is a closed subset of $H_2\oplus H_1\oplus\mathbb{C}^n$, which makes $\widetilde T$ continuous by the Closed Graph Theorem. (This last is not an obvious statement; it's a consequence of the Baire Category Theorem). Finally, $\mathrm{im}\ T$ is precisely the pullback of $H_1$ through $\widetilde T$, making it closed.</p> <p>As to why most sources don't present it this way… I think in most cases where somebody wants to prove that a given operator $T$ is Fredholm, it's just easier to establish that $\mathrm{coker}\ T$ is finite-dimensional after proving that $\mathrm{im}\ T$ is closed.</p> http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/46171#46171 Answer by Chad Groft for Adding a formal inverse of an element to a free monoid Chad Groft 2010-11-16T01:35:11Z 2010-11-16T02:19:14Z <p>Let $z$ be a word, and let $M=FM(a,b)/z^{-1}$. If we wish $a$ and $b$ to be invertible in $M$, then $z$ must contain both $a$ and $b$ at least once. (For example, $FM_2[a^{-n}]=FM_2[a^{-1}]\cong F(a)\ast FM(b)$ by the canonical maps.)</p> <p>Suppose $z = a^nwa^m$ with $n, m>0$. If $z^{-1}$ exists, then $a$ has a right inverse $r = a^{n-1}wa^mz^{-1}$ and a left inverse $l = z^{-1}a^nwa^{m-1}$, and in fact these two are equal by the standard argument ($l = lar = r$); so just say $l=r=a^{-1}$. Then $z^{-1}a^nwa^m = e$ implies $z^{-1}a^nw = a^{-m}$ implies $a^mz^{-1}a^nw = e$ ($w$ has a left inverse), and similarly $w$ has a right inverse which is the same. If $z$ contains any occurrences of $b$, then we choose $w$ to begin and end with $b$; by the earlier argument applied to $w$, $b$ is invertible.</p> <p>Symmetrically, if $z$ begins and ends with $b$ but contains an occurrence of $a$, then $z^{-1}$ exists implies $a^{-1}$, $b^{-1}$ exists.</p> <p>I suspect these are the only cases which work (<em>i.e.</em>, inverting a word of the form $awb$ or $bwa$ would not invert $a$ or $b$) but cannot yet prove it. (<strong>EDIT:</strong> This is false, see Mark's comment below.)</p> <p><strong>EDIT:</strong> Partial result! Consider the structure $M$ whose underlying set is</p> <p><code>$\{(m,e) \in \mathbb{N}\times\mathbb{Z} : m\ge e\}$</code></p> <p>with binary operation $(m,e)\ast(m',e') = (\max(m,e+m'), e+e')$. It is routine to check that this is a monoid. Let $z=awb$ contain $i$ copies of $a$ and $j$ copies of $b$, and consider the morphism $f\colon FM(a,b)\to M$ with $f(a) = (0,-j)$ and $f(b) = (i,i)$.</p> <p>From counting it is clear that $f(z) = (m,0)$ for some $m\in\mathbb{N}$. If $m=0$ (as it will be for any word of the form $a^ib^j$, and many other words besides), then $f$ extends to a morphism $FM(a,b)[z^{-1}]\to M$.</p> <p>But $f(a)$ has no left inverse; if $(m,e)\ast (0,-j) = (0,0)$, then $e=j$ and $\max(m,j)=0$, which is impossible ($j>0$ by assumption). Thus $a^{-1}$ cannot be a member of $FM(a,b)[z^{-1}]$, <em>i.e.</em>, inverting $z$ does not invert $a$.</p> <p>(Intuition: For each word in $FM(a,b)$, start at zero and read the word from left to right. For each $a$, descend $j$ steps; for each $b$, ascend $i$ steps; and track both your peak and your current position. If reading $z$ never gets you to the positive numbers, then adjoining $z^{-1}$ does not get you $a^{-1}$ (or similarly $b^{-1}$).)</p> http://mathoverflow.net/questions/27279/proof-of-godel-incompleteness/27283#27283 Answer by Chad Groft for Proof of Gödel incompleteness Chad Groft 2010-06-06T22:55:29Z 2010-06-06T22:55:29Z <p>There's a subtle point at the bottom of the first page and top of the second, to wit:</p> <p>"For every sentence <em>&sigma;</em>, $M\vDash\sigma$ iff $N\vDash(m\vDash\sigma)$. In particular, $N\vDash$ (<em>m</em> is a model)."</p> <p>If "model" means "model of ZF", then one cannot conclude this. It is possible that <em>N</em> knows, for each <em>particular &sigma;</em> &isin; ZF, that $m\vDash\sigma$, without knowing that <em>m</em> models ZF as a whole. This is because <em>N</em> 's grasp of what exactly is in ZF can be incorrect; if there are nonstandard integers, then there are also nonstandard (codes for) sentences, some of which will be in the "local copy" of ZF.</p> <p>However, if "model" means "model of &Sigma;" where &Sigma; is an explicit finite list of axioms, all of which are in ZF (and with other nice properties as in the paper), then one can make the necessary leap. To model &Sigma; is to model each <em>&sigma;</em> in the explicit list; thus, if <em>M</em> does this, then <em>N</em> must know that <em>m</em> does this.</p> http://mathoverflow.net/questions/23849/minimum-enclosing-rectangle-of-a-convex-polygon-proof/23854#23854 Answer by Chad Groft for Minimum enclosing rectangle of a convex polygon proof Chad Groft 2010-05-07T13:53:29Z 2010-05-07T13:53:29Z <p>Suppose you've got your polygon <em>P</em>, embedded in the Euclidean plane with some standard coordinate system. Then there's some rectangle <em>R</em> with horizontal and vertical sides which encloses <em>P</em> and is as small as possible among all such rectangles (just take horizontal lines through the topmost and bottommost points, and vertical lines through the rightmost and leftmost points). Translating the coordinate system doesn't change the rectangle or its area, but rotating it through an angle <em>&theta;</em> will; so the rectangle <em>R</em><sub><em>&theta;</em></sub> and its area <em>A</em><sub><em>&theta;</em></sub> are really functions of <em>&theta;</em> (and (<em>&pi;</em>/2)-periodic functions at that). As such, <em>A</em> definitely has a minimum at some angle <em>&theta;</em><sub>min</sub>.</p> <p>The meat of the theorem is that, for any angle <em>&phi;</em> where <em>R</em><sub><em>&phi;</em></sub> does not meet the conclusion, the function <em>A</em> does not even have a local minimum. To see this, note that <em>R</em><sub><em>&phi;</em></sub> intersects <em>P</em> at a finite set of points <em>S</em> — usually |<em>S</em>| = 4, but 3 or 2 are also possible. Now consider the rectangle <em>R'</em><sub><em>&theta;</em></sub> which is the smallest rectangle with sides parallel to the <em>&theta;</em>-axes and which contains <em>S</em>, and let <em>A'</em><sub><em>&theta;</em></sub> be its area. Note two things:</p> <ul> <li>For <em>&theta;</em> near <em>&phi;</em>, <em>R'</em><sub><em>&theta;</em></sub> = <em>R</em><sub><em>&theta;</em></sub>, and hence <em>A'</em><sub><em>&theta;</em></sub> = <em>A</em><sub><em>&theta;</em></sub>.</li> <li>Near <em>&phi;</em>, the function <em>A'</em> is <em>concave downward</em>. Why? Divide the rectangle <em>R'<sub>&theta;</sub></em> along the lines between the points of <em>S</em>. We get a convex polygon determined by <em>S</em> (and hence constant), plus |<em>S</em>|-many right triangles. Each triangle has a hypotenuse which stays constant as <em>&theta;</em> changes, and an interior angle which changes as <em>&theta;</em>/2, hence an area which is concave downward.</li> </ul> <p>Under our assumption, <em>&phi;</em> can't possibly be a local minimum of <em>A</em>, let alone a global one; so wherever the global minimum is, it must have a side coincident with one of the sides of <em>P</em>.</p> http://mathoverflow.net/questions/21087/is-there-a-primitive-recursively-enumerable-set-whose-complement-is-not-such/21101#21101 Answer by Chad Groft for Is there a "primitive-recursively enumerable" set whose complement is not such? Chad Groft 2010-04-12T12:25:29Z 2010-04-12T12:25:29Z <p>There is a stronger result: <em>Every r.e. set is primitive r.e. in your sense.</em></p> <p>Short proof: Kleene's Normal Form Theorem.</p> <p>Longer proof: Let <em>S</em> be an r.e. set, assumed WLOG nonempty; fix <em>a</em> &isin; <em>S</em>, and fix an algorithm <em>e</em> where <em>S</em> is precisely the range of the function computed by <em>e</em>.</p> <p>Consider the following algorithm: Given the input pair (<em>n</em>, <em>M</em>), run <em>e</em> on input <em>n</em> for <em>M</em> steps. If it gives an output by then, output whatever <em>e</em> outputs; otherwise output <em>a</em>.</p> <p>The functions which set up the initial state of computation, advance a state by one step, and extract the output from a final state, are all p.r. Thus the above algorithm defines a p.r. function, and it is easy to check that its range is <em>S</em>.</p> <p>Edit: Cutland's <em>Computability</em> is a decent resource for these questions.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20918#20918 Answer by Chad Groft for Most 'unintuitive' application of the Axiom of Choice? Chad Groft 2010-04-10T12:38:15Z 2010-04-10T12:38:15Z <p>The Axiom of Determinacy (AD) fails.</p> <p>What that means: Partition the set <em><sup>&omega;</sup>&omega;</em> into two sets <em>S</em> and <em>T</em>, and think of this partition as a <em>game</em> (<em>S</em>, <em>T</em>) with two players. To play, player 1 picks a natural number <em>a</em><sub>0</sub>, then player 2 picks <em>b</em><sub>0</sub> (as a function of <em>a</em><sub>0</sub>), then player 1 picks <em>a</em><sub>1</sub> (as a function of <em>b</em><sub>0</sub>), then player 2 picks <em>b</em><sub>1</sub> (as a function of <em>a</em><sub>0</sub> and <em>a</em><sub>1</sub>), and so on until <em>a<sub>n</sub></em> and <em>b<sub>n</sub></em> are selected for all <em>n</em> &isin; <em>&omega;</em>. Then the sequence <em>a</em><sub>0</sub>, <em>b</em><sub>0</sub>, <em>a</em><sub>1</sub>, <em>b</em><sub>1</sub>, &hellip; is either in <em>S</em> (in which case player 1 wins), or in <em>T</em> (in which case player 2 wins).</p> <p>The game (<em>S</em>, <em>T</em>) is <em>determined</em> if either player 1 or player 2 has a winning strategy, <em>i.e.</em>, if there are functions <em>f<sub>n</sub></em>: <em><sup>n</sup>&omega;</em> &rarr; <em>&omega;</em> where choosing <em>a<sub>n</sub></em> = <em>f<sub>n</sub></em>( <em>b</em><sub>0</sub>, &hellip;, <em>b</em><sub><em>n</em>–1</sub> ) guaranteed player 1 victory, or similarly for player 2. (We can't have both.) AD is just the statement that every such game is determined, which is false in ZFC. As with most of the weird examples, the undetermined game is constructed with a well-ordering of <strong>R</strong>. </p> <p>What makes this so unintuitive to me is that both AC and AD are generalizations of statements that are easily seen for finite objects. (Any finite game, or even any game with finite depth, is determined, by an easy induction on the depth.)</p> <p>There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to <em>L</em>(<strong>R</strong>). That the relative consistency strength of this statement is equivalent to that of large cardinals is considered good evidence that those large cardinals are, in fact, consistent. More precisely, ZF + AD is consistent iff ZFC + "there are infinitely many Woodin cardinals" is consistent, and AD<sup><em>L</em>(<strong>R</strong>)</sup> is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals".</p> http://mathoverflow.net/questions/19243/do-the-empty-set-and-the-entire-set-really-need-to-be-open/19250#19250 Answer by Chad Groft for Do the empty set AND the entire set really need to be open? Chad Groft 2010-03-24T23:53:06Z 2010-03-24T23:53:06Z <p>This question may be better answered by going to the intuition.</p> <p>Let <em>X</em> be a set with some sort of "local structure"; a metric space will do, but any reasonable sort of "closeness" is fine. We want to say a set <em>U</em> &sube; <em>X</em> is open if, whenever <em>U</em> contains a point <em>p</em>, it also contains all those points <em>q</em> &isin; <em>X</em> which are "near <em>p</em>".</p> <p>Given this, <em>U</em> = <em>X</em> is clearly open. If <em>p</em> &isin; <em>U</em>, we want all the points of <em>X</em> "near <em>p</em>" to be in <em>U</em>; but <em>every point</em> of <em>X</em> is in <em>U</em>, so this is trivially true.</p> <p>&empty; is also clearly open. For this to be false, &empty; would have to contain a point <em>p</em> but not all the points near <em>p</em>; but as &empty; contains no points, this is impossible.</p> <p>Also consider the following: Let <em>f</em> : <em>X</em> &rarr; {0,1} be the constant function sending every <em>p</em> &isin; <em>X</em> to 0. We want constant functions to be continuous, no matter how fine the topology on {0,1}. So <em>f</em> <sup>-1</sup>[{0}] = <em>X</em> and <em>f</em> <sup>-1</sup>[{1}] = &empty; both must be open (and both must be closed).</p> http://mathoverflow.net/questions/15957/is-any-interesting-question-about-a-group-g-decidable-from-a-presentation-of-g Is any interesting question about a group G decidable from a presentation of G? Chad Groft 2010-02-21T03:37:41Z 2010-03-20T05:24:48Z <p>We say that a group <em>G</em> is in the class <em>F<sub>q</sub></em> if there is a CW-complex which is a <em>BG</em> (that is, which has fundamental group <em>G</em> and contractible universal cover) and which has finite <em>q</em>-skeleton. Thus <em>F<sub>0</sub></em> contains all groups, <em>F<sub>1</sub></em> contains exactly the finitely generated groups, <em>F<sub>2</sub></em> the finitely presented groups, and so forth.</p> <p>My question: For a fixed <em>q</em> ≥ 3, is it possible to decide, from a finite presentation of a group <em>G</em>, whether <em>G</em> is in <em>F<sub>q</sub></em> or not? I would assume not, but am not having much luck proving it.</p> <p><strike>One approach would be to prove that, if <em>G</em> is a group in <em>F<sub>q</sub></em> and <em>H</em> is a finitely presented subgroup, then <em>H</em> &isin; <em>F<sub>q</sub></em> as well. This would make being in <em>F<sub>q</sub></em> a Markov property, or at least close enough to make it undecidable.</strike></p> <p>Henry Wilton's comment below makes it clear that being <em>F<sub>q</sub></em> is not even quasi-Markov, so the above idea won't work. I still suspect that "<em>G</em> &isin; <em>F<sub>q</sub></em>" is not decidable, but now my intuition is from Rice's theorem:</p> <blockquote> <p>If $\mathcal{B}$ is a nonempty set of computable functions with nonempty complement, then no algorithm accepts an input <em>n</em> and decides whether <em>&phi;<sub>n</sub></em> is an element of $\mathcal{B}$.</p> </blockquote> <p><strike>It seems likely to me that something similar is true of finite presentations and the groups they define.</strike></p> <p>John Stillwell notes below that this can't be true for a number of questions involving the abelianization of G. This wouldn't affect the Rips construction/1-2-3 theorem discussion below if the homology-sphere idea works, since those groups are all perfect.</p> <p>Any thoughts?</p> http://mathoverflow.net/questions/17295/results-about-the-order-of-a-group-forcing-a-particular-property/17297#17297 Answer by Chad Groft for Results about the order of a group forcing a particular property. Chad Groft 2010-03-06T17:10:13Z 2010-03-06T17:10:13Z <p>Very famous one is the Feit-Thompson theorem: if <em>n</em> is odd, then <em>G</em> is solvable. Though I suppose this is stated (but not proved) in most modern algebra texts.</p> http://mathoverflow.net/questions/15948/inverse-limit-in-metric-geometry/16741#16741 Answer by Chad Groft for Inverse limit in metric geometry Chad Groft 2010-03-01T05:00:05Z 2010-03-01T05:05:40Z <p>I'd be surprised if there were any applications, for the simple reason that your definition of inverse limit for metric geometry doesn't translate well into topology. It's easy to disconnect points in the limit which aren't disconnected in the terms.</p> <p>For example, fix a metric space (<em>X</em>, <em>d</em>) and define (<em>X<sub>n</sub></em>, <em>d<sub>n</sub></em>) = (<em>X</em>, 2<sup><em>n</em></sup><em>d</em>), with &phi;<sub><em>m, n</em></sub> the identity on the underlying set <em>X</em>. Then the inverse limit would have underlying set <em>X</em> (essentially), but <em>d</em><sub>&infin;</sub>(<em>x</em>, <em>y</em>) = &infin; unless <em>x</em> = <em>y</em>.</p> <p>Come to think of it, this seems to provide a counterexample to your statement, since the underlying space could easily be a polyhedron (with uncountable underlying set), while any discrete set which embeds into R<sup><em>d</em></sup> is at most countable.</p> <p>(Never mind, I see in your paper that you assume the space to be embedded is compact.)</p> http://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics/16073#16073 Answer by Chad Groft for Colloquial catchy statements encoding serious mathematics Chad Groft 2010-02-22T18:26:06Z 2010-02-22T18:26:06Z <blockquote> <p>Truth is undefinable,</p> </blockquote> <p>which is a statement of Tarski's theorem. More precisely,</p> <blockquote> <p>Truth in a context where one can do arithmetic is undefinable in that context.</p> </blockquote> http://mathoverflow.net/questions/14574/your-favorite-surprising-connections-in-mathematics/16014#16014 Answer by Chad Groft for Your favorite surprising connections in Mathematics Chad Groft 2010-02-22T02:17:27Z 2010-02-22T02:17:27Z <p>The fact that the circumference of a unit circle is used to normalize the bell curve. Elementary compared to the other examples, yes, but how shocking was it when you first learned it?</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70435#70435 Comment by Chad Groft Chad Groft 2011-10-14T01:49:21Z 2011-10-14T01:49:21Z Resurrecting an old answer here: It should be noted that many of these can be ruled out by resorting to countable AC or dependent choice, which avoid many of the strange consequences of full AC. For example, &quot;A set can be infinite, but have no countably infinite subset&quot;, is ruled out by countable AC. http://mathoverflow.net/questions/20386/mathematics-as-a-hobby/20397#20397 Comment by Chad Groft Chad Groft 2011-08-24T11:57:31Z 2011-08-24T11:57:31Z &quot;Everything else, like getting the books and papers you need, is basically solved by knowing google and wikipedia :-)&quot; How are you seeing the papers? One does need a good university library nearby, for that at the very least. Even MathSciNet isn't available to the general public. http://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-other/58337#58337 Comment by Chad Groft Chad Groft 2011-03-13T16:16:45Z 2011-03-13T16:16:45Z That's not a problem. The whole argument is proof by contradiction; you've just provided a different contradiction. http://mathoverflow.net/questions/58341/is-a-space-with-no-covering-spaces-simply-connected Comment by Chad Groft Chad Groft 2011-03-13T16:10:21Z 2011-03-13T16:10:21Z Nitpick: I assume you mean &quot;connected covering space&quot;, because otherwise... http://mathoverflow.net/questions/54981/is-the-closedness-of-the-image-of-operator-needed-in-the-defintion-of-fredholm/54984#54984 Comment by Chad Groft Chad Groft 2011-02-10T03:58:48Z 2011-02-10T03:58:48Z That &quot;im T + C^n&quot; is supposed to be at the end of the first paragraph. Not sure why it didn't show up there. http://mathoverflow.net/questions/48771/proofs-that-require-fundamentally-new-ways-of-thinking/48782#48782 Comment by Chad Groft Chad Groft 2010-12-14T02:07:18Z 2010-12-14T02:07:18Z I took the last set theory course that Cohen taught, and this isn't how he presented his insight at all (though his book takes this approach). The central problem is &quot;how do I prove that non-constructible [sub]sets [of N] are possible without access to one?&quot;, and his solution is &quot;don't use a set; use an adaptive oracle&quot;. Once that idea is present, the general method falls right into place. The oracle's set of states can be any partial order, generic filters fall right out, names are clearly necessary, everything else is technical. The hardest part is believing it will actually work. http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/46171#46171 Comment by Chad Groft Chad Groft 2010-11-16T04:16:40Z 2010-11-16T04:16:40Z My guess is that adjoining $z^{-1}$ does not get you all the way to $F_2$, but it's not a very well-informed guess. http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/46171#46171 Comment by Chad Groft Chad Groft 2010-11-16T02:45:30Z 2010-11-16T02:45:30Z Note also that the criteria above don't cover the whole space of possibilities. $z=a^2b^3a^2bab^2$ is the simplest word I can find which isn't covered. http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/46171#46171 Comment by Chad Groft Chad Groft 2010-11-16T02:20:23Z 2010-11-16T02:20:23Z Good point. I'll edit the answer to note this. http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12062#12062 Comment by Chad Groft Chad Groft 2010-07-03T14:45:52Z 2010-07-03T14:45:52Z I don't think this is an example. Remember that the zero polynomial has negative degree and every number as a root; so one must argue separately that zero-degree polynomials have no roots. The whole point was to not argue the base case separately. http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem/27664#27664 Comment by Chad Groft Chad Groft 2010-06-10T10:57:25Z 2010-06-10T10:57:25Z <i>G</i> is part of the input. http://mathoverflow.net/questions/24350/what-does-it-mean-for-a-mathematical-statement-to-be-true/24353#24353 Comment by Chad Groft Chad Groft 2010-05-13T13:18:17Z 2010-05-13T13:18:17Z @H Hasson: First sentence is true, but misses the depth of the result. Because the Halting Problem is undecidable and individual cases can be encoded as 1st-order sentences of number theory, the set Th(N) of <i>true</i> 1st-order sentences of number theory is not computable, and therefore is not computably enumerable. Now for any proof system worthy of the name, the set of provable [1st-order number theory] sentences <i>is</i> c.e. It therefore cannot coincide with Th(N) — either the system proves false sentences, or (preferably) fails to prove true ones. One only need <i>encompass</i> 1st-order theory. http://mathoverflow.net/questions/23788/reducing-aca-proof-to-first-order-pa Comment by Chad Groft Chad Groft 2010-05-07T00:18:50Z 2010-05-07T00:18:50Z I don't think the Speed-Up Theorems apply. We're not bounding the length of a proof of <code>$\phi$</code> in terms of the length of <code>$\phi$</code>, we're bounding one type of proof in terms of another type. I would guess that there is some sort of recursive construction of a first-order proof from a second-order proof. You'd want to prove a super-theorem like &quot;if <code>$\mathrm{ACA}&#95;0 \vdash \phi$</code>, then there is a proof whose formulae all have no more 2nd-order variables or quantifiers than <code>$\phi$</code> itself&quot;, by eliminating steps which decreased QC or variable count. http://mathoverflow.net/questions/21741/probability-homework-help Comment by Chad Groft Chad Groft 2010-04-18T13:30:05Z 2010-04-18T13:30:05Z MO is for research-level questions. Try tutorii.com. http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20918#20918 Comment by Chad Groft Chad Groft 2010-04-10T16:12:18Z 2010-04-10T16:12:18Z Just the set <i>n_-tuples in _&amp;omega;</i>. It's usually written as <i>&amp;omega;&lt;sup&gt;n&lt;/sup&gt;</i>, but that notation could also refer to ordinal exponentiation, which is not quite the same.