Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

August 27

How do you show that two groups are not isomorphic

It's easy enough to show when two groups are isomorphic, (just find an isomorphism) but how do you show that two groups (which have the same cardinality) are not isomorphic? (Specific example: the cosets of $\{1,-1,i,-i\}$ and $\mathbb {C} ^{\times }$) Widener (talk) 02:04, 27 August 2012 (UTC)

I'm not sure what you mean by the notation $\mathbb {C} ^{\times }$, but in general, you show non-isomorphism between groups (or structures in general) by finding some property of the structures that's definable from the structure's non-logical symbols, and showing that one structure has the property and the other one doesn't. For example, for groups, as a trivial example, you might show that one group is abelian and the other is not, or one group has a finite subgroup (not counting the trivial one) and the other doesn't, or.... --Trovatore (talk) 02:27, 27 August 2012 (UTC)

(I should say, this doesn't always work. Sometimes two structures might be elementarily equivalent, but still not isomorphic. In that case, you have to think of something else — there's no general boilerplate argument as far as I know.) --Trovatore (talk) 02:40, 27 August 2012 (UTC)

There can be no boilerplate (at least for groups given in presentations) because the Group isomorphism problem is undecidable. Staecker (talk) 11:37, 28 August 2012 (UTC)

Thanks fur the help, but I still can't think of any way for my particular example. $\mathbb {C} ^{\times }$ means the group of complex numbers except zero endowed with multiplication. Widener (talk) 04:42, 27 August 2012 (UTC)

As $\mathbb {C} ^{\times }=(\mathbb {R} _{>0},\cdot )\times S^{1}$ for $S^{1}$ = unit circle, are you looking for a proof that $S^{1}$ is not isomorphic to the factor group $S^{1}/\{\pm 1,\pm i\}$? —Kusma (t·c) 08:47, 27 August 2012 (UTC)

(As these groups are isomorphic, that is going to be difficult). —Kusma (t·c) 08:56, 27 August 2012 (UTC)

They are isomorphic? What's the isomorphism? Widener (talk) 09:00, 27 August 2012 (UTC)

Think of it this way: $S^{1}$ is the unit circle. The factor group is the same circle, wrapped around four times. Work from there. --Trovatore (talk) 09:38, 27 August 2012 (UTC)

See Group cohomology. — Fly by Night (talk) 23:22, 30 August 2012 (UTC)

Isomorphic

Lets $A$ be the group of all matricies of the form ${\begin{bmatrix}a&0\\0&b\end{bmatrix}}$, $B$ the group of matrices of the form ${\begin{bmatrix}1&c\\0&1\end{bmatrix}}$ and $C$ the group of matrices of the form ${\begin{bmatrix}a&c\\0&b\end{bmatrix}}$. Show that $A\times B$ is not isomorphic to $C$. — Preceding unsigned comment added by Widener (talk • contribs) 08:59, 27 August 2012 (UTC)

I would ask you again to show how far you've gotten, and your reasoning processes so far. --Trovatore (talk) 09:03, 27 August 2012 (UTC)

These "show that X is not isomorphic to Y" questions are basically just guess and check as far as I can tell Widener (talk) 09:09, 27 August 2012 (UTC)

$\left({\begin{bmatrix}a&0\\0&b\end{bmatrix}},{\begin{bmatrix}1&c\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}d&0\\0&e\end{bmatrix}},{\begin{bmatrix}1&f\\0&1\end{bmatrix}}\right)=\left({\begin{bmatrix}ad&0\\0&be\end{bmatrix}},{\begin{bmatrix}1&c+f\\0&1\end{bmatrix}}\right)$

${\begin{bmatrix}g&h\\0&i\end{bmatrix}}{\begin{bmatrix}j&k\\0&l\end{bmatrix}}={\begin{bmatrix}gj&gk+hl\\0&il\end{bmatrix}}$

Widener (talk) 09:13, 27 August 2012 (UTC)

Exactly one of the two groups is abelian. —Kusma (t·c) 09:45, 27 August 2012 (UTC)

Cosets

