305 -1. Algebra and induction

January 21, 2009

1. Abstract algebra is the study of algebraic structures (groups, rings, fields, etc). Most of this study is done at a fairly general level, and its development marks a significant shift from how mathematics had been done before, where the emphasis was on particular structures (say, the set of reals, or triangles in Euclidean plane) and their properties. We follow the textbook in that our approach will be with the goal of solving the question of which polynomial equations (with integer) coefficients can be solved (by radicals). Concepts will be introduced with this goal in mind, and we will begin by looking at fields (mainly number fields) and move to groups, rather than the other way around, as it is customary.

The study of equations has always been an integral part of algebra, and it certainly guided its origins. The book starts with a nice short history, here is the pdf on this subject I used in lecture. It ends with a short list of names of (mostly) mathematicians that intends to illustrate the historical development of the idea of mathematical induction. Following the book, we introduce induction in the  form of the well-ordering principle.

2. Notation. {\mathbb N}=\{0,1,2,\dots\} is the set of natural numbers. P={\mathbb Z}^+={\mathbb N}^+ is the set of positive integers. {\mathbb Z} is the set of integers (or whole numbers).

The well-ordering principle. Every nonempty set of natural numbers has a least element.

This should be understood as an axiomatic property of the natural numbers.

Our first application is in proving the following result, (what one usually calls the division algorithm).

Theorem. Given integers m,n with n>0, there are integers q,r such that m=nq+r and 0\le r<n.

Proof.  Consider the set A of natural numbers that can be written in the form m-nq for some integer q. (So, as q varies, the numbers m-nq belong to A or not depending on whether they are nonnegative.)

This set is nonempty (this can be proved by analyzing two cases, depending on whether m\ge0 or not; in each case, we can explicitly exhibit an element of A). By the well-ordering principle, A has a least element. Call it r.

Since r\in A, there is some integer q such that m=nq+r; fix such q and r in what follows. It remains to show that 0\le r<n. That 0\le r follows from the fact that r\in A, and all the elements of A are nonnegative.

That r<n is proved by contradiction: Otherwise, 0\le r-n<r, and r=m-nq, so r-n=m-n(q+1)=m-nq' where q'=q+1. It follows that r-n\in A, but this is impossible, since r-n<r, and r is the least element of A. This is a contradiction. It follows that it is not the case that r\ge n, so r<n, as wanted. \mathsf{QED}


580 -I. Some choiceless results

January 21, 2009

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 f:X\to{\mathcal P}(X) then f is not surjective.

Proof. Let A=\{y\in X:y\notin f(y)\}. Then A\notin{\rm ran}(f). {\sf QED}

Version 2. If f:{\mathcal P}(X)\to X then f is not injective.

Proof. Let A=\{y\in X: \exists Z,(y=f(Z)\notin Z)\} and set a=f(A), so a\in A, so there is some Z\ne A with f(Z)=f(A). {\sf QED}

Note that in version 1 we explicitly (i.e., definably) found a set not in the range of f. In version 2, we found a set A for which there is a set Z with (A,Z) witnessing a failure of injectivity, but we did not actually define such a set Z. 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 (L,\le) be a complete lattice, and let f:L\to L be order preserving. Then the set of fixed points of f 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 f:A\to B and g:B\to A. Then there is a bijection h:A\to B.

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 A and B are disjoint and form a directed graph whose nodes are elements of A\cup B and there is an edge from a to b iff either a\in A and b=f(a) or a\in B and b=g(a). Consider the connected components of this graph. Each component is either a cycle of even length, or a {\mathbb Z}-chain, or a {\mathbb N}-chain. In each case, one can canonically find a bijection between the elements of the component in A and the elements in B. 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).