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}$

305 -2. Solving cubic and quartic polynomials.

January 28, 2009

1. We all know how to solve a linear equation such as $ax+b=0$, namely $x=-b/a$ (assuming $a\ne0$; if $a=0$ then either $b=0$ and any $x$ is a solution, or else there are no solutions). This was known to Babylonian and Persian mathematicians (with the usual caveats about the signs of $a,b$, since the notion of negative numbers had not been introduced yet.)

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

• Some equations have no solutions.

If we are interested in solving polynomial equations in general, at some point we will need an argument justifying that we can. For now, let us proceed formally, assuming that we will always find solutions.

Just as with linear equations, we all know as well how to solve quadratics, such as $ax^2+bx+c=0$. Namely, we can factor $a$ out (if  $a=0$ we are in the linear case, so let’s assume that this is not the case) and then complete the square. We get $ax^2+bx+c=$

$\displaystyle a\left(x^2+\frac ba x+\frac ca\right)= a\left[\left(x+\frac b{2a}\right)^2+\left(\frac ca -\frac {b^2}{4a^2}\right)\right],$

so $ax^2+bx+c=0$ iff $(x+b/2a)^2=(b^2/4a^2)-(c/a)$, or

$\displaystyle x=\frac{-b\pm\sqrt{b^2-4ac}}{2a},$

Another small subtlety appears here, namely, there is some inherent ambiguity in the meaning of the expression $\sqrt r$. We usually resolve this by “choosing a sign” of the square root. As long as we are looking at quadratic polynomials with integer (or rational, or real, or even complex) coefficients, there is a standard way of making this choice. In more general situations (in arbitrary fields) there is no such standard procedure.

Besides this subtlety, a more serious one needs to be faced. Nowadays, we are used to working with complex numbers, so the view of a square root of a negative number does not cause confusion, but this was a serious issue for many centuries, and when complex numbers were first used, many were skeptical of whether they actually made sense. It wasn’t until Gauss’ presentation of complex numbers as pairs of reals that their use became mainstream. This is related to the question of whether one can always solve an equation. The answer was “no” until complex numbers were introduced and accepted, and then it became “yes.”

2. Cubic equations. The history of the solutions to cubic and quartic equations is full of melodrama, the historical note at the end of Chapter 2 of the book is well worth reading, see also this.

580 -Some choiceless results (3)

January 27, 2009

[Updated December 3. The previous proof that there is a canonical bijection $\alpha\sim\alpha\times\alpha$ for all infinite ordinals $\alpha$ was seriously flawed. Thanks to Lorenzo Traldi for pointing out the problem.]

5. Specker’s lemma.

This result comes from Ernst Specker, Verallgemeinerte Kontinuumshypothese und Auswahlaxiom, Archiv der Mathematik 5 (1954), 332-337. I follow Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413-426 in the presentation of this and the following result. The Kanamori-Pincus paper, to which we will return next lecture, has several interesting problems, results, and historical remarks, and I recommend it. It can be found here.

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

I won’t be here this Friday. Professor Marion Scheepers will cover the lecture for me.

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|m$ or else $(p,m)=1$. $\Box$

Proposition. Let $p$ be prime, and let $m,n$ be integers. If $p|mn$ then either $p|m$ or $p|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 it is the case that $P(m)$ holds, then also $P(k)$ holds$).$

Then $\forall k\ge N\,(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$.

The book discusses additional examples and has many more in the exercises. Other examples will be discussed in the first homework set, to be posted later today.

580 -Some choiceless results (2)

January 25, 2009

There are a few additional remarks on the Schröder-Bernstein theorem worth mentioning. I will expand on some of them later, in the context of descriptive set theory.

The dual Schröder-Bernstein theorem (dual S-B) is the statement “Whenever $A,B$ are sets and there are surjections from $A$ onto $B$ and from $B$ onto $A,$ then there is a bijection between $A$ and $B$.”

* This follows from the axiom of choice. In fact, ${\sf AC}$ is equivalent to: Any surjective function admits a right inverse. So the dual S-B follows from choice and the S-B theorem.

* The proofs of S-B actually show that if one has injections $f:A\to B$ and $g:B\to A$, then one has a bijection $h:A\to B$ contained in $f\cup g^{-1}$. So the argument above gives the same strengthened version of the dual S-B. Actually, over ${\sf ZF}$, this strengthened version implies choice. This is in Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375-381.

* If $j : {}x \to y$ is onto, then there is $k:{\mathcal P}(y)\to {\mathcal P}(x)$ 1-1, so if there are surjections in both directions between $A$ and $B$, then ${\mathcal P}(A)$ and ${\mathcal P}(B)$ have the same size. Of course, this is possible even if $A$ and $B$ do not.

Open question. (${\sf ZF}$) Does the dual Schröder-Bernstein theorem imply the axiom of choice?

* The dual S-B is not a theorem of ${\sf ZF}$.

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 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|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 | m,n$ and $d\in S$.
3. $S=\{ kd: k\in{\mathbb Z}^+\}$.
4. $d$ is the least member of $S$.