Chapter 25

The following is the Richard paradox (named after its originator, Jules Richard (1862-1956)): Arrange all twoletter combinations in alphabetical order, then all threeletter combinations and so on, and then eliminate all combinations that do not define a real number. (For example, "six" defines a real number, while "sx" does not.) Then the set of real numbers definable in a finite number of letters forms a denumerable, well-ordered set \(E=\left\\{p_{1}, p_{2}, \ldots\right\\}\). Now define the real number \(s=a_{1} a_{2} \ldots\) between 0 and 1 by requiring \(a_{n}\) to be one more than the \(n\)th decimal of \(p_{n}\) if this decimal is not 8 or 9 and equal to 1 otherwise. Although \(s\) is defined by a finite number of letters, it is not in \(E\), a contradiction. How can one resolve this paradox? How is this paradox related to the barber paradox or to Zermelo's original paradox?

Show that the trichotomy law follows from Zermelo's wellordering theorem.

Show that Zermelo's axiom of separation resolves Russell's barber paradox as well as the Richard paradox (Exercise 1) in the sense that certain "sets" are now excluded from discussion.

Formulate and prove the Heine-Borel theorem in the plane.

Show that the set of rational numbers in \([0,1]\) is not connected.

Assume that a set \(E\) is compact according to Fréchet's definition in terms of nested sets. Show that every infinite subset \(E_{1}\) of \(E\) has at least one limit element in \(E\).

Show by use of examples that the nested set property on the real line depends on the subsets being both closed and bounded.

