Wikipedia:Reference desk/Archives/Mathematics/2009 May 13

Mathematics desk
< May 12	<< Apr | May | Jun >>	May 14 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 13

What are the benefits to humans of using a tree structure?

Such as building one on paper.

Or accessing one in a book or on a webpage.

Take the example in the article tree structure for example. What would the benefits be of having an entire encyclopedia rendered into a tree?

The Transhumanist 02:20, 13 May 2009 (UTC)

In the old days before computers, they used to render trees into encyclopedias. Does that help? 67.122.209.126 (talk) 10:06, 13 May 2009 (UTC)

Very funny. :) The Transhumanist 00:05, 14 May 2009 (UTC)

Second difference equation

What functions f: R → R satisfy f(x+2)-2f(x+1)+f(x)=0 for all x in R? Affine times 1-periodic works... Then? --Carminat (talk) 09:54, 13 May 2009 (UTC)

Homework? This is a linear recurrence. The first thing you could do is figure out the generating polynomial. 67.122.209.126 (talk) 10:16, 13 May 2009 (UTC)

For any 1-periodic functions a(x) and b(x), the function f(x) = a(x) + xb(x) solves the equation. This is the general form of a solution. — Emil J. 14:13, 13 May 2009 (UTC)

Carminat's guess is quite correct, except that I'd say "affine plus 1-periodic". Michael Hardy (talk) 21:52, 13 May 2009 (UTC)

Oh.... I see. Carminat was asking whether there are any other solutions besides affine plus 1-periodic. Notice that

$f(x+2)-2f(x+1)+f(x)=0\,$

implies that

$f(x+2)-f(x+1)=f(x+1)-f(x),\,$

so that every time you go one step to the right, you add the same amount. That makes it a straight line as long as you move only in steps of size 1. So affine plus 1-periodic is all there is. Michael Hardy (talk) 22:03, 13 May 2009 (UTC)

No, it isn't, see my post above. For example, the function $f(x)={\begin{cases}0,&x-\lfloor x\rfloor <1/2,\\x,&x-\lfloor x\rfloor \geq 1/2\end{cases}}$ solves the recurrence, and cannot be written as a sum of an affine and 1-periodic function. — Emil J. 12:14, 14 May 2009 (UTC)

Also, affine times 1-periodic functions do solve the equation (though they do not exhaust all solutions either), so it is reasonable to assume that Carminat really meant "times" when he wrote "times", not "plus". — Emil J. 12:21, 14 May 2009 (UTC)

OK, so MH's argument proves that for all x the restriction of f to x+Z is an affine function; but as you say it possibly depends on x, so you got your general form f(x) = a(x) + xb(x), where a and b are 1-periodic because x+Z=x+1+Z. Nice! --pma (talk) 14:01, 15 May 2009 (UTC)

Sigh. Haste makes waste. Michael Hardy (talk) 00:01, 18 May 2009 (UTC)

Does mathematics exist in an empty universe?

I am struggling with this question for a long time and at last decided to ask it here. The subject line says it all. Suppose the universe was absolutely empty. Will mathematical concepts make any sense in such a universe?

thanks for your help,

Yes they would. Mathematics centers around formal systems, which are just a set of axioms and rules of inference. They can certainly 'exist' in some platonic sense.

No they wouldn't. Formal systems with some degree of consistency and usefulness require a certain amount of creativity to develop. They also wouldn't make "sense", in the sense that they wouldn't have any kind of useful real-world interpretation.

That is, of course, just the tip of the iceberg on the debate of whether mathematics 'exists' in a platonic sense outside of our universe. You're welcome. --COVIZAPIBETEFOKY (talk) 14:05, 13 May 2009 (UTC)

Assuming that no empty universe exists, the answer is both yes and no, because a false statement implies any statement. So both: "If the universe is empty then mathematics does exist", and: "If the universe is empty then mathematics does not exist", are logically true. See material conditional. See however also counterfactual conditional. Bo Jacoby (talk) 15:18, 13 May 2009 (UTC).

