Lessons from teaching gifted elementary school students (Part 5d)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

A bright young student of mine noticed that multiplication is repeated addition:

$x \cdot y = x + x + x \dots + x$ ,

Also, exponentiation is repeated addition:

$x \uparrow y = x^y = x \cdot x \cdot x \dots \cdot x$ ,

The notation $x \uparrow y$ is unorthodox, but it leads to the natural extensions

$x \upuparrows y = x \uparrow x \uparrow x \dots \uparrow x$ ,

$x \uparrow^3 y = x \upuparrows x \upuparrows x \dots \upuparrows x$ ,

and so. I’ll refer the interested reader to Wikipedia and Mathworld (and references therein) for more information about Knuth’s up-arrow notation. As we saw in yesterday’s post, these numbers get very, very large… and very, very quickly.

When I was in elementary school myself, I remember reading in the 1980 Guiness Book of World Records about Graham’s number, which was reported to be the largest number ever used in a serious mathematical proof. Obviously, it’s not the largest number — there is no such thing — but the largest number that actually had some known usefulness. And this number is only expressible using Knuth’s up-arrow notation. (Again, see Wikipedia and Mathworld for details.)

From Mathworld, here’s a description of the problem that Graham’s number solves:

Stated colloquially, [consider] every possible committee from some number of people $n$ and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find $N$ , the smallest $n$ that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees.

In 1971, Graham and Fairchild proved that there is a solution $N$ , and that $N \le F(F(F(F(F(F(F(12)))))))$ , where

$F(n) = 2 \uparrow^n 3$ .

For context, $2 \uparrow^4 3$ is absolutely enormous. In yesterday’s post, I showed that $2 \uparrow^3 = 65,536$ . Therefore,

$2 \uparrow^4 3 = 2 \uparrow^3 (2 \uparrow^3 2)$

$= 2 \uparrow^3 65,536$

$= 2 \upuparrows 2 \upuparrows 2 \upuparrows \dots \upuparrows 2$ ,

repeated 65,536 times.

That’s just $2 \uparrow^4 3$ . Now try to imagine $F(12) = 2 \uparrow^{12} 3$ . That’s a lot of arrows.

Now try to imagine $F(F(12)) = 2 \uparrow^{F(12)} 3$ , which is even more arrows.

Now try to imagine $F(F(F(F(F(F(F(12)))))))$ . I bet you can’t. (I sure can’t.)

Graham and Fairchild also helpfully showed that $N \ge 6$ . So somewhere between 6 and Graham’s number lies the true value of $N$ .

A postscript: according to Wikipedia, things have improved somewhat since 1971. The best currently known bounds for $N$ are

$13 \le N \le 2 \uparrow^3 6$ .

Lessons from teaching gifted elementary school students (Part 5c)

A bright young student of mine noticed that multiplication is repeated addition:

$x \cdot y = x + x + x \dots + x$ ,

Also, exponentiation is repeated addition:

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

So, my student asked, why can’t we define an operation that’s repeated exponentiation? Like all good explorers, my student claimed naming rights for this new operation and called it $x \hbox{~playa~} y$ :

$x \hbox{~playa~} y = x^{x^{x^{\dots}}}$

For example,

$4 \hbox{~playa~} 3 = 4^{4^4} = 4^{256} \approx 1.34 \times 10^{154}$

Even with small numbers for $x$ and $y$ , $x \hbox{~playa~} y$ gets very large.

Unfortunately for my student, someone came up with this notion already, and it’s called Knuth’s up-arrow notation. I’ll give some description here and refer the interested reader to Wikipedia and Mathworld (and references therein) for more information. Surprisingly, this notion has only become commonplace since 1976 — within my own lifetime.

Let’s define $x \uparrow y$ to be ordinary exponentiation:

$x \uparrow y = x \cdot x \cdot x \dots \cdot x$ .

Let’s now define $x \upuparrows y$ to be the up-arrow operation repeated $y$ times:

$x \upuparrows y = x \uparrow x \uparrow x \dots \uparrow x$ .

In this expression, the order of operations is taken to be right to left.

