Life In 19x19

DrStraw wrote:

flOvermind wrote:Puzzle 1:
Find two periodic functions f and g, such that their sum is the identity function (that is, f(x) + g(x) = x).

I still have an issue with the statement of the problem. The operation is function addition and x is not the identity for that operation. x is only the identity under function composition.

Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.

Identity function: f(x)=x

Not that confusing.

DrStraw wrote:I still have an issue with the statement of the problem. The operation is function addition and x is not the identity for that operation. x is only the identity under function composition.

The problem with that is probably that English is not my native language. That's why I've written the clarifying definition "f(x)+g(x)=x", because I was not sure if "identity function" is the correct word.

DrStraw wrote:Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.

These functions are not periodic. There doesn't exist a d>0 such that f(x) = f(x+d).

Solution to Problem 1:

robinz wrote:Oh, I think I see (based on the last hint). NB: don't look at the hidden text unless you want to see the solution. (Ignore that last sentence and read it if it subsequently gets shot down though - but I'm pretty sure it works.)

So you basically choose a basis for the reals over the rationals - this bit requires the axiom of choice. Then you pick any two elements of your basis - they may as well be 1 and pi, or your favourite irrational number - and express any x as x=a+b*pi+{a linear combination of the other basis elements}. Then just set, for example, f(x)=b*pi+{blah}, g(x)=a, and you have a solution. (f has period 1, g has period pi.)

Nice - I really ought to have been able to come up with that from the earlier hints

Correct.

More about problem #2:

Shaddy, my algorithm shows a paradox that arises by defining these equivalence classes. It's not even directly related to the original problem (though, of course, if the concept of equivalence classes is shown to be bogus, the original solution doesn't work). The fact that each individual lacks knowledge of one hat is not relevant for my algorithm.

Bill Spight wrote:As for the difference between "for each" and "for all", modern mathematical logic does not recognize it. The key to the difference is what Redundant says: your process does not halt. So, even though the bit is flipped for each element, at no point in the process is it flipped for all of the elements. The process remains in the realm of the potentially infinite. Aristotle would say that, even though each element is eventually changed, we cannot conclude that all of the elements are eventually changed. The number of changed elements is always finite.

Consider how paradoxes arise in probability theory when you try to consider actually infinite sets. Jaynes is right, IMO, that we should construct finite models and take them to the limit. In that he is following Aristotle, although I do not know if he was aware of Aristotle's distinction.

I understand what you mean - my algorithm will never reach the point where all elements (or an infinite number, for that matter) are flipped. The point is, again, that there exists no way to find the equivalence classes either - any calculation will not finish in the same manner. So my technical problem is: how do you define this world? I am keeping in mind that this world is completely detached from reality! But you cannot say: "despite the fact that you can obviously never calculate for all elements, our solution algorithm is valid; but your algorithm is not valid because you can never calculate for all elements."

By the way, I couldn't agree more with your paraphrasing of Jaynes. Not beginning with finite models taken to the limit can lead to this kind of insanity .

gaius wrote:More about problem #2:

Shaddy, my algorithm shows a paradox that arises by defining these equivalence classes. It's not even directly related to the original problem (though, of course, if the concept of equivalence classes is shown to be bogus, the original solution doesn't work). The fact that each individual lacks knowledge of one hat is not relevant for my algorithm.

I'll give a proof of the well definedness of the equivalence relation. We must check that it is reflexive, symmetric, and transitive.

Let a, b, and c be sequences of zero and one. a has zero differences with a, so the relation is reflexive. If a differs from b on some finite set, then b differs from a on the same finite set by the transitivity of equality. Now, if a differs from b on some set (of places in the sequence) S, and b differs from c on T, then a differs from C on at most cardinal of S union T places. Since both S and T are finite, their union is finite also.

Your notion seems to be one of computability, that we cannot ever actually tell whether or not two sequences are in the same equivalence class in finite time. This is true, but not relevant to the mathematics. It's just another example of how this algorithm is not possible in reality. However, mathematics is in no way meant to be a model for reality.

ah, yeah, i misunderstood your algorithm. red and bill have said everything i wanted to say now that i understand, though..

edit: i have thought of something to say. for any n finite, it will not halt. if we accept that it can compute infinitely like the people in the problem, then it will halt- but you've changed an infinite number of terms, so the equivalence still works.

EDIT: Shaddy came up with a very interesting point! My gut feeling is still protesting, but I'll have to sleep on it before I'll say anything more here .

@Redundant: OK, you just (I think) proved that the equivalence relation is well-defined when applied to a finite number of sets. Whether or not this automatically implies that the collection of equivalence classes forms a discrete basis set for all the infinite sequences of ones and zeroes is beyond me.