It is an interesting question in the philosophy of mathematics, and I'm not sure it has a universally accepted answer. You can make the question more extreme, as well - if there was no universe (rather than there being a universe, it just being empty) would there be mathematics? Mathematics certainly exists outside the universe to some extent - you can discuss mathematical concepts that don't model any physical thing and they can even be quite useful in solving problems where the problem and solution are described in terms of other, more physical, mathematics. Whether it can be divorced from the universe entirely it a difficult question. I'm tempted to say it can be, but I'm not sure of all the philosophical implications of that, having never studied it in any depth. --Tango (talk) 15:30, 13 May 2009 (UTC)

No, mathematics is just a set of (sets of) axioms and their logical theory. It exists all on its own, without the need for any physical reality at all. If this is relevant is akin to the old question if a falling tree makes a noise if nobody is present to listen. --Stephan Schulz (talk) 15:38, 13 May 2009 (UTC)

If one identifies mathematics with the logical implications of certain axiomatic choices, then one can certainly argue that those axiomatic choices are chosen based on physical observations. One could then argue that a universe which is empty or sufficiently different from our own would neither construct nor find useful the mathematics of our universe. Dragons flight (talk) 15:52, 13 May 2009 (UTC)

That's certainly the view I'm erring towards, but I don't think it is universally held. --Tango (talk) 16:02, 13 May 2009 (UTC)

"God made the integers ;-)". I agree that the choice of axiom systems we are interested in is often guided by our experiences with physical reality. But the existence of these theories is unaffected. I'd make the point that logic as the language of maths is universal (or should that be "suprauniversal"?), and you can easily (*) use that to argue about all possible finite or enumerable axiomatizations. (*) for suitably weird values of "easy".... --Stephan Schulz (talk) 16:04, 13 May 2009 (UTC)

LOL. "But the existence of these theories is unaffected." Does a theory "exist" even if no intelligent being in your entire universe can concieve of it.  ;-) Personally I'd lean towards no. Dragons flight (talk) 16:13, 13 May 2009 (UTC)

Definitely yes! No question! I can write a program that enumerates all finite axiom sets, and all enumerable ones in the limit. Thus, the existence of these axiom sets (and hence the implied theories) is inherent in this one program. --Stephan Schulz (talk) 16:19, 13 May 2009 (UTC)

That's just begging the original question, your program does not exist in the empty universe either. — Emil J. 16:32, 13 May 2009 (UTC)

In addition to the problem that you aren't in the relevant universe, I'd love to know how you plan to enumerate axioms that you are incapable of conceiving. Dragons flight (talk) 16:40, 13 May 2009 (UTC)

Easy. I enumerate all strings over a suitable alphabet. That includes all valid axiomatizations (and a lot of garbage, ok). The harder part is to enumerate the infinite sets... --Stephan Schulz (talk) 16:47, 13 May 2009 (UTC)

And what if your alphabet is incapable of expressing certain axioms? The judgment that it is "suitable" is still constrained by a set of conceivable things. Dragons flight (talk) 16:55, 13 May 2009 (UTC)

That comes down to the thesis of Turing and Church (and the whole sheebang coming with it), which implies that any alphabet with 3 characters (2 real ones and a blank) is enough to encode any problem "efficiently". It's certainly enough to describe mathematics as we know it. --Stephan Schulz (talk) 17:35, 13 May 2009 (UTC)

As discussed at Church-Turing thesis, though it is established that "computability" can be expressed in many forms, the underlying conception of what computation is remains a physically motivated assumption (or in some views an axiom). The underlying issue has never actually been expressed in a way that is provable. Hence people in a different universe could very well have a different intuition for what computation is and hence arrive at different program for expressing / exploring the axioms of mathematics. If they understand computation differently, then they may ignore (or be unable to express) axioms we take for granted. Dragons flight (talk) 18:18, 13 May 2009 (UTC)

You might as well ask whether, in a hypothetical universe, the English language and the color blue exist. It comes down to some philosophical argument about whether the English language, mathematics, and the color blue can exist without anyone actually speaking English, without any object actually colored blue, and without any person actually studying mathematics. There are philosophical arguments on both sides about the sense in which these abstract objects exist, and there is not any definitive answer. — Carl (CBM · talk) 19:23, 13 May 2009 (UTC)

Indeed. If you are a Platonist or a formalist then you believe that mathematical objects and results are not dependent on the contents of "reality", so hypothesising an empty universe has no effect on the "existence" of mathematics. If you are a intuitionist or a constructivist then you believe that mathematical objects are the result of physical (or at least mental) processes; as these cannot exist in a empty universe then an empty universe contains no mathematics. Gandalf61 (talk) 11:07, 14 May 2009 (UTC)

