## 515 – Homework 2

February 14, 2012

This set is due Feb. 29 at the beginning of lecture. Let me know if more time is needed or anything like that. Problem 4 was incorrect as stated; I have fixed it now. Thanks to Tara Sheehan for bringing the problem to my attention.

## 187 – List of all presentations

January 10, 2012

For ease, I re-list here all the presentations we had throughout the term. I also include some of them. If you gave a presentation and would like your notes to be included, please email them to me and I’ll add them here.

• Jeremy Elison, Wednesday, October 12: Georg Cantor and infinity.
• Kevin Byrne, Wednesday, October 26: Alan Turing and Turing machines.
• Keith Ward, Monday, November 7: Grigori Perelman and the Poincaré conjecture.
• David Miller, Wednesday, November 16: Augustin Cauchy and Cauchy’s dispersion equation.
• Taylor Mitchell, Friday, November 18: Lajos Pósa and Hamiltonian circuits.
• Sheryl Tremble, Monday, November 28: Pythagoras and the Pythagorean theorem.
• Blake Dietz, Wednesday, November 30: $\mbox{\em Paul Erd\H os}$ and the Happy End problem.

Here are Jeremy’s notes on his presentation. Here is the Wikipedia page on Cantor, and a link to Cantor’s Attic, a wiki-style page discussing the different (set theoretic) notions of infinity.

Here are a link to the official page for the Alan Turing year, and the Wikipedia page on Turing. If you have heard of Conway’s Game of Life, you may enjoy the following video showing how to simulate a Turing machine within the Game of Life; the Droste effect it refers to is best explained in by H. Lenstra in a talk given at Princeton on April 3, 2007, and available here.

Here is a link to the Wikipedia page on Perelman, and the Clay Institute’s description of the Poincaré conjecture. In 2006, The New Yorker published an interesting article on the unfortunate “controversy” on the priority of Perelman’s proof.

Here are David’s slides on his presentation, and the Wikipedia page on Cauchy.

Here is a link to Ross Honsberger’s article on Pósa (including the result on Hamiltonian circuits that Taylor showed during her presentation).

Here are Sheryl’s slides on Pythagoras and his theorem. In case the gif file does not play, here is a separate copy:

The Pythagorean theorem has many proofs, even one discovered by President Garfield!

Finally, here is the Wikipedia page on $\mbox{Erd\H os}$. Oakland University has a nice page on him, including information on the $\mbox{Erd\H os}$ number; see also the page maintained by Peter Komjáth, and an online depository of most of $\mbox{Erd\H os's}$ papers.

## 502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in ${{\sf ZF}:}$

1. The axiom of choice: Every set can be well-ordered.
2. Every collection of nonempty set admits a choice function, i.e., if ${x\ne\emptyset}$ for all ${x\in I,}$ then there is ${f:I\rightarrow\bigcup I}$ such that ${f(x)\in x}$ for all ${x\in I.}$
3. Zorn’s lemma: If ${(P,\le)}$ is a partially ordered set with the property that every chain has an upper bound, then ${P}$ has maximal elements.
4. Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set ${S}$ such that ${|S\cap x|=1}$ for all ${x}$ in the family.
5. Any set is a well-ordered union of finite sets of bounded size, i.e., for every set ${x}$ there is a natural ${m,}$ an ordinal ${\alpha,}$ and a function ${f:\alpha\rightarrow{\mathcal P}(x)}$ such that ${|f(\beta)|\le m}$ for all ${\beta<\alpha,}$ and ${\bigcup_{\beta<\alpha}f(\beta)=x.}$
6. Tychonoff’s theorem: The topological product of compact spaces is compact.
7. Every vector space (over any field) admits a basis.

## 502 – Cantor-Bendixson derivatives

November 8, 2009

Given a topological space $X$ and a set $B\subseteq X,$ let $B'$ be the set of accumulation points of $B,$ i.e., those points $p$ of $X$ such that any open neighborhood of $p$ meets $B$ in an infinite set.

Suppose that $B$ is closed. Then $B'\subseteq B.$ Define $B^\alpha$ for $B$ closed compact by recursion: $B^0=B,$ $B^{\alpha+1}=(B^\alpha)',$ and $B^\lambda=\bigcap_{\alpha<\lambda}B^\alpha$ for $\lambda$ limit. Note that this is a decreasing sequence, so that if we set $B^\infty=\bigcap_{\alpha\in{\sf ORD}}B^\alpha,$ there must be an $\alpha$ such that $B^\infty=B^\beta$ for all $\beta\ge\alpha.$

[The sets $B^\alpha$ are the Cantor-Bendixson derivatives of $B.$ In general, a derivative operation is a way of associating to sets $B$ some kind of “boundary.”]