Wikipedia:Reference desk/Archives/Mathematics/2010 July 15

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.

July 15

Testing the bias on a coin

If a coin is flipped a number of times, and the results are n heads and m tails, what is the probability that the next flip will be heads?115.178.29.142 (talk) 03:22, 15 July 2010 (UTC)

There's no way to know. But the maximum likelihood estimate is n/(n+m). 67.119.12.184 (talk) 05:11, 15 July 2010 (UTC)

Assuming of course that you have no other information regarding the fairness of the coin, the probability that the next flip will be heads is P=(n+1)/(n+m+2). This formula also applies when n=m=0, unlike the approximate estimate P≈n/(n+m). Bo Jacoby (talk) 09:33, 15 July 2010 (UTC).

If you were pretty certain there should be little or no bias either way then (n+10)/(n+m+20) might be better. You can see it depends on your prior probability. Dmcq (talk) 09:48, 15 July 2010 (UTC)

Dmcq's result assumes that the coin has been flipped n+m+18 times given n+9 heads and m+9 tails. The prior probability can not be chosen freely. No information about the fairness of the coin means that the prior probability of heads, (H|), is 1/2, and the prior probability of tails, (T|), is also 1/2. The wanted conditional probability of heads, giving the facts, F, (that there were already n heads and m tails), is computed by Bayes' formula together with the formula for the hypergeometric distribution