Numbers constructed by $\upuparrows$ get very, very big and very, very quickly. For example:

$2 \upuparrows 2 = 2 \uparrow 2 = 2^2 = 4$ .

Next,

$2 \upuparrows 3 = 2 \uparrow (2 \uparrow 2)$

$= 2 \uparrow (2^2)$

$= 2 \uparrow 4$

$= 2^4$

$= 16$

Next,

$2 \upuparrows 4 = 2 \uparrow (2 \uparrow (2 \uparrow 2))$

$= 2 \uparrow 16$

$= 2^{16}$

$= 65,536$

Next,

$2 \upuparrows 5 = 2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow 2)))$

$= 2 \uparrow 65,536$

$= 2^{65,536}$

$\approx 2.0035 \times 10^{19,728}$

Next,

$2 \upuparrows 6 = 2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow 2))))$

$= 2 \uparrow 2^{65,536}$

$= 2^{2^{65,536}}$

$\approx 10^{6.031 \times 10^{19,727}}$

We see that $2 \upuparrows 6$ is already far larger than a googolplex (or $10^{10^{100}}$ ), which is often (and erroneously) held as the gold standard for very large numbers.

I’ll refer the interested reader to a previous post in this series for a description of how logarithms can be used to write something like $2^{65,536}$ in ordinary scientific notation.

Knuth’s up-arrow notation can be further generalized:

$x \uparrow^3 y = x \upuparrows x \upuparrows x \dots \upuparrows x$ ,

repeated $y$ times. The numbers $x \uparrow^4 y$ , $x \uparrow^5 y$ , etc., are defined similarly.

These numbers truly become large quickly. For example,

$2 \uparrow^3 2 = 2 \upuparrows 2 = 4$ , from above.

Next,

$2 \uparrow^3 3 = 2 \upuparrows (2 \upuparrows 2)$

$= 2 \upuparrows 4$

$= 65,536$ , from above

Next,

$2 \uparrow^3 4 = 2 \upuparrows (2 \upuparrows (2 \upuparrows 2))$

$= 2 \upuparrows 65,536$

$= 2 \uparrow 2 \uparrow 2 \uparrow \dots \uparrow 2$ ,

where there are 65,536 repeated 2’s on this last line. It’d be nearly impossible to write this number in scientific notation, and we’ve only reached $2 \uparrow^3 4$ .

Lessons from teaching gifted elementary school students (Part 5b)

Here’s a question I once received (though I probably changed the exact wording somewhat):

Exponentiation is to multiplication as multiplication is to addition. In other words,

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

$x \cdot y = x + x + x \dots + x$ ,

where the operation is repeated $y$ times.

So, multiplication is to addition as addition is to what?

My kneejerk answer was that there was no answer… while exponents can be thought of as repeated multiplication and multiplication can be thought of as repeated addition, addition can’t be thought of as some other thing being repeated. But it took me a few minutes before I could develop of proof that could be understood by my bright young questioner.

Suppose $y = 1$ . Then the expressions above become

$x^1 = x$

and

$x \cdot 1 = x$

However, we know full well that

$x + 1 \ne x$ .

Therefore, there can’t be an operation analogous to addition as addition is to multiplication or as multiplication is to exponentiation.

Lessons from teaching gifted elementary school students (Part 5a)

Here’s a question I once received (though I probably changed the exact wording somewhat):

Exponentiation is to multiplication as multiplication is to addition. In other words,

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

$x \cdot y = x + x + x \dots + x$ ,

where the operation is repeated $y$ times.

So, multiplication is to addition as addition is to what?

Which then naturally led to my student’s next question, which I was dreading:

Can you prove that?

This led to another kneejerk reaction, but I kept this one quiet: “Aw, nuts.”

I suggested that $x + y$ can be thought of as starting with $x$ and then adding $1$ repeatedly $y$ times, but my bright student wouldn’t hear of this. After all, in the repeated renderings of $x^y$ and $x \cdot y$ , there’s no notion of starting with a number and then doing something with a different number $y$ times.

So I had to put my thinking cap on, and I’m embarrassed to say that it took me a good five minutes before I came up with a logically correct answer that, in my opinion, could be understand by the bright young student who asked the question.