If $H$ is not normal, show that there exist two left cosets of $H$ whose product is not a coset.

This is my reasoning that it cannot be a left coset: Since $H$ is not normal, there exists $b\in G$ such that $bH\neq Hc$ for any $c\in G$. Therefore, $aHbH\neq a(cH)H=acH$. But any left coset can be written in the form $acH$ so we know $aHbH$ cannot be a left coset if $H$ is not normal.

I cannot see an analogous proof to show that it cannot be a right coset though; I tried a different approach: starting with $aHbH=Hc$ and deriving that H is normal but that doesn't seem to work either. Widener (talk) 09:29, 27 August 2012 (UTC)

I don't see why your second inequality follows from the first. I think you're taking the wrong approach here; you've found the right $b$, but you haven't taken any care in choosing which $c$ to use. You should choose a particular $c$.

Remember that the definition of normality isn't just that $bH=Hc$ for some $c$, but rather that $bH=Hb$. So since $H$ isn't normal, we know that $bH\neq Hb$. While this is weaker than what you said earlier, the specificity can help guide your choice of cosets.

For showing that the product isn't itself a coset, your argument should take the following form: "If it were any coset (left or right), it would need to be ... But it can't be that, because ..."--121.73.35.181 (talk) 11:14, 27 August 2012 (UTC)

August 28

Is this a Topology?

Hi, I have tried to define a topology in order to examine a defenition I have read in an article. As far as I can see it meets the requirements of the definition af a topology but I want to be sure. So, here is my definition and I would love to have your opinion: The space X is: (n is natiral) $\{(0,0)\}\cup \{(1,1),(1,1/2),(1,1/3)...,(1,1/n)...\}\cup \{(1/2,1),(1/2,1/2),(1/2,1/3)...,(1/2,1/n)...\},...,\cup \{(1/n,1),(1/n,1/2),(1/n,1/3)...,(1/n,1/n)...\}\cup ,...,\cup \{(0,1),(0,1/2),(0,1/3)...,(0,1/n)...\}$ The Topology is: points of the form $\{(1,1),(1,1/2),(1,1/3)...,(1,1/n)...\}\cup \{(1/2,1),(1/2,1/2),(1/2,1/3)...,(1/2,1/n)...\},...,\cup \{(1/n,1),(1/n,1/2),(1/n,1/3)...,(1/n,1/n)...\}$ are open sets. Open neighborhood of the points $\{(0,1),(0,1/2),(0,1/3)...,(0,1/n)...\}$ are intersection of X with half open segments of the form $\{[0,1/n)\}$ on the lines x=1/k and an open neighbothood of $\{(0,0)\}$ is $\{(0,0)\}$ union with open neigborhoods of $\{(0,1),(0,1/2),(0,1/3)...,(0,1/t)...\}$ wher t<1/n for some natural n. It seems to me that is is closed to infinite unions and finite intersections and I add to this set X inself and $\phi$. Is this a Topology??? Thanks!!! PS: What is the Latex command for a new line??? — Preceding unsigned comment added by FunctionSpace (talk • contribs) 06:26, 28 August 2012 (UTC)

It's a little hard to follow. Are the elements of X certain points in R², or are they themselves intervals from the real line? It might be easier if you could say what the idea is in words, or draw an ASCII picture or something (if you put a space before every line, MediaWiki will treat it as monospace verbatim, so ASCII pictures are feasible). --Trovatore (talk) 06:45, 28 August 2012 (UTC)

Here are links to pictures I drew. In the first, the red points are the points of X. and the second third and fourth show all three types of basic open sets of X http://freepicupload.com/v-356examp1.png http://freepicupload.com/v-119examp2.png http://freepicupload.com/v-382examp3.png http://freepicupload.com/v-355examp4.png Thanks!!! — Preceding unsigned comment added by FunctionSpace (talk • contribs) 10:03, 28 August 2012 (UTC)

Yes, I think so. I haven't written it down and been careful about it, but it appears to me that you have specified a base for a topology — given any two basic open sets, and any point in their intersection, there's a basic open set that contains that point and is contained in the intersection. Therefore the collection of all unions of the basic open sets thus specified is a topology.

