User chad groft - MathOverflow

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}$?

2011-12-06T05:24:17Z

Yes. Start with a model of GCH and add $\aleph_{\omega+1}$ Cohen reals. Then $2^{\aleph_n}=\aleph_{\omega+1}$ for all $n<\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.)

Answer by Chad Groft for When 2^a = 2^b implies a=b (a,b cardinals)

2010-03-05T03:01:14Z

François's and Joel's answers to the general question are correct.

As for the "dimension of a free group is uniquely determined, even if it's infinite", there's a better argument. Let G be a free group on two sets of generators x and y; we wish to show |x| = |y|. First let A = G_ab be the free abelian group on generators x and y; then let V = A ⊗_Z F₂ be the vector space over F₂ with bases x and y, ~~so that |V| = 2^|x| = 2^|y|~~ (strike that, it's false for infinite cardinalities). (We could use any field here~~, but the argument is more intricate~~.)

If |V| is finite, then |x| = |y| follows immediately. So suppose |V| is infinite, so that |x| and |y| are infinite. Each element of x is the sum of finitely many elements of y, and every element of y must show up in at least one such sum (why?). This means |y| ≤ |x|•ℵ₀ = |x| (cardinal arithmetic). Similarly |x| ≤ |y|, so |x| = |y|.

Answer by Chad Groft for Is the "closedness of the image of operator" needed in the defintion of Fredholm operators?

2011-02-10T03:57:38Z

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$.

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$.

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.

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.

Answer by Chad Groft for Adding a formal inverse of an element to a free monoid

2010-11-16T01:35:11Z

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.)

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.

Symmetrically, if $z$ begins and ends with $b$ but contains an occurrence of $a$, then $z^{-1}$ exists implies $a^{-1}$, $b^{-1}$ exists.

I suspect these are the only cases which work (i.e., inverting a word of the form $awb$ or $bwa$ would not invert $a$ or $b$) but cannot yet prove it. (EDIT: This is false, see Mark's comment below.)

EDIT: Partial result! Consider the structure $M$ whose underlying set is

$\{(m,e) \in \mathbb{N}\times\mathbb{Z} : m\ge e\}$

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)$.

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$.

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}]$, i.e., inverting $z$ does not invert $a$.

(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}$).)

Answer by Chad Groft for Proof of Gödel incompleteness

2010-06-06T22:55:29Z

There's a subtle point at the bottom of the first page and top of the second, to wit:

"For every sentence σ, $M\vDash\sigma$ iff $N\vDash(m\vDash\sigma)$. In particular, $N\vDash$ (m is a model)."

If "model" means "model of ZF", then one cannot conclude this. It is possible that N knows, for each particular σ ∈ ZF, that $m\vDash\sigma$, without knowing that m models ZF as a whole. This is because N '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.

However, if "model" means "model of Σ" where Σ 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 Σ is to model each σ in the explicit list; thus, if M does this, then N must know that m does this.

Answer by Chad Groft for Minimum enclosing rectangle of a convex polygon proof

2010-05-07T13:53:29Z

Suppose you've got your polygon P, embedded in the Euclidean plane with some standard coordinate system. Then there's some rectangle R with horizontal and vertical sides which encloses P 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 θ will; so the rectangle R_θ and its area A_θ are really functions of θ (and (π/2)-periodic functions at that). As such, A definitely has a minimum at some angle θ_min.

The meat of the theorem is that, for any angle φ where R_φ does not meet the conclusion, the function A does not even have a local minimum. To see this, note that R_φ intersects P at a finite set of points S — usually |S| = 4, but 3 or 2 are also possible. Now consider the rectangle R'_θ which is the smallest rectangle with sides parallel to the θ-axes and which contains S, and let A'_θ be its area. Note two things:

For θ near φ, R'_θ = R_θ, and hence A'_θ = A_θ.
Near φ, the function A' is concave downward. Why? Divide the rectangle R'_θ along the lines between the points of S. We get a convex polygon determined by S (and hence constant), plus |S|-many right triangles. Each triangle has a hypotenuse which stays constant as θ changes, and an interior angle which changes as θ/2, hence an area which is concave downward.

Under our assumption, φ can't possibly be a local minimum of A, let alone a global one; so wherever the global minimum is, it must have a side coincident with one of the sides of P.

Answer by Chad Groft for Is there a "primitive-recursively enumerable" set whose complement is not such?

2010-04-12T12:25:29Z

There is a stronger result: Every r.e. set is primitive r.e. in your sense.

Short proof: Kleene's Normal Form Theorem.

Longer proof: Let S be an r.e. set, assumed WLOG nonempty; fix a ∈ S, and fix an algorithm e where S is precisely the range of the function computed by e.

Consider the following algorithm: Given the input pair (n, M), run e on input n for M steps. If it gives an output by then, output whatever e outputs; otherwise output a.

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 S.

Edit: Cutland's Computability is a decent resource for these questions.

Answer by Chad Groft for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T12:38:15Z

The Axiom of Determinacy (AD) fails.

What that means: Partition the set ^ωω into two sets S and T, and think of this partition as a game (S, T) with two players. To play, player 1 picks a natural number a₀, then player 2 picks b₀ (as a function of a₀), then player 1 picks a₁ (as a function of b₀), then player 2 picks b₁ (as a function of a₀ and a₁), and so on until a_n and b_n are selected for all n ∈ ω. Then the sequence a₀, b₀, a₁, b₁, … is either in S (in which case player 1 wins), or in T (in which case player 2 wins).