I’ll reveal that answer in tomorrow’s post. In the meantime, I’ll leave a thought bubble if you’d like to think about it on your own.

15-year-old catches math error at the Boston Museum of Science

See the full article here: http://www.boston.com/news/local/massachusetts/2015/07/06/year-old-catches-math-error-the-museum-science/awhREamdn1KRg7nz2gGyPO/story.html?p1=Must_Reads

Is 2i less than 3i? (Part 4: Two other attempted inequalities)

In yesterday’s post, I demonstrated that there is no subset $\mathbb{C}^+ \subset \mathbb{C}$ of the complex numbers which satisfies the following four axioms:

If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1+z_2 \in \mathbb{C}^+$
If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1 z_2 \in \mathbb{C}^+$ .
For every $z \ne 0$ , either $z \in \mathbb{C}^+$ or $-z \in \mathbb{C}^+$ , but not both.
$0 \notin \mathbb{C}^+$

However, it’s instructive (and fun) to try to construct such a set. Yesterday I showed that the following subset satisfies three of the four axioms:

$\mathbb{C}^+ = \{x + iy : x > 0 \qquad \hbox{or} \qquad x = 0, y > 0\}$

Apostol’s calculus suggests two other subsets to try:

$\mathbb{C}^+ = \{x + iy : x^2 + y^2 > 0 \}$

and

$\mathbb{C}^+ = \{x + iy : x > y\}$

Neither of these sets work either, but I won’t spoil the fun for you by giving you the proofs. I leave a thought bubble if you’d like to try to figure out which of the four axioms are satisfied by these two notions of “positive” complex numbers.

Is 2i less than 3i? (Part 3: An inequality that almost works)

In yesterday’s post, I demonstrated that there is no subset $\mathbb{C}^+ \subset \mathbb{C}$ of the complex numbers which satisfies the following four axioms:

If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1+z_2 \in \mathbb{C}^+$
If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1 z_2 \in \mathbb{C}^+$ .
For every $z \ne 0$ , either $z \in \mathbb{C}^+$ or $-z \in \mathbb{C}^+$ , but not both.
$0 \notin \mathbb{C}^+$

However, it’s instructive (and fun) to try to construct such a set. One way of attempting this is defining

$\mathbb{C}^+ = \{x + iy : x > 0 \qquad \hbox{or} \qquad x = 0, y > 0\}$

This set $\mathbb{C}^+$ leads to the lexicographic ordering of the complex numbers: if $z_1 = a_1 + i b_1$ and $z_2 = a_2 + i b_2$ , where $a_1, a_2, b_1, b_2 \in \mathbb{R}$ , we say that $z_1 \prec z_2$ if

$a_1 < a_2 \qquad \hbox{or} \qquad a_1 = a_2, b_1 < b_2$

I used the symbol $z_1 \prec z_2$ because, as we’ll see, $\prec$ satisfies some but not all of the usual properties of an inequality. This ordering is sometimes called the “dictionary” order because the numbers are ordered like the words in a dictionary… the real parts are compared first, and then (if that’s a tie) the imaginary parts are compared. See Wikipedia and Mathworld for more information.

In any case, defining $\mathbb{C}^+$ in this way satisfies three of the four order axioms.

Suppose . It’s straightforward to show that . Let and , where . Then , and so .
- Case 1: If $a_1 + a_2 > 0$ , then clearly $z_1 + z_2 \in \mathbb{C}^+$ .
- Case 2: If $a_1 + a_2 = 0$ , that’s only possible if $a_1 = 0$ and $a_2 = 0$ . But since $z_1, z_2 \in \mathbb{C}^+$ , that means that $b_1 > 0$ and $b_2 > 0$ . Therefore, $b_1 + b_2 > 0$ . Since $a_1 + a_2 = 0$ , we again conclude that $z_1 + z_2 \in \mathbb{C}^+$ .
Suppose , where . Then or . We now show that, no matter what, or , but not both.
- Case 1: If $a > 0$ , then $-a < 0$ , and so $z \in \mathbb{C}^+$ but $-z \notin \mathbb{C}^+$ .
- Case 2: If $a < 0$ , then $-a > 0$ , and so $-z \in \mathbb{C}^+$ but $z \notin \mathbb{C}^+$ .
- Case 3: If , then since . Also, if , then , so that and .
  - Subcase 3A: If $b > 0$ , then $-b < 0$ , and so $z \in \mathbb{C}^+$ but $-z \notin \mathbb{C}^+$ .
  - Subcase 3B: If $b < 0$ , then $-b > 0$ , and so $-z \in \mathbb{C}^+$ but $z \notin \mathbb{C}^+$ .
