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

Mathematics desk
< May 6	<< Apr | May | Jun >>	May 8 >

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 7

Chaitin version of Gödel incompleteness theorem

Chaitin proved that for any theory that can represent enough arithmetic, there is an upper bound c such that no specific number can be proven in that theory to have Kolmogorov complexity greater than c. We can probably assume that for the fanciest mathematical theories we have (ZFC with large cardinals, or whatever) c is no larger than a few thousand. Leonid Levin observed that there is no Turing machine algorithm that, given an arbitary integer n, produces a bit string of length n whose Kolmogorov complexity is at least n/2, but it is trivial to generate such a string by rolling dice.

My question: suppose we take an axiom system like ZFC, and adjoin to it a bunch of new axioms of the form "the string xxxxxxxxx has Kolmogorov complexity at least n", where n is a large-ish number like a million, and xxxxxxxx is a bit string generated by flipping 2n coins. Of course there is some small chance that the random coin flips will generate some low-complexity strings, resulting in wrong axioms and an inconsistent theory. But assuming that doesn't happen and we get a consistent theory, is it likely to contain interesting and meaningful theorems that are independent of ZFC? 67.122.209.126 (talk) 09:12, 7 May 2009 (UTC)

It would depend on what you mean by "interesting", but there is no sign that those sorts of axioms would generate theorems that are considered interesting by most mathematicians. — Carl (CBM · talk) 11:53, 7 May 2009 (UTC)