The game (S, T) is determined if either player 1 or player 2 has a winning strategy, i.e., if there are functions f_n: ⁿω → ω where choosing a_n = f_n( b₀, …, b_n–1 ) 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 R.

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.)

There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to L(R). 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^L(R) is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals".

Answer by Chad Groft for Do the empty set AND the entire set really need to be open?

2010-03-24T23:53:06Z

This question may be better answered by going to the intuition.

Let X 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 U ⊆ X is open if, whenever U contains a point p, it also contains all those points q ∈ X which are "near p".

Given this, U = X is clearly open. If p ∈ U, we want all the points of X "near p" to be in U; but every point of X is in U, so this is trivially true.

∅ is also clearly open. For this to be false, ∅ would have to contain a point p but not all the points near p; but as ∅ contains no points, this is impossible.

Also consider the following: Let f : X → {0,1} be the constant function sending every p ∈ X to 0. We want constant functions to be continuous, no matter how fine the topology on {0,1}. So f ^-1[{0}] = X and f ^-1[{1}] = ∅ both must be open (and both must be closed).

Is any interesting question about a group G decidable from a presentation of G?

2010-02-21T03:37:41Z

We say that a group G is in the class F_q if there is a CW-complex which is a BG (that is, which has fundamental group G and contractible universal cover) and which has finite q-skeleton. Thus F₀ contains all groups, F₁ contains exactly the finitely generated groups, F₂ the finitely presented groups, and so forth.

My question: For a fixed q ≥ 3, is it possible to decide, from a finite presentation of a group G, whether G is in F_q or not? I would assume not, but am not having much luck proving it.

One approach would be to prove that, if G is a group in F_q and H is a finitely presented subgroup, then H ∈ F_q as well. This would make being in F_q a Markov property, or at least close enough to make it undecidable.

Henry Wilton's comment below makes it clear that being F_q is not even quasi-Markov, so the above idea won't work. I still suspect that "G ∈ F_q" is not decidable, but now my intuition is from Rice's theorem:

If $\mathcal{B}$ is a nonempty set of computable functions with nonempty complement, then no algorithm accepts an input n and decides whether φ_n is an element of $\mathcal{B}$.

~~It seems likely to me that something similar is true of finite presentations and the groups they define.~~

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.

Any thoughts?

Answer by Chad Groft for Results about the order of a group forcing a particular property.

2010-03-06T17:10:13Z

Very famous one is the Feit-Thompson theorem: if n is odd, then G is solvable. Though I suppose this is stated (but not proved) in most modern algebra texts.

Answer by Chad Groft for Inverse limit in metric geometry

2010-03-01T05:00:05Z

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.

For example, fix a metric space (X, d) and define (X_n, d_n) = (X, 2ⁿd), with φ_{m, n} the identity on the underlying set X. Then the inverse limit would have underlying set X (essentially), but d_∞(x, y) = ∞ unless x = y.

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^d is at most countable.

(Never mind, I see in your paper that you assume the space to be embedded is compact.)

Answer by Chad Groft for Colloquial catchy statements encoding serious mathematics

2010-02-22T18:26:06Z

Truth is undefinable,

which is a statement of Tarski's theorem. More precisely,

Truth in a context where one can do arithmetic is undefinable in that context.

Answer by Chad Groft for Your favorite surprising connections in Mathematics

2010-02-22T02:17:27Z

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?

Comment by Chad Groft

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, "A set can be infinite, but have no countably infinite subset", is ruled out by countable AC.

Comment by Chad Groft

2011-08-24T11:57:31Z

"Everything else, like getting the books and papers you need, is basically solved by knowing google and wikipedia :-)" 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.

Comment by Chad Groft

2011-03-13T16:16:45Z

That's not a problem. The whole argument is proof by contradiction; you've just provided a different contradiction.

Comment by Chad Groft

2011-03-13T16:10:21Z

Nitpick: I assume you mean "connected covering space", because otherwise...

Comment by Chad Groft

2011-02-10T03:58:48Z

That "im T + C^n" is supposed to be at the end of the first paragraph. Not sure why it didn't show up there.

Comment by Chad Groft

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 "how do I prove that non-constructible [sub]sets [of N] are possible without access to one?", and his solution is "don't use a set; use an adaptive oracle". 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.

Comment by Chad Groft

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.

Comment by Chad Groft

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.

Comment by Chad Groft

2010-11-16T02:20:23Z

Good point. I'll edit the answer to note this.

Comment by Chad Groft

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.

Comment by Chad Groft

2010-06-10T10:57:25Z

G is part of the input.

Comment by Chad Groft

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 true 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 is 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 encompass 1st-order theory.

Comment by Chad Groft

2010-05-07T00:18:50Z

I don't think the Speed-Up Theorems apply. We're not bounding the length of a proof of $\phi$ in terms of the length of $\phi$ , 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 "if $\mathrm{ACA}_0 \vdash \phi$ , then there is a proof whose formulae all have no more 2nd-order variables or quantifiers than $\phi$ itself", by eliminating steps which decreased QC or variable count.

Comment by Chad Groft

2010-04-18T13:30:05Z

MO is for research-level questions. Try tutorii.com.

Comment by Chad Groft

2010-04-10T16:12:18Z

Just the set n_-tuples in _ω. It's usually written as ω<sup>n</sup>, but that notation could also refer to ordinal exponentiation, which is not quite the same.