problem 2:

@gaius The original statement of Redundant's problem is solveable, however much it looks like it isn't.

_________________
Occupy Babel!

Shaddy, your "proof" sounds like it comes from a textbook somewhere, but all my mathematical intuition screams that there must be a flaw in this logic. As I said before, I'm not a mathematician but a physicist - I like to think in terms of concrete stuff.

My first thought was that the whole conclusion seems to conflict with information theory; you generate information where there is none. Can you disprove this line of reasoning? Thinking further though, your "proof" does not do anything for finite sets except for the trivial observation that, with a finite set of people, the number of errors is also finite. You are not really boosting the accuracy rate, you're only making sure the amount of errors is not infinite (right?). Maybe that could lift my objection, though my math is not good enough to really be certain.

After thinking a bit more, I have far greater problems with the following paradox. You imply that, for every infinite sequence of ones and zeroes, it is possible to find a uniquely defined equivalence set. Accepting that, let's evaluate this "algorithm" (it has infinite runtime, but apparently such an algorithm is acceptable in your paradigm!):

1. Take an infinite sequence of ones and zeroes.
2. Change the first element. By definition, the resulting sequence will still be in the same equivalence set as the original one (there is only one mistake!).
3. Now, do the following: IF we are in the original equivalence set, change the next (second, third, etc.) element. ELSE, halt.
4. Repeat (3) for all elements.

Now, obviously, after repeating for all elements, the list will not be in the same equivalence set any more. Therefore, we conclude that after some number of steps (let's call it n), (3) must halt. But then, despite only having one difference, the list at step n-1 and at step n are not in the same equivalence set!

Paradox?

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

Good point! Always interesting, these mathematicians with their non-well-behaved functions . Anyway, I did get quite far with a solution of problem #1, though you'll probably say my solution is not complete:

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

The axiom of choice is obviously baloney. It's a rule mathematicians came up with to get out of doing work.

Bertrand: "Hey boss, I'm taking off early to go fishing."
Boss: "Have you finished that TPS report yet?"
Bertrand: "It is possible for me to do the TPS report, so we can just take it for granted that I did."

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

The order is irrelevant to the solution I have. There is in fact a solution. If anyone wants to check me on this, here it is.
Solution:

Note: I'll come back and edit this to be more readable later. I have to get to class right now.
Also: Shaddy just ninja'd me.

A possible solution to Problem 1, though using complex-valued functions in the complex plane:

_________________
And the go-fever which is more real than many doctors’ diseases, waked and raged...
- Rudyard Kipling, "The Light That Failed" (1891)

Hehe... Nice try, but the problem is that even though f+g converges and is (almost*) equal id, the individual functions f and g do not converge, hence are not really functions. I'm too lazy at the moment to try and verify your solution under the assumption that f and g are allowed to be distributions

There is a solution with proper functions, you don't need distributions. And in the correct solution, (f+g)(x) = x everywhere, not just almost* everywhere

(*Almost, of course, meaning that the exceptions have a Lebesgue measure of zero).

Hehe, that's a nifty way around the real problem . Though, I suppose this depends on your definition, but I don't believe the inequality 2*pi*i > 0 holds. Perhaps the problem should be rephrased for absolute clarity: rather than "d > 0" it could say "real d > 0".

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

Well, inequalities don't actually make any sense in the complex numbers. (By which I mean, there's no way of assigning an order under which all the properties you'd want to be true actually are.) So simply saying d>0 implies that d needs to be real. And, while tundra's "solution" was kind of clever, it's invalid over the reals (x, when restricted to the reals, isn't periodic), and clearly not what flOvermind has in mind.

I'm out of clever ideas myself, and would quite like to hear the solution, actually

That appears to be correct, even though it is not the solution I had in mind. To be honest, it's a bit of a surprise to me that in the complex plane the solution is so "well-behaved"

By the way, your solution is more complicated than necessary:



Way around? Not really, I'd say he's pretty close
d > 0 could actually be replaced by d != 0. The only intention of that was to make sure nobody claims "But my function is periodic, because f(x) = f(x+0) ". In my original post, I even forgot it until DrStraw pointed it out...

A strong hint at the real-valued solution:

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.)

Well, that's what I was groping for anyhow.

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

I think, as Aristotle might say, you are highlighting the difference between potential infinity and actual infinity. (IIRC, Aristotle did not think that actual infinity existed, even logically.) Normally, "for each" and "for all" mean the same thing. However, it does make a difference for step 4. I think that Aristotle would say that you must say, "Repeat (3) for each element." That leaves us in the realm of the potentially infinite. The problem has a solution only in the realm of the actually infinite.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Some general statements about problem two:

It also helps to think of how totally impossible this strategy is to implement in reality. It consists of memorizing an uncountable number of infinitely long sequences of zero and one.

Also, gaius is right in that there is no upper bound on the number of incorrect guesses that can be had, we only know that it will always be finite following this strategy.

However, gaius' algorithm does not in fact halt. At any n, we can have changed at most finitely many members, so we still move on to n+1.

I still fail to see the difference. Of course I understand that the algorithm I posted is completely unreasonable because it will never finish, but so is the solution algorithm as it requires the construction of infinitely many "equivalence classes". However, the "solution algorithm" assumes a theoretical paradigm in which countably infinite runtimes are somehow acceptable, so I will reiterate my point. Either (a) we accept countably infinite runtimes as workeable; my algorithm will finish, and the paradox will be clear, or (b) we do not accept countably infinite runtimes, in which case the "solution algorithm" clearly does not finish, and hence, is not a valid solution to the problem. Whether we choose (a) or (b), the answer is disproved. In fact, if correct, my reasoning would disprove the existence of well-defined equivalence classes.

I realise that people smarter than me have probably considered this point too, but I would really like to hear how they came up with a workaround!

Bill, I am personally not a native English speaker, but in my vocabulary the words "each" and "all" are synonyms. As you might know, Aristotle was not an English speaker either. In fact, he spoke a strange language called Ancient Greek. Perhaps you could elaborate on the difference between these two words?

EDIT: I am not 100% sure that these runtimes are countably infinite. If not, please replace the phrase "countably infinite" by "infinite". The reasoning will be unaffected.

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

I think I see a problem with your algorithm. It seems to me that you are saying, ok, we have an infinite sequence of 0s and 1s like this

001010100110110101001...

and we flip bits in sequence until we arrive at something that is not in our original equivalence class. However, we should not be keeping them flipped. Each person has knowledge of every hat except his own, so the first person's knowledge is like


_01010100110110101001...

, the second person's like

0_1010100110110101001...

and so on. Each person knows the entire sequence, except one bit- so it's always finitely different from the sequence they have memorized because they make at most one mistake.

edit: about the information thing. I don't know if that really applies here, because the scenario is completely removed from reality, but by setting an order, we gain some information, which we use to do stuff with equivalence classes. And yeah, this doesn't work for finite numbers of people, there's a separate solution for that case of the problem.

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.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

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.

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).