$(H|F)={\frac {(F|H)(H|)}{(F|H)(H|)+(F|T)(T|)}}$ $={\frac {{\frac {{\binom {n+1}{n}}{\binom {m}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}}{{\frac {{\binom {n+1}{n}}{\binom {m}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}+{\frac {{\binom {n}{n}}{\binom {m+1}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}}}$ $={\frac {n+1}{n+m+2}}$

Bo Jacoby (talk) 11:11, 15 July 2010 (UTC).

That is a pretty good prior if you'd never come across a coin before but most people recognize that coins are usually pretty unbiased. Now supposed we tossed the coin once and it came up heads. That would give the chance of the coming coming up heads as 2/3. That means if I bet 100 quatloos on tails and the other person 200 on heads then we should break even over a number of throws - in three goes on average I'd lose twice and they'd lose once. Now would you really be willing to bid against me if I put 150 quatloos on tails to your 200 on heads? Dmcq (talk) 12:00, 15 July 2010 (UTC)

Indeed. Bo is assuming we have no information about the fairness of the coin, but that's not the case. We know it's a coin, which means it is very likely to be very close to fair. --Tango (talk) 12:42, 15 July 2010 (UTC)

If you already know that the coin is fair, then don't test it, just tell the OP that the probability is 1/2 because you know that it is a fair coin. But the OP is not sure, and that's why he tests it. If you have noticed (or have been told) that coins are usually pretty unbiased, it must be because coins have been flipped before, and then the values of n and m are high. It doesn't need to have been the same coin every time. Now the OP clearly assumes that "a coin is flipped a number of times, and the results are n heads and m tails", so we are justified in assuming that n and m are the correct counts. Or perhaps the OP is using the word coin figuratively meaning some device providing random values called heads and tails. In any case (n+1)/(n+m+2) is the correct formula for the probability that the next flip show head. Bo Jacoby (talk) 14:46, 15 July 2010 (UTC).

Previous coin tosses aren't the only kind of evidence you could have. You could have the word of the person that gave it to you that is isn't a fixed coin, for example. Or simply the knowledge that most coins in existence are fair. Knowing that a different coin was tossed and got certain results isn't the same as knowing that the coin in your hand was tossed and get certain results. --Tango (talk) 14:53, 15 July 2010 (UTC)

I feel this is rapidly heading towards at least one side of at least one sheep seems black territory. :) Dmcq (talk) 15:33, 15 July 2010 (UTC)

That's nonsense. There is no dichotomy between "know for certain the coin is fair" and "have no idea what a coin is, and hence use a maximum-entropy prior". If you know that 99% of coins are fair, then when given a random coin (which you have no reason to suspect was chosen based on its fairness or lack thereof), you'll say there's 99% that this coin is fair. If you then toss it 3 times and it's all heads, you'll still have a high credence to it being fair (the exact amount depends on the continuous prior distribution for the bias of biased coins), and thus your credence for the next toss being heads will be close to 50%. As more evidence is collected where this coin lands heads more then it should, your posterior will shift towards the coin having the bias implied by the Heads:Tails ratio.

Even if past coin tosses is the only knowledge of coins you have (as opposed to, say, proficiency in metallurgy and rigid body mechanics), you can't compress this knowledge to 2 numbers m and n. If you sample 2 coins and toss each many times, then "one coin always lands heads, one always tails" is very different, wrt your conclusions about the bias of coins, from "each coin lands a roughly equal number of heads or tails". Your probability distribution for the bias of coins can take any form depending on what observations you have made. -- Meni Rosenfeld (talk) 15:51, 15 July 2010 (UTC)

The arcsin for numbers >1

How do you find the arcsin for numbers greater than 1 (which I believe is a complex value) —Preceding unsigned comment added by 115.178.29.142 (talk) 04:44, 15 July 2010 (UTC)

By the way, I know the real part is pi/2 . but what is the imaginary part?115.178.29.142 (talk) 05:15, 15 July 2010 (UTC)

Sin(z) is defined in terms of the exponential function exp(z) as sin(z)=(exp(iz)-exp(-iz))/2i, and exp(z) is in turn defined in terms of a power series (see article Exponential_function). So when you want to find arcsin of x, you solve for z in x=(exp(iz)-exp(-iz))/2i Money is tight (talk) 05:24, 15 July 2010 (UTC)

Which will give you the expression in Inverse trigonometric functions#Logarithmic forms.—Emil J. 11:51, 15 July 2010 (UTC)

$\arcsin(x)={\frac {\pi }{2}}\pm i\,\operatorname {arccosh} (x){\text{ for }}x>1$ Gandalf61 (talk) 13:00, 15 July 2010 (UTC)

Comparing two averages

If you are comparing two samples from completely separate populations, you can use a two sample t-test. Is there anyway to compare a population's mean to a subset's mean? For instance, you look at 2000 students with an average weight of 150 pounds. Then you choose 50 of those students and get their average weight. Is there anyway to check that their average weight is not significantly different from the population's average of 150 pounds? Like: an average of 149 might not be significant, but an average of 220 is significant. Remember, you don't have the average and standard deviation of the whole population without those students.

Basically you're trying to show that the group of students you chose as a whole is not significantly heavier than the other students at the school. 160.10.98.106 (talk) 15:21, 15 July 2010 (UTC)

The whole population without those students is (2000×150−50×220) / (2000−50) = 148.2 pounds per student. Your problem is treated by analysis of variance. Bo Jacoby (talk) 09:46, 17 July 2010 (UTC).

It depends how you know the population's average. If you've measured the entire population then there's no uncertainty in its mean, so to test the null hypothesis that the weights of the 50 students could be a random sample from the population then you can use a one-sample t-test with the population mean as the specified value μ₀, and you'd gain precision by using the population standard deviation if you know it rather than the sample standard deviation. If on the other hand you found the population mean from a random sample of the population then you have a two sample t-test provided none of that sample were also members of your subset of 50 students. If they were, it's going to get a bit trickier—simplest to exclude those students from one group or the other, e.g. from the larger group. Qwfp (talk) 11:14, 17 July 2010 (UTC)

Theoretical computer science

Suppose F is a boolean function with n variables, and I want to determine whether there exists an assignment of true or false to those variables such that F is true. With a nondeterministic Turing machine, this can clearly be solved in time n, so this is in NP. However, a deterministic Turing machine requires time 2ⁿ to check all 2ⁿ possible assignments of variables, so this is not in P. Therefore, P!=NP. What's the problem with this proof? --138.110.206.101 (talk) 16:25, 15 July 2010 (UTC)

You're assuming there's no better method for a deterministic Turing machine to use than straightforward brute force search. You're also taking "polynomial-time" to mean polynomial in the number of variables, while I think the only sensible meaning for it here is polynomial in the length of the proposition. Algebraist 16:31, 15 July 2010 (UTC)

[ec] The problem is that you have assumed that brute-forcing all possibilities is the most efficient algorithm to solve this. To prove that a problem is not in P you have to show that each and every algorithm that solves it is superpolynomial, not that one particular algorithm is superpolynomial. -- Meni Rosenfeld (talk) 16:33, 15 July 2010 (UTC)

Are there any polynomial-time deterministic algorithms for determining whether a boolean equation has a solution? --138.110.206.101 (talk) 16:40, 15 July 2010 (UTC)

We don't know. That's exactly what the P =? NP problem asks for. However, there are SAT solvers which do better than the brute force assignment search (they achieve time complexity $2^{\epsilon n}$ for some $0<\epsilon <1$), which should at least persuade you that the problem is nontrivial.—Emil J. 16:43, 15 July 2010 (UTC)

This is a very common mistake for those beginning to study P/NP. You are not using a standard nondeterministic Turing machine. You are using an infinite-length nondeterministic Turing machine. What if the maximum number of values that your machine can store is m. You have n values to check. If m>n, no problem. If m<n, you have a problem. You cannot do this in simply polynomial time. A basic rule: If your "polynomial" time solution begins with "get a tape long enough to store all the values" or "get enough memory to store all the variables" or "get a rope long enough to stretch around all the posts", it is not a polynomial solution. -- kainaw™ 17:24, 15 July 2010 (UTC)

What on earth are you talking about? The standard Turing machine, as used in the definition of NP, has (at least potentially) an infinite tape. It can get away with a polynomially bounded tape as it is a poly-time machine here, but it certainly cannot be bounded by a constant. That would be equivalent to a nondeterministic finite automaton, which can only recognize regular languages, a tiny subset of P (let alone NP). The OP's NP algorithm is correct, and it is in fact a textbook example (SAT being among the most popular NP-complete problems).—Emil J. 18:04, 15 July 2010 (UTC)

I was attempting to use language to make it understood to the questioner. When you say "infinite tape" and you know what you are talking about, those just learning about P/NP hear "the tape starts out with an infinite amount of data already written on it and all I have to do is read it quickly from one end to the other". I have argued for many years that the language used in describing P/NP leads to more confusion than anything else. -- kainaw™ 18:07, 15 July 2010 (UTC)

Whereas telling the OP that he or she made a mistake when they actually did not (in this part of the argument, that is) is supposed to reduce confusion, right?—Emil J. 18:15, 15 July 2010 (UTC)

I figured he was confused enough already because he most likely intended to describe a 3-SAT but didn't. A 2-SAT (or 1-SAT, which is what he described) has a simple solution. 3-SAT is where the trouble starts. Further, it appeared that he was going towards the standard "I can't believe I solved the 3-SAT problem" solution of: 1. Get enough memory to store every 3-variable set in the 3-SAT. 2. Calculate the possibility of each of those being true. 3. Solve those solutions as a 1-SAT. Step 1 is where it immediately gets thrown out of P. -- kainaw™ 21:54, 15 July 2010 (UTC)

But the OP was not trying to prove that SAT (or 3-SAT, though I don't see anything in their post which would indicate that they intend such a restriction) is in P. On the contrary, they were trying to prove that it is not in P (whereas it is in NP, that's what the part about nondeterministic TM does).—Emil J. 10:27, 16 July 2010 (UTC)

Implicit function theorem

My text book writes "...note that the chain rule applied to F(x,g(x)) = 0 gives

$\mathbf {D_{x}} F(\mathbf {x} ,g(\mathbf {x} ))=[{\frac {\partial F}{\partial x}}(\mathbf {x} ,g(\mathbf {x} ))][\mathbf {D} g(\mathbf {x} )]$

which is equivalent to

${\frac {\partial g}{\partial x_{i}}}=-{\frac {\frac {\partial F}{\partial x_{i}}}{\frac {\partial F}{\partial z}}}.$

I was wondering the first equation can be arrived at. Oh, and F:ℝⁿ⁺¹ → ℝ. PS Do you have to bold the D everytime you write the derivative matrix? Because it's hard to bold on paper...74.15.137.192 (talk) 19:31, 15 July 2010 (UTC)

Let $f:\mathbb {R} ^{n+1}\rightarrow \mathbb {R}$, $g:\mathbb {R} ^{n}\rightarrow \mathbb {R}$.

Define $h:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n+1}$, $h:x\mapsto (x,g(x))$.

We have ${\frac {\partial (f\circ {}h)}{\partial {}x_{j}}}(x)=\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x)){\frac {\partial {}h_{j}}{\partial {}x_{i}}}(x)$.

For $0\leq {}j\leq {}n$, $\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x)){\frac {\partial {}h_{j}}{\partial {}x_{i}}}(x)=\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x)){\frac {\partial {}x_{j}}{\partial {}x_{i}}}(x)=\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x))\delta _{ij}={\frac {\partial {}f}{\partial {}x_{j}}}(h(x))$.