There are nine cases, I guess, for the intersections, reduced to six by symmetry, but really the only one that's at all subtle is the case of two basic open sets that contain (0,0) and you're looking for a basic open set containing (0,0) that's contained in the intersection. And that one's not very subtle either. --Trovatore (talk) 10:36, 28 August 2012 (UTC)

(Note to anyone who might be checking the links from work: This seems to be a free site that tries to get your attention to check out the rest of it; haven't worked out how it's monetized. But in any case I saw one or two shots that might be mildly problematic depending on where you work.) --Trovatore (talk) 10:40, 28 August 2012 (UTC)

I think it works out to be just the ordinary topology on R², restricted to X. --Trovatore (talk) 10:55, 28 August 2012 (UTC)

No, I meant to make it different. the difference is, an open neighborhood of (0,0) can be the set which is shown in here http://freepicupload.com/v-897examp5.png this set can not be induced from R^2.. Do you still agree that what I defined is a topology? Thanks!!! --FunctionSpace (talk) 11:24, 28 August 2012 (UTC)

I can't find your picture, but yes, I think you're right, if you take a basic open set containing (0,0), where the heights of the intervals go to zero as you move left, that set is not open in the usual topology. And yes, I still think it's a topology. --Trovatore (talk) 19:38, 28 August 2012 (UTC)

