Wikipedia:Reference desk/Archives/Mathematics/2013 January 26

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 26

Ehrenfeucht Fraisse Games

I don't know why, but I have a hell of a time understanding the definition of how these games work, I understand the concepts and terms involved, I can see the value of them, etc. But I can't seem to get a familiar feel for them in my brain, they seem very unintuitive and I can't remember how they work a few minutes after reading about them. At any rate, can anyone hear help me out and give me an informal break down of these in simplified terms; less explaining the definition, more something that I can use as a reference point in my head so it doesn't just seem like a bunch of formalism (like how the complex numbers are a nice example of an algebraic closure or how the p-adics are a nice example of a limit, etc.) Thank you for any help:-)Phoenixia1177 (talk) 07:24, 26 January 2013 (UTC)

One player is trying to make his sequence "look" just like his opponent's sequence, in the sense that all of his pieces bear the same relationship to his structure and to each other, as his opponent's pieces bear to her structure and to each other. She is trying to stop him, by playing pieces for which he can't find a match. If he has a winning strategy, then the two structures must be a lot alike (elementarily equivalent in the simplest/most standard formulation, but it could be some other relationship depending on the details of the rules). If she has a winning strategy, then it exemplifies some essential difference between the structures. --Trovatore (talk) 08:13, 26 January 2013 (UTC)

OK, a few more things have come filtering back to me since I wrote that. First, the player I was calling by feminine pronouns above, usually called Spoiler, the one who wants the sequences to be observably different, is allowed to pick from either structure at each move. The one I was using masculine pronouns for, usually called Duplicator, must then pick a corresponding element from the other structure. Then you compare, not "his" sequence and "her" sequence, but rather the sequences within each structure.

If you require Spoiler to pick from only one structure, I'm not sure what concept you get, but it's quite a bit weaker.

To get elementary equivalence, what you need is that for any fixed number of rounds n, Duplicator can stay alive for n rounds. If Duplicator can stay alive indefinitely without knowing the number of rounds in advance, that's much stronger; in fact, for countable structures, it actually implies they're isomorphic — see back-and-forth argument. --Trovatore (talk) 03:12, 27 January 2013 (UTC)