$\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x)){\frac {\partial {}h_{n+1}}{\partial {}x_{i}}}(x)=\sum _{i=1}^{n}{\frac {\partial {}f}{\partial {}x_{i}}}(h(x)){\frac {\partial {}g}{\partial {}x_{i}}}(x)=Df(h(x)){Dg(x)}^{T}$.

Hence $D(f\circ {}h)(x)=({\frac {\partial {}f}{\partial {}x_{1}}}(h(x)),\ldots ,{\frac {\partial {}f}{\partial {}x_{n}}}(h(x)),Df(h(x)){Dg(x)}^{T})=(Df(h(x)),Df(h(x)){Dg(x)}^{T})$.

Barsamin (talk) 08:51, 20 July 2010 (UTC)

Okay thanks. 74.15.137.192 (talk) 06:30, 20 July 2010 (UTC)

Riddle (of my own)

I apologize if you think it's to easy. Additionaly, user:EmilJ is hereby asked not to respond, unless no response has been given by Sunday morning. If even EmilJ won't respond by Monday morning, then I'll provide the solution. The riddle goes as follows:

By "arithmetical" mapping - we shall hereby mean: a mapping expressible in the arithmetical language: (+,×,0,1), i.e. a function for which there exists a formula $\varphi (x,y)$ comprising of logical symbols as well as the symbols: +,×,0,1, so that for every a in the domain there is a unique b in the codomain such that $\varphi (a,b)$.

