Logic Puzzle

Thu Oct 29, 2009 8:36 pm, by BarrySlaff

A friend of mine found this on giqtest.com, so make what you will of the source, but we can't figure it out-- any takers?

K_lgic_puzzle.jpg

Description
Filesize 28.58 KB
Viewed 7 Time(s)

Crunching Limits

Thu Oct 15, 2009 12:04 pm, by BarrySlaff

Problem 1: consider the recurrence $f_n=5f_{n-1}-6f_{n-2}$ . Evaluate $\displaystyle\lim_{n\to\infty}|f_n|^{1/n}$ .

Solution:

First, using the method of generating function (see two posts ago), we find $f(n)=2^{n+1}-3^n$ .

Next, $\displaystyle\lim_{n\to\infty}\frac{f(n+1)}{f(n)}=\lim_{n\to\infty}\frac{2^{n+2}-3^{n+1}}{2^{n+1}-3^n}$

$=\displaystyle\lim_{n\to\infty}\frac{(2-3)(2^{n+1}+(3)2^n+(3^2)2^{n-1}+\dots+(3^{n-1})2+3^n)}{(2-3)(2^{n}+(3)2^{n-1}+(3^2)2^{...$

$=\displaystyle\lim_{n\to\infty}\left(3+\frac{2^{n+1}}{2^{n}+(3)2^{n-1}+(3^2)2^{n-2}+\dots+(3^{n-2})2+3^{n-1}}\right)$

Now $0 \le \displaystyle\lim_{n\to\infty}\frac{2^{n+1}}{2^{n}+(3)2^{n-1}+(3^2)2^{n-2}+\dots+(3^{n-2})2+3^{n-1}} \le \lim_{n\to\in...$ ,

hence $\displaystyle\lim_{n\to\infty}\frac{f(n+1)}{f(n)}=3$ .

Hence for every $\epsilon>0$ , $\exists N$ such that $n>N$ implies

$|f(n)|(3-\epsilon) < |f(n+1)| < |f(n)|(3+\epsilon)$ ; and hence

$|f(n+j)|(3-\epsilon)^j < |f(n+j+1)| < |f(n+j)|(3+\epsilon)^j$ .

Then $\displaystyle\lim_{j\to\infty}|f(n)|^{1/j}(3-\epsilon)^j^{1/j} \le \lim_{j\to\infty}|f(n+j+1)|^{1/j} \le \lim_{j\to\infty}|f(...$ .

$(3-\epsilon) \le \displaystyle\lim_{j\to\infty}|f(n+j+1)|^{1/j} \le (3+\epsilon)$ .

Taking the limit $\epsilon\to0$ , i.e. $n\to\infty$ , yields: $\displaystyle\lim_{n\to\infty}|f(n)|^{1/n}=3$ .

Problem 2: The Stirling Numbers of the Second Kind, written $S(n,k)$ , give the number of distinct partitions of a set of $n$ objects into $k$ nonempty classes. It can be shown that:

$S(n,k)=\displaystyle\sum_{r=1}^{k}(-1)^{k-r}\frac{r^n}{r!(k-r)!} \quad (n\ge k \ge 0)$ .

Evaluate $\displaystyle\lim_{n\to\infty}S(n,k)^{1/n}$

Solution:

To start; $\quad \displaystyle\lim_{n\to\infty}S(n,k)^{1/n}=\lim_{n\to\infty}\left[\frac{k^n}{k!0!}-\frac{(k-1)^n}{(k-1)!1!}+\frac{(k-2)...$

As $n\to\infty$ , the sign of the $r=1$ term becomes irrelevent, as do the (fixed) denominators. Hence:

$=\displaystyle\lim_{n\to\infty}\left[[k^{n-1}-(k-1)^{n-1}]+[(k-2)^{n-1}-(k-3)^{n-1}]+\dots\right]^{1/n}$

$=\displaystyle\lim_{n\to\infty}\left[\sum_{i=0}^k \left([k-2i]^{n-1}-[k-(2i+1)]^{n-1}\right)\right]^{1/n}$

We use the factorization $a^h-b^h=(a-b)(a^{h-1}+a^{h-2}b+a^{h-3}b^2+\dots+ab^{h-2}+b^{h-1})$ .
Letting $a=k-2i$ and $b=k-(2i+1)$ yields:

$=\displaystyle\lim_{n\to\infty}\left[\sum_{i=0}^k\sum_{j=0}^{n-2}(k-2i)^{n-1-j}(k-(2i+1))^{j}\right]^{1/n}$ $( \quad =\displaystyle\lim_{n\to\infty}S(n,k)^{1/n} \quad )$ . From this we observe:

$\displaystyle\lim_{n\to\infty}\left[\sum_{i=0}^k(k-2i)^{n-2}+(k-2i-1)^{n-2}\right]^{1/n} \le \lim_{n\to\infty}S(n,k)^{1/n} \l...$ ,

which says $\displaystyle\lim_{n\to\infty}\left[\sum_{i=0}^k(k-i)^{n-2}\right]^{1/n} \le \lim_{n\to\infty} S(n,k)^{1/n} \le \lim_{n\to\in...$

Since $k^{n-2}<\displaystyle\sum_{i=0}^k (k-i)^{n-2}$ , and since $\displaystyle\sum_{i=0}^k n(k-i)^{n-2} < (k+1)nk^{n-2}$ , it follows that

$\displaystyle\lim_{n\to\infty}(k^{n-2})^{1/n} \le \lim_{n\to\infty} S(n,k)^{1/n} \le \lim_{n\to\infty} \left[(k+1)nk^{n-2}\ri...$

So $k \le \displaystyle\lim_{n\to\infty} S(n,k)^{1/n} \le k$ , and hence $\displaystyle\lim_{n\to\infty} S(n,k)^{1/n} = k$ .

Continuous at Exactly One Point

Sat Oct 10, 2009 3:34 pm, by BarrySlaff

Let $\Re$ denote the real numbers and let $Q$ denote the rational numbers. The following function is one of my favorites:

$f: \Re \to \Re, \quad f(x) = \begin{cases}x \quad \text{if} \quad x\in Q \\ 0 \quad \text{if} \quad x\not\in Q\end{cases}$

Recall the definition of continuity: a function $f$ is continuous at the point $x_0$ if for every $\epsilon > 0$ , there exists $\delta > 0$ such that $|x - x_0| < \delta$ implies $|f(x) - f(x_0)| < \epsilon$ .

Claim: this function is continuous only at the point $x = 0$ .

Proof of Claim:

At all $x_0\neq0$ , $f$ clearly is not continuous. For suppose we choose $\epsilon = \displaystyle\frac {x_0}{2}$ ; then there is no $\delta > 0$ such that $|x - x_0| < \delta$ implies $|f(x) - f(x_0)| < \frac {x_0}{2}$ , since $f(x) = 0$ for any irrational $x$ , and $f(x)=x$ for any rational $x$ .

On the other hand, consider $x_0 = 0$ with $2\delta = \epsilon$ . Then $|x - x_0| = |x| < \delta$ implies $|f(x) - f(x_0)| = |f(x)| < 2\delta$ , since $|f(x)|\le| x | < \delta < 2\delta = \epsilon$ . It follows that $f$ is continuous at $x_0 = 0$ .

Therefore $f$ is continuous at $x = 0$ and nowhere else.

Generating Functions

Thu Oct 01, 2009 7:01 pm, by BarrySlaff

There are two problems posted this time, a generating functions problem and a counting problem.

There are a bunch of ways to do generating functions problems like these. The analyst in me feels guilty whenever I write these infinite sums without proving convergence, and especially when I use the equivalence $\sum \frac {d}{dx}a_nx^n = \frac {d}{dx}\sum a_nx^n$ without proving uniform convergence, but my professor stresses that these series should be treated as algebraic objects instead of true functions.

I list two solutions to the counting problem, the second of which is more elegant but not originally mine.

$\textbf{Problem 1: }$ Find a simple finite expression for the series in which the coefficient of $x^n$ is the sum of the squares of all of the integers $1,2,\dots,n$ .

$\textbf{Solution: }$ Let $F(x) = \sum f(n)x^n$ , where $f(n)=\displaystyle\sum_{j=0}^n j^2$ . From the definition of the sequence coefficients, we immediately have the recursion $f(n) = f(n - 1) + n^2$ . Then

$\displaystyle\sum_{n = 1}^{\infty}f(n)x^n = \sum_{n = 1}^{\infty}f(n - 1)x^n + \sum_{n = 1}^{\infty}n^2x^n$

$= \sum_{n = 1}^{\infty}f(n - 1)x^n + \sum_{n = 1}^{\infty}(n^2 - n)x^n + \sum_{n = 1}^{\infty}nx^{n}$

$= x\sum_{n = 1}^{\infty}f(n - 1)x^{n - 1} + x^2\sum_{n = 1}^{\infty}(n^2 - n)x^{n - 2} + x\sum_{n = 1}^{\infty}nx^{n - 1}$

$= x\sum_{n = 1}^{\infty}f(n - 1)x^{n - 1} + x^2\sum_{n = 1}^{\infty}\frac {d^2}{dx^2}x^{n} + x\sum_{n = 1}^{\infty}\frac {d}{...$

$= x\sum_{n = 1}^{\infty}f(n - 1)x^{n - 1} + x^2\frac {d^2}{dx^2}\sum_{n = 1}^{\infty}x^{n} + x\frac {d}{dx}\sum_{n = 1}^{\inf...$

$= x\sum_{n = 1}^{\infty}f(n - 1)x^{n - 1} + \frac {2x^2}{(1 - x)^3} + \frac {x}{(1 - x)^2}$

$= > F(x) - f(0) = xF(x) + \displaystyle\frac {2x^2}{(1 - x)^3} + \frac {x}{(1 - x)^2}$

$= > (1 - x)F(x) = \displaystyle\frac {x^2 + x}{(1 - x)^3}$

$= > F(x) = \displaystyle\frac {x^2 + x}{(1 - x)^4}$

$\textbf{Problem 2: }$ Of the $4^n$ ordered pairs of subsets of $N = \{1,2,\dots,n\}$ , how many ordered pairs have an empty intersection?

$\textbf{Solution: }$ Let each of the $2^n$ elements of the power set of $N$ be assigned $S_n$ for $n\in \{1,2,\dots,2^n\}$ . For each $n$ , let the number of subsets of $N$ having no element in common with $S_n$ be $a_n$ . Then the total number of ordered pairs with empty intersection is

$\displaystyle\sum_{k = 1}^{2^k}a_k$ .

Consider a subset $S$ of the set $N$ , $|S| = k$ for $k < n$ . There are $n - k$ elements in $N$ but not in $S$ ; hence there are $2^{n - k}$ subsets of $N$ with no element in common with $S$ . Now we just have to add up the numbers of all these sets. For each $k$ , there are $\displaystyle\binom{n}{k}$ distinct subsets with $|S| = k$ .

Hence $\displaystyle\sum_{k = 1}^{2^k}a_k = \displaystyle\sum_{k = 0}^{n}\binom{n}{k}2^{n - k}$

But $\displaystyle\binom{n}{k} = \binom{n}{n - k}$ , so there are $\displaystyle\sum_{k = 0}^{n}\binom{n}{n - k}2^{n - k} = \sum_{k = 0}^{n}\binom{n}{k}2^{k} = \sum_{k = 0}^{n}\binom{n}{k}2^{k...$

$= 3^n$ by the binomial theorem. Hence there are $3^n$ such ordered pairs.

$\textbf{Alternate Solution: }$ There are $n$ elements in this set, and we want all ordered pairs which have empty intersection, so each element can be disposed of in three ways: it can be a member of the first subset in the ordered pair, a member of the second subset of the ordered pair, or a member of neither. So there are three choices for each of the $n$ elements and hence $3^n$ such ordered pairs.

So, What Are Real Numbers, Exactly?

Sun Aug 09, 2009 5:52 pm, by BarrySlaff

Rudin devotes the first chapter and appendix of his Principles of Mathematical Analysis to answering this question. What follows is essentially my summary of this chapter/appendix. I'm bothering to summarize it both so I understand it better and because, well, it's really cool.

The question is motivated as follows: it is easy enough to intuitively deal with rational numbers (fractions of integers, including integers themselves). But how is it clear that we can add or multiply numbers like $\sqrt {2}$ , $\pi$ , and $e$ , which are numbers that cannot be represented as the finite sum or product of rational numbers? That is, how can we be sure that these irrational numbers follow the same "rules"? Moreover, it is clear that the rational numbers have certain "gaps"-- for instance, as I showed (via Rudin) three posts ago, there is no greatest rational number $p$ such that $p^2 < 2$ . To fill these gaps, and to be certain that we can operate on every element of the gap-less number line, we have to rigorously define the field of real numbers, $R$ .

First, I'll give some definitions and theorems. Then, I'll present Rudin's Theorem 1.19, which asserts the existence of the real numbers as we like to think of them. Finally, I've summarized the proof this theorem, which Rudin credits to Dedekind and Cantor, both in 1872.

A "field" consists of a set $S$ and two operations, "addition" and "multiplication," such that
0) addition and multiplication are closed on the set; that is, if $x,y \in S$ , then $x + y$ and $xy$ are in the set.
1) addition is commutative
2) addition is associative
3) there is a unique additive identity, 0, so that $x + 0 = x$ for all $x\in S$ .
4) each element $x$ has a unique additive inverse $- x$ , so that $x + ( - x) = 0$ .
5) multiplication is commutative
6) multiplication is associative
7) there is a unique multiplicative identity, 1, so that $1x = x$ for all $x\in S$ .
8) each element $x$ has a unique multiplicative inverse $x^{ - 1}$ , so that $x(x^{ - 1}) = 1$ .
9) multiplication distributes over addition: $x(y + z) = xy + xz$ . (This is the "distributive law.")

(Rudin) Definition 1.5: An "order'' on a set $S$ is a relation, denoted by $<$ , with the following two properties: if $x\in R$ and $y\in R$ then one and only one of the statements $x < y$ , $x = y$ , $y < x$ is true; and if $x, y, z \in R$ , with $x < y$ and $y < z$ , then $x < z$ .

Definition 1.17: An "ordered field'' is a field $F$ which is also an "ordered set,'' such that

(i) $x + y < x + z$ if $x,y,z\in F$ and $y < z$ .

(ii) $xy > 0$ if $x\in F$ , $y\in F$ , $x > 0$ , and $y > 0$ .

Definition 1.8: The least-upper-bound $\alpha$ of a set $E$ is denoted by $\alpha = \sup E$ . This means $\alpha$ is an upper bound of $E$ , and no $\beta < \alpha$ is an upper bound of $E$ .

Definition 1.10: An ordered set $S$ is said to have the least-upper-bound property if the following is true: if $E\subset S$ , $E$ is not empty, and $E$ is bounded above, then $\sup E$ exists in $S$ .

Theorem 1.19. There exists an ordered field $R$ which has the least-upper-bound property. Moreover, $R$ contains $Q$ as a sub-field (that is, $Q$ is also a field with the same "addition" and "multiplication" operations as we are about to define for $R$ .) The elements of $R$ shall be called "real numbers.''

The relevant definitions and proof of Theorem 1.19 are divided into nine steps, summarized below. The below sketch of the proof requires a lot of fill-in-the-blank since 1) typing the whole thing would be really tedious, and 2) I don't want to get into copyright trouble.