Yes, this is exactly what I meant. My problem is, that, it seems to me that this space is sequential [[1]], But not Pytkeev. (A space is Pytkeev if every point in $x\in {\overline {A\setminus \{x\}}}$ has a $\pi$-net (a countable familly of infinite sets such that every neihborhood of x contains at least one set of this familly) --FunctionSpace (talk) 20:36, 28 August 2012 (UTC)

20.

This is from Stein and Shakarchi:
Show that $\max _{0<x\leq \pi /N}{\frac {1}{2}}\int _{0}^{x}\left({\frac {\sin((N+1/2)t)}{\sin(t/2)}}-1\right)dt=\int _{0}^{\pi }{\frac {\sin t}{t}}dt$
Is this statement even true? It looks like you can always make the left hand side bigger by making N bigger, so there is no maximum. This is because the value for x which maximizes the LHS given a particular N is smaller as you make N bigger. Widener (talk) 16:30, 28 August 2012 (UTC)

Should there be a $\lim _{N\to \infty }$? If so then this holds up empirically. Not sure I get your argument; with larger N the integrand is larger but goes over a smaller interval, so the total remains roughly the same and converges to the specified value. -- Meni Rosenfeld (talk) 09:35, 29 August 2012 (UTC)

That's what I thought, but none is present. It's a supremum, not a maximum (where the supremum is taken over x and N). Widener (talk) 16:52, 29 August 2012 (UTC)

${\frac {\sin({\frac {N+1}{2}}t)}{\sin(t/2)}}-1$ may be negative. Likely, t = x (where the maximum is reached) is the first point where it is equal to 0, because it decreases for 0 < t < ⁠π/N + 1⁠ . Incnis Mrsi (talk) 11:24, 29 August 2012 (UTC)

August 29

Interesting curves where θ = f(r) ?

I'm testing a program I've written which (among other things) graphs polar equations where the angle is a function of the radius. So far all I've tested is θ = r, which is just a basic spiral. Anyone have anything more interesting for me to try ? StuRat (talk) 12:41, 29 August 2012 (UTC)

You can try $r^{2},\ {\sqrt {r}},\ \exp(r)$. If you had $r=f(\theta )$ you would have some nicer options. -- Meni Rosenfeld (talk) 14:21, 29 August 2012 (UTC)

I have both. For r = f(θ) I found some nice roses and heart plots, the last of which looks like something right off a valentine. StuRat (talk) 14:34, 29 August 2012 (UTC)

theta = 2 pi r/(r-1) Count Iblis (talk) 16:00, 29 August 2012 (UTC)

theta = 2 pi sin(r) Count Iblis (talk) 16:10, 29 August 2012 (UTC)

I like that last one, since it's the only one which isn't some type of spiral. StuRat (talk) 03:29, 30 August 2012 (UTC)

$\theta =\pm \arccos {\frac {r^{2}+d^{2}-m^{2}}{2rd}}$ for $0<m<d$ is a circle with radius m and the center d apart from the coordinate system's pole. --CiaPan (talk) 06:14, 30 August 2012 (UTC)

How can the center be a single variable "d" ? Isn't it always 2 coords in 2D, either (x,y) or (r,θ) ? StuRat (talk) 10:13, 30 August 2012 (UTC)

Sorry for my poor English, I meant the distance from the pole to the circle's center equals d. CiaPan (talk) 11:12, 30 August 2012 (UTC)

Thanks for the clarification. StuRat (talk) 18:58, 30 August 2012 (UTC)

Rose (mathematics) expands on the roses mentioned above.--Salix (talk): 10:33, 30 August 2012 (UTC)

Conic sections have general equation in polar coordinates
    $r={\frac {l}{1+e\cos \theta }}$
(with the pole being the section's focus), see Conic section#Polar coordinates. Solving for θ results in
    $\theta =\pm \arccos {\frac {l-r}{er}}$
(except the circle, which has e=0). --CiaPan (talk) 11:48, 30 August 2012 (UTC)

Isn't that a division by zero error ? StuRat (talk) 18:58, 30 August 2012 (UTC)

Congratulations! You've discovered the asymptote through numerical experimentation! Nimur (talk) 20:48, 30 August 2012 (UTC)

Asymptotic to a circle ? StuRat (talk) 06:42, 31 August 2012 (UTC)

August 30

Every nonfinitely generated abelian group must contain one of... (resumed)

I asked this question, and got one useless response (that misunderstood the question). Here it is my question, slightly revised to clarify, and my attempt to answer my own question.

Is there any list of relatively simple nonfinitely generated abelian groups, such that any arbitrary nonfinitely generated abelian group must contain one of the groups in the list as a subgroup?

An attempt to answer my own question. I believe the following is such a list, except I'm unsure about the last point. Let $A$ be an abelian group:

Case 1: $A$ contains an infinite sequence of divisible elements, ie, a sequence $x_{1},x_{2},\cdots$ such that $\langle x_{i}\rangle \subsetneq \langle x_{i+1}\rangle$. Then $\langle x_{1},x_{2},\cdots \rangle$ is isomorphic to a subgroup of $\mathbb {Q}$ or $\mathbb {Q} /\langle 1\rangle$.

Case 2: $A$ does not contain such an infinite sequence, and its torsion group is not finitely generated. Then by CRT, only finitely many primes occur as the order of some element, because otherwise every finite order element is divisible. One of those primes must occur infinitely often, because the elements of order $p^{i}$ generate the torsion subgroup, again by CRT, and if, for such a prime $p$, there are only finitely many elements of order $p$, then it's not to difficult to show, using the classification of finitely generated abelian groups, that there must be an element of order $p$ which begins a sequence of the form in case 1. Then countably infinitely many elements of order $p$ generate a vector space over $\mathbb {F} _{p}$ of countably infinite dimension - ie, $\left(\mathbb {Z} /p\mathbb {Z} \right)^{\aleph _{0}}$.

Case 3: Otherwise, must $A$ necessarily contain a direct sum of countably many copies of $\mathbb {Z}$?

Thanks for anyone who happens to know, or be able to work through the math and make any additional arguments necessary! --70.116.7.160 (talk) 14:01, 30 August 2012 (UTC)

August 31

volume

What is the volume (ounces or mls) in a fifth of whiskey? — Preceding unsigned comment added by 71.182.193.144 (talk) 00:33, 31 August 2012 (UTC)

It depends on the mixture, the temperature, the altitude of the sample and your position on the Earth. Moreover, it depends on the orbit of the Earth around the Sun, and on the Sun's motion through our galaxy. All of these things affect the volume. — Fly by Night (talk) 00:57, 31 August 2012 (UTC)

How density varies would only matter if a fifth was a unit mass. It is not, it's a unit of volume. See below. Therefore, if the number of fifths goes up for a given mass, so does the number of ounces and milliliters, in proportion, such that the number of ounces or milliliters in a fifth remains constant. (Note that I didn't engage in a personal attack just because you gave a poor answer.) StuRat (talk) 02:20, 31 August 2012 (UTC)

Not a personal attack, but a plain statement of fact - the first response was inappropriate, being patronising, belittling and worst of all, plain wrong. If you can't give an accurate, polite and helpful answer then don't give any.←86.139.64.77 (talk) 20:46, 1 September 2012 (UTC)

See Fifth (unit). hydnjo (talk) 01:00, 31 August 2012 (UTC)

Resolved

Solving a summation

I don't have the math background to know where to start with this. I have a summation of the usual sort with n on the top and i=0 on the bottom... and then the actual summation formula itself is a constant with i as an exponent. The problem is, I don't want to know what the answer is at a given n, I want to know what n is when I reach a given constant. I want to solve for the n. How do I go about figuring this out? Broba (talk) 07:42, 31 August 2012 (UTC)

Here's a simpler example of what I'm trying to do to illustrate the basics of what I can't figure out: Summation with i=0, the formula inside the summation is 3 * i. I want to know at what value of n the summation equals 18. What's the method you use to arrive at the value of n? Is it possible to do the same if the summation equals say 17? Broba (talk) 07:47, 31 August 2012 (UTC)

Quite simple to do with a computer program, although your example is easy enough to do by hand:

i  3i   ∑
---------
0   0   0
1   3   3
2   6   9
3   9  18

So we don't get 17 for the summation, assuming n is an integer. I don't think non-integer solutions for n (like n = 8/3) make sense in a summation, since, if you add in i = 8/3, how can you justify not adding in i = 7/3, as well, along with the infinite number of other non-integers ? StuRat (talk) 07:58, 31 August 2012 (UTC)

Well, another way to do something like this would be to close form solution of the summation as a function of n (if possible) and then setting it equal to whatever number you want (17 in this case) and solving for n. Like StuRat said, there is no guarantee if n would be a natural integer or not. Are you looking only for natural integers? To illustrate with your example, let $f(n)=\sum _{i=0}^{n}3i={\frac {3n(n+1)}{2}}$. Then you want to solve for n where ${\frac {3n(n+1)}{2}}=17$ and in this case we have a simple quadratic and the answer is $n={\frac {-3+{\sqrt {417}}}{6}}=2.90343...$. There is another solution too which is negative which we ignore. As you can see this is close to n=3 which would give us the sum equals 18. Is this what you are kind of looking for? Someone here might be able to help you furthermore if you give us the sum and how/where this problem arises.68.121.32.26 (talk) 10:32, 31 August 2012 (UTC)

But are non-integer solutions actually allowed in a summation ? To me it doesn't make any sense. As I noted before, if you sum in one non-integer value (the final one), then you would have to sum in all non-integer values, wouldn't you ? This would typically mean the solution is either positive infinity or negative infinity, regardless of n, which isn't very useful. StuRat (talk) 20:22, 31 August 2012 (UTC)

For an exponential function, use $\sum _{i=0}^{n-1}a^{i}={\frac {1-a^{n}}{1-a}}$ Ssscienccce (talk) 15:27, 31 August 2012 (UTC)

Thank you both 68.121.32.26 and Ssscienccce. That is the approach I'm trying to take, although I think my problem has additional complexities. What is the name of this sort of math... I had a lot of trouble knowing what to search for for this.

The complications I have is that I tried to use the exponential function that Ssscienccce gave but I have some coefficients that I believe are screwing it up. Non integers are fine (expected probably). This is specifically the form of the problem I'm trying to solve (and yes I could estimate it with a program, I'm not interested in that... I'm looking for the method to arrive at the answer more than any specific answer):

$\sum _{i=0}^{n}100e^{0.05n}=5000$

I'm trying to solve for $n$ here of course. As an aside, I have a hunch there's some analogy to this kind of problem in physics but I haven't grasped exactly which yet. Broba (talk) 17:47, 31 August 2012 (UTC)

Oh I got it now. I just found another version of Ssscienccce's explanation with coefficients. Thanks for you help. Broba (talk) 21:56, 31 August 2012 (UTC)

Resolved

Didn't you mean $\sum _{i=0}^{n}100e^{0.05i}=5000$ ? Bo Jacoby (talk) 06:56, 1 September 2012 (UTC).

compare all to all

I have a set S and I want to compare every item in S to every other item in S. The comparison is a simple function like f(S1,S2). I claim that it is impossible to do this without S*(S-1) comparisons. I've been told it can be done with S*log(S) comparisons, but not how it can be done that way. Can anyone explain to me how that is possible? — Preceding unsigned comment added by 128.23.113.249 (talk) 14:29, 31 August 2012 (UTC)

Use any of the worst-case $n\log n$ comparison sorts from the table in sorting algorithm#Comparison of algorithms, such as merge sort. Once you sort the set, you can compare any two items by comparing their index in the sorted set without invoking f. This all assumes that f is a bona fide total order.—Emil J. 14:41, 31 August 2012 (UTC)

Please correct me if I'm wrong, but that implies that S is sortable. I'm trying to come up with an example that shows how they are not sortable based on f. What if you have a set of people S. Then f(S1,S2) is a rating of how much S1 likes S2. We can make it simple and assume f(S1,S2)=f(S2,S1) if that is important. Then, you have a weighted graph where each node is an element in S and the edges have a weight, the value of f for the two nodes. If I use f to sort S with, say, merge sort, I won't compare every element in S to every other element and, therefore, will be missing edges in my graph. Does that make sense or am I just rambling nonsense? — Preceding unsigned comment added by 128.23.113.249 (talk) 14:59, 31 August 2012 (UTC)

Your f is not a comparison function (i.e., an indicator function of a total (pre)order). If you allow a completely arbitrary function as f, then there is of course no way of finding all its values for all pairs of elements other than checking all the |S|² pairs.—Emil J. 15:37, 31 August 2012 (UTC)

Thank you. I believe our class argument is actually an argument about how f is defined, not about the set S. It all depends on if f defines total order or just some arbitrary relationship between two items. — Preceding unsigned comment added by 128.23.113.249 (talk) 15:42, 31 August 2012 (UTC)

You may want to check out Closest pair of points problem Ssscienccce (talk) 16:19, 31 August 2012 (UTC)

solutions to an assignment

Hello I am an independent learner looking through material here: http://www.hutter1.net/ethz/uaiethz.htm and in particular trying the assignment here: http://www.hutter1.net/ethz/assign1.pdf but sadly there are no solutions to this assignment on that website. Some questions are easy math questions but some are hard. Could someone kind create solutions or refer to elsewhere? — Preceding unsigned comment added by Bulkc (talk • contribs) 18:05, 31 August 2012 (UTC)

That's a bit much to ask of us, I'm afraid. We also won't do your homework for you. However, if you do it, and post your answers here, we might be willing to check it for you and point out any mistakes. StuRat (talk) 20:28, 31 August 2012 (UTC)

Ok. The first two questions and the probability questions are easy any way. I think I can do too the question MDL-ML, part (i) of MDL-Ber and some of KC-KC myself. What about the rest? For example can you show me how to do KC-KC part (iv) which does not follow from the rest I think. Or inequality K(xy) < K(x,y) — Preceding unsigned comment added by Bulkc (talk • contribs) 20:51, 31 August 2012 (UTC)

For (iv), let $T$ be the machine that, on input $a$, first runs $U(a)$. Then, if the output is a pair $(x,f)$, runs $f$ on $x$ and outputs $f(x)$. Now, if $U(a)=(x,f)$, then $T(a)=f(x)$. This shows that $K_{T}(f(x))\leq K(x,f)$, which is less than $K(x)+K(f)$ by part (iii). Since $K\leq ^{+}K_{T}$, the result follows.

For $K(xy)\leq ^{+}K(x,y)$, let $T$ be the machine that, on input $a$, first runs $U(a)$. Then, if the output is a pair $(x,y)$, $T$ outputs $xy$. Then follow the same reasoning as above.--121.73.35.181 (talk) 00:08, 1 September 2012 (UTC)

Thank you! I can do now these questions, and some other ones, due to your advice about Turing machines. But, I am still having some trouble. What about AP-CM (ii) and (iii)? Or MDL-Ber (iii), (v) and (vi)?--Bulkc (talk) 06:14, 1 September 2012 (UTC)

Actually, I just did MDL-Ber (v) using (iv)! — Preceding unsigned comment added by Bulkc (talk • contribs) 06:32, 1 September 2012 (UTC)

Woops, had one of my inequalities backwards. Fixed.--121.73.35.181 (talk) 10:28, 1 September 2012 (UTC)

• After much work and reading through the material, I think I can solve all questions except for AP-CM. I think this is hardest. — Preceding unsigned comment added by Bulkc (talk • contribs) 02:58, 2 September 2012 (UTC)

September 1

Konig's lemma

In the proof of Konig's lemma it is mentioned that:

König's lemma may be considered to be a choice principle; the first proof above illustrates the relationship between the lemma and the axiom of dependent choice. At each step of the induction, a vertex with a particular property must be selected. Although it is proved that at least one appropriate vertex exists, if there is more than one suitable vertex there may be no canonical choice.

In the proof mentioned, it is clear that there are only finitely many such vertices to consider at any given stage.(Cf: "Every one of the infinitely many vertices of G can be reached from v1 with a simple path, and each such path must start with one of the finitely many vertices adjacent to v1."..."We may thus pick one of these vertices and call it v2." That is, the choice is being made among finitely many vertices. Why then do we need the axiom of choice or some weaker version of it to prove the lemma? Thanks--Shahab (talk) 13:07, 1 September 2012 (UTC)

I am not at all well up on this, but I believe it is because we are making infinitely many such choices. I do know that (because there is no uniform way of telling a left sock from a right sock, unlike for shoes) you need choice to get one sock from each of infinitely many pairs (apart, of course, from the fact that they are in a nice Euclidean space...) Straightontillmorning (talk) 13:39, 1 September 2012 (UTC)

Yep. You need choice to make infinitely many choices; it doesn't matter whether each of those choices is from finitely or infinitely many possibilities.--121.73.35.181 (talk) 21:02, 1 September 2012 (UTC)

This is a complete guess: if there's only one suitable vertex, you can identify it by trying out paths of increasing length for every vertex. If only one is suitable, this search will end eventually. If more then one is suitable, it won't. Ssscienccce (talk) 14:59, 1 September 2012 (UTC)

September 2

Graph theory

How many trees are there with n vertices such that each vertex has degree at most 4, if ones that are the same other than the naming of the vertices are excluded? --168.7.237.248 (talk) 04:08, 2 September 2012 (UTC)

By working out the first few terms by hand and searching the OEIS, I found A000602. -- BenRG (talk) 06:06, 2 September 2012 (UTC)

What's the closed form for that sequence? --128.42.223.234 (talk) 16:03, 2 September 2012 (UTC)

Maths and music

Hi. First of all, I want to acknowledge that the following is homework. However, I've come here because I actually don't understand the problems:

1. I'm asked to find the continued fraction for $\log _{2}(3/2)$, calculate convergents ${\frac {p_{n}}{q_{n}}}$, and then find the first $q_{n}>12$. That's all fine: $q_{n}=29$. But then "Compute the relative frequency of the fifth harmonic in equal temperament in this scale with $q_{n}$ semitones and compare to the error to 3/2 to that of our usual scale with 12 semitones." I don't understand any of this. I've tried reading a few Wikipedia articles, but it still makes no sense to me; I have no musical background.
2. And I have no idea where to begin with this one: "When building a guitar it is useful to be able to determine where to put fret i in relation to fret i + 1. Find the numerical value of the ratio of the length of the string remaining when pressing down at fret i to the distance of fret i to fret i + 1, assuming the usual 12 semitone scale and equal temperament."

Can anyone give some advice on these questions? As I said, I've tried reading a few articles, but the musical terminology is lost on me. I'd appreciate it if someone could distill these problems into a more pure mathematical form, or – just as helpfully – explain in very simple terms the music theory I need to know to comprehend them. PS: I have quoted these questions verbatim. Feeling like they're grammatically incorrect? You and me both. —Anonymous Dissident^Talk 13:36, 2 September 2012 (UTC)

What does "the first $q_{n}>12$" mean? Please, write down something like log₂ 3/2 =(some fraction with p and q). Incnis Mrsi (talk) 14:50, 2 September 2012 (UTC)

Surely that means "the value of $q_{n}$ for the least n such that this is more than 12" (I don't know continued fractions.) However, I do know what 12-semitone equal temperament is so I'll try to be helpful. Musical intervals, in terms of frequencies, are ratios. An octave corresponds to doubling the frequency. In an octave under the standard system there are 12 semitones (A-A#-B-C-C#-D-D#-E-F-F#-G-G#-A), and equal temperament divides them equally (in a logarithmic sense), so that going up a semitone is multiplies the frequency by the twelfth root of two. Presumably you are considering a twenty-nine semitone equally tempered scale so going up a semitone is multiplying by the twenty-ninth root of two. Then for the fifth harmonic, I think we're looking at perfect fifths. I can't make out harmonic series (music), but the former says that the "just" interval for a perfect fifth is 3/2 (ie the frequency goes up by that factor). In equal temperament, it's a bit wrong (because the twelfth root of two is ugly) - I don't see where the fifth harmonic comes in. For the second question, Guitar#Frets says that changing by one fret changes by a semitone. By virtue of the assumption of twelve-tone equal temperament, that means the frequency changes by (a factor of) the twelfth root of two. If you (like I was) are having trouble with parsing the sentence we want the ratio of the (remaining string when you press at the i'th fret) [i.e. that bit that vibrates to give you that note] to the (distance between the i'th and (i+1)'st). So you need to assume frequency f for the ith fret, work out how long the string needs to be, work out how long it needs to be for the next note, and hope f cancels.

I hope that helps slightly, but it probably won't. Straightontillmorning (talk) 16:09, 2 September 2012 (UTC)

Binomial process

I have a closed population which is subjected to a hazard which removes them from the population. I am modelling the number removed each month using a binomial distribution with a constant percentage hazard rate. What is the distribution of the cumulative number of removals after the first T months? I don't necessarily need an exact distribution - the population is large enough that a normal approximation should be sufficient for my purposes. Is it as simple as a mean of n*(1-(1-p)^T) and a variance of n*(1-(1-p)^T)*(1-p)^T? I know it is that simple for a Poisson process, but I suspect it doesn't work the same way for a Binomial. Thanks for your help. --Tango (talk) 17:25, 2 September 2012 (UTC)

I don't think it's a question of Poisson versus binomial. My intuition is that with a constant percentage hazard rate, the strong law of large numbers should give you a log-normal distribution in the limit of large T. Looie496 (talk) 17:46, 2 September 2012 (UTC)

Thanks, but I should have said, T is quite small. For a Poisson, the absolute rate is constant, so you can just scale it. In this case, the rate is reducing because n is reducing, so I doubt it is so simple. --Tango (talk) 18:17, 2 September 2012 (UTC)

Any single individual will have a probability of survival equal to (1-(1-p)^T). And this will be independent from all other individuals. So the whole T months period for all individuals will be n independent trials with sucess chance (1-(1-p)^T). This means that the number of survivors will be Binomially distributed with mean and variance as given in original post. Taemyr (talk) 21:24, 2 September 2012 (UTC)

Stone Cetch Compactification using ultrafilters

Hello, In this topology, I saw in a proof that: $x\in {\overline {\cup A}}$ and $x\in {\overline {\cup B}}$ implies that $(\cup A)\cap (\cup B)\neq \emptyset$. Can somone explain why this is true? since, this claim is not true in topology in general... Thanx. — Preceding unsigned comment added by General Topology (talk • contribs) 18:32, 2 September 2012 (UTC) General Topology (talk) 18:43, 2 September 2012 (UTC)