Wikipedia:Reference desk/Archives/Mathematics/2011 January 17

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.

January 17

continuous function on C equals zero somewhere

let f: C -> C be continuous, if there is a positive integer n and nonzero complex number C so lim_(z -> infinity) z^-n f(z) = c prove f(w)=0 for some w in C. how do I do this please help? i dont know how to start is there a theorem i shuold use? 86.30.204.236 (talk) 01:50, 17 January 2011 (UTC)

This is the penultimate step of the winding number based proof of the fundamental theorem of algebra. Does that ring any bells? Some clues can be found in the linked articles. –Henning Makholm (talk) 02:31, 17 January 2011 (UTC)

yes thankyou i got it! :) 86.30.204.236 (talk) 10:42, 17 January 2011 (UTC)

math formula to computer formula

Its a 2 part question:
1 What is the name of the process in with you transform a math equation like $x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}$ into a computer friendly version like x = (-b +- sqrt(b^2 - 4ac)) / (2a)
2 where can i find s guide that explains haw to do this to someone that doesn't already know ?
--IngerAlHaosului (talk) 05:13, 17 January 2011 (UTC)

Perhaps the article about mathematical markup languages can answer some of your questions. —Bkell (talk) 07:31, 17 January 2011 (UTC)

A lot will depend on what you want to do with the equation, if you want to display it than a mathematical markup language or a formula editor will be want you need, here the process is called typesetting.

If you want to be able to evaluate the formula then you'll either need a programming language or numerical software. The first thing you want to do is find the mathematical library and how to use it, in C its math.h in Java its java.math. You also need to know about the operators the language supports.--Salix (talk): 11:13, 17 January 2011 (UTC)

You might also want to look at how Mathmatica or Maple would deal with this. Rich Farmbrough, 02:40, 18th day of January in the year 2011 (UTC).

The free SmallBASIC is said to be good for beginners doing maths, as described here http://www.ascii-world.com/about-smallbasic 92.28.242.93 (talk) 13:53, 18 January 2011 (UTC)

Logical formula for existence of a path in a graph

First-order logic says, "there is no formula φ(x,y) of first-order logic, in the signature of graphs, that expresses the idea that there is a path from x to y. Connectedness can be expressed in second-order logic, however.

Could someone give an example of a formula in second-order logic for the existence of a path between two vertices in a graph? 85.118.15.14 (talk) 13:03, 17 January 2011 (UTC)

Assuming E(u,v) is the edge relation of the graph, and x and y are the vertices you are asking about:

$\forall X\,(x\in X\land \forall u,v\,(E(u,v)\land u\in X\to v\in X)\to y\in X).$

—Emil J. 13:31, 17 January 2011 (UTC)

Awesome, thanks. 85.118.15.14 (talk) 13:55, 17 January 2011 (UTC)

EmilJ has an slick way to do it, but you can also do it in a more direct way, because second-order logic has so much power. This can be useful when you're trying to do more complicated things. The idea is to first use a quantifier over relations to get a linear ordering of a finite subset of the graph, and then say there is a function f that maps the least element of the ordering to x, and so that f(z) and f(S(z)) are always connected, and so that the last element of the well ordering maps to y. All this can be expressed in a single second-order formula:

${\begin{aligned}(\exists X\subseteq G)&(\exists R\subseteq G^{2})(X{\text{ is finite}}\land R{\text{ is a linear order of }}X\\&\land (\exists f:G\to G)[(\forall a)(a=\min(X)\to f(a)=x)\\&\land (\forall a)(a=\max(X)\to f(a)=y)\\&\land (\forall a\in X)(\forall b\in X)(a=S(b)\to E(f(a),f(b)))])\end{aligned}}$

All the English phrases in there can be replaced with formulas; for finite, say that every map from X to itself that is injective is surjective. — Carl (CBM · talk) 13:58, 17 January 2011 (UTC)

Thanks -- quick question, though: I was wondering what the purpose of f is? That is, why not:

${\begin{aligned}(\exists X\subseteq G)&(\exists R\subseteq G^{2})(X{\text{ is finite}}\land R{\text{ is a linear order of }}X\\&\land x=\min(X)\\&\land y=\max(X)\\&\land (\forall a\in X)(\forall b\in X)(a=S(b)\to E(a,b))])\end{aligned}}$