Show that a real function sequentially continuous on a closed and compact set \(E\) (in Fréchet's definition) is bounded there and attains its upper bound at least once.

Show that if \(E\) is closed and compact according to Fréchet's definition, and if \(\left\\{E_{n}\right\\}\) is a nested sequence of closed subsets \(E\), then the intersection \(\cap_{n} E_{n}\) is not empty.

Prove that the space of real functions continuous on \([a, b]\) under the maximum norm metric is "normal" in the sense of Fréchet.

Show that the space of all infinite sequences of real numbers \(\left\\{x=\left\\{x_{1}, x_{2}, \ldots\right\\}\right\\}\) with the metric $$ (x, y)=\sum_{p=1}^{\infty} \frac{1}{p !} \frac{\left|x_{p}-y_{p}\right|}{1+\left|x_{p}-y_{p}\right|} $$ is normal.

Show that if \(E\) is a topological space and \(A\) a closed subset, that is, one containing all its accumulation points, then \(E-A\) is a domain (open set) in the notion of Hausdorff. Conversely, if the subset \(B\) of \(E\) is an open set, show that \(E-B\) is closed, using Hausdorff's definition.

Show that Hausdorff's two definitions of continuity at a point are equivalent.

Use Hausdorff's neighborhood definition of continuity to show that a continuous function preserves connectedness and compactness.

How many linearly independent closed one-dimensional subvarieties are there on the sphere? On the torus?

Show that the set \(\\{0,1,-1\\}\) with ordinary addition and multiplication satisfies each of Dickson's axioms except the first.

Show that the quotient \(3.12 \div 4.21\) is equal in Hensel's arithmetic relative to \(p=5\) to the periodic "decimal" \(2.42204220 \ldots\) by actually performing the long division.

Show for Hensel's \(p\)-adic numbers that the multiplicative inverse of a unit (a number whose smallest power of \(p\) is the zero power) is again a unit.

Let \(x\) be a \(p\)-adic number. Define the \(r\)-neighborhood of \(x, U_{r}(x)\), where \(r\) is an integer, to be \(U_{r}(x)=\\{y \mid y \equiv\) \(\left.x\left(\bmod p^{r}\right)\right\\}\). Show that this choice of neighborhoods of \(x\) makes the field \(\mathbf{Q}_{p}\) into a topological space in the sense of Hausdorff.

Any number \(x\) in \(\mathbf{Q}_{p}\) may be written uniquely as \(x=p^{\alpha} e\) where \(e\) is a unit. The integer \(\alpha\) is called the order of \(x\) relative to \(p\), written \(v_{p}(x)\). For any \(x, y\) in \(\mathbf{Q}_{p}\), define \((x, y)\) to be \((1 / p)^{v_{p}(x-y)}\). Show that \((x, y)\) defines a metric on \(\mathbf{Q}_{p}\) in the sense of Fréchet.

Show that each of the following multiplication tables of two basis elements \(i, j\) determines an associative algebra of degree 2 over the real numbers. Are there any other ones? $$ \begin{aligned} &\begin{array}{c|cc} & i & j \\ \hline i & i & j \\ j & j & 0 \end{array}\\\ &\begin{array}{c|cc} & i & j \\ \hline i & i & j \\ j & 0 & 0 \end{array}\\\ &\begin{array}{l|ll} & i & j \\ \hline i & j & 0 \\ j & 0 & 0 \end{array} \end{aligned} $$

Find a nilpotent element in the algebra of \(2 \times 2\) matrices over the rational numbers

Find an idempotent element (which is not a diagonal matrix) in the algebra of \(2 \times 2\) matrices over the rational numbers.

In the Neyman-Pearson version of the test for the lady tasting tea, show that \(P(X=8 \mid p=1 / 2)=\left(\begin{array}{c}10 \\ 8\end{array}\right)(1 / 2)^{10}\).

In the Neyman-Pearson version of the test for the lady tasting tea, verify that the power \(P\left(R \mid H_{2}\right)\) is given as a function of the probability \(p\) as \(\left(\begin{array}{c}10 \\ 8\end{array}\right) p^{8}(1-p)^{2}+\left(\begin{array}{c}10 \\ 9\end{array}\right) p^{9}(1-p)+\) \(p^{10}\).

Show that for a polynomial of degree \(n\), the \(n\) th-order differences are always constant.

Construct a difference table that would enable Babbage's Difference Engine to calculate the pyramidal numbers, the numbers that are the sums of the triangular numbers and can be considered as representing, say, the number of cannonballs contained in triangular pyramids of a given height.

Consider a Turing machine with two states \(q_{1}, q_{2}\) capable of printing two symbols 0 and 1 . Suppose it is defined by the following instructions: a. If the machine is in state \(q_{1}\) and reads a 1 , it prints 1 , moves one square to the right, and remains in state \(q_{1}\). b. If the machine is in state \(q_{1}\) and reads a blank, it prints 1, moves one square to the right, and changes to state \(q_{2}\). (Note that there is no instruction for the machine when it is in state \(q_{2}\).) Suppose the machine begins in state \(q_{1}\) with a tape whose first square is blank, whose next two squares to the right have 1 's, and all of the rest of whose squares to the right are blank, and suppose further that the leftmost 1 is the initial square to be read. Show that the final configuration of the tape will be the same as the initial one except that it will have three 1 's instead of two. In general, interpreting a tape with \(n\) l's as representing the number \(n+1\), show that this Turing machine will calculate the function \(f(n)=n+1\) for \(n\) any nonnegative integer.

Determine a Turing machine that computes the function \(f(n)=2 n .\)

Use the distributive law of addition over multiplication, \(a+(b c)=(a+b)(a+c)\), and the theorem of Exercise 44 to establish the following law for Boolean functions: \(x+\) \(f(x, y)=x+f(0, y)\)

Prove the Boolean expansion theorem \(f(x, y)=x f(1, y)\) \(+x^{\prime} f(0, y)\) and the theorem \(x f(x, y)=x f(1, y)\). Note that these are the duals of the results in Exercises 44 and \(45 .\)

Construct a circuit representing the addition of binary numbers as outlined in the text.

Consider the elliptic curve given by the equation \(y^{2}=x^{3}+\) 17. We turn the set of rational points into an Abelian group as follows: If \(P_{1}\) and \(P_{2}\) are rational points, first construct the line connecting them. Next, determine the point \(P_{3}^{\prime}\) where the line intersects the curve again. Finally, let the sum \(P_{1}+P_{2}\) be the point \(P_{3}\), which is the reflection of \(P_{3}^{\prime}\) in the \(x\) axis. (If \(P_{1}=P_{2}\), then take the tangent line at that point to begin the process.) The additive identity for this group will be the point \(P_{0}\) at infinity. Using this addition, show that the sum of \(P_{1}=(2,5)\) and \(P_{2}=(4,9)\) is \((-2,3)\). Find the point that is double \((-2,3)\).

Consider the elliptic curve given by the equation \(y^{2}=x^{3}-\) \(43 x+166\). Using the description of addition on elliptic curves given in Exercise 49, calculate all multiples of the rational point \((3,8)\). Determine the order of this point.

Determine the order of the group \(P S L(2,8)\). (Hint: Recall that \(P S L\left(n, p^{k}\right)\) is the quotient group of \(S L\left(n, p^{k}\right)\) by its subgroup consisting of multiples \(m I\) of the identity matrix, where \(m^{n} \equiv 1\left(\bmod p^{k}\right)\).)