By definition, $0 = 0 + 0i \notin \mathbb{C}^+$ .

However, the fourth property fails. By definition, $i = 0 + 1i \in \mathbb{C}^+$ . However, $i \cdot i = -1 + 0i \notin \mathbb{C}^+$ .

Because this definition of $\mathbb{C}^+$ satisfies three of the four order axioms, the relation $\prec$ satisfies some but not all of the theorems stated in the first post of this series. For example, if $z_1 \prec z_2$ and $z_2 \prec z_3$ , then $z_1 \prec z_3$ . Also, if $z_1 \prec z_2$ and $w_1 \prec w_2$ , then $z_1 + w_1 \prec z_2 + w_2$ .

I’ll leave it to the interested reader to determine which of the theorems are true, and which are false (and have counterexamples).

Is 2i less than 3i? (Part 2: Proof by contradiction)

Is $2i$ less than $3i$ ?

That’s a very natural question for a student to ask when first learning about complex numbers. The short answer is, “No… there isn’t a way to define inequality for complex numbers that satisfies all the properties of real numbers.”

I demonstrated this in a roundabout way in yesterday’s post. Today, let’s tackle the issue using a proof by contradiction. (I almost said, “Let’s tackle the issue more directly,” but avoided that phrase because a proof by contradiction is sometimes called an indirect proof, which would lead to the awkward sentence “Let’s tackle the issue more directly with an indirect proof.”)

Suppose that there’s a subset $\mathbb{C}^+ \subset \mathbb{C}$ of the complex numbers which satisfies the following four axioms:

If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1+z_2 \in \mathbb{C}^+$
If $z_1, z_2 \in \mathbb{C}^+$ , then $z_1 z_2 \in \mathbb{C}^+$ .
For every $z \ne 0$ , either $z \in \mathbb{C}^+$ or $-z \in \mathbb{C}^+$ , but not both.
$0 \notin \mathbb{C}^+$

As discussed yesterday, the ordinary properties of inequalities derive from these four order axioms. Assuming these four order axioms are true for the complex numbers, let’s investigate whether $i$ is “positive” or not. According to the third axiom, either $i \in \mathbb{C}^+$ or $-i \in \mathbb{C}^+$ , but not both.

Case 1. $i \in \mathbb{C}^+$ . Then by the second axiom, $i \cdot i \in \mathbb{C}^+$ , or $-1 \in \mathbb{C}^+$ . Applying the second axiom again, since $i \in \mathbb{C}^+$ and $-1 \in \mathbb{C}^+$ , we have $i \cdot (-1) \in \mathbb{C}^+$ , or $-i \in \mathbb{C}^+$ . But that’s impossible because we assumed that $i \in \mathbb{C}^+$ .

Case 2. $-i \in \mathbb{C}^+$ . Then by the second axiom, $(-i) \cdot (-i) \in \mathbb{C}^+$ , or $-1 \in \mathbb{C}^+$ . Applying the second axiom again, since $-i \in \mathbb{C}^+$ and $-1 \in \mathbb{C}^+$ , we have $(-i) \cdot (-1) \in \mathbb{C}^+$ , or $i \in \mathbb{C}^+$ . But that’s impossible because we assumed that $-i \in \mathbb{C}^+$ .

Either way, we obtain a contradiction. Therefore, there is no subset $\mathbb{C}^+$ of the complex numbers that serves as the “positive” complex numbers, and so there’s no way to define inequalities for complex numbers that satisfies all of the usual properties of inequalities.