85.118.15.14 (talk) 14:57, 17 January 2011 (UTC)

That works too. The only point I was trying to make is that you can do all sorts of relatively complicated constructions. When I wrote the formula, I was thinking of X as a finite initial segment of the natural numbers, even though it's really a subset of G. Then the function f was enumerating a path from x to y one step at a time. I wanted the function to "translate" from a natural number to an element of G. — Carl (CBM · talk) 16:13, 17 January 2011 (UTC)

Is a group uniquely determined by the orders of its elements?

Suppose G and H are finite groups, and b is a bijection from G to H preserving element order -- i.e. if g has order n, then b(g) has order n. Is b an isomorphism? I've been pondering this for a while, since we so often use element orders to show groups aren't isomorphic. I've tried to find a counterexample, but haven't been able to pin one down. I've looked at presentations: taking the crude presentation for G (i.e. a generator for each element, and a relator for each equation between three words). We can use b to induce a presentation whose relators are a subset of those in the crude presentation of H. I'm trying to see if there is a way of adding more relators to the induced presentation to reduce the size of the group it defines so it equals the order of G, without 'breaking' the structure of the orders of the group members, but managing to obtain a group which isn't isomorphic to G. Suggestions would be appreciated, Icthyos (talk) 15:14, 17 January 2011 (UTC)

If G is any nonabelian group, then the function from G to itself mapping each element to its inverse is an order-preserving bijection, but it is not an isomorphism.—Emil J. 15:25, 17 January 2011 (UTC)

And if what you really mean is "if two finite groups have the same number of elements of every order, must they be isomorphic?", then the answer is still no, the smallest counterexample being $\mathbb {Z} _{4}^{2}$ and $Q_{8}\times \mathbb {Z} _{2}$. Algebraist 00:24, 18 January 2011 (UTC)

Ah-ha, thanks to both of you. Icthyos (talk) 13:02, 18 January 2011 (UTC)

How to read aloud the usual notation for the definite integral

I'm not a native speaker. I need to give a lesson in English and I have a doubt about how to read the notation for the definite integral, i.e.:

$\int _{a}^{b}f(x)dx$

How do you read it? --Giacomo (talk) 18:08, 17 January 2011 (UTC)

I am not a native speaker of English either. But anyway, I would read it as; "The integeral of f of x from a to b." Taemyr (talk) 18:40, 17 January 2011 (UTC)

That is fine; personally I would probably change the order slightly and read it as "The integral from a to b of f of x," adding "dx" at the end if it is important to specify the variable of integration. —Bkell (talk) 19:50, 17 January 2011 (UTC)

Often people will also say "with respect to x" to indicate the variable of integration. --COVIZAPIBETEFOKY (talk) 22:57, 17 January 2011 (UTC)

Thank you. --Giacomo (talk) 08:29, 18 January 2011 (UTC)

Probability of doubling up

You and your friend repeatedly wager $1 on the flip of a weighted coin where win the flip with a probability of X. What is the probability of you hitting $N before you hit -$N? —93.139.18.238 (talk) 19:02, 17 January 2011 (UTC)

This sounds like a homework question. What have you done so far? One way to tackle this problem is to use Markov chains. —Bkell (talk) 19:48, 17 January 2011 (UTC)

(ec) If N is a power of 2, I get ${\frac {X^{N}}{X^{N}+(1-X)^{N}}}$. This looks too nice not to generalize to other prime factors. I can't immediately see any intuitive reason why such a simple formula should be expected to hold, though -- does anybody know one? –Henning Makholm (talk) 20:00, 17 January 2011 (UTC)

[ec] Denote by $f(m)$ the probability of this when you start with $m. Then $f(m)=Xf(m+1)+(1-X)f(m-1),\ f(N)=1,\ f(-N)=0$, and this can be solved to find $f(m)={\frac {(1/X-1)^{m+N}-1}{(1/X-1)^{2N}-1}}$. Putting $m=0$ gives ${\frac {1}{(1/X-1)^{n}+1}}$. -- Meni Rosenfeld (talk) 20:03, 17 January 2011 (UTC)

See also Recurrence relation#Linear homogeneous recurrence relations with constant coefficients for the hat Meni pulled the solution for f out of. –Henning Makholm (talk) 20:30, 17 January 2011 (UTC)

Use of Baire Category Theorem

