580 -Some choiceless results (4)

January 29, 2009

Let me begin with a remark related to the question of whether \aleph(X)\preceq {\mathcal P}^2(X). We showed that this is the case if X\sim Y^2 for some Y, or if X is Dedekind-finite.

Theorem. The axiom of choice is equivalent to the statement that any Dedekind-infinite cardinal is a square.

Proof. Let X be a set. Assuming that every D-infinite cardinal is a square, we need to show that X is well-orderable. We may assume that \omega\preceq X. Otherwise, replace X with X\cup\omega. Let \kappa=\aleph(X). Assume that X\sqcup\kappa is a square, say X\sqcup\kappa\sim Y^2. Then \kappa\preceq Y^2. By Homework problem 2, \kappa\preceq Y, so Y\sim \kappa\sqcup Z for some Z, and X\sqcup \kappa\sim Y^2\sim\kappa^2\sqcup 2\times\kappa\times Z\sqcup Z^2\succeq\kappa\times Z.

Lemma. Suppose A,B,C are D-infinite sets and \lambda is an (infinite) initial ordinal. If \lambda\times A\preceq B\cup C then either \lambda\preceq B or A\preceq C.

Proof. Let f:\lambda\times A\to B\sqcup C be an injection. If there is some a\in A such that f(\cdot,a):\lambda\to B we are done, so we may assume that for all a\in A there is some \alpha\in\lambda such that f(\alpha,a)\in C. Letting \alpha_a be the least such \alpha, the map a\mapsto f(\alpha_a,a) is an injection of A into C. {\sf QED}

By the lemma, it must be that either \kappa\preceq X or else Z\preceq\kappa. The former is impossible since \kappa=\aleph(X), so Z is well-orderable, and thus so is Y, and since Y\sim Y^2\succeq X, then X is well-orderable as well. {\sf QED}

Read the rest of this entry »

305 -2. Solving cubic and quartic polynomials.

January 28, 2009


This is trivial, but there is a subtle point here:

  • Some equations have no solutions.






the well known quadratic formula.




Read the rest of this entry »

580 -Some choiceless results (3)

January 27, 2009


5. Specker’s lemma.


Read the rest of this entry »

305 -Homework set 1

January 26, 2009

This set is due February 6 at the beginning of lecture. Consult the syllabus for details on the homework policy.

1. a. Complete the proof by induction that if a,b are integers and (a,b)=1, then (a^n,b)=1 for all integers n\ge1.

b. This result allows us to give a nice proof of the following fact: Let n be a natural number and let m be a positive integer. If the m-th root of n, \root m\of n, is rational, then it is in fact an integer. (The book gives a proof of a weaker fact.)  Prove this result as follows: First verify that if a/b=c/d and b+d\ne0, then \displaystyle \frac ab=\frac{a+c}{b+d}. Show that any fraction a/b with a,b integers, can be reduced so (a,b)=1. Assume that \root m\of n is rational, say a/b. Then also \root m\of n=n/(\root m\of n)^{m-1}. Express this last fraction as a rational number in terms of n,b,a. Use that (a^k,b)=1 for all k\ge1 and the general remarks mentioned above, to show that \root m\of n is in fact an integer.

2. Show by induction that for all integers k\ge 1 there is a polynomial q(x) with rational coefficients, of degree k+1 and leading coefficient 1/(k+1), such that for all integers n\ge1, we have \displaystyle \sum_{i=1}^n i^k =q(n). There are many ways to prove this result. Here is one possible suggestion: Consider \displaystyle \sum_{i=1}^n [(i+1)^{k+1}-i^{k+1}].

3. Euclidean algorithm. We can compute the gcd of two integers m,n, not both zero, as follows; this method comes from Euclid and is probably the earliest recorded algorithm. Fist, we may assume that m, n are positive, since (m,n)=(|m|,|n|), and also we may assume that m\ge n, so m>0. Now define a sequence r_0,r_1,r_2,\dots of natural numbers as follows:

  • r_0=m, r_1=n.
  • Given r_i,r_{i+1}, if r_{i+1}=0, then {\tt STOP}.
  • Otherwise, r_{i+1}>0, and we can use the division algorithm to find unique integers q,r with 0\le r<r_{i+1} such that r_i=r_{i+1}q+r. Set r_{i+2}=r.
  • Let A be the set of those r_k that are strictly positive. This set has a least element, say r_k. By the way the algorithm is designed, this means that r_{k+1}=0.
  •  Show that r_k=(m,n), and that we can find from the algorithm, integers x,y such that r_k=mx+ny.

(If the description above confuses you, it may be useful to see the example in the book.)

4. Assume that the application of the algorithm, starting with positive integers m>n, takes k steps. [For example, if m=35 and n=25, the algorithm gives:

Step 1: 35=25.1+10, so r_0=35,r_1=25,r_2=10.

Step 2: 25=10.2+5, so r_3=5.

Step 3: 10=5.2, so r_4=0, and (35,25)=5. Here, k=3]

Show that n\ge F_{k+1}, where the numbers F_1,F_2,\dots are the Fibonacci numbers, see Exercises 15-22 in Chapter 1 of the book.

5. Extra credit problem. With m,n,k as in the previous exercise, let t be the number of digits of n (written in base 10). Show that k\le 5t.

305 -Algebra and induction (3)

January 26, 2009