Step 1: The members of $R$ will be certain subsets of $Q$ , called "cuts.'' A cut is, by definition, any $\alpha \subset Q$ with the following three properties:

(I) $\alpha$ is not empty and $\alpha\neq Q$ .

(II) If $p\in \alpha$ , $q\in Q$ , and $q < p$ , then $q\in \alpha$ .

(III) If $p\in\alpha$ , then $p < r$ for some $r\in \alpha$ .

Step 2: Define $\alpha < \beta$ to mean: $\alpha$ is a proper subset of $\beta$ . It can be demonstrated that this satisfies the definition of an order on a set (see Definition 1.5, above).

Step 3: To prove that the ordered set $R$ has the least-upper-bound property (Definition 1.8, above): let $A$ be a nonempty subset of $R$ and assume that $\beta \in R$ is an upper bound of $A$ . Define $\gamma$ to be the union of all cuts $\alpha\in A$ ; then it can be shown that $\gamma\in R$ and $\gamma = \sup A$ .

Step 4: Define "addition" as follows: for $\alpha \in R$ and $\beta \in R$ define $\alpha + \beta$ to be the set of all sums $r + s$ where $r\in\alpha$ and $s\in\beta$ . Define $0^*$ to be the set of all negative rational numbers; it is clear that $0^*$ is a cut. The field axioms for addition (see above) can now be shown to hold in $R$ , with $0^*$ being the additive identity.

Step 5: The addition axioms can be shown to imply that $R$ satisfies the first criterion (i) for ordered fields.

Step 6: Define "multiplication" of positive cuts (other cases will be defined in step 7) as follows: for $\alpha \in R^ +$ and $\beta\in R^ +$ , define $\alpha\beta$ to be the set of all $p$ such that $p \le rs$ for some choice of $r\in\alpha$ , $s\in\beta$ , $r > 0$ , $s > 0$ . Define $1^*$ to be the set of all $q < 1$ . Then the field axioms for multiplication (see above) can be verified with $1^*$ as the multiplicative identity.

Step 7: We complete the definition of multiplication by setting the usual conventions for positive-negative multiplication, which can be shown to be consistent with the multiplication defined in step 6. Then, the distributive law can be proven. These findings can be shown to imply that $R$ satisfies the second criterion (ii) for ordered fields; so it is now clear that $R$ is an ordered field with the least-upper-bound property.

This completes the proof of the first part of Theorem 1.19. Going one step further and proving the "moreover" brings us to...

Steps 8-9: So far, these cuts are just floating aimlessly in $R$ . Now we attach them to something familiar.

Associate with each $r\in Q$ the set $r^*$ which consists of all $p \in Q$ such that $p < r$ . Clearly each $r^*$ is a cut, and it can be demonstrated that these cuts satisfy:

(a) $r^* + s^* = (r + s)^*$

(b) $r^*s^* = (rs)^*$

(c) $r^* < s^*$ if and only if $r < s$ .

Based on these three relations, it can be shown that $Q$ is a subfield of $R$ .

Infinite Sequences

Mon Aug 03, 2009 9:47 pm, by BarrySlaff

What follows are Exercises 2 and 3 from Rudin Chapter 3, and solutions. I found #2 interesting because I would never have thought the answer intuitively likely. I found #3 interesting because I saw a lot of problems like it in high school math contests, but in those situations, we were never asked to prove that the sum converges at all! We could have been working with phantom sums the whole time (but thankfully, we weren't).

First, two relevant theorems from Rudin:

Theorem 3.3 (a): Suppose $\{s_n\}$ and $\{t_n\}$ are complex sequences, and $\displaystyle\lim_{n\to\infty}s_n = s$ , $\displaystyle\lim_{n\to\infty}t_n = t$ . Then $\displaystyle\lim_{n\to\infty}(s_n + t_n) = s + t$ .

Theorem 3.14: Suppose $\{s_n\}$ is monotonic. Then $\{s_n\}$ converges if and only if it is bounded.

Exercises:

2. Calculate $\displaystyle\lim_{n\to\infty}(\sqrt {n^2 + n} - n)$ .

Solution: The answer follows easily from the fact that

$(\sqrt {n^2 + n} - n) = \sqrt {n}(\sqrt {n + 1} - \sqrt {n}) = \displaystyle\frac {\sqrt {n}}{\sqrt {n + 1} + \sqrt {n}}$

But the second equivalence was not obvious at first. My first successful thought was

$\displaystyle\lim_{n\to\infty} \sqrt {n}(\sqrt {n + 1} - \sqrt {n}) = \displaystyle\frac {1}{2}\displaystyle\lim_{n\to\infty}...$

$\le \displaystyle \frac {1}{2} \displaystyle\lim_{n\to\infty} (\sqrt {n + 1} + \sqrt {n})(\sqrt {n + 1} - \sqrt {n}) = \displ...$ .

This motivates: $\displaystyle\lim_{n\to\infty} \sqrt {n}(\sqrt {n + 1} - \sqrt {n}) = \displaystyle\lim_{n\to\infty}\frac {\sqrt {n}}{\sqrt {...$ .

So the answer is apparently $\displaystyle\frac {1}{2}$ , which is readily demonstrated:

$\displaystyle\lim_{n\to\infty} \frac {\sqrt {n}}{2\sqrt {n}} = \displaystyle\frac {1}{2}$ , and

$\displaystyle\lim_{n\to\infty} \left( \frac {\sqrt {n}}{2\sqrt {n}} - \frac {\sqrt {n}}{\sqrt {n + 1} + \sqrt {n}} \right)$

$= \displaystyle\lim_{n\to\infty} \frac {\sqrt {n}(\sqrt {n + 1} - \sqrt {n})}{2\sqrt {n}(\sqrt {n + 1} + \sqrt {n})}$

$= \displaystyle\lim_{n\to\infty} \displaystyle\frac {1}{2(\sqrt {n + 1} + \sqrt {n})^2} = 0$ .

Then by Theorem 3.3(a),

$\displaystyle\lim_{n\to\infty} \frac {\sqrt {n}}{2\sqrt {n}} - \left( \displaystyle \frac {\sqrt {n}}{2\sqrt {n}} - \frac {\s...$

$= \displaystyle\lim_{n\to\infty} \frac {\sqrt {n}}{\sqrt {n + 1} + \sqrt {n}}$

$= \displaystyle\frac {1}{2} - 0 = \displaystyle\frac {1}{2}$ .

Hence $\displaystyle\lim_{n\to\infty} (\sqrt {n^2 + n} - n) = \displaystyle\frac {1}{2}$ .

3. If $s_1 = \sqrt {2}$ , and $s_{n + 1} = \sqrt {2 + \sqrt {s_n}}$ ( $n = 1,2,3,\dots),$ prove that $\{s_n\}$ converges, and that $s_n < 2$ for $n = 1,2,3,\dots$ .

Solution: the first few terms of the sequence are

$s_1 = \sqrt {2}$

$s_2 = \sqrt {2 + \sqrt {\sqrt {2}}}$

$s_3 = \sqrt {2 + \sqrt {\sqrt {2 + \sqrt {\sqrt {2}}}}}$ .

$s_4 = \sqrt {2 + \sqrt {\sqrt {2 + \sqrt {\sqrt {2} + \sqrt {\sqrt {2}}}}}}$

This pattern evidently continues for all $n$ .

Recall Theorem 3.14: Suppose $\{s_n\}$ is monotonic. Then $\{s_n\}$ converges if and only if it is bounded.

Now $\{s_n\}$ is monotonic since for $a$ , $b$ , $c$ all positive, $c > b$ implies $\sqrt {a + c} > \sqrt {a + b}$ . So if $\{s_n\}$ is bounded, it converges.

Lemma: for positive $M$ and $N$ , $M - N$ has the same sign as $M^2 - N^2$ . Proof of lemma: $M^2 - N^2 = (M - N)(M + N) = c(M - N)$ , with $c > 0$ . The lemma follows since this is a property of ordered fields.

Applying the lemma, let $M = 2$ and $N = s_n$ . Then $2 - s_n$ has the same sign as

$2^2 - (s_n)^2 = 4 - (2 + \sqrt {s_{n - 1}}) = 2 - \sqrt {s_{n - 1}}$ (*)

Now this has the same sign as: $16 - (s_{n - 1})^2 = 16 - (2 + \sqrt {s_{n - 2}}) = 14 - \sqrt {s_{n - 2}}$ (**)

(*) and (**) motivate the definition $B_{n - k} = A_{n - k} - \sqrt {s_{k}}$ for $k = 1,\dots,n$ , where $A_1 = 2$ , $A_{j + 1} = (A_j)^4 - 2$ . By the lemma, $B_j$ has the same sign as $B_{j + 1}$ for all $j$ ; so every $B_j$ has the same sign as $B_{n - 1} = A_{n - 1} - \sqrt {s_1} = A_{n - 1} - \sqrt {\sqrt {2}}$ . Since $A_1 > \sqrt {2}$ and $\{A_j\}$ increases monotonically, it follows that $B_{n - 1} > 0$ ; so every $B_j > 0$ , and since $2 - s_n$ has the same sign as $B_1$ , it follows that $2 - s_n > 0$ . Hence $s_n < 2$ for all $n$ .

Since $0 < s_n < 2$ , for all $n$ , it follows that $\{s_n\}$ is bounded. Since $\{s_n\}$ is monotonic and bounded, it follows that $\{s_n\}$ converges. This completes the solution.

Topological Application of the Previous Generalization

Wed Jul 29, 2009 7:56 am, by BarrySlaff

Last time, I generalized a claim from the first chapter of Rudin's Principles of Mathematical Analysis. While working the exercises from the second chapter, I found an opportunity to apply that generalization.

First, I restate the generalization:

Generalization of Rudin 1.1

Let A be the set of all positive rationals $p$ such that $p^2 < N$ and let $B$ consist of all positive rationals $p$ such that $p^2 > N$ . We shall show that $A$ contains no largest number and $B$ contains no smallest.

More explicitly, for every $p$ in $A$ we can find a rational $q$ in $A$ such that $p < q$ , and for every $p$ in $B$ we can find a rational $q$ in $B$ such that $q < p$ . To do this, we associate with each rational $p > 0$ the number
$q = N\displaystyle\frac {p + 1}{p + N}$
The accompanying discussion shows that $p\in{A}$ implies ${q}\in{A}, q > p$ ; and $p\in{B}$ implies ${q}\in{B}, q < p$ . So $A$ contains no largest number and $B$ contains no smallest.

Remark: from the accompanying discussion is it evident that this can be further generalized from positive integers $N$ to positive rationals $r$ . I make use of this further generalization in what follows.

First, some notes for the benefit of those less familiar with real analysis:

Definition (Rudin 2.15): A set $X$ , whose elements we shall call points, is said to be a metric space if with any two points $p$ and $q$ of $X$ there is associated a real number $d(p,q)$ called the distance from $p$ to $q$ such that $d(p,q)>0$ if $p\neq q$ ; $d(p,p)=0$ ; $d(p,q)=d(q,p)$ ; and $d(p,q)\le d(p,r)+ d(r,q)$ for any $r\in X$ .

Definitions (Rudin 2.18): Let $X$ be a metric space, and let $E\subset X$ .

A neighborhood of a point $p$ is a set $N_r(p)$ consisting of all $q$ such that $d(p,q)<r$ for some $r>0$ . The number $r$ is called the radius of $N_r(p)$ .
A point p is a limit point of the set $E$ if every neighborhood of p contains a point $q\neq{p}$ such that $q\in E$
$E$ is closed if every limit point of $E$ is a point of $E$ .
A point $p$ is an interior point of $E$ if there is a neighborhood $N$ of $p$ such that $N \subset E$
$E$ is open if every point of $E$ is an interior point of $E$ .
$E$ is bounded if there is a real number $M$ and a point $q\in X$ such that $d(p,q)<M$ for all $p \in E$ .

Theorem (Rudin 2.19): Every neighborhood is an open set. [Proved in the text.]

Definition (Rudin 2.31): By an open cover of a set $E$ in a metric space $X$ we mean a collection $\{G_a\}$ of open subsets of $X$ such that $E\subset \bigcup_a G_a$ .

Definition (Rudin 2.32): A subset $K$ of a metric space $X$ is said to be compact if every open cover of $K$ contains a finite subcover. More explicitly, the requirement is that if $\{G_a\}$ is an open cover of $K$ , then there are finitely many indices $a_1,\dots, a_n$ such that $K\subset G_{a1}\cup \dots \cup G_{an}$ .

This concludes the preliminary notes. What follows is Exercise 16 from Rudin chapter 2, and solution.

16. Regard $Q$ , the set of all rational numbers, as a metric space, with $d(p,q)=|p-q|$ . Let $E$ be the set of all $p\in{Q}$ such that $2<p^2<3$ . Show that $E$ is closed and bounded in $Q$ , but that $E$ is not compact. Is $E$ open in $Q$ ?

Remark: this is intended to show that the Heine-Borel theorem (Rudin 2.41), which states ``closed and bounded in $\Re^k$ $<=>$ compact in $\Re^k$ ,'' cannot be generalized to all metric spaces.

Solution: $E$ is closed in $Q$ if $E$ contains all its limit points. In the generalization of Rudin 1.1, it was shown that for rational $p$ and $r$ ( $r$ can be an integer, in this case $2$ or $3$ ), if $p^2<r$ then $p^2<r\frac{p+1}{p+r}<r$ , and if $p^2>r$ then $p^2>r\frac{p+1}{p+r}>r$ ; from this it follows that there is no least element of $E$ and no greatest element of $E$ .

So for any $p\in{E}$ , $\exists p(1)$ such that $p(1)<p$ , $p(1)\in{E}$ ; and $\exists p(1)'$ such that $p(1)'>p$ , $p(1)'\in{E}$ . Then $\frac{1}{2}[p+p(1)]=p(2)\in{E}$ and $\frac{1}{2}[p+p(1)']=p(2)'\in{E}$ . The recursion $p(k)=(1/2)[p(k-1)+p]$ can be continued, and letting $k\to\infty$ shows that every $p\in E$ is a limit point of $E$ , since for rational $R>0$ , the neighborhood $N_p(R)$ contains $p(k)$ for all but finitely many $k$ .

(We just showed that every $p\in E$ has some $N_p \subset E$ . It follows that $E$ is open in $Q$ ).

Using standard methods (and proved in chapter 1 and chapter 1 exercises) it can be shown that there is no rational $q$ such that $q^2=2$ or $q^2=3$ . For $q$ such that $q^2<2$ , using the same generalization of Rudin 1.1 and the same method as was used just above, we can show that $\exists q_1$ such that $q^2<(q_1)^2<2$ . Put $R=q_1-q$ ; then $N_q(R)$ contains no element of $E$ , so $q$ is not a limit point of $E$ . The proof of the claim ``if $q^2>3$ , then $q$ is not a limit point of $E$ '' is analogous.

It has been demonstrated that all $p\in{E}$ are limit points of $E$ and all $Q\not\in{E}$ are not limit points of $E$ . Hence $E$ contains all its limit points, and it follows that $E$ is closed in $Q$ .

(Remark: we have shown that $E$ is both open and closed in $Q$ . So despite the linguistic implication that "open" and "closed" are opposites, a set can be both open and closed in a metric space.)

$E$ clearly is bounded in $Q$ , for instance by $q=1$ , $q=2$ .

To show that $E$ is not compact, we start by proving a relevant claim.

Claim (*): if $2<q^2<p^2$ , then $\displaystyle\left(2\frac{p+1}{p+2}\right)^2<\left(\displaystyle\frac{p+q}{2}\right)^2$

Proof: with $q<p$ , we want to find the sign of $\displaystyle\left(\frac{p+q}{2}\right)^2-\left(2\frac{p+1}{p+2}\right)^2$ . This has the same sign as

$\displaystyle\frac{p+q}{2}-2\frac{p+1}{p+2}$ , which has the same sign as

$[p+2][p+q]-(2)(2)[p+1]$

$=p^2+pq+2p+2q-4p-4$

$=[2q-2p]+[p^2+pq-4]$

$>[2q-2p]+[p^2-2]$ . For $r$ such that $2<r^2<q^2<p^2$ , we have

$>(2r-2p)+(p^2-r^2)$

$=2(r-p)+(p+r)(p-r)=(p+r-2)(p-r)$

$>0$ since $z^2>2$ , $z$ positive together imply $z>1$ . This completes the proof of the claim.

(Remark: this claim is easily generalized from $2$ to rational $R$ , but this is not pursued here.)

Now we will show that $E$ is not compact by constructing an open cover of $E$ for which there is no finite subcover. Consider any $p\in{E}$ . Using the generalization of Rudin 1.1, define the recursion $p(0)=p$ , $p(i+1)=2\displaystyle\frac{p(i)+1}{p(i)+2}$ for non-negative integers $i$ . Then $2<p(i+1)^2<p(i)^2$ for all such $i$ .

Let $p(i)-p(i+2)=r_i$ . From the above Claim (*), we know that for all $q$ such that $2<q^2<p(i)^2$ , we have $p(i+1)^2<\left(\displaystyle\frac{p(i)+q}{2}\right)^2$ ; it follows that $\{p(i)\}$ is not bounded by any $q\in{E}$ .

Then $C=\{(p(2),5)\}\cup \{N_{p(i)}(r_i)\}$ is an open cover of $E$ with no finite sub-cover, since the finiteness of any subset $C'$ of the open sets in $C$ implies $\exists I$ such that $p(i)\not\in C'$ for all $i>I$ . It follows that $E$ is not compact.

Rudin 1.1: How I Might Think of That, and Generalization

Tue Jul 21, 2009 8:09 pm, by BarrySlaff

On the second page of his Principles of Mathematical Analysis, Walter Rudin demonstrates that there is no largest rational number less than $\sqrt {2}$ and no smallest rational number greater than $\sqrt {2}$ . Rudin takes care of both cases by pulling, seemingly out of nowhere, the function $q(p)$ from rationals $p$ to rationals $q$ :
$q(p) = p - \frac {p^2 - 2}{p + 2} = \frac {2p + 2}{p + 2}$
It is straightforward to verify that if $2 < p^2$ , then $q < p$ and $2 - q^2 < 0$ ; and if $2 > p^2$ , then $q > p$ and $2 - q^2 > 0$ . The demonstration is therefore complete, but one is left wondering: how might someone have come up with that slick formula? My musings yielded the following findings and generalization.

For positive integer $N$ suppose we let $A$ be the set of all positive rationals $p$ such that $p^2 < N$ and let $B$ consist of all positive rationals $p$ such that $p^2 > N$ . We want to show that $A$ contains no largest number and $B$ contains no smallest. That is, we want to show that for every $p$ in $A$ we can find a rational $q$ in $A$ such that $p < q$ , and for every $p$ in $B$ we can find a rational $q$ in $B$ such that $q < p$ .

Even though $\sqrt {N}$ is not yet well-defined in cases where $\sqrt {N}$ is irrational (since the real numbers are not constructed until later in the chapter), we can use it for purposes of coming up with an expression for $q$ , and we're justified in using it as long as we can ultimately verify what we need without it. So we want a function $r$ from rationals to rationals such that

(I) $p < r(p) < \sqrt {N}$ when $p < \sqrt {N}$
(II) $p > r(p) > \sqrt {N}$ when $p > \sqrt {N}$
(III) $p = r(p) = \sqrt {N}$ when $p = \sqrt {N}$ , i.e. $\sqrt {N}$ is a fixed point of $r$ .

A large class of functions from rationals to rationals is the class of rational functions, i.e. functions which are quotients of polynomials. Let $r(p) = X(p)/Y(p)$ for polynomials $X = x_np^n + \dots + x_1p + x_0$ and $Y = y_np^n + \dots + y_1p + y_0$ with rational coefficients. Starting methodically:

The case with $\deg(X) = \deg(y) = 0$ is a constant and thus clearly cannot yield satisfactory $r(p)$ .

The case with $\deg(X) = 1$ , $\deg(Y) = 0$ is a line of the form $r(p) = x_1p + x_0$ . To define $r(p)$ for all $N$ , we need $r(\sqrt {N}) = \sqrt {N} = x_1\sqrt {N} + x_0$ . It is clear that if either of $x_1$ or $x_0$ is rational, then the other must be defined in terms of $\sqrt {N}$ , which violates the rationality of coefficients of $X$ . The only exception is the case $x_1 = 1$ and $x_0 = 0$ , which yields $r(p) = p$ for all $p$ , violating (I) and (II) above.

The case with $\deg{X} = 0$ , $\deg(Y) = 1$ has the form $r(p) = \frac {1}{y_1p + y_0}$ . This is evidently a decreasing function for $p > 0$ ; so if (III) is satisfied, then (I) and (II) are necessarily violated.

This brings us to the ultimately successful case: $\deg{X} = 1$ , $\deg{Y} = 1$ . Let

$r(p) = \displaystyle\frac {kp + m}{p + n}$

for rational $k,m,n$ . Starting with (III) yields

$k\sqrt {N} - n\sqrt {N} + m - \sqrt {N}^2 = 0$

The obvious integer solutions are $k = n$ and $m = N$ . So $r(p) = \displaystyle\frac {kp + N}{p + k}$ and it remains to determine $k$ and verify the solution.

For the first condition, we want $r(p) - p > 0$ and $\sqrt {N} - r(p) > 0$ for $p < \sqrt {N}$ . The first part is verified regardless of $k$ . The second part requires $k > \sqrt {N}$ . Since $N\ge{1}$ , one general solution is $k = N$ .

For the second condition, we want $p - r(p) > 0$ when $r(p) - \sqrt {N} > 0$ for $p > \sqrt {N}$ . The first part is immediately verified regardless of $k$ , but the second part also requires $k > \sqrt {N}$ ; so the same general solution works.

Then in general, $r(p) = N\displaystyle\frac {p + 1}{p + N}$ . This matches Rudin's special case.

So, Generalization of Rudin 1.1

Let A be the set of all positive rationals $p$ such that $p^2 < N$ and let $B$ consist of all positive rationals $p$ such that $p^2 > N$ . We shall show that $A$ contains no largest number and $B$ contains no smallest.

More explicitly, for every $p$ in $A$ we can find a rational $q$ in $A$ such that $p < q$ , and for every $p$ in $B$ we can find a rational $q$ in $B$ such that $q < p$ . To do this, we associate with each rational $p > 0$ the number
$q = N\displaystyle\frac {p + 1}{p + N}$
The above discussion shows that $p\in{A}$ implies ${q}\in{A}, q > p$ ; and $p\in{B}$ implies ${q}\in{B}, q < p$ . So $A$ contains no largest number and $B$ contains no smallest.

Page 1 of 1 [8 Entries]

Thoughts of a mathematically-minded undergraduate. Comments welcome.

Blog owner: BarrySlaff

Contact owner

About owner

Joined: 19 Jul 2009

Blog details

Blog started: 21 Jul 2009
Total entries: 8
Total visits: 682

Barry's Mathematics Page