We briefly discussed relative constructibility and compared the models where is exclusively treated as a predicate with the models where is an element. In particular, is a model of choice but may fail to be.

An 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 well-orderings of a set . We can assume that is an ordinal and the first well-ordering is . Let be the second well-ordering. Then (since is a set of ordered pairs of ordinals). In , where choice holds, (and therefore also in ) there is a subset of of the same size as and where coincides with .

Question. Find a `choice-free’ argument for Exercise 3.

The main example we will consider of a model of the form is , due to its connection with determinacy.

We introduced the setting to discuss determinacy, namely infinite 2-person games with perfect information. We proved the Gale-Stewart theorem that open games are determined and discussed Martin’s extension to Borel games. A nice reference for the proof of Martin’s result (using the idea of `unraveling‘, which reduces any Borel game to an open game in a different space) is Kechris’s book on descriptive set theory:

This entry was posted on Friday, May 30th, 2008 at 6:07 pm 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.

[…] 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 […]

[…] 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 […]

Georgii: Let me start with some brief remarks. In a series of three papers: a. Wacław Sierpiński, "Contribution à la théorie des séries divergentes", Comp. Rend. Soc. Sci. Varsovie 3 (1910) 89–93 (in Polish). b. Wacław Sierpiński, "Remarque sur la théorème de Riemann relatif aux séries semi-convergentes", Prac. Mat. Fiz. XXI (1910) 17–20 […]

It is not possible to provide an explicit expression for a non-linear solution. The reason is that (it is a folklore result that) an additive $f:{\mathbb R}\to{\mathbb R}$ is linear iff it is measurable. (This result can be found in a variety of places, it is a standard exercise in measure theory books. As of this writing, there is a short proof here (Intern […]

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 […]

Equality is part of the background (first-order) logic, so it is included, but there is no need to mention it. The situation is the same in many other theories. If you want to work in a language without equality, on the other hand, then this is mentioned explicitly. It is true that from extensionality (and logical axioms), one can prove that two sets are equ […]

$L$ has such a nice canonical structure that one can use it to define a global well-ordering. That is, there is a formula $\phi(u,v)$ that (provably in $\mathsf{ZF}$) well-orders all of $L$, so that its restriction to any specific set $A$ in $L$ is a set well-ordering of $A$. The well-ordering $\varphi$ you are asking about can be obtained as the restriction […]

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 […]

[…] 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 […]

[…] 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 […]