User rob arthan - MathOverflow

Answer by Rob Arthan for Busy Beaver - Proof for BB(2) = 4

2012-03-18T11:05:06Z

I imagine the seminar exercise went something like this.

Let $M$ be a winning machine with starting state $A$, halting state $H$ and one other state $B$. Let's build the transition function of $M$ (or an equivalent or better winner) by looking at the first few transitions. We can assume the first transition is:

$(A, 0) \mapsto (1, R, B)$

because, (a) if $M$ does not write 1, we can swap $A$ and $B$ to get a slightly faster winner, (b) if $M$ moves left, then the machine obtained from $M$ by swapping $L$ and $R$ is an equivalent winner, (c) if $M$ stays in state $A$ it will not terminate, and (d) if $M$ halts it isn't a winner.

Then we can assume the second transition is:

$(B, 0) \mapsto (t_1, L, s_1)$

for some $t_1 \in \{0, 1\}$ and $s_1 \in \{A, B\}$ , because if $M$ moves right again into either state $A$ or $B$ it will not terminate and if it halts it isn't a winner.

On the third transition, we are in state $s_1$ reading 1 and we can't win by halting, so we have:

$(s_1, 1) \mapsto (t_2, d, s)$

for some $t_2 \in \{0, 1\}$ , $d \in \{L, R\}$ and $s \in \{A, B\}$ . As $M$ must halt, for $s_1 \not= s_2 \in \{A, B\}$ , $M$ must halt on $(s_2, 1)$, so the remaining element of the transition function is:

$(s_2, 1) \mapsto (1, X, H)$

where $X$ is irrelevant and $M$ must write 1, since changing a 1 to a 0 on the last step is clearly a losing strategy. There are now just 32 possibilities for $t_1$, $t_2$, $d$, $s$ and $s_1$ to work through. I originally stopped here with an ellipsis, since in the seminar context the participants could divide the work up and do it by brute force, but let me give an argument that while still rather bitty can be checked by an individual.

After the third transition the tape looks like this:

$\begin{array}{lccccc} \mbox{Index:} & \ldots & -1 & 0 & 1 & 2 & \ldots\\ \mbox{Contents:} & \ldots & 0 & t_2 & t_1 & 0 & \ldots \end{array} $

and we are in state $s$ reading either cell $-1$ (if $d = L$) or cell $1$ (if $d = R$). I claim that $d = L$. To see this assume for a contradiction that $d = R$. Then if $t_1 = 0$, $M$ will not terminate (if $s = A$, we are essentially back in the starting position and $M$ will diverge to the right; if $s = B$ and $t_2 = 1$ $M$ will spin on cells 0 and 1 and if $s = B$ and $t_2 = 0$, $M$ will diverge to the left.) Now if $t_1 = 1$ and $s = s_2$, $M$ will halt on the next transition and so is not a winner. So $t_1 = 1$ and $s = s_1$, but then $M$ will loop (two cases to check: $s = A$ and $s = B$). In all cases when $d = R$, $M$ fails to win so $d = L$.

Now we know that the only transition that moves right is the one on $(A, 0)$. This implies that $M$ can never move right past a 1 that has already been written. It follows that the penultimate transition must be a move right. I.e., it must be a transition on $(A, 0)$. But the successor state for this transition is $B$, so we must have $s_1 = A$ and $s_2 = B$. Now if $s = A$, $M$ will either fail to terminate or will halt and lose on the fourth transition (depending on the value of $t_2$). We conclude that $s = B$, so the transition function looks like this:

$\begin{array}{l} (A, 0) \mapsto (1, R, B) \\ (B, 0) \mapsto (t_1, L, A) \\ (A, 1) \mapsto (t_2, L, B) \\ (B, 1) \mapsto (1, X, H) \end{array}$

We now have just four cases to check and unsurprisingly the only possibility that makes $M$ terminate after writing four 1s is the one with $t_1 = t_2 = 1$.

Problem with Shelah and Stern's paper on the Hanf number of the theory of Banach spaces

2012-03-11T15:30:09Z

I have been trying to understand "The Hanf number of the first order theory of Banach spaces" by Shelah and Stern (Trans. AMS 244 (1978) 147-241). They construct a normed space $M$ from a Hilbert space $\cal H$ by taking the unit ball of $M$ to be the intersection of that of $\cal H$ with the halfspaces defined by $(x, \pm a) \le 1 - \delta_a$ for certain unit vectors $a$ and small $\delta_a >0$. They then need to show that the $\cal H$-unit ball is definable in $M$ using a first order language with symbols for vector addition and membership of the $M$-unit ball. With this in view, in their Lemma 2.9, they claim certain of the vectors $a$ are definable, but they don't have what they need to apply the lemma they appeal to for this (they have an inequality $\|b\| \le (1 - \delta)^{-1}$ but their Lemma 2.3 needs the opposite inequality).

So this looks like a bug. I suspect it can be fixed, e.g., by taking the unit ball to be the convex hull of the proposed one and the vectors $\pm a$. But this would be quite disruptive to the rest of the argument, I suspect.

My questions are (1) have I missed something so that Shelah and Stern's proof does actually go through more or less as its stands, or (2) is there another reference that gives a correct proof of these results.

"Archimedeanising" an ordered field

2012-02-03T17:49:40Z