Now, one has to find a field F (+,× being its corresponding addition and multiplication, 0,1 being its units respectively), with respect to which the relation: " there is an arithmetical mapping from S to T " - is not transitive, i.e. one has to find three sub-sets of F, let's call them A,B,C, such that there's an arithmetical mapping from A to B, and there's an arithmetical mapping from B to C, but there's no arithmetical mapping from A to C.

HOOTmag (talk) 21:20, 15 July 2010 (UTC)

I'll bow out too then with EmilJ and ponder deeply on "How much wood could a woodchuck chuck if a woodchuck could chuck wood?" Dmcq (talk) 23:33, 15 July 2010 (UTC)

If you think my riddle is too easy, you may Email me. Thanks.HOOTmag (talk) 23:48, 15 July 2010 (UTC)

Well, I was supposed not to respond to this question, but let me just say that I don't understand the description. What do you mean by "expressible in the arithmetical language"? I would read it as "definable by a first-order formula in the structure (F,+,×,0,1)", but then the riddle would have no solution, because the composition $g\circ f$ of two definable surjections is a surjection definable by $\exists u\,(f(x)=u\land g(u)=y)$. You thus may want to clarify the statement of the problem.—Emil J. 10:39, 16 July 2010 (UTC)

Yes: by "expressible in the arithmetical language" I really mean just as you've interpreted it.

No: although there are surjections f and g expressible in the arithmetical language, the surjection $g\circ f$ may be not expressible in the arithmetical language. This is my riddle, and it does have a solution.

To make things even more provocative, I've replaced "surjection" by "mapping", as you can see now in the current version of my riddle.

Good luck. HOOTmag (talk) 14:49, 16 July 2010 (UTC)

You contradict yourself. What I wrote above is a (standard) proof that the composition of two definable functions is definable, so you obviously cannot mean it as I've interpreted it. You have to explain your terminology, otherwise your "riddle" is just gobbledygook.—Emil J. 15:07, 16 July 2010 (UTC)

No, I don't.

Yes, what you wrote above is really a (standard) proof that the composition of two [arithmetically] definable functions is [arithmetically] definable.

However, the composition of two [arithmetically] definable functions is unnecessarilly an [arithmetically] definable function.

No, my riddle is not gobbledygook.

Good luck. HOOTmag (talk) 15:27, 16 July 2010 (UTC)