Hi all,

I'm taking a course in what is essentially functional analysis, and i'm currently working on some questions which relate primarily to the Baire Category theorem - particularly BCT1 in the Wikipedia page. I've come across the following problem, which seems to me to be a straightforward application of the theorem, but I can't quite manage to iron out a problem. The question is as follows:

Let $A_{j}$ be a sequence of subsets of [0,1] such that for each N ≥ 1, $\bigcup _{j=N}^{\infty }A_{j}$ is open and dense in [0, 1]. Prove that the set S of points x ∈ [0, 1] such that x ∈ $A_{j}$ for infinitely many j is dense. Must S be open? Must it be true that $\bigcap _{j=1}^{\infty }A_{j}\neq \phi$?

The part I'm stuck on is the first bit - showing the set of points is dense. It seemed like a straightforward use of the theorem, defining $B_{j}=\{x\in [0,\,1]:x\in {\text{at least j of the }}A_{i}\}$, and then using Baire category to show the infinite intersection is dense - however, my stumbling block is that I'm not convinced the $B_{j}$ are open: I feel like I should be able to prove that they are, using the fact that $\bigcup _{j=N}^{\infty }A_{j}$ is open - or conversely that the complement of the $B_{j}$ are closed, but I am unable to prove the result successfully - indeed, I'm not at all convinced it's true, perhaps it's the fact that the question looks so straightforward that's throwing me off. Could anyone please help?

Many thanks, Delaypoems101 (talk) 23:19, 17 January 2011 (UTC)

I don't see any reason your B_j should be open. Probably easy to come up with a counterexample.

Here's a hint: Being in infinitely many A_j implies that you're in all of the $\bigcup _{j=N}^{\infty }A_{j}$. --Trovatore (talk) 23:32, 17 January 2011 (UTC)

That's brilliant, thankyou - I thought my solution was the obvious one but that was even more obvious, not sure how I overlooked it! Now to see if I can conjure up a counter-example for either of the next parts... Delaypoems101 (talk) 03:08, 18 January 2011 (UTC)

Ack, stuck again. I'm having trouble even thinking of many subsets with this property: I tried playing around with something Cantor-set like but I can think of so few examples for which the property holds that I can't come up with a counterexample. Could anyone suggest a logical way to start trying to find or construct a counterexample rather than arbitrary guessing at sets? (Since I really doubt S need be open...) Thankyou again for the help :) Delaypoems101 (talk) 03:46, 18 January 2011 (UTC)

Notice that the $\bigcup _{j=N}^{\infty }A_{j}$ are a descending sequence of open sets, as N increases. What happens at each individual step, as you go from N to N+1? What constraints does this put on the A_j, and how much freedom do you have to manipulate them? In general, does the intersection of an infinite descending sequence of dense open sets need to be open? If not, can you take an example of such an infinite sequence whose intersection is not open, and arrange it so your $\bigcup _{j=N}^{\infty }A_{j}$ is close to that sequence? --Trovatore (talk) 03:54, 18 January 2011 (UTC)

At each individual step we remove exactly the x in [0, 1] which are in A_j but not A_j+i for any positive i: this means, I suppose, that the elements we have removed at any given stage must be isolated, in the sense that none of them is the limit of any (non-constant) sequence, otherwise we lose openness in the union. I can't see any explicit conditions this puts on the A_j however, because it seems like any such conditions would all be dependent on $\bigcup _{i=j+1}^{\infty }A_{i}$, not just $A_{j}$. I strongly suspect that the intersection of an infinite descending sequence of dense open sets need not be open, but I'm afraid as I've never really had to deal with openness and denseness simultaneously, this is all a bit foreign to me, combining the 2 ideas. Sorry I'm not really on top of this yet - I understand the concepts, but I struggle to combine openness and denseness - many of the things that come to my mind keep involving the rationals, which obviously aren't any use when it comes to openness. Delaypoems101 (talk) 05:58, 18 January 2011 (UTC)

The uselessness of the rationals is not obvious to me. What were your thoughts involving the rationals? You could be on the right track. --Trovatore (talk) 08:02, 18 January 2011 (UTC)

Do you have some measure theory available? If you construct the A_j's such that their measure falls off sufficiently quickly, you should be able to prove that S has measure 0 and so cannot be (non-trivially) open. –Henning Makholm (talk) 09:51, 18 January 2011 (UTC)