If a question cannot be asked experimentally, you do not need to answer it theoretically (said Werner Heisenberg). Bo Jacoby (talk) 12:29, 14 May 2009 (UTC).

I suspect that the original question is made ambiguous in first place by the unspecified meaning of the verb to exist in the question itself. Therefore let's say: A) mathematics A-exists in an empty universe and B) mathematics does not B-exist in an empty universe, where the meaning of A-existence and B-existence is chosen in such a way that statements A) and B) are true by definition. --pma (talk) 15:13, 14 May 2009 (UTC) ;-)

The question you are asking is about a philosophical view called mathematical platonism. Some people believe in it, others don't. 207.241.239.70 (talk) 04:22, 15 May 2009 (UTC)

Triangle areas

If a triangle has semiperimeter s and interior angles a, b, and c, what is its area? --Lucas Brown 42 (talk) 16:20, 13 May 2009 (UTC)

Please do your own homework.

Welcome to Wikipedia. Your question appears to be a homework question. I apologize if this is a misinterpretation, but it is our aim here not to do people's homework for them, but to merely aid them in doing it themselves. Letting someone else do your homework does not help you learn nearly as much as doing it yourself. Please attempt to solve the problem or answer the question yourself first. If you need help with a specific part of your homework, feel free to tell us where you are stuck and ask for help. If you need help grasping the concept of a problem, by all means let us know.  Buffered Input Output 16:42, 13 May 2009 (UTC)

This is not homework - this is purely for personal interest. --Lucas Brown 42 (talk) 16:52, 13 May 2009 (UTC)

It should be easy to derive from Heron's formula and the law of sines. — Emil J. 16:57, 13 May 2009 (UTC)

(ec) You can use the law of sines together with the semiperimeter to get the side lengths and then use $\mathrm {area} =AB\sin {c}$ to get the area. --Tango (talk) 16:59, 13 May 2009 (UTC)

Do you mean "$\mathrm {area} =AB\sin {c}/2$?" --Lucas Brown 42 (talk) 17:03, 13 May 2009 (UTC)

Yes. And the result is ${\frac {2s^{2}\sin a\sin b\sin c}{(\sin a+\sin b+\sin c)^{2}}}$. — Emil J. 17:12, 13 May 2009 (UTC)

Um... no, I'm using the new fangled definition of area that is twice as big as the old one, get with the times! ;) --Tango (talk) 18:00, 13 May 2009 (UTC)

Note to the literal-minded: Tango's last comment was with tongue in cheek. The formula that says area = AB sin c is for the area of a parallelogram given the lengths A and B of its adjacent sides and the angle c between them. The area of the triangle is half of that, since the triangle is half of the parallelogram. Michael Hardy (talk) 21:48, 13 May 2009 (UTC)

The winking emoticon was supposed to indicate that. What actually happened was that I was concentrating so much on getting the mathrm bit right in the latex that I forgot to include the fraction (which was the whole reason for writing it in latex in the first place!). --Tango (talk) 21:52, 13 May 2009 (UTC)

I don't see any winking emoticon or any hint of one. Michael Hardy (talk) 01:15, 14 May 2009 (UTC)

Oh.......... that thing. I hadn't noticed it until I looked for it. Michael Hardy (talk) 01:15, 14 May 2009 (UTC)

Thanks! --Lucas Brown 42 (talk) 17:18, 13 May 2009 (UTC)

Finding an approximation to a linear system

