Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Why do you think that $\max\{x_n,y_n\}$ approaches $x+y$ as $n\to\infty$? In fact it approaches $\max\{x,y\}$. –  Brian M. Scott Jan 7 '13 at 16:39
    
Given max([2, 1.7, 1.24, 0.8], [5, 1.5, 1.04, 0.6]), wouldn't the answer (by the method I gave above) be [5, 1.7, 1.24, 0.8]? A number larger than either individual number. Not approaching x+y I agree, but still... –  Karl Barker Jan 7 '13 at 16:47
1  
But Cauchy sequences are infinite sequences; what happens in the first four terms really tells you nothing. –  Brian M. Scott Jan 7 '13 at 16:50
    
Okay, so is there no property that elements in a Cauchy sequence are in decreasing order, as in my examples. Just realised that. Also, since I'm talking about computable reals, these Cauchy sequences are either finite, or only considered to some finite precision? –  Karl Barker Jan 7 '13 at 16:55
2  
There is no restriction on how the terms of a Cauchy sequence bounce around. I strongly suspect that you’ve misunderstood. So far as I know, you’re still looking at infinite sequences; they just have a computable modulus of convergence. –  Brian M. Scott Jan 7 '13 at 17:03
show 4 more comments

2 Answers

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?

sequences

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}$.

share|improve this answer
    
That's a great demonstration, thanks. As you can probably tell, I'm really not versed in Cauchy sequences. How did you generate those sequences? I'm having trouble understanding this wiki page on constructing sequences for reals. –  Karl Barker Jan 8 '13 at 10:42
1  
@Karl For example =3+(RAND()-0.5)*500/ROW()^3 which adds random numbers that tend to zero because of the division by ROW(). Particular numbers there were picked for no particular reason. –  user53153 Jan 8 '13 at 13:12
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.