Thanks. Levin mentions a theorem of [corrected] Barzdin, Jockusch, and Soare, which says if you start with an axiom system like PA (let's stick with arithmetic so we can say that every sentence has a truth value), then construct an independent sentence S by diagonalization, then flip a coin and adjoin either S or not-S depending on the outcome, then diagonalize the new system to get S1, flip another coin and adjoin either S1 or not-S1, etc., you end up with a theory in which almost every sentence is decidable. The obvious problem is that while the theory is guaranteed consistent (assuming PA is consistent), about half of those new axioms will be false, so the theory is unsound. The randomized axioms about Kolmogorov complexity, by comparison, aren't guaranteed to be either true or consistent, but each one is extremely likely to be true, with a lower probability bound that can be computed. I'm wondering if there's any hope of showing something like "if you do this procedure n times, you will get a theory with over 99% chance of deciding Goldbach's conjecture, and less than 1% chance of being inconsistent, and which if it is consistent is also sound".

As a general thought, I find it interesting that if there is really such a thing as a random coin flip, then the physical universe offers us an extremely large collection of easily accessible arithmetic sentences that are almost certainly true but which cannot be proved from axioms. I wonder what Church and Turing would have said about that. 67.122.209.126 (talk) 17:10, 7 May 2009 (UTC)

By the way, which paper of Levin's are you looking through? I think you have misread the thing about random completions; the result of Jockusch and Soare that I think Levin is referring to does not apply to PA, but rather to some specially constructed essentially undecidable theories. The set of completions of PA has measure 0 and so it is actually very unlikely that you would generate one by randomly flipping a coin. — Carl (CBM · talk) 17:30, 7 May 2009 (UTC)

Thanks, I guess I was mis-remembering this article by Levin, which I looked at quite a while back. 67.122.209.126 (talk) 17:48, 7 May 2009 (UTC)

bijection between RXR and R

Hi, I know this is rather trivial, but I can't seem to find (through searching or anywhere) a quick way to establish an injection from RXR to R ... I know the other direction is easy. I know #R^2 = #R, but why google keeps spitting out irrelevant results instead is beyond me. John Riemann Soong (talk) 09:18, 7 May 2009 (UTC)

Given a pair of reals (x,y), express x and y in decimal notation, and interleave the digits. You might have to be a tiny bit careful about the 0.999... problem, but I think not terribly careful — any reasonable choice will work I think; you just have to do a little bit of checking to see that that's so. --Trovatore (talk) 09:21, 7 May 2009 (UTC)

Hmmm, that's what I thought I could do. So if I have say an ordered pair (pi,e), it's valid to "interleave" the digits of pi and e (3.2174118529...)? John Riemann Soong (talk) 09:25, 7 May 2009 (UTC)

Yes. However you should handle any chain of 9's together with the following non-9 digit as a unit—do not interleave 9's from one number's expansion with digits from the other. This way you'll get a bijection R×R→R. --CiaPan (talk) 10:36, 7 May 2009 (UTC)

The main difficulty in the case of R² and R is that the bijection cannot be continuous. Once you know that you cannot have continuity, here is an easy way to get the bijection. First divide the real line into the rationals Q and irrationals I. The rationals are countable and so in bijection with Q², and the irrationals are homeomorphic to Baire space N^ω; the operation of interleaving sequences gives a continuous bijection from (N^ω)² to N^ω. — Carl (CBM · talk) 11:59, 7 May 2009 (UTC)

Another thing is -- I know this is probably /somewhere/, but it's difficult to get a "formula" for the diagonisation argument for expressing the bijection between NXN and N. I know how to construct the bijection visually, but despite my googling I can't seem to locate a rule that would take an ordered pair (x,y) on NXN and spit me out a natural number n. I know it should be rather simple...I saw it in lecture but I can't find the rule anywhere now. John Riemann Soong (talk) 09:32, 7 May 2009 (UTC)

There's any number of possibilities. One is $2^{x}\left(2y+1\right)-1$. To decode it, add 1, and divide out the largest power-of-2 factor; that's $2^{x}$, and you'll easily see how to recover y. --Trovatore (talk) 09:50, 7 May 2009 (UTC)

Another example is $f:(a,b)\mapsto [(a+b)^{2}+a+3b]/2$ which gives these results:

		a
		0	1	2	3
b	0	0	1	3	6
	1	2	4	7	11
	2	5	8	12	17
	3	9	13	18	24

CiaPan (talk) 11:10, 7 May 2009 (UTC)

Maybe you are thinking of the Cantor pairing function. 67.122.209.126 (talk) 18:17, 7 May 2009 (UTC)

As for the problem with 0.999…, I'd solve that by mapping to a subset of the reals by interleaving extra digits like mapping the pair (0.abc…, 0.def…) to the number 0.2ad2be2cf2… so the resulting digit sequence can never clash with another one; and then using that theorem about cardinality that if there's an injection from one set to another and there's one in the other way too then there's a bijection. – b_jonas 22:02, 7 May 2009 (UTC)

You're right in that the Cantor–Bernstein–Schroeder theorem states that such pair of injections implies equal cardinalities. Anyway IMHO it's quite nice to have the explicit bijection defined. Joining all 9's with the next non-nine digit allows you to achieve it — then you have eg.
    (0.139922945618, 0.007700773) ←→ 0.103099272794050671783
    (0.999995, 0.6543) ←→ 0.9999956050403
    (0.1919, 0.92929292) ←→ 0.19291929092092
    (0.919191..., 0.191919...) ←→ 0.9119191919191...
The last example shows how this method guarantees proper assignment in both directions, as opposed to a simple interleaving of single digits, which would give
    0.0790909090909... → (0.0999999.., 0.700000...) = (0.1000000.., 0.700000...) → 0.17
CiaPan (talk) 07:43, 8 May 2009 (UTC)

Can't you solve the 0.999... problem by just always using the terminating decimal expansion for such numbers? --Tango (talk) 13:13, 8 May 2009 (UTC)

What pair of numbers do you want to map to 0.191919191919... then? — Emil J. 13:23, 8 May 2009 (UTC)

I wouldn't. Presumably we are doing this to prove the two sets have the same cardinality? That doesn't require a bijection, just an injection in each direction. The obvious inclusion is sufficient for that direction, the interleaving is only required to go the other way. --Tango (talk) 13:34, 8 May 2009 (UTC)

No, we aren't. Read the sentence above, that begins with 'Anyway IMHO...' --CiaPan (talk) 10:29, 9 May 2009 (UTC)

Nope. Think about 0.4949494949... (or 0.9119191919191... or 0790909090909... mentioned before, or ANY number which has 9 on every other place from some position to infinity). --CiaPan (talk) 09:58, 9 May 2009 (UTC)

To EmilJ: It's (0.191919..., 0.919191...), of course. The first 1 goes to the first number in a pair, then each '91' alternately to both numbers. Funny, this was the first version of my one but last example, but I swapped the pair so that the result has some first digits a bit less obvious. :) --CiaPan (talk) 09:58, 9 May 2009 (UTC)

Please, if you mess with the indentation of other people's posts, at least do it properly. I was asking Tango about his proposal, I wasn't talking about your bijection. — Emil J. 14:12, 10 May 2009 (UTC)

OK. --CiaPan (talk) 14:45, 10 May 2009 (UTC)

67.122.209.126: yes, Cantor pairing function is what I meant. I have invented this function by myself, didn't now it has a name. :) CiaPan (talk) 07:47, 8 May 2009 (UTC)

why does having a unique right inverse for some function f imply bijectivity while having a unique left inverse doesn't?

Admittedly, I'm having a hard time visualising the inverses and the logical implications all at once, ahhh. John Riemann Soong (talk) 11:37, 7 May 2009 (UTC)

To figure that out, look at some diagrams like the ones at inverse function and keep in mind the definition of a right inverse. — Carl (CBM · talk) 11:46, 7 May 2009 (UTC)

Actually, having a unique left inverse does imply bijectivity, unless the domain of f is a singleton. — Emil J. 14:37, 7 May 2009 (UTC)

List of functional analysis topics

Why infinite dimensional complex analysis is not listed as nonlinear functional analysis in

http://en.wikipedia.org/wiki/List_of_functional_analysis_topics#Non-linear  ? twma 11:48, 7 May 2009 (UTC)

statistics: is 98% confidence the same as 98% of cases out a billion?

this is a simpler part of my very long question above.

This question is very simple: if I try a billion random cases (of something simple, like two coin tosses), then would choosing a metric that happens in 98% of the billion cases leave me with 98% confidence in the metric? —Preceding unsigned comment added by 94.27.231.41 (talk) 12:44, 7 May 2009 (UTC)

I think no. – b_jonas 21:57, 7 May 2009 (UTC)

1 +1 ?

1 + 1? —Preceding unsigned comment added by 77.212.224.56 (talk) 14:47, 7 May 2009 (UTC)

2. --Tango (talk) 15:08, 7 May 2009 (UTC)

11. Rarely, 0. 87.97.102.111 (talk) 16:22, 7 May 2009 (UTC)

Can easily get to 3 or more for rabbits, see Fibonacci series. Or one great big one for clouds turning into a Cumulonimbus. And of course there can be only one in Highlander (franchise) Dmcq (talk) 17:11, 7 May 2009 (UTC)

It's 1, of course. In boolean algebra. --CiaPan (talk) 17:20, 7 May 2009 (UTC)

1 + 1 = 1 therefore... I am the pope. PS The OP may find the article on 1+1 quite useless. Eric. 131.215.159.91 (talk) 18:14, 7 May 2009 (UTC)

I wish I new!! You won't believe me, but I had a password in a certain motorway site; then I forgot the password and now the only way to get back the password is to answer a secret question that I gave. The question is exactly this one!! 1+1?; and of course I had a kind of very smart answer, based on some mathematical trick, but now I cannot remember it, no way! So, I'm kind of really interested in the answers --pma (talk) 17:38, 7 May 2009 (UTC)

A window? --Tango (talk) 17:49, 7 May 2009 (UTC)

My guess is that you just typed a random answer because you thought you'll never need the security question. That's what I always do with them anyway. Just register a new account unless you have your email address set at registration and can use that to reset your password. – b_jonas 21:53, 7 May 2009 (UTC)

It depends what you mean by 1 and what you mean by + . Cuddlyable3 (talk) 23:29, 7 May 2009 (UTC)

trigonometric functions

my friend gave me these two questions. i always thought i was good at trigonometry until i came across these two DEVILS. please give some hints to solve them.

i have to prove that

1. cos(270 + x) * cos(x) [cosec(x) * cosec(x)/cot(x) – cot(270)] = 1

2. sin26x – sin24x = sin2x * sin10x —Preceding unsigned comment added by 122.50.141.64 (talk) 14:59, 7 May 2009 (UTC)

wait, i have to edit the second question

(sin6x * sin6x) - (sin4x * sin4x) = sin2x * sin10x —Preceding unsigned comment added by 122.50.141.64 (talk) 15:01, 7 May 2009 (UTC)

For the first one, write out the cosecs and cots in terms of sine, cosine and tangent, and then consider cos(270+x) and see if you can simplify it (remember, adding something to x results in shifting the graph horizontally). Once you've done all that it should be easy enough to prove. --Tango (talk) 15:17, 7 May 2009 (UTC)

To get you started on the second one, notice that sin (10x) = sin (6x + 4x). Eric. 131.215.159.91 (talk) 18:24, 7 May 2009 (UTC)

Arcs and Radii

Triangles can be defined by 2 measures, base and height, a circle by 1, radius, and a regular polygon by the number of side and side lengths. I belive that an arc is defined by the chord that forms it and the distance from the chord to the highest part of the arc. Not only that, but I think that based on those two measurements you can determine the radius of the circle that formed the arc and define the circle based on the arc.

Ok.

My question is, how do you do it? I am assuming it's possible because it seems like one of those things that math would predict, but I don't know how to do it. I was thinking to maybe form a triangle with a line tangent to the end point of the arc, and the "height of the arc" to form a triangle and find the angle where the "height" and tangent intersect, and knowing that right triangle form similar triangles when an altitude is drawn from the right angle, I would know the central angle that forms the arc and could use Thag's theorem or some other method to find the radius. I have no idea how to do that or if it is possible.

This is a question I've wondered about for a long time, and this is the first possible soulution I've thought of, can someone help?

--68.231.197.20 (talk) 15:06, 7 May 2009 (UTC)

Let c be the length of the chord, h the height of the arc, and r the radius we want to find. Consider the right triangle with vertices at the centre of the circle, one endpoint of the arc, and the middle of the chord. Its sides have lengths r, c/2, and r − h, hence by Pythagoras' theorem, r² = c²/4 + (r − h)². Solving for r, we obtain $r={\frac {h}{2}}+{\frac {c^{2}}{8h}}$. — Emil J. 15:18, 7 May 2009 (UTC)

You need three numbers to uniquely determine a triangle. If you just have base and height you could move the peak horizontally without changing those numbers and get different triangles. --Tango (talk) 15:21, 7 May 2009 (UTC)

No, three numbers for each vertex of a triangle at a paricular position in 3-D space (= nine values), but only two in the sense (up to congruence) of the question. Dbfirs 20:39, 8 May 2009 (UTC)

If all you're looking for is the area of the triangle, then two numbers are sufficient, but if you want the actual shape as well, you'll need three, as Tango said. If you want to specify the position too, then you'll need more still. —Bkell (talk) 01:33, 9 May 2009 (UTC)

Indeed. These two triangles (please pretend they are triangles, I'm sure you can tell what I'm trying to draw!) are not congruent but have the same base and height:

  /\        /|
 /  \     /  |
/____\  /____|

--Tango (talk) 13:09, 9 May 2009 (UTC)

i spent the better part of a minute trying to figure out what the second one was (i thought it was a bunch of triangles in one big triangle or something), i made a small change ot make it clearer, i hope you don't mind 94.27.136.54 (talk) 15:35, 9 May 2009 (UTC)

Apologies to Tango for doubting his answer, which was perfectly clear. (now that my brain is functioning correctly) Dbfirs 19:48, 10 May 2009 (UTC)

Harmony in music based on periodic waveforms

Forgive my forthcoming ignorance but this is driving me round the bend, so I hope it will be a simple matter to put me straight.

I'm looking at this page about musical harmony from Eric Weisstein: [1]

In particular this paragraph:

"In principle, the number of subdivisions in each octave is arbitrary. However, in order to obtain harmony, it is necessary that most notes in the scale have frequencies which differ from other notes by ratios of small whole numbers, say ${\frac {p}{q}}$. For example, let two notes in the scale have frequencies $f_{0}$ and ${\frac {p}{q}}f_{0}$. Then, when the wave producing the first note has completed q cycles, the wave producing the second will have completed p cycles. This means that the combined waveform of the two notes played simultaneously will repeat every pq cycles, producing a periodic waveform which is pleasing to the ear. If p and q are not small integers, then the time required for the pattern to repeat will be quite long, and will sound discordant. The best scale will therefore contain a large number of notes which are resonant, which is indeed the way musical harmony developed historically."

I don't understand the part about the combined waveform repeating every pq cycles. Every pq cycles of what? In terms of the original frequency, $f_{0}$, you would expect the waveform to repeat every q cycles. In terms of the ${\frac {p}{q}}f_{0}$ frequency, every p cycles.

As an example, take x = $f_{0}$, and p/q = 3/2. I'm plotting sine waves to help me think about this. We can model the two waves as sin(x) and sin(3x/2). I'm using (3x/2) since the wavelength of the higher frequency wave must be 2/3 of the original wave, so I am stretching sin(x) scale factor 2/3 parallel to the x-axis. The wave cycles match up every 2 cycles of the lower frequency wave, as expected. This creates a repeating pattern, which could also be plotted as y = sin(x) + sin(3x/2). This pattern repeats every 2 cycles of the $f_{0}$ wave again, i.e. every q cycles. Am I missing something here? I can't understand where the pq thing comes from. —Preceding unsigned comment added by 83.67.73.216 (talk) 16:25, 7 May 2009 (UTC)

As far as I follow your reasoning, I agree with you. The combined waveform repeats with period ${\tfrac {q}{f_{0}}}={\tfrac {p}{f_{1}}}$; for each big cycle, q repetitions of the first wave and p repetitions of the second wave have elapsed.
Alas, bear in mind that it is indeed true that after $p\cdot q$ cycles of any of the waves, the conjunction happens again [for the p-th time after pq cycles of the first wave, or for the q-th time after such number of cycles of the second one]. Pallida  Mors 17:38, 7 May 2009 (UTC)

Pallida - that must have been what he was getting at, thank you. I think he could have been much clearer about what he was referring to.

I think what Wesstein says is a little bit bogus. The ear is very good at distinguishing pitches and combinations of pitches, but terrible at distinguishing phase. If you simultaneously hit the C and G keys on a piano, because of equal temperament the pitch ratio is actually irrational so that thing about repeating after pq cycles never happens, but the ratio is close enough to 3:2 that it sounds like a perfect fifth. 67.122.209.126 (talk) 18:24, 7 May 2009 (UTC)

It must be said that phase differences are indeed perceived and used, essentially in tuning. See, for instance, interference beat. Pallida  Mors 18:29, 7 May 2009 (UTC)

Right, much as I'm generally happy to agree with sentences that combine Weisstein and bogus, small-integer ratios do matter. It's not because the ear picks up the phase. It's because the overtones interfere constructively.

This is an important component of barbershop music — singers learn to suppress vibrato almost to non-existence so they can sing chords with the all-important "ring". --Trovatore (talk) 22:04, 7 May 2009 (UTC)

Perhaps this article [2] could benefit from the above information and source. Cuddlyable3 (talk) 23:18, 7 May 2009 (UTC)

Weisstein is wrong about ...a periodic waveform which is pleasing to the ear. It's not the periodicity of the composite wave, it's the (relative) absence of beats between the upper partials. —Tamfang (talk) 05:21, 11 May 2009 (UTC)

Division of exponential random variables

Hi there - I was wondering if you guys could check my solution to this! I want to find the PDF of ${\frac {X}{Y}}$, where the $X/Y$ are both exponentially distributed random variables with parameter $\lambda$.

My solution:

${\frac {d}{dz}}\mathbb {P} \left({\frac {X}{Y}}\leq z\right)=\int _{0}^{\infty }{\frac {\partial }{\partial z}}\mathbb {P} (X\leq zy)P_{Y}(y)\,dy$

$=\int _{0}^{\infty }{\frac {\partial }{\partial z}}(1-e^{-\lambda yz})\cdot (-\lambda e^{-\lambda y})\,dy$

$=\int _{0}^{\infty }\lambda ^{2}ye^{-\lambda y(1+z)}$

$=\left[-\left({\frac {\lambda y}{1+z}}+{\frac {1}{(1+z)^{2}}}\right)e^{-(1+z)\lambda y}\right]_{y=0}^{y=\infty }$

$={\frac {1}{(1+z)^{2}}}$

Is this correct? Is this a familiar PDF for any function in particular? Thanks very much, Mathmos6 (talk) 18:49, 7 May 2009 (UTC)

It seems correct, with CDF F(t)=P[z<t]=1-1/(1+t). This not only has max value 1, as necessary, but it also satisfies the obvious requirement, given the identical distributions of X and Y, that F(t)=1-F(1/t). 86.132.232.103 (talk) 20:22, 7 May 2009 (UTC)

It's correct, assuming X and Y are independent. I like to be explicit about the assumption of independence. It's a Pareto distribution, except translated to the left so that the lower bound of the support is 0. Michael Hardy (talk) 21:45, 7 May 2009 (UTC)

Theorem guaranteeing minimum value of bounded function

I have a function that is strictly between 0 and 1. I need to prove that there for finite x_i = 1, 2, 3 .... there will always be a number k such that k < x for all x. I vaguely remember a theorem that says all bounded sets have a minimum value, but I don't remember what it was. —Preceding unsigned comment added by 97.77.52.150 (talk) 20:44, 7 May 2009 (UTC)

I'm afraid I don't understand your notation, so I'm not quite sure what you are asking. All bounded sets have a lower bound, by definition. If it is a finite bounded set then it will have a minimum, but that's a fairly trivial statement so I wouldn't call it a theorem. A continuous bounded function on a finite interval of the real numbers will also have a minimum. If it is over the whole of the real numbers then it may just have an infimum (greatest lower bound), but it may never attain it (it could asymptotically approach it). Is any of that what you are looking for? If not, you'll need to clarify your question. --Tango (talk) 21:16, 7 May 2009 (UTC)

When Tango said "finite interval" he meant "finite closed interval". McKay (talk) 00:42, 8 May 2009 (UTC)

He did indeed, thank you! --Tango (talk) 09:19, 8 May 2009 (UTC)

In any case, I would probably not accept "finite interval" as correct terminology, since the interval is clearly not finite except of course in the trivial case. "Bounded interval" would be more precise, and in the context of Tango's post, "Closed and bounded interval". Just to clarify for the OP, by "closed interval", it is meant an interval of the form [a, b] where a and b are real numbers, or any interval of the form [a, posinf) or (neginf, b] where a and b are real numbers. --PST 05:28, 8 May 2009 (UTC)

It's of finite measure. I believe it is a fairly standard term (although, perhaps, not universal). --Tango (talk) 09:19, 8 May 2009 (UTC)

If PST has in mind that the number of elements is not finite, I'd reply that the number of elements is not bounded either. Incidentally "finite interval" beats "bounded interval" on MathSciNet by a factor of more than 3 (but I didn't check the usage of more than a couple of instances). McKay (talk) 10:56, 8 May 2009 (UTC)

The term, "Bounded interval", in the sense that I intend, is with respect to the natural total order on the real numbers. "Finite interval", although I have seen it being used, is not standard. As evidence for this, you do not often see "finite interval" in the literature or in textbooks. Indeed, a finite interval is of finite measure (with respect to the Lebesgue measure on R), but intervals only make sense in partially ordered sets, and therefore using terminology from another category to justify terminology in order theory, is probably not the best use. PST 12:40, 8 May 2009 (UTC)

I agree, bounded is a better term, but finite is still a common one - our article (Interval (mathematics)) mentions it as a common alternative. --Tango (talk) 13:08, 8 May 2009 (UTC)

In the case of intervals of the real numbers, I'm confident that "finite interval" is significantly more common in the journals than "bounded interval". McKay (talk) 06:41, 9 May 2009 (UTC)

That does answer my question. Thanks —Preceding unsigned comment added by 97.77.52.150 (talk) 03:30, 8 May 2009 (UTC)