I have this equation-
Ax = y
Where A is a rational 10*10 matrix, and x and y are vectors in R¹⁰. I know A and y, I don't know what x is equal to. I also know that there is no x where Ax equals exactly y.
I want to find the vector x' such that Ax' is as close as possible to y. Meaning that (Ax' - y) is as close as possible to (0,0,0,...0).

(If it helps I can add that I also know that A has no rows/columns full of 0's).

You want the Moore–Penrose pseudoinverse; check in particular the Applications to linear systems. --pma (talk) 17:35, 13 May 2009 (UTC)

Maybe I'm daft, but shouldn't a linear system of 10 equations in 10 variables always have at least one exact solution? --Stephan Schulz (talk) 17:49, 13 May 2009 (UTC)

I would have thought so... If A is singular, there wouldn't be a unique solution, but there should be a solution. --Tango (talk) 18:05, 13 May 2009 (UTC)

No. If A is not invertible, then the map $x\mapsto Ax$ is not surjective, so there exist y's such that no x solves the equation. Aenar (talk) 18:12, 13 May 2009 (UTC)

Indeed, I stand corrected. Thank you! --Tango (talk) 18:34, 13 May 2009 (UTC)

Me too, after thinking of the trivial example of A=(0), y=(1). But what's the correct form of my solid pseudo-knowledge about systems of linear equations and their solutions? --Stephan Schulz (talk) 20:23, 13 May 2009 (UTC)

The number of solutions to a linear system is always 0, 1, or infinite. For A m×n: if m is greater than, equal to, or less than n, you get those numbers of solutions for almost every $\mathrm {A} x=y$, respectively. AllMost combinations are possible, though, for at least some choices of y. If A has full column rank (implying $m\geq n$), the $\infty$ case is ruled out (the transformation is injective); otherwise that case is guaranteed to occur for some y. If A has full row rank (implying $m\leq n$), the 0 case is ruled out (it's surjective); otherwise it is guaranteed for some y. (Note that for $m=n$ the only choices are "unique solution" (invertible A) or "0, 1, or many solutions, depending on y" (singular A).) --Tardis (talk) 21:10, 13 May 2009 (UTC)

That "All" was incorrect — at least one combination of shape and solution count can't happen. In particular, if A hasn't full column rank, it has a null space and so can't have unique solutions for any y; some y may have 0 solutions (unless A has full row rank), and all the rest have many. This implies that "wide" matrices ($m>n$) can't have unique solutions. I don't think that "tall" matrices have any such categorical exclusions, but I'm suspicious of the asymmetry. --Tardis (talk) 21:21, 13 May 2009 (UTC)

The question is asymmetric (Ax=y and xA=y are very different equations), so the solutions being asymmetric isn't that surprising. --Tango (talk) 21:49, 13 May 2009 (UTC)

That is quite true, but I think the asymmetry really arises because the forward transformation from x to y always gives exactly one y, regardless of how well-defined (or well-behaved) its inverse is. Meanwhile, I messed up again: for no y does a singular A yield a unique x (because, again, it must have a null space). --Tardis (talk) 17:26, 14 May 2009 (UTC)

For more advanced functional analysis kinf of thing, look at the Fredholm alternative (Igny (talk) 21:53, 13 May 2009 (UTC))

OK, let's go back to the original request that was very clear. Given an m times n matrix A (a singular 10x10 matrix in the OP), and given y in R^m, we want a vector x in Rⁿ minimizing ||Ax-y||. This is an elementary convex problem; it always has a solution, that you find differentiating wrto x the quadratic polynomial ||Ax-y||²=(Ax,Ax)-2(Ax,y)+(y,y) : by convexity, the minimizers are exactly the critical points, thus solve the square linear system: A^TAx=2A^Ty. Moreover, if the system has a kernel, the solution is of course not unique: to make a canonical choice one chooses the vector x of minimal norm in the affine space of the solutions of A^TAx=2A^Ty, that is, among all minimizers of ||Ax-y||. This choice exhibites x as linear function of y: that is y=A⁺x. The corresponding matrix A⁺ is the so called Moore–Penrose pseudoinverse of A; you can do the same in the context of Hilbert spaces and linear operators. The details are given in the links I provided, just click on it! --pma (talk) 06:44, 14 May 2009 (UTC)

7 tens

How many three digit numbers having 7 tens. —Preceding unsigned comment added by True path finder (talk • contribs) 18:43, 13 May 2009 (UTC)

for the ones starting with a 1, the possibilities are "170, 171, 172, 173, 174, 175, 176, 177, 178, 179" and you have the same number of possibilities for all the starting digits, of which there are nine (1, 2, 3, 4, 5, 6, 7, 8, or 9), so count the list and multiply it by 9.

The reason there aren't 10 starting digits is because "070" and so on aren't three-digit numbers. 79.122.61.98 (talk) 20:00, 13 May 2009 (UTC)