I do have measure theory available, yes - my thoughts on the rationals would be something like taking A_n to be open balls of radius 1/n^k (some k $\geq$ 2) around all points of the form ${\frac {a}{n}}$, but I'm not sure that gets us anywhere, or indeed what $\bigcup _{j=N}^{\infty }A_{j}$ looks like. Do you think my idea is anything along the right lines? (I can't think of many other ways we could make use of the rationals, since they in themselves are very far from open...) Delaypoems101 (talk) 12:20, 18 January 2011 (UTC)

Aha, a thought: enumerate the rationals as $q_{1},\,q_{2},\,...$, then define $C_{n}=\bigcup _{r=1}^{\infty }(q_{r}-{\frac {1}{2^{n+r}}},q_{r}+{\frac {1}{2^{n+r}}})$: the sequence is decreasing, so the intersection of all the $C_{n}$ is just the rationals, dense and not open, and since the sequence is decreasing it's probably feasible to construct $A_{n}$ for which $\bigcup _{n=N}^{\infty }A_{n}=C_{N}$. Sound good? :) Delaypoems101 (talk) 12:45, 18 January 2011 (UTC)

Yes, either of these stategies could work. Some random comments:

1. You mean "enumerate", not "emulate".
2. Since the C_n's are decreasing, taking A_n = C_n will get what you want.
3. It's not clear to me that S in either of the two constructions will contain only the rationals (by my experience, such intersections have a tendency to be uncountable). But that doesn't matter; the point is just to make sure it is dense. For openness, what can you say about the measure of the C_n's?

–Henning Makholm (talk) 13:40, 18 January 2011 (UTC)

Upon further thought, any dense subset of [0,1] that is the limit of a decreasing sequence of open sets must necessarily be uncountable. The standard argument for the uncountability of the Cantor set can be adapted to show this. –Henning Makholm (talk) 17:57, 18 January 2011 (UTC)

This follows immediately from the very Baire category theorem this thread is about.—Emil J. 19:16, 18 January 2011 (UTC)

Afraid I don't see how. It's entirely possible that I'm missing something basic; my grounding in general topology is sketchy. But now that you mention it, the argument I had in mind is close to being a proof of the BCT itself. –Henning Makholm (talk) 19:43, 18 January 2011 (UTC)

Suppose the intersection were countable. Enumerate the elements of the intersection as $q_{i},i\in \omega$. Then $\bigcup _{i}(C_{i}-x_{i})$ is empty, contradicting the Baire category theorem (note that an open dense set minus a point is still open dense).--203.97.79.114 (talk) 11:33, 19 January 2011 (UTC)

← More generally, in a Baire space, a set cannot be both meagre and comeagre: Suppose $X$ were both meagre and comeagre. Then $\bigcap _{i}A_{i}\subseteq X\subseteq \bigcup _{i}B_{i}$, where the $A_{i}$ are open dense, and the $B_{i}$ are closed nowhere dense. Then $A_{i}-B_{i}$ is open dense, but $\bigcap _{i}(A_{i}-B_{i})$ is empty, contradicting the Baire category theorem.--203.97.79.114 (talk) 11:48, 19 January 2011 (UTC)

Hah, yes, I wrote that half-asleep sorry. I see your point about the intersection containing more than the rationals, it seemed obvious at first but indeed it could easily contain something else too, though intuitively I suspect it doesn't. The measure of the C_n's tends to 0, indeed I believe this was how I was first shown that the measure of the rationals is 0. It won't be hard to calculate the sum of the lengths as an arithmetic progression when it comes down to it. Now, onto the intersection and whether i can find a counterexample... Thanks for all the help :) Delaypoems101 (talk) 16:54, 18 January 2011 (UTC)

Of course there is no requirement that S must have empty interior. For example, consider $A_{j}=[0,1]-\{1/n\mid n<j\}$. –Henning Makholm (talk) 19:16, 18 January 2011 (UTC)

Is that for the final part sorry, or just another example? Unless I'm misunderstanding you, I'm looking for a counterexample where the intersection is empty, not one where it isn't. Delaypoems101 (talk) 05:36, 19 January 2011 (UTC)

That's easy. Let $A_{1}=\emptyset$.--203.97.79.114 (talk) 11:33, 19 January 2011 (UTC)