More importantly though, you did not really address my argument, which is pertinently NOT one of computability. I have stated many times that I am willing to accept infinite memory and runtimes. However, I will, yet again, repeat my problem, which you did NOT address:

Myself wrote:You cannot say: "despite the fact that you can obviously never calculate for all elements, our solution algorithm is valid; but your algorithm is not valid because you can never calculate for all elements."

I have provided an algorithm that, provided infinite runtimes are available, will give an inconsistency in your model. I would love to hear why this does not actually break your logic; unfortunately, it seems that no one here has a deep enough understanding of the math to explain this. That's fine, neither do I, but please either address this issue or admit that you don't know the answer!

gaius wrote:I have provided an algorithm that, provided infinite runtimes are available, will give an inconsistency in your model. I would love to hear why this does not actually break your logic; unfortunately, it seems that no one here has a deep enough understanding of the math to explain this. That's fine, neither do I, but please either address this issue or admit that you don't know the answer!

Back to this, you say that because after infinite time, your algorithm gives a member of a new equivalence class means that there is some n where we actually change equivalence class. This is false.

Consider the sequence of (1/n) it converges to zero, yet no element of the sequence is nonzero. It's the same here, the "end result" of the process of changing finitely many elements at once an infinite number of times is in a different equivalence class, but at no point in the process do we change equivalence classes.

Shaddy wrote:problem 2:

Take the equivalence on infinite sequences of 0s and 1s that two sequences are equal iff they differ in finitely many places. Each person knows all of the equivalence classes and they agree on a specific sequence for each equivalence class. By the axiom of choice, they can do this. When the hats are distributed, the people line up and this is one of the equivalence classes - (since each person is only one person, it will not change the finiteness of how the sequence differs from the others in the class) so each person recites whether there is a 0 or 1 in that place in the memorized sequence. This differs in at most finitely many places from the memorized sequence, so only finitely many people can get it wrong.

Shaddy, will you say a little bit more about your solution? It seems to me that a lot is riding on an ambiguity in "This" in the last sentence. You would agree, right, that when the Nth person recites his number, the maximum number of people who could have gotten their number wrong is "N", and that the number of people who have gotten their number right will be a binomial around N/2?

flOvermind wrote:

DrStraw wrote:Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.

These functions are not periodic. There doesn't exist a d>0 such that f(x) = f(x+d).

Yes they are: d=1. For example f(0.5) = f(1.5) = f(2.5) = 0.25

Time wrote:Identity function: f(x)=x

Not that confusing.

As I said, that is only the identity function under the operation of composition, but the problem is one of function addition. The identity function under addition is f(x) = 0.

jts wrote:

Shaddy wrote:problem 2:

Take the equivalence on infinite sequences of 0s and 1s that two sequences are equal iff they differ in finitely many places. Each person knows all of the equivalence classes and they agree on a specific sequence for each equivalence class. By the axiom of choice, they can do this. When the hats are distributed, the people line up and this is one of the equivalence classes - (since each person is only one person, it will not change the finiteness of how the sequence differs from the others in the class) so each person recites whether there is a 0 or 1 in that place in the memorized sequence. This differs in at most finitely many places from the memorized sequence, so only finitely many people can get it wrong.

Shaddy, will you say a little bit more about your solution? It seems to me that a lot is riding on an ambiguity in "This" in the last sentence. You would agree, right, that when the Nth person recites his number, the maximum number of people who could have gotten their number wrong is "N", and that the number of people who have gotten their number right will be a binomial around N/2?

Looking at the other people, each person will know which equivalence class they are in (as they only fail to know the state of their own hat). Thus everyone will guess based on the same representative of that equivalence class, which differs from the true distribution in only finitely many places.

DrStraw wrote:

flOvermind wrote:

DrStraw wrote:Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.

These functions are not periodic. There doesn't exist a d>0 such that f(x) = f(x+d).

Yes they are: d=1. For example f(0.5) = f(1.5) = f(2.5) = 0.25

It helps to know that the reals modulo one are isomorphic to the zero ring, that is that everything is zero. DrStraw's solution is correct as far as the problem statement is concerned, but a little underhanded, demonstrating that the problem is not sufficiently well defined.

I'm not sure if this will help anyone, but here is where I first heard of the infinite prisoners/hats puzzle--it has a fair bit of exposition. http://cornellmath.wordpress.com/2007/0 ... -is-wrong/

DrStraw wrote:

flOvermind wrote:

DrStraw wrote:Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.

These functions are not periodic. There doesn't exist a d>0 such that f(x) = f(x+d).

Yes they are: d=1. For example f(0.5) = f(1.5) = f(2.5) = 0.25

But under the reals modulo 1, 1 = 0, therefore, d is not > 0
Or, if you define f as a function from the reals to the reals mod 1, f(x) != x. Either the functions are not periodic, or their sum is not the identical mapping (is that the correct English word?).