If $K$ is an ordered field, let $B$ be the subring comprising the $x \in K$ such that $|x| \le n$ for some $n \in N$, and let $I$ be the ideal of $B$ comprising the infinitesimal elements (i.e. the $x \in K$ such that $|x| \le 1/n$ for every non-zero $n \in N$). Then $I$ is a maximal ideal and the order on $K$ induces an order on $A = B/I$ making it into an archimedean ordered field.

Has this construction been studied? More specifically, when does the natural projection of $B$ onto $A$ split (in the category of rings or, better still, ordered rings)? I believe it always has an order-preserving splitting if $K$ is real closed.

Answer by Rob Arthan for Morse-Kelley set theory consistency strength

2012-02-01T16:04:01Z

ZF can describe the set of formulas that are not provable in ZF, but, unless it's inconsistent, it can't prove that that set is non-empty. Mostowski proved that MKM can prove this set is non-empty:

@article{0039.27601, author="Mostowski, Andrzej", title="{Some impredicative definitions in the axiomatic set-theory.}", language="English", journal="Fundam. Math.", volume="37", pages="111-124", year="1950", keywords="{set theory}", }

Answer by Rob Arthan for analysis over non-Archimedean ordered fields

2012-01-18T11:48:12Z

I don't understand Stefan's suggestion that you can get a field by taking (presumably) the Dedekind-Macneille completion of the ordered field of Newton-Puiseux series or any non-archimedean field. A non-archimedean field cannot be order-theoretically complete, e.g., because the set of integers is bounded above but can have no least upper bound (if $x > \mathbb{Z}$, then so is $x - 1$).

However, many notions of analysis do make sense over a real closed field. Such fields can be non-archimedean, the above mentioned field of Newton-Puiseux series being a classic example. This is part of the subject matter of real algebraic geometry (see the book of that name by Bochnak, Coste and Roy), or more generally of tame topology (see the book Tame Topology and O-minimal Structures by van den Dries). There are also lots of papers and survey articles on these topics at the Real Algebraic and Analytic Geometry preprint server: http://www.maths.manchester.ac.uk/raag/.

Universal functors according to Cohn.

2010-08-05T17:19:44Z

In section III.1 of P.M. Cohn's Universal Algebra a notion of universal functor ${\cal L} \rightarrow {\cal K}$ is defined for a representation of one category in another given by a (covariant) functor $F: {\cal L}^{\mbox{opp}} \times {\cal K} \rightarrow \mbox{Set}$. The objects part of the functor is specified by a universal property and Cohn states and proves a proposition (1.1) stating that if this exists, then it is indeed the objects part of a functor $U$ and that a certain mapping $\rho$ is a natural transformation from $I$ to $U$.

Cohn writes $\rho$ as $\rho(A) : A \rightarrow U(A)$ where $A \in \mbox{Ob} {\cal L}$. But as $A$ and $U(A)$ are objects in different categories, even given his convention of omitting certain "obvious" functors, I can make no sense of this in the general case, where the representation is not given by a forgetful functor. (To make things "type correct", $\rho(A)$ has to be an element of the set $F(A, U(A))$).

I can see how to define the morphisms part of the functor $U$ using the universal property and how to prove that $U$ is then a functor by a diagram chase in $\mbox{Set}$, but this is nothing like Cohn's proof which appears to compose morphisms from two different categories. I can also see how Cohn's proof would say something in the case where the representation is derived from a forgetful functor, but I can't even see how to formulate the claim that $\rho$ is a natural transformation from $I$ to $U$ in the general case. I doubt very much that Cohn is wrong, so what am I missing?

Comment by Rob Arthan

2012-02-08T13:45:37Z

Sorry to be repetitive! For some bizarre reasons, the earlier answers didn't appear until I posted mine.

Comment by Rob Arthan

2012-02-04T13:34:56Z

@Moshe: Apologies: I misunderstood your reply. I think now that you were saying that the projection is called the "standard part map" and I have no quibbles with that.

Comment by Rob Arthan

2012-02-04T09:46:39Z

@Moshe: Thanks for a useful reference. I think you will find the existence of a standard part map is a hypothesis rather than a theorem in the work you refer to e.g., see the paper by [Marikova](math.mcmaster.ca/~marikova/thesispaper3.pdf). I should have said that the splittings I am interested in are to be ring homomorphism, or, even better, ordered ring homomorphisms. As you say the projection always splits when you just view $K$ and $A$ as vector spaces over $\mathbb{Q}$ (given AC to construct a basis, in general, as Gerald points out).

Comment by Rob Arthan

2012-02-04T09:33:37Z

That doesn't work in general. Let $K$ be the splitting field for the polynomial $X^2 - 2 - \epsilon$ over the field $\mathbb{Q}(\epsilon)$ of rational functionals with rational coefficients of an an infinitesimal indeterminate $\epsilon$. Then $A$ is isomorphic to $\mathbb{Q}[\sqrt{2}]$, but 2 is not a square in $K$.

Comment by Rob Arthan

2012-01-18T16:23:16Z

Stefan: thanks for the clarification. For completeness (in the non-technical sense :-)), I should have pointed out that in the real algebraic geometry approach, you do get all the usual goodies like the intermediate value theorem, the mean value theorem, Rolle, Taylor series etc. for definable functions satisfying the appropriate continuity or differentiability conditions.

Comment by Rob Arthan

2010-08-25T21:56:19Z

The Google Books link I gave is for the 2nd edition of Cohn. Thanks to you both for the very helpful answers. This seems like quite a wide lacuna for the unsuspecting reader to me.