Is 2i less than 3i? (Part 1: Order Axioms)

Is $2i$ less than $3i$ ?

However, for this answer to make sense, we need to talk about how inequalities are defined in the first place.

Following Apostol’s calculus, there are four axioms from which the ordinary notions of inequality follow. We shall assume that there exists a certain subset $\mathbb{R}^+ \subset \mathbb{R}$ , called the set of positive numbers, which satisfies the following four order axioms:

If $x, y \in \mathbb{R}^+$ , then $x+y \in \mathbb{R}^+$
If $x, y \in \mathbb{R}^+$ , then $xy \in \mathbb{R}^+$ .
For every real $x \ne 0$ , either $x \in \mathbb{R}^+$ or $-x \in \mathbb{R}^+$ , but not both.
$0 \notin \mathbb{R}^+$

We then define the symbols $<$ , $\le$ , $>$ , and $\ge$ in the obvious way:

$x < y$ means that $y-x$ is positive.
$x > y$ means that $y < x$.
$x \le y$ means that either $x < y$ or $x=y$ .
$x \ge y$ means that $y \le x$

From only these four axioms, many familiar theorems about inequalities can be proven. For what it’s worth, when I was a student in Algebra I, I had to prove nearly all of these theorems.

If $a, b \in \mathbb{R}$ , then exactly one of the following three relations is true: $a < b$ , $a > b$ , $a = b$ .
If $a < b$ and $b < c$ , then $a < c$ .
If $a < b$ , then $a + c < b + c$ .
If $a < b$ and $c > 0$ , then $ac < bc$ .
If $a \ne 0$ , then $a^2 > 0$ .
$1 > 0$ .

We interrupt this list with a public-service announcement: Yes, there’s a proof that $1$ is greater than $0$ . When I tell this to students, I can usually see their heads start to spin, as they think, “Of course we know that!” Then I ask them what the definitions of $1$ and $0$ are. Usually, they have no idea. Then I’ll remind them that $0$ is defined to be the additive identity (so that $x + 0 = x$ and $0 + x = x$ for all real numbers $x$ ), while $1$ is defined to be the multiplicative identity (so that $x \cdot 1 = x$ and $1 \cdot x = x$ for all real numbers $x$ ). Based on those definitions alone, I then ask my students, is it obvious that the multiplicative identity has to be larger than the additive identity? The answer is no, which is why the above order axioms are needed.

Here are some more familiar theorems about inequalities that derive from the four order axioms.

If $a < b$ and $c < 0$ , then $ac > bc$ .
If $a < b$ , then $-a > -b$ .
If $a < 0$ , then $-a > 0$ .
If $ab > 0$ , then $a$ and $b$ are either both positive or both negative.
If $a < c$ and $b < d$ , then $a + b < c + d$ .
If $a < 0$ and $b < 0$ , then $a + b < 0$ .
If $a > 0$ , then $1/a > 0$ .
If $a < 0$ , then $1/a < 0$ .
If $0 < a < b$ , then $0 < 1/b < 1/a$ .
If $a \le b$ and $b \le c$ , then $a \le c$ .
If $a \le b \le c$ and $a = c$ , then $b = c$ .

These last two theorems are less familiar. They basically state that (1) there is no “biggest” real number and (2) there is no positive number that’s immediately to the right of 0.

There is no real number $a$ so that $x \le a$ for all real numbers $x$ .
If $0 \le x < h$ for every positive real number $h$ , then $x =0$ .

Here’s another important theorem that ultimately derives from the four order axioms, proving that a number system including $\sqrt{-1}$ is incompatible with the four order axioms.

There is no real number $x$ so that $x^2 + 1 = 0$ .

The proof of this theorem is simple, given the theorems above. If $x = 0$ , then $x^2 + 1 = 1$ , which is greater than 0. If $x \ne 0$ , then $x^2 > 0$ , and so $x^2 + 1 > 0 + 1 > 1$ . Since $1 > 0$ , it follows by transitivity that $x^2 > 0$ . Either way, $x^2 + 1 > 0$ , and so $x^2 + 1 \ne 0$ .