For example for any n one can choose two graphs of cycles with greater than n nodes and so show that whether there is an odd or even number of nodes in such cycles is not a first order property of graphs. As an aside you might like to have a quick look at axiom of determinacy (which isn't a commonly accepted axiom) to see games a bit like this can be much more complicated if you allow n to be infinite. Dmcq (talk) 14:37, 27 January 2013 (UTC)

Yes, although AD itself is not particularly relevant here — the game is an "open" game (meaning that the first player wins only if she wins in finite time, whereas the second player wins just by staying alive forever), and such games are determined by an easy elementary argument. (So are "closed" games, which is the same idea but with the players reversed.) The central article for the whole concept is determinacy, which has a more general scope than the article about the axiom. (The article needs work, though.) --Trovatore (talk) 20:59, 27 January 2013 (UTC)

(I just noticed that the phrase determined by an easy elementary argument might be misunderstood. What I meant to say was, "by an easy elementary argument, such games are determined", where "determined" is shorthand for "one of the players has a winning strategy".) --Trovatore (talk) 22:20, 27 January 2013 (UTC)

Here's what I think is a pretty concrete, intuitive example, that shows up some of the issues: Suppose you're just looking at linear orders; your language has just one non-logical symbol, namely < . Let's consider two structures. Structure A will be the natural numbers, and structure B will be the natural numbers, with a copy of the integers placed on top:

        ^
        |
        |
        |
        v
^       ^
|       |
|       |
|       |
o       o
A       B

Clear, I hope? Now, are the two structures isomorphic? Obviously not, and Spoiler can prove it, as follows, in the game where Duplicator is required to stay alive indefinitely. For Spoiler's first move, she picks an element in the "upper" part of B. Duplicator is forced to respond with some value from A. Let's say he picks 1257. Now Spoiler can trivially win in 1258 more rounds, each time picking a lower value in B (upper half or lower half, just as long as the first value in the lower half is at least 1257). Then at each round Duplicator must pick a lower value in A, and by round 1259 he has run out of room.

But are they elementarily equivalent? Now Duplicator is told in advance how many rounds he must stay alive. If that number is 1259 rounds, then in response to the strategy given above, he could stay alive that long provided he picks at least the value 1260. But that doesn't mean he can win against any strategy by playing 1260; maybe he has to play something bigger to have enough room against a cleverer strategy on Spoiler's part. You might have fun figuring out just how big.

On the point that, at each round, Spoiler is allowed to pick from either structure — note that if Spoiler plays a value immediately next to another value already played in B, we want Duplicator to have to play the value immediately next to the corresponding value in A. Here's how she keeps him honest: If he leaves a gap in A, on the next round, she will pick a value in that gap. Now he's forced to play a value between the two values in B — but there isn't one, because they're immediately adjacent. --Trovatore (talk) 10:45, 28 January 2013 (UTC)

Great stuff Trovatore, thanks for the explanations! -Sam^Talk 18:55, 31 January 2013 (UTC)

An arithmetico-geometric series?

Dear Wikipedians:

The following series:

$\sum \limits _{n=2}^{\infty }{\frac {4}{n(7^{n})}}$

appears similar to an arithmetico-geometric series with common difference of 1 and common ratio of ${\frac {1}{7}}$. But on closer inspection does not seem to be an arithmetico-geometric series as the $n$ appears on the denominator instead of the numerator.

Wondering if there is an exactly expression for the above series?

Thanks,

216.58.82.243 (talk) 19:15, 26 January 2013 (UTC)

It's $4(\ln(6/7)-1/7)$ by the series for $\ln(1-x)$ evaluated at $x=1/7$. Sławomir Biały (talk) 19:18, 26 January 2013 (UTC)

Wonderful! Thanks so much for all the help! 216.58.82.243 (talk) 20:05, 26 January 2013 (UTC)

No, it's 4(ln(7/6)−1/7) = 0.0451741 by Σ_n=1^∞xⁿ/n = ln(1/(1−x)) evaluated at x = 1/7. Bo Jacoby (talk) 10:15, 29 January 2013 (UTC).

Maclaurin series question

Dear Wikipedians:

When confronted with the Maclaurin series for the function

$f(x)=\cos(x^{2})+1-x$

I reasoned that since the Maclaurin series for $\cos(x)$ is

$\sum \limits _{n=0}^{\infty }(-1)^{n}{\frac {x^{2n}}{(2n)!}}$

we have

$\cos(x^{2})=\sum \limits _{n=0}^{\infty }(-1)^{n}{\frac {(x^{2})^{2n}}{(2n)!}}=\sum \limits _{n=0}^{\infty }(-1)^{n}{\frac {x^{4}n}{(2n)!}}$

So

$f(x)=\cos(x^{2})+1-x=\sum \limits _{n=0}^{\infty }(-1)^{n}{\frac {x^{4}n}{(2n)!}}+1-x=1-{\frac {x^{4}}{2!}}+{\frac {x^{8}}{4!}}-{\frac {x^{12}}{6!}}+\ldots +1-x=2-x-{\frac {x^{4}}{2!}}+{\frac {x^{8}}{4!}}-{\frac {x^{12}}{6!}}+\ldots$

But at the same time I could not help but feel that seems to be too trivial. Could there be the possibility that the original intention was for me to take $f(x)$ as a whole and directly evaluate Maclaurin from that? But then wouldn't it yield the same result?

Any insight appreciated.

Thanks.

216.58.82.243 (talk) 20:27, 26 January 2013 (UTC)

You have asked the question in a way that makes it impossible to answer. You said that you were "confronted with the Maclaurin series", but clearly that is not what happened. Since you didn't tell us what instructions you were given, there is no way for us to say whether you followed those instructions. Looie496 (talk) 01:28, 27 January 2013 (UTC)

Sorry I did not fully write out the instructions in the original question, they read:

Given the power series for $\cos u$, find the Maclaurin series for $f(x)=\cos(x^{2})+1-x$

Thanks,

216.58.82.243 (talk) 05:42, 27 January 2013 (UTC)

Then what you did seems fine to me. Dmcq (talk) 14:02, 27 January 2013 (UTC)

Thanks. 216.58.82.243 (talk) 15:24, 27 January 2013 (UTC)

Given that being asked to find the Maclaurin series for $1-x$ would be ridiculous, what you did was the only sensible way.31.54.246.112 (talk) 16:15, 27 January 2013 (UTC)

Note that $(x^{2})^{2n}=x^{4n}$ and $(x^{2})^{2n}\neq x^{4}n$. Bo Jacoby (talk) 10:05, 29 January 2013 (UTC).

monad or not?

Jacobson's "Basic algebra" at vol. I, chapter I, says that a monad is a set together with a binary operation with closure and identity. Is this thing the same of Monad_(category_theory)?--217.148.122.53 (talk) 20:56, 26 January 2013 (UTC)

It's (more or less) the same thing as a monoid, which is sometimes also called a monad. The two things are related, people talk about this in the context of functional programming, where monads are a big deal. Google for "monoid monad" for lots of pages talking about the relationship. Staecker (talk) 13:13, 27 January 2013 (UTC)

A generalization of the idea I believe, see abstract nonsense ;-) Don't mind that though it is worth knowing some category theory. Dmcq (talk) 13:56, 27 January 2013 (UTC)

math problem

can someone help me with the math on these equations? 3x +2y=72. x+y=30.Bobdorrance (talk) 21:47, 26 January 2013 (UTC)

Replies: (Triple edit confilct) first Nonsenseferret, then Toshio Yamaguchi, then NorwegianBlue, who collapsed the answers.

Homework? Two unknowns, x and y. Express one in terms of the other. Then substitute. Don't peek until you've really tried!

oh go on then, (I) 3x + 2y = 72 (II) x + y = 30 (I - 2xII gives) x = 12 (put this into II) 12 + y = 30 so y = 18 et voila ---- nonsense ferret 22:04, 26 January 2013 (UTC)— Preceding unsigned comment added by Nonsenseferret (talk • contribs) 22:04, 26 January 2013 (UTC) I'll give you some hints: You can for example subtract x from the second equation. You'll get an equation of the form y=. Note that you also have y in the first equation, so you can replace the y in the first equation with the value in the second equation. There are other possibilities, such as multiplying the second equation by 2 and subtracting it from the first equation. -- Toshio Yamaguchi 22:09, 26 January 2013 (UTC) y = 30 - x 3x + 2(30 - x)= 72 3x + 60 - 2x = 72 x = 72 - 60 x = 12 y = 30 - x y = 18 --NorwegianBlue talk 22:23, 26 January 2013 (UTC)

Hmm, I think this is more or less what I said, but well.... -- Toshio Yamaguchi 22:37, 26 January 2013 (UTC)

Well yes, that's the meaning of 'edit conflict'. The three of us started typing at about the same time, not knowing about the others, with equivalent responses. I got an edit conflict with the two of you when submitting my reply. I collapsed the thread to urge the questioner to have one more go at the problem before checking the answers. --NorwegianBlue ^talk 23:31, 26 January 2013 (UTC)

I'm just glad you got the same answer, might have been a bit embarrassing for me to get it wrong ;) ---- _nonsense ferret 01:07, 27 January 2013 (UTC)