Then your terminology must be even more puzzling than I expected. The composition of two functions is always a function, by definition. What you write makes no sense.—Emil J. 15:31, 16 July 2010 (UTC)

No, my terminology is just like yours.

Yes, The composition of two functions is always a function, and the composition of two [arithmetically] definable functions is [arithmetically] definable.

However, the composition of two [arithmetically] definable functions is unnecessarilly an [arithmetically] definable function.

No, what I wrote does make sense.

Good luck. HOOTmag (talk) 15:38, 16 July 2010 (UTC)

Let me try it in a different way. Here's the standard terminology:

• a function f: A → B is, depending on whom you ask, either a relation R ⊆ A × B such that for every a in A there exists a unique b in B such that a R b, or the triple (R, A, B) where R is as above,
• the composition of functions f: A → B and g: B → C is the function $g\circ f\colon A\to C$ such that $(g\circ f)(a)=g(f(a))$ (sometimes f and g are written in the opposite order),
• a function f: A → B, where A and B are subsets of the domain of a structure M, is definable in M, if there exists a first-order formula $\varphi (x,y)$ in the language of M such that for every a and b in M, $M\vDash \varphi (a,b)$ iff a is in A and f(a) = b.

Tell us which of these your terminology disagrees with. In particular, you seem to make a distinction between a definable function and a function which is definable, but these two are synonyms in the standard terminology.—Emil J. 15:49, 16 July 2010 (UTC)

Your third terminology of "definability in M" has nothing to do with my riddle.

To put things clearer: A,B being sub-sets of the field F, the expression "arithmetical mapping" f: A → B should be interpreted here as follows: there exists a formula $\varphi (x,y)$ comprising of logical symbols as well as the symbols: +,×,0,1 (which are interpreted as the addition the multiplication and the units of both operations of F respectively), so that for every a in A and for every b in B, $\varphi (a,b)$ iff f(a) = b. I'll be back on sunday morning. HOOTmag (talk) 16:15, 16 July 2010 (UTC)

Aha, so you don't want the function itself to be arithmetically definable, but that there exists an arithmetically definable relation whose intersection with A × B is (the graph of) the function. Then the problem becomes sensible.—Emil J. 16:29, 16 July 2010 (UTC)

so others don't have to read through all this, you should move this part of the conersatino to the talk page (to preserve it) and just change the original phrasing so it is clear as finally realized by EmilJ. 92.229.14.255 (talk) 21:26, 16 July 2010 (UTC)

Let F = GF(4) = {0, 1, a, a + 1}, and put A = {0}, B = {a}, C = {a, a + 1}, f(0) = a, g(a) = a. Then f: A → B and g: B → C are arithmetical mappings in HOOTmag's sense (f by the true formula, g by x = y), but no mapping from A to C is arithmetical, because it is not invariant under the Frobenius automorphism (which swaps a and a + 1). Pretty much the same thing can be done with any field which carries any nonidentical automorphism.—Emil J. 12:00, 18 July 2010 (UTC)