Definition. p>1 is prime iff the only positive divisors of p are 1 and p.

Proposition. A number p>1 is prime iff for all m, either p\mid m or else (p,m)=1. \Box 

Proposition. Let p be prime, and let m,n be integers. If p\mid mn then either p\mid m or p\mid n. \Box

In the more general setting of rings, of which the integers are an example, it is customary to call a number p prime when it satisfies the second proposition, and to call it irreducible when it satisfies the definition above. Both notions coincide for the integers, but there are examples of rings where there are irreducible elements that are not prime. We will introduce rings later on in the course.

Mathematical induction. Let N\in{\mathbb Z}. Let P(\cdot) be a statement about integers, so for each integer m, P(m) may or may not hold. Assume

  1.  P(N) holds, and
  2. \forall k\ge N,( if P(k) holds then P(k+1) holds).

Then \forall k\ge N,(P(k) holds).

Strong induction. Let N\in{\mathbb Z}. Let P(\cdot) be a statement about integers. Assume

  • \forall k\ge N,( if \forall m with N\le m<k it is the case that P(m) holds, then also P(k) holds).


Both induction and strong induction are consequences of the well-ordering principle. In fact, all three statements are equivalent. Most properties about the natural numbers are established by inductive arguments. Here are two examples:

Example 1. For all n\ge1, \displaystyle \sum_{ i=1}^n i=\frac {n(n+1)}2.

We also have \displaystyle \sum_{ i=1}^n i^2=\frac {n(n+1)(2n+1)}6 and \displaystyle \sum_{ i=1}^n i^3=\left(\frac {n(n+1)}2\right)^2. In fact, for all k\ge 1, there is a polynomial q(x) with rational coefficients, of degree k+1 and leading coefficient \displaystyle \frac1{k+1} such that for all n\ge1\displaystyle \sum_{ i=1}^n i^k=q(n).

Example 2. For all integers a,b, if (a,b)=1 then for all n\ge1, (a^n,b)=1.

580 -Some choiceless results (2)

January 25, 2009








Read the rest of this entry »

305 -Algebra and induction (2)

January 23, 2009

Last time we showed that given (integers) m,n with n>0, there are q,r with 0\le r<n such that m=nq+r. We began today by showing that these integers q,r are unique. When r=0, we say that n divides m, in symbols n\mid m.

Definition. A greatest common divisor of the integers m,n not both zero, is a positive integer d that divides both m,n and such that any integer that divides both m,n, also divides d.

We showed that for any m,n not both zero, there is a unique such d, in symbols d={\rm gcd}(m,n) or simply d=(m,n). We also showed the following characterization:

Theorem. Let m,n be integers, not both zero. Let S=\{l\in{\mathbb Z}^+: for some integers x,y, l=mx+ny\}.  Then the following are equivalent statements about the integer d:

  1. d=(m,n).
  2. d \mid m, d\mid n, and d\in S.
  3. S=\{ kd: k\in{\mathbb Z}^+\}.
  4. d is the least member of S.

305 -1. Algebra and induction

January 21, 2009


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.








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.


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).

BOISE EXTRAVAGANZA IN SET THEORY – Announcement 2, Call for papers

January 20, 2009

The 18-th annual meeting of BEST will be hosted at Boise State University during the weekend of March 27 (Friday) – March 29 (Sunday), 2009.

It is organized by Liljana Babinkostova, Andres Caicedo, Stefan Geschke, Richard Ketchersid and Marion Scheepers.

Contributed and invited talks will be held on Friday, Saturday and Sunday at the Department of Mathematics, Boise State University. The four invited speakers are:

Steve Jackson (University of North Texas)

Ljubisa Kocinac (University of Nis, Republic of Serbia)

Assaf Rinot (Tel Aviv University, Israel)

Grigor Sargsyan (University of California, Berkeley)

The conference webpage is available at URL


There are four important deadlines regarding the conference:

Lodging: The Hampton Inn & Suites is providing rooms at a reduced rate for BEST participants. To take advantage of the reduced rate, reservations must be made online by MARCH 12. Follow this link for the Hampton Inn’s online reservation site for BEST.

Financial support: Limited financial support is available to partially offset travel expenses of some participants. The criteria for granting support include whether the participant has alternative financial support for the conference, and whether the participant is presenting a talk at the conference. Preference is given to graduate students and early career researchers. The amount of support is contingent on the budget constraints. University accounting regulations require completing certain forms online BEFORE the conference, and submitting original receipts of expenses. Reimbursements will be sent after the conference. The deadline for applying for financial support is MARCH 3.

To apply for support, email the organizers at 


Applications from graduate students must be supported by a separate email from their thesis advisor. Anyone interested in participating should contact the organizers as soon as possible by sending an email to


Abstracts: Atlas Conferences, Inc. is providing abstract services for BEST 18. The deadline for submitting an abstract for invited or contributed talk is MARCH 25. Links are available at the BEST 18 web site.




with this information. Subsequently information regarding preparation of papers will be sent to contributing authors by Contemporary Mathematics. The deadline for submitting a paper is JULY 21.

The conference is supported by a grant from the National Science Foundation. Abstract services are provided by Atlas Conferences, Inc. Contemporary Mathematics is published by the American Mathematical Society. Reduced lodging rate is provided by The Hampton Inn & Suites. Support from these entities is gratefully acknowledged.