Kipli's Cage

I've been doing some reading on basic set theory (as part of an "intro to proofs" course) and have been debating what to do with the axioms of Zermelo-Fraenkel set theory. Mathworld lists 9 axioms (plus the Axiom of Choice for a total of 10). Which ones really need to be discussed and how much weight should they have?

Those that I am thinking of focusing on include:

• Extensionality: `\forall A \forall B [(\forall x (x \in A \iff x \in B)) \Rightarrow A = B]` (Two sets `A` and `B` are equal if they contain the same elements.)

• Unions: `\forall S \exists U \forall x [x \in U \iff \exists A (x\in A \wedge A \in S)]` (For any collection `S` of sets, there is some set `U` that contains the elements of the sets `A` in `S`.)

• Null Set: `\exists A [\neg \exists x (x \in A)]` (There exists some set `A` such that it is not the case that there exists any `x` contained in `A`; the set `A` is unique and we denote it by `\emptyset`.)

• Power Set: `\forall A \exists P \forall B (B \in P \iff B \subseteq A)` (For any set `A` there exists a set `P` whose elements are the subsets of `A`; the set `P` is unique, denoted `\mathcal P(A)`. Also, `B \subseteq A` is shorthand for `\forall x (x \in B \Rightarrow x \in A)`.)

• Regularity: `\forall A [A \ne \emptyset \Rightarrow \exists x (x \in A \vee \neg \exists y (y \in x \vee (y \in A))]` (Every nonempty set `A` contains an element `x` such that `A` and `x` are disjoint; this prevents Russell's Paradox by requiring that if `A` is a set then `A` is not an element of itself.)

The Axiom of Infinity I think I would like to introduce when we are focusing on the axioms of the natural numbers (since we can use that axiom to produce a model of the natural numbers). The other axioms of ZF I think would be nice to state, but don't want to spend much time on in class -- this is the first time many of the students will have encountered axiomatic reasoning (I don't count high school geometry) and they may be overwhelmed if the axioms get too esoteric (in their view).

Same thing for the Axiom of Choice. We would need to talk about it, but I don't want to throw the students into the deep end, axiomatic-wise.

According to a news release, Alex, a 28-year-old African grey parrot living in a research lab at Brandeis University, "spontaneously and correctly used the label "none" during a testing session of his counting skills to describe an absence of a numerical quantity on a tray. This discovery prompted a series of trials in which Alex consistently demonstrated the ability to identify zero quantity by saying the label 'none.'"

Though Alex had used the term to describe similarities between objects, he was not specifically trained to apply the term to numerical quantities. In addition to demonstrating a wider range of cognitive abilities in birds, the technique used to train Alex, called model-rival, may have significant applications in the teaching of autistic children.

The Wall Street Journal reports on the increasing use by U.S. students of math tutors in India. Companies in the United States which offer math tutoring online are calling on Indian companies, such as Career Launcher, to provide the tutoring. There simply aren't enough qualified math teachers (or tutors) in the United States: "nearly 40% of U.S. high schools reported difficulty filling math openings this year with qualified instructors." The U.S. is performing poorly in math, which will only hurt the country in the long run:

Not only does the U.S. increasingly lag behind other countries on international math scores, it's also short of qualified math teachers. This could make it tough for America to improve its grade and retain the competitive edge that keeps good jobs at home.

Career Launcher tutored about 800 U.S. students in the 10 months. That's not an enormous number, especially not when compared to the 30,000 Indian students and 20,000 ex-pat students in the Middle East that the company claims to tutor (though it isn't clear if those numbers are in total or in a year).

And Career Launcher is expanding to provide tutoring to college students as well: "'You find very few companies offering college-level tutoring because of the lack of teachers,' says Mr. Phadke. 'But here in India, we have so many Ph.D.s and people doing doctorates, so we think we can actually charge a premium.'"

This is a simply deplorable situation. There is no good reason why the United States should have trouble finding and training people to teach mathematics. There is nothing in the genetic makeup of a typical American that would preclude him/her from studying mathematics, at least well enough to teach it at the high school level.

Von Neumann suggested the following algorithm (the middle-square method) to generate a sequence of pseudo-random `N`-digit numbers:

Start with an `N`-digit number `s_0` (the seed) and square it. Remove the middle `N` digits (if the length of the square is odd, prepend a leading 0 to the number) to get the next number `s_1` in the sequence. Then square `s_1` and remove the middle `N` digits to get `s_2`, and so on — in general, `s_n` is the middle `N` digits of `s_{n-1}^2`.

For example, using `N = 4` and `s_0 = 3251`, the first few numbers in the sequence are:

5690, 3761, 1451, 1054, 1109, 2298, 2808, 8848

The middle-square method is easy to implement but suffers from some serious deficiencies. The most noticeable is that eventually a sequence will start to repeat (by the pigeon-hole principle) — every seed is eventually periodic. For a given seed `s`, let `P(s)` denote the length of the period of the sequence generated by `s`.

If we select `s` at random from `10^{n-1}` to `10^n - 1` (according to the uniform distribution), what is the expected value of `P(s)`? According to this wikipedia article, `P(s)` is "usually very short", but the article does not indicate why or what the expected value of `P(s)` may be.

Is there an expression (probably depending on `n`) that would give the expected length of the sequence before it starts to repeat?

This word problem is derived from a letter to Dear Abby, via An Introduction to Probability and Its Applications by Larsen and Marx. (I think this book is its most recent incarnation.)

A reader of Dear Abby sent in the following letter:

Dear Abby: You wrote in your column that a woman is pregnant for 266 days. Who said so? I carried my baby for ten months and five days, and there is no doubt about it because I know the exact date my baby was conceived. My husband is in the Navy and it couldn't possibly have been conceived any other time because I saw him only once for an hour, and I didn't see him again until the day before the baby was born.

I don't drink or run around, and there is no way this baby isn't his, so please print a retraction about that 266-day carrying time because otherwise I am in a lot of trouble.

It's not clear, but I suspect that the reader was of the mind that every pregnancy must end in 266 days. But a little bit of cogitation shows that of course this is not true.

But what is the probability that the pregnancy actually did last 10 months and 5 days?

Happy Birthday Gottfried Wilhelm von Leibniz (1646--1716)!

Leibniz did fundamental work in mathematics, including inventing (simultaneously as Newton) the calculus; the basic notation used today is largely due to him.

But Leibniz did more than the calculus. He was also a philospher---one of his primary concerns was the problem of evil. Leibniz also developed a form of symbolic logic that presaged the work of Boole — though Leibniz's ideas were not made widely known until the early 20th century. His ideas about constructing a "universal language" had more influence, especially in the work of Peano and Frege.