Excellent. Now try to solve the same riddle but with my original "surjection" (and also with "bijection") instead of "mapping". (By "arithmetical surjection", I mean: an "arithmetical mapping" - which is also a surjection. By "arithmetical bijection" from A to B, I mean: an "arithmetical mapping" from A to B - which is also an "arithmetical mapping" from B to A). HOOTmag (talk 12:00, 18 July 2010 (UTC)

I'm also not sure in what way f is arithmetical. As clever as using an ifexpr statement is, it doesn't really work since it's visible when editing... --Tango (talk) 20:26, 17 July 2010 (UTC)

It's arithmetical since the formula uses no symbols other than the logical ones and the arithmetical ones. HOOTmag (talk 12:00, 18 July 2010 (UTC)

But how can you write it without using the symbol a? I thought we were only allowed addition, multiplication and identities. --Tango (talk) 22:53, 17 July 2010 (UTC)

f is expressed (e.g.) by the formula: "0=0" (or by any true formula, as EmilJ indicated). You should remember that B= {a}, so the only object in B satisfying the formula "0=0" is a. If you still have any doubt, look again at the very definition of "arithmetical mapping", above. HOOTmag (talk 12:00, 18 July 2010 (UTC)

I've boldly removed the time delays because they were getting ridiculous and Emil J.'s answer wasn't correct anyway (not being a surjection). Ah, I see. That kind of trick will only work if A and B are singleton sets, though, which will make it difficult to use it with surjections (if there is a surjection from B to C, and B is a singleton set, then C must be too, which means any mapping from A to C is trivially arithmetical by the same trick). --Tango (talk) 23:45, 17 July 2010 (UTC)

I've boldly put back the time delays, because EmilJ who decided to use them didn't allow you to remove them. and Emil J.'s answer was correct (because the current version of my riddle is not about surjections but rather about mappings). If you want to remove the time delays from your posts, you can do that, but please don't touch Emilj's posts and my posts :). My riddle has a solution even for surjections. For more details, read my response to EmilJ's last response, and wait for EmilJ's response, or wait untill Monday morning when I give the full answer if EmilJ hasn't responded by then. HOOTmag (talk 12:00, 18 July 2010 (UTC)

I've removed them again. Please do not put them back without a consensus on the talk page. Hiding answers to questions goes against the intentions of the reference desk, which is to answer people's questions. This isn't a competition page. --Tango (talk) 12:00, 18 July 2010 (UTC)

I've put them back again. If you want to remove them from your posts, you can do that, but please do not remove them from other editors' posts - without a consensus on the talk page. Changing other editors' posts without getting their explicit permission - goes against Wikipedia rules. The current discussion has nothing to do with competitions. This page welcomes riddles, as well as solutions for riddles, but it isn't a quarrel page. HOOTmag (talk 12:00, 18 July 2010 (UTC)

Consensus on the talk page seems to be that this timed-hiding of posts is inappropriate for the ref desk. It's disruptive, so that stuff can be removed. If you don't remove them yourself, I'm sure someone else will. :) ←Baseball Bugs ^{What's up, Doc?} carrots→ 16:12, 18 July 2010 (UTC)

Which I have now done. Put them back again, and I will ask that you be blocked for disruption. Have a nice day. :) ←Baseball Bugs ^{What's up, Doc?} carrots→ 16:17, 18 July 2010 (UTC)

Unfortunately, your removing the time delays, was done too late, when it was already not actual, since the time delays had expired more than four hours before you removed them.

Similarly, your advice not to put them back, was given too late, due to the same reason mentioned above.

Unfortunately, your redundant warning about what you may do if the time delays (which are already not actual) are put back, does not assume good faith. I'm sure that if you had been aware of the sequence of events, you wouldn't have hurried to warn innocent wikipedians, who acted only according to what Wikipedia rules permit (in my opinion and in other editors' opinion, like DMacks). If you disagree with me (and with DMacks) and think that Wikipedia allows the wikipedians to edit other editors' posts, then your opinion is legitimate and should be discussed gravely solemnly and seriously (in other cases in the future since our case is already not actual after the time delays had expired at 12:00 before they were removed), because as far as I'm concerned - I do assume good faith from all sides.

have a nice day too. :)

HOOTmag (talk) 21:24, 18 July 2010 (UTC)

There is no concensus with regard to the time delays, because two editors (Dmacks and me) think that Wikipedia rules don't permit any editor to change other editors' posts without getting their permission.

You advise me "remove the stuff" from what?

1. From my posts only? Note that I responded to hidden responses, while I couldn't present my post as an unhidden response to a hidden one: just try to think about our page, if it had contained an unhidden response to a hidden post...
2. Did you advise me to remove the time delays from the other users' posts to which I responded? In my opinion, I was not permitted by Wikipedia to do so, and this opinion - is not mine only - but is also what DMacks thinks.

If you disagree with me (and with DMacks) and think that Wikipedia permits me to edit other editors' posts in our specific circumstances, then your opinion is legitimate and should be discussed gravely solemnly and seriously, but you cannot advise me to act in a way considered by me (and by another editor) as violating Wikipedia rules.

Anyways, your advice to remove the time delays is already not actual, since you advised me this after the time delays had expired (they expired at 12:00, i.e. more than four hours before your advice was given).

HOOTmag (talk) 21:24, 18 July 2010 (UTC)

EmilJ has given a solution for the case of arithmetical mappings. Here is an example of solution for the case of arithmetical surjections/bijections:

Memorandum:

• By "arithmetical" surjection/bijection - we shall hereby mean: a surjection/bijection expressible in the arithmetical language: (+,×,0,1), i.e. a surjection/bijection for which there exists a formula $\varphi (x,y)$ comprising of logical symbols as well as the symbols: +,×,0,1, so that for every a in the domain there is a unique b in the codomain such that $\varphi (a,b)$.
• Now, one has to find a field F (+,× being its corresponding addition and multiplication, 0,1 being its units respectively), with respect to which the relation: " there is an arithmetical surjection/bijection from S to T " - is not transitive, i.e. one has to find three sub-sets of F, let's call them A,B,C, such that there's an arithmetical surjection/bijection (respectively) from A to B, and there's an arithmetical surjection/bijection (respectively) from B to C, but there's no arithmetical surjection/bijection (respectively) from A to C.

F is the set of complex numbers. A = { 1,3 }, B = { i,3i }, C = { -i,i }. An arithmetical surjection/bijection from A to B is: x×x + y×y = 0. An arithmetical surjection/bijection from B to C is: x×y + y×x = x×x + y×y + 1+1+1+1. There is no arithmetical surjection/bijection from A to C. Furthermore, there is no arithmetical mapping from A to C. HOOTmag (talk) 23:07, 19 July 2010 (UTC)

What is your proof that there is no arithmetical mapping (or even just bijection) from A to C? --Tango (talk) 23:54, 19 July 2010 (UTC)

It's trivial. The proof you're looking for is the same proof by which one proves that there's no arithmetical definition for i, which can make a distinction between i and -i. Just think about it... HOOTmag (talk) 00:03, 20 July 2010 (UTC)

(ec) Actually, after thinking about it for a moment, the proof is fairly obvious (although you should still have stated it). Since i and -i cannot be distinguished by polynomials with real coefficients and you require a polynomial with real (in fact, integer) coefficients in x and y (which will reduce to a polynomial with real coefficients in y once you substitute in the possible values of x, since A is a subset of the reals) which has (x,i) as a root but not (x,-i) for some x, such a mapping cannot exist. --Tango (talk) 00:09, 20 July 2010 (UTC)

Yes, as you've pointed out, it's really obvious. Anyways, what still bothers me is whether it's an easy riddle. The answer may influence another problem which I decided not to present here. HOOTmag (talk) 00:44, 20 July 2010 (UTC)

Well, "easy" is subjective, so I'm not really sure what you are asking... --Tango (talk) 00:47, 20 July 2010 (UTC)

Well, I've assumed that the "smaller/simpler" the minimal field is, the "easier" the riddle is expected to be. Note that the previous version of my riddle was about arithmetical mappings, and EmilJ gave a minimal field comprising four objects only, whereby I realize that the riddle is relatively "easy" when it's about arithmetical mappings. I wonder whether the field must be as big as the set of all complex numbers, or at least: the set of all algebraic numbers, when the riddle is about surjections/bijections. I hoped that somebody could supply a field having a smaller cardinality (i.e. a finite field), or at least: a field which is not algebraically closed. Had this happened, I would find my riddle much "easier" than how I've considered it to be, as far. Unfortunately, nobody could present a smaller/simpler field, as far. HOOTmag (talk) 10:31, 20 July 2010 (UTC)

Your example does not need complex numbers. It works without change for every field F of characteristic ≠ 2 in which −1 is a square, and there exists an automorphism exchanging the two square roots of −1 (which in particular holds if F is Galois over a subfield where −1 is not a square). Examples include F = Q(i) or the finite field F = GF(9). The latter is a minimal example (it's impossible for prime fields as each of their elements is definable, and unless I am mistaken, no example fits in GF(4) either, by case analysis).—Emil J. 11:12, 20 July 2010 (UTC)

Thank you Emil. Given the complex field as a possible solution, Q(i) becomes a trivial solution (though it's not algebraically closed). The more important solution is GF(9), because it's a finite field, and it's the minimal field I've been looking for. Nine - as a minimal number of elements - means that my riddle is (intuitively) "moderate": neither easy nor difficult... :) Thank you again, all the best. HOOTmag (talk) 12:08, 20 July 2010 (UTC)