Max/min of reals as Cauchy sequences

Question

Apologies if this seems overly simplified, I'm just getting to grips with this.

This is related to the computability of the min() and max() functions of real numbers reconstructed using Cauchy sequences of rational numbers.

To check my understanding first: Cauchy sequences are a sequence of rational numbers converging to a real value with some accuracy. They might look like:

[2, 1.7, 1.24, 0.8]

etc.

The addition of two reals represented like this is done by:

x + y = [x0 + y0, ...xn + yn]

and similar for subtraction and multiplication.

In my lecture notes however, the max() and min() functions are show as:

max(x, y) = [max(x0, y0), ...max(xn, yn)]
min(x, y) = [min(x0, y0), ...min(xn, yn)]

which would surely have the some weird effect of returning some value nering x + y?

Could someone please explain how these functions should work?

Thanks

Answer 1

A CS major can easily check the claims about sequences against numerical experiments (keeping in mind that an experiment does not prove the theory, but may disprove it with a counterexample). For example, I used RAND() to generate two sequences: $x_n\to 3$ and $y_n\to 2$, and calculated (in OpenOffice) their maximum $\max(x_n,y_n)$ and minimum $\min(x_n,y_n)$. Do you see what numbers $\max(x_n,y_n)$ and $\min(x_n,y_n)$ are approaching?

Aside: a lot of interesting sequences can be quickly generated in a spreadsheets. For example, $x_{n+1}=\frac12 (x_n+\frac{a}{x_n})$ is a nice sequence for approximation of $\sqrt{a}$. If $a$ is rational and the initial value $x_1$ (which is ours to choose) is also rational, then the sequence consists of rational numbers quickly converging to $\sqrt{a}$.

Answer 2

Since you have expressed a lack of "rigorous" mathematical background, I'll try to stay simple.

Cauchy sequences are infinite combinations of numbers that get closer together as you go on. It really means that for any distance $\epsilon$>0, we can find a value in the sequence such that all of the remaining values are within $\epsilon$ of any other value.

More technically, there exists an $N$, such that for all $n, m \ge N, |x_n-x_m|<\epsilon$. The absolute value bars being the distance from $x_m$ to $x_ n$, all the later terms fit in an interval around $x_N$ of length $2\epsilon$, and since we can make $\epsilon$ really small, they all bunch up around the limit. The limit doesn't need to exist, it is just the "value" for which they all clump around. Now to the problem at hand.

We now see that the max and min functions, as we have defined them, work. Let's look at $max(x_n, y_n)$, Then since $x_n \to x$ and $y_n \to y$, so $max(x_n, y_n)\to max(x, y)$. Since large values of our "max sequence" have arguments really close to the limits, the value is close to the limit.

To see this, take $\epsilon$>0, and take $N=max(N', N'')$, where $N'$ is the value for $x$ and $N''$ for $y$ for $\epsilon$. Then the max has bunched itself in a little interval for values greater then $N$. Since $\epsilon$ can be as small as we like, we have shown that it clumps up around the limit.

Convergence and the idea of getting arbitrary close are closely tied concepts mathematics. Your definition works for any converging sequence, which is implied by the limits.

---

A good book if you don't have much experience in mathematics is Rosenlicht's, "Introduction to Analysis". It's not really in your field, but it's short and well written. It will give you some fundamental mathematics, some convergence and topology, and then rigorous limits, continuity, and calculus.