Update. I present here a quick sketch of the solution of Exercise 3.(b). See Lecture 18, where it is shown that the result actually holds in , although the proof uses choice.

Let and be two well-orderings of a set . We want to find a subset of of the same size as where the two well-orderings coincide. Let . By combining with an isomorphism between and its order type, we may assume that is an ordinal and . By restricting attention to the subset of , we may assume is a well-ordering of . By further restricting to the subset of of order type under , we may assume that as well.

Assume first that is regular. The result follows easily. The desired set can be built by a straightforward recursion: Given and a sequence of elements of increasing under both well-orderings, regularity ensures that the sequence is bounded under both well-orderings, and we can find which is larger than all the previous under both orderings.

The argument for singular is slightly more delicate. Namely, we may not be able to carry out the construction above since the sequence could be unbounded in one of the orderings when . We circumvent the problem by only considering ordinals whose cofinality is larger than the cofinality of . Notice that if an increasing sequence of order type is unbounded in an ordinal of cofinality , then .

To implement this idea, let be an increasing sequence of regular cardinals cofinal in , with . Consider the subset . It must contain a subset of size where coincides with . By the remark above, this subset is bounded in . Let denote the shortest initial segment of containing . By removing from the set , we are left with a set of size , and any ordinal there is larger than the elements of under both orderings. The induction continues this way, by considering at stage a set of size .

This entry was posted on Tuesday, May 20th, 2008 at 12:40 am and is filed under 116c: Set theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

[…] amusing application of the fact that is that the result of Exercise 3 from Homework 7 holds in , although the proof I wrote there uses choice. Namely, work in and consider two […]

Stefan, "low" cardinalities do not change by passing from $L({\mathbb R})$ to $L({\mathbb R})[{\mathcal U}]$, so the answer to the second question is that the existence of a nonprincipal ultrafilter does not imply the existence of a Vitali set. More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${ […]

Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ with all its edges of the same color. For example, $R(3)= 6$, which is usually stated by saying that in a party of 6 people, necessarily there are 3 that know e […]

No, this is not consistent. Todorčević has shown in ZF that, in fact, there is no function $F\!:\mathcal W(S)\to S$ with the property you require. Here, $\mathcal W(S)$ is the collection of subsets of $S$ that are well-orderable. This is corollary 6 in MR0793235 (87d:03126). Todorčević, Stevo. Partition relations for partially ordered sets. Acta Math. 155 (1 […]

As suggested by Gerald, the notion was first introduced for groups. Given a directed system of groups, their direct limit was defined as a quotient of their direct product (which was referred to as their "weak product"). The general notion is a clear generalization, although the original reference only deals with groups. As mentioned by Cameron Zwa […]

Gödel sentences are by construction $\Pi^0_1$ statements, that is, they have the form "for all $n$ ...", where ... is a recursive statement (think "a statement that a computer can decide"). For instance, the typical Gödel sentence for a system $T$ coming from the second incompleteness theorem says that "for all $n$ that code a proof […]

When I first saw the question, I remembered there was a proof on MO using Ramsey theory, but couldn't remember how the argument went, so I came up with the following, that I first posted as a comment: A cute proof using Schur's theorem: Fix $a$ in your semigroup $S$, and color $n$ and $m$ with the same color whenever $a^n=a^m$. By Schur's theo […]

It depends on what you are doing. I assume by lower level you really mean high level, or general, or 2-digit class. In that case, 54 is general topology, 26 is real functions, 03 is mathematical logic and foundations. "Point-set topology" most likely refers to the stuff in 54, or to the theory of Baire functions, as in 26A21, or to descriptive set […]

In the presence of the axiom of foundation, it is true as you indicate that no set belongs to itself, and so the definition of transitive set can be written with $\subset$ (or $\subsetneq$, whichever symbol you prefer). However, one may study also set theories where foundation fails, and then it is natural to define transitive sets in a way that allows self- […]

You do not need much to recover the full ultrapower. In fact, the $\Sigma_1$-weak Skolem hull should suffice, where the latter is defined by using not all Skolem functions but only those for $\Sigma_1$-formulas, and not even that, but only those functions defined as follows: given a $\Sigma_1$ formula $\varphi(t,y_1,\dots,y_n)$, let $f_\varphi:{}^nN\to N$ be […]

[…] amusing application of the fact that is that the result of Exercise 3 from Homework 7 holds in , although the proof I wrote there uses choice. Namely, work in and consider two […]