The topic of this course is Combinatorial set theory, so even though we will study additional axioms, we will not emphasize forcing or inner model-theoretic techniques. Similarly, we will study some results of a descriptive set theoretic nature, but will not delve into the fine definability issues that descriptive set theory involves. We will assume the axiom of choice throughout (and I will assume basic knowledge of axiomatic set theory, cardinals and ordinals), but we begin by looking at some results that do not require the axiom of choice.

1. Cantor’s theorem

Version 1. If then is not surjective.

Proof. Let . Then .

Version 2. If then is not injective.

Proof. Let and set so , so there is some with .

Note that in version 1 we explicitly (i.e., definably) found a set not in the range of . In version 2, we found a set for which there is a set with witnessing a failure of injectivity, but we did not actually define such a set . I do not know whether this can be done; we will see later a different argument in which such a pair is defined.

2. The Tarski-Knaster theorem.

Theorem. Let be a complete lattice, and let be order preserving. Then the set of fixed points of is a complete lattice (and, in particular, non-empty).

This is a handout on this result that I wrote for a set theory course I taught at Caltech.

3. The Schröder-Bernstein theorem.

Theorem.Assume that there are injections and . Then there is a bijection .

This is proved as a corollary of the Tarski-Knaster result, see the handout attached above.

Another nice way of proving the result is graph theoretic. We may assume that and are disjoint and form a directed graph whose nodes are elements of and there is an edge from to iff either and or and . Consider the connected components of this graph. Each component is either a cycle of even length, or a -chain, or a -chain. In each case, one can canonically find a bijection between the elements of the component in and the elements in . Putting these bijections together gives the result.

Cantor’s proof of this result uses the axiom of choice (in the form: every set is in bijection with an ordinal).

43.614000-116.202000

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Wednesday, January 21st, 2009 at 6:03 pm and is filed under 580: Topics in 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.

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038). Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternat […]

Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Un […]

I am looking for references discussing two inequalities that come up in the study of the dynamics of Newton's method on real-valued polynomials (in one variable). The inequalities are fairly different, but it seems to make sense to ask about both of them in the same post. Most of the details below are fairly elementary, they are mostly included for comp […]

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

Not necessarily. That $\mathfrak m$ is consistently singular is proved in MR0947850 (89m:03045) Kunen, Kenneth. Where $\mathsf{MA}$ first fails. J. Symbolic Logic 53(2), (1988), 429–433. There, Ken shows that $\mathfrak{m}$ can be singular of cofinality $\omega_1$. (Both links above are behind paywalls.)

No, the rank of a set $x$ is the least $\alpha$ such that $x\in V_{\alpha+1}$. Note that if $\alpha$ is limit, any $x\in V_\alpha$ belongs to some $V_\beta$ with $\beta

The real numbers are the usual thing. Surreal numbers are not real numbers, so no, they are not an example of non-constructible reals. Any real $r$ can be written as an infinite sequence $(n;d_1,d_2,\dots)$ where $n$ in an integer and the $d_i$ are digits. Whether the real is rational, constructible or not, is irrelevant. Any rational number, in fact, any al […]

Following Tomas's suggestion, I am posting this as an answer: I encountered this problem while directing a Master's thesis two years ago, and again (in a different setting) with another thesis last year. I seem to recall that I somehow got to this while reading slides of a talk by Paul Pollack. Anyway, I like to deduce the results asked in the prob […]

This is a beautiful and truly fundamental result, and so there are several good quality presentations. Try MR1321144. Kanamori, Akihiro. The higher infinite. Large cardinals in set theory from their beginnings. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1994. xxiv+536 pp. ISBN: 3-540-57071-3, or any of the newer editions (the 2003 second ed […]