Reasons to disbelieve the Axiom of Choice

[lpetrich]

 Axiom of choice - For every set of nonempty subsets of some set, there is some function that maps each subset onto an element of it.

It follows from the other axioms of set theory for finite sets, but not for infinite ones.

 

[Jarhyn]

A thought, at @Swammerdami, can you postulate some method of selecting prisoners for which the methodology of this selection cannot be reverse engineered by the prisoners observing the series?

I don't think you can.

So, either there is some way to break the "randomness" of the series and thus for every prisoner to be correct, or the series itself cannot be constructed.

 

[Swammerdami]

A thought, at @Swammerdami, can you postulate some method of selecting prisoners for which the methodology of this selection cannot be reverse engineered by the prisoners observing the series?

I don't think you can.

So, either there is some way to break the "randomness" of the series and thus for every prisoner to be correct, or the series itself cannot be constructed.

"some method of selecting prisoners" — Do you mean "some method of selecting prisoners' hat colors"?

As I said, the solution (when AC is assumed) ALWAYS works! It doesn't depend on whether the sequence of colors is random or contrived. Remember that the prisoners, before seeing any hats, will consult together on their strategy. The prison warden can eavesdrop on this discussion, try to select a sequence that counters their strategy, but still the prisoners will succeed (i.e. only a finite number will misguess their color).

 

[Jarhyn]

A thought, at @Swammerdami, can you postulate some method of selecting prisoners for which the methodology of this selection cannot be reverse engineered by the prisoners observing the series?

I don't think you can.

So, either there is some way to break the "randomness" of the series and thus for every prisoner to be correct, or the series itself cannot be constructed.

"some method of selecting prisoners" — Do you mean "some method of selecting prisoners' hat colors"?

As I said, the solution (when AC is assumed) ALWAYS works! It doesn't depend on whether the sequence of colors is random or contrived. Remember that the prisoners, before seeing any hats, will consult together on their strategy. The prison warden can eavesdrop on this discussion, try to select a sequence that counters their strategy, but still the prisoners will succeed (i.e. only a finite number will misguess their color).

But... That's the thing. CAN you select that sequence? Can you describe a function guaranteed to violate all tests for statistical randomness?

As I'm looking at it, the problem itself seems to not make sense in the first place.

Your OP on the subject says explicitly IF there is an argument for Mythicism, THEN they should be able to articulate it.

Is there an argument for statistically impenetrable randomness?

Because your problem may have a problem.

 

[Swammerdami]

But... That's the thing. CAN you select that sequence? Can you describe a function guaranteed to violate all tests for statistical randomness?
. . .
Your OP on the subject says explicitly IF there is an argument for Mythicism, THEN they should be able to articulate it.

It DOES seem impossible that the prisoners have a successful strategy. As I've said, the whole argument can be viewed as a demonstration that the Axiom of Choice is FALSE!

The Axiom of Choice IS, however, valid when applied to FINITE sets. (I stipulated that the Mythicism argument had to fit in the Library of Congress.)

 

[Jarhyn]

But... That's the thing. CAN you select that sequence? Can you describe a function guaranteed to violate all tests for statistical randomness?
. . .
Your OP on the subject says explicitly IF there is an argument for Mythicism, THEN they should be able to articulate it.

It DOES seem impossible that the prisoners have a successful strategy. As I've said, the whole argument can be viewed as a demonstration that the Axiom of Choice is FALSE!

The Axiom of Choice IS, however, valid when applied to FINITE sets. (I stipulated that the Mythicism argument had to fit in the Library of Congress.)

More, I don't see it as impossible that the prisoners have a successful strategy. Rather, I see the wardens as having no possible successful strategy, and that this is the case due to the fact that they cannot make any sequence that prevents calculation of the sequence based on the computer you give to the prisoners.

Even if you can devise a mechanism that produces "random seeming" numbers, the prisoners have infinite computing power to break that.

What I'm seeing here is an experiment that assumes a contradiction: an algorithm which cannot be expressed.

As such it might fall to the same complaint you have with the AC in wanting it to not be able to assume the existence of an algorithm which cannot be expressed.

 

[Jarhyn]

I think it might come down to whether one accepts the idea of "ineffable randomness".

It is a fact that each prisoner will be looking at either something that can be coerced to make sense, or something that cannot be coerced to make sense, and each individual prisoner, despite being lined up and seeing different slices of the same... Well again, depends on whether you accept ineffable randomness as a coherent thought, but... "unsolvable problem".

Each prisoner is in effect looking not at prisoners but a random set of discorollate fields, for which removal of themselves does not change the statistics.

They cannot possibly know something they by definition are being assumed cannot be calculated on: ineffable randomness.

So either there isn't ineffable randomness and the infinite series can be isolated in some way as to find it in finite descriptive space OR there is ineffable randomness and the infinite series is just each prisoner seeing a similar but different random series and being asked to pick a number from 1 to 1000, and the gambler's fallacy by definition means that what they see does not inform them of their hat color.

You have to be able to describe the set, for it to be a set, and you have not described, cannot describe infinite randomness and complexity.

And if the randomness is ineffable... How do the guards express it upon the line?

 

[Bomb#20]

Whether the prisoner knows his own number or not turns out not to matter to the solution.
Similarly, the solution works whether the hat assignments are random or contrived.

(This curious paradox is "well-known." I've not posted any link, but Google will find lots.)

Solution DOES assume that each prisoner is able to contemplate the countably infinite sequence of hats — already impossible in the real world — as well as the uncountable set of such sequences. But just replace each "prisoner" with a mathematical abstraction: Doesn't that legitimize the pure-mathematical question?

Well, if that's the case, I stand by my answer: if every prisoner guesses the least common hat color that they see, it will be their hat color, assuming a perfect infinite normal distribution: they will always be the "odd man out".

Information about commonness and hat distribution is the only thing any prisoner can possibly see and the axiom of choice.
...
This obviously doesn't work if the pure distribution is not actually perfectly random.

There's no such thing as "the least common hat color that they see" in an infinite random distribution. They can't count all the red hats and get infinity and then count all the chartreuse hats and get infinity minus one. Infinity minus one is still infinity.

(They can of course measure the asymptotic density of the colors and choose the lowest, if they're unequal, but the asymptotic density is the same regardless of anyone's personal hat color -- if they rely on that they will all see the same asymptotic densities and therefore all make the same guess.)

 

[Jarhyn]

H

Whether the prisoner knows his own number or not turns out not to matter to the solution.
Similarly, the solution works whether the hat assignments are random or contrived.

(This curious paradox is "well-known." I've not posted any link, but Google will find lots.)

Solution DOES assume that each prisoner is able to contemplate the countably infinite sequence of hats — already impossible in the real world — as well as the uncountable set of such sequences. But just replace each "prisoner" with a mathematical abstraction: Doesn't that legitimize the pure-mathematical question?

Well, if that's the case, I stand by my answer: if every prisoner guesses the least common hat color that they see, it will be their hat color, assuming a perfect infinite normal distribution: they will always be the "odd man out".

Information about commonness and hat distribution is the only thing any prisoner can possibly see and the axiom of choice.
...
This obviously doesn't work if the pure distribution is not actually perfectly random.

There's no such thing as "the least common hat color that they see" in an infinite random distribution. They can't count all the red hats and get infinity and then count all the chartreuse hats and get infinity minus one. Infinity minus one is still infinity.

(They can of course measure the asymptotic density of the colors and choose the lowest, if they're unequal, but the asymptotic density is the same regardless of anyone's personal hat color -- if they rely on that they will all see the same asymptotic densities and therefore all make the same guess.)

Hence my point that each prisoner is seeing a number that removing themselves from does not change.

See my later posts on randomness and the problem itself.

If Swammerdami can provide me with a way of assigning an infinite number of hats in any finite way, it can be derived from the infinite series of hats, with an "infinitely" powerful computer, and the prisoners can apply some process to figure it out, and the number of wrong guesses is exactly zero.

If the question is to identify how to predict something that contradicts math entirely, then it's a nonsense question in the first place.

If the problem cannot be expressed, how can it be solved or even considered as solvable?

 

[Bomb#20]

"some method of selecting prisoners" — Do you mean "some method of selecting prisoners' hat colors"?

As I said, the solution (when AC is assumed) ALWAYS works! It doesn't depend on whether the sequence of colors is random or contrived. Remember that the prisoners, before seeing any hats, will consult together on their strategy. The prison warden can eavesdrop on this discussion, try to select a sequence that counters their strategy, but still the prisoners will succeed (i.e. only a finite number will misguess their color).

But... That's the thing. CAN you select that sequence?

Piece of cake.

We're evidently assuming counterfactual physics here, since we're postulating an infinite line of prisoners who can all see and distinguish everyone ahead of themselves, and can derive judgments from this information. This puzzle is therefore set in an alternate universe where everyone can receive and process in finite time an infinite amount of information from unbounded distances. So we just allow the wardens to rely on the same alternate physics. They choose the sequence of prisoners based on the infinite sequence of photons they receive in finite time from the infinitely many stars they can see.

Can you describe a function guaranteed to violate all tests for statistical randomness?

"f( n ) = 0".

I take it you meant "to pass all tests". Can I describe such a function? No. "Describe" for humans necessarily involves a finite description. But can a prisoner or guard in Swami-world describe such a function? Could be. They have the ability to operate on infinitely large descriptions. You seem to be approaching this puzzle with the assumption that the infinities in that alternate world can all be generated by finite procedures. So I think you and Swami are not talking about the same puzzle.

Is there an argument for statistically impenetrable randomness?

In the real world? Sure: it's the observation that quantum mechanics appears to work but nobody has yet successfully constructed a deterministic model that matches QM predictions.

 

[Jarhyn]

sequence of photons they receive in finite time from the infinitely many stars they can see

And the prisoners can given infinite time to look at that past result of this whole physical process, derive that. Even sourcing it from an entirely different universe, given infinite time, and processing power, there is some determinism that determines the sequence and that may be derived.

No matter how far you run from it, you still need to be able to express this randomness and it won't be "ineffable", it will just be large.

Either way you're attempting to build the math problem on something which does not exist in the scope of math problems especially of infinite sequences.

 

[Bomb#20]

sequence of photons they receive in finite time from the infinitely many stars they can see

And the prisoners can given infinite time to look at that past result of this whole physical process, derive that. Even sourcing it from an entirely different universe, given infinite time, and processing power, there is some determinism that determines the sequence and that may be derived.

But the prisoners are denied access to part of the data they'd need in order to do that -- they don't get to see the color of their own hats or the hats behind them. If you're proposing that a prisoner simulate the whole universe for all possible arrangements of stars, derive the hat color sequence that each arrangement would cause the guards to select, and pick the simulation that gives a result that matches what he sees, that won't give a unique solution. Infinitely many simulations will predict hat arrangements that match what he sees. Some of those simulations will predict his own hat is red and some of them will predict it's blue.

 

[Jarhyn]

sequence of photons they receive in finite time from the infinitely many stars they can see

And the prisoners can given infinite time to look at that past result of this whole physical process, derive that. Even sourcing it from an entirely different universe, given infinite time, and processing power, there is some determinism that determines the sequence and that may be derived.

But the prisoners are denied access to part of the data they'd need in order to do that -- they don't get to see the color of their own hats or the hats behind them. If you're proposing that a prisoner simulate the whole universe for all possible arrangements of stars, derive the hat color sequence that each arrangement would cause the guards to select, and pick the simulation that gives a result that matches what he sees, that won't give a unique solution. Infinitely many simulations will predict hat arrangements that match what he sees. Some of those simulations will predict his own hat is red and some of them will predict it's blue.

No, they have exactly access to an infinite source of data from which the sequence is defined: the sequence itself.

If we're going to assume that happened at some time in the past, and they have infinite access to that series, it had to be produced by some process which will ultimately be derivable, because the process which creates it.

I repeat that if you wish to postulate an infinite series, you have to postulate a mechanism that allows it's construction without contradictions or nonsense.

Even the computer afforded the prisoners is only relying on finite but large numbers of operations to drive and predict the series.

The experiment cannot be constructed in such a way that the prisoners cannot crack the series, without postulating ineffable randomness. If you have ineffable randomness, each prisoner can only gamble on 1:nHats.

You're still going to have to justify your postulate that you can produce random numbers that way.

 

[Bomb#20]

sequence of photons they receive in finite time from the infinitely many stars they can see

And the prisoners can given infinite time to look at that past result of this whole physical process, derive that. Even sourcing it from an entirely different universe, given infinite time, and processing power, there is some determinism that determines the sequence and that may be derived.

But the prisoners are denied access to part of the data they'd need in order to do that -- they don't get to see the color of their own hats or the hats behind them. If you're proposing that a prisoner simulate the whole universe for all possible arrangements of stars, derive the hat color sequence that each arrangement would cause the guards to select, and pick the simulation that gives a result that matches what he sees, that won't give a unique solution. Infinitely many simulations will predict hat arrangements that match what he sees. Some of those simulations will predict his own hat is red and some of them will predict it's blue.

No, they have exactly access to an infinite source of data from which the sequence is defined: the sequence itself.

Part of the sequence, not all of it. It's specified in the conditions of the puzzle that prisoner N does not have access to elements 0 through N of the sequence.

If we're going to assume that happened at some time in the past, and they have infinite access to that series, it had to be produced by some process which will ultimately be derivable, because the process which creates it.

Your explanation cuts off in the middle. ...because the process which creates it what?

I repeat that if you wish to postulate an infinite series, you have to postulate a mechanism that allows it's construction without contradictions or nonsense.

There's no contradiction or nonsense involved in postulating a possible universe whose initial conditions contain an infinite amount of data. For all we know, our own universe might be an example of that.

Even the computer afforded the prisoners is only relying on finite but large numbers of operations to drive and predict the series.

Upthread you said 'Even if you can devise a mechanism that produces "random seeming" numbers, the prisoners have infinite computing power to break that.'. You appear to be relying on contradictory premises.

The experiment cannot be constructed in such a way that the prisoners cannot crack the series, without postulating ineffable randomness.

Ineffable randomness is a pretty small bite to chew once you've postulated an infinite universe. If you aren't willing to accept that QM generates new random data retail, then you're pretty much committed to assuming a deterministic universe that must have started out already loaded with infinitely many bits. That's still ineffable randomness -- just wholesale instead of retail, and swept under the rug into the unexplainable initial conditions so we don't have to watch the bits forming before our eyes.

If you have ineffable randomness, each prisoner can only gamble on 1:nHats.

According to Swami, the Axiom of Choice offers an escape hatch from that conclusion. It will be interesting to see his argument whenever he decides we've stewed on it long enough...

You're still going to have to justify your postulate that you can produce random numbers that way.

The proof is in the laboratory. As far as we can tell, every time a photon hits a piece of glass it generates a true random number, when it passes through or bounces back.

 

[Swammerdami]

When the problem is posed with flesh-and-bones prisoners, it assumes impossible physics. Even a computer with a countably infinite number of transistors wouldn't be able to cope with the uncountable power set.

But the problem can be reframed into the language of pure mathematics, using quantifiers. Abstract mathematics works with infinite sets routinely.

I'll post the solution in a day if nobody beats me to it. Unlike the Banach-Tarski Paradox, where the use of AC is buried amid other ornate complexity, the "proof" that only a finite number of prisoners will misguess is breathtakingly simple! Start with the brief Spoiler upthread, and think about Equivalence Classes.

(I put "proof" in quotes because this ridiculous result puts serious doubt on the truthiness of the Axiom of Choice!)


ETA: "serious doubt about Choice" — Mods, please do not move this thread to the discussion of Determinism in the Religious forum.

 

[Jarhyn]

The really stupid assumption would be that for any A that contains all sequences, you should be able to select a B that is one of the sequences A contains that will start at some finite point in sequence A, so all you have to do is define any one sequence and assume when you see it, you're at the head of it. Or something really dumb like that. Maybe the reverse? At some point the assumption is that one infinite set contains another infinite set as a subset.

This is silliness though and assumes some things about randomness, which is my point going back to the fact that I would like to see @Swammerdami pose a way of defining an infinite set whose foundation cannot be derived or described with visibility on the set.

 

[Swammerdami]

An infinite set of prisoners {#1, #2, #3, ...}, are each given a colored hat and can see hats in front of them: #j sees #(j+1), #(j+2), ... With no information except his location (#j), and the hats he can see, and any strategy discussed the night before with his fellows, each prisoner tries to guess his own hat color.

Devise a strategy that guarantees that only a finite number of prisoners will misguess. You should assume the Axiom of Choice.

~ ~ ~ ~ ~ ~ ~ ~

SOLUTION:

Write 'a' or 'b' to denote an infinite sequence of hat colors:
a = a₁a₂a₃a₄ ...
b = b₁b₂b₃b₄ ...
Write a ≈ b to denote that a and b differ at only a finite number of points.

If a is the actual correct sequence (a_j is the hat color of prisoner #j) and b is the sequence of guesses, then the prisoners succeed if and only if a ≈ b.

Note that a ≈ b and b ≈ c imply that a ≈ c. This makes '≈' an equivalence relation. This relation partitions the set of all sequences into an uncountable number of equivalence classes. Each prisoner (#j) observes all but a finite number of hats (#1, #2, ..., #j) and therefore knows which equivalence class contains the actual sequence. Only one such class fits; that class will be the same for all prisoners.

During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence. For example, suppose they assigned 'b' as the representative of the class containing 'a.' The prisoners simply guess their hat color according to 'b.' Since a ≈ b, they succeed.
Q.E.D.

Here is one write-up on the problem. That article mentions that the solution works even if the number of prisoners and/or the number of hat colors is uncountable. It shows, at least for the countable case, that the number of misguesses can be reduced to just one at the most, if prisoners can hear earlier guesses.
~ ~ ~ ~ ~ ~ ~ ~ ~

I realize that I botched the presentation of this puzzle in at least two important ways. I am hugely embarassed.
Major apologies to all. Give yourselves full credit if you were misled by my mistakes.
I don't know what excuses to offer — (personal crises? creeping senility?) — but I should refrain from attempting presentations of this complexity in future.

 

[Bomb#20]

With no information except his location (#j), and the hats he can see, and any strategy discussed the night before with his fellows, each prisoner tries to guess his own hat color.
...
I realize that I botched the presentation of this puzzle in at least two important ways. I am hugely embarassed.

I take it one botch is that earlier you said whether a prisoner knows his own number doesn't matter. (That botch doesn't strike me as terribly important; we can just take it as read that when the prisoners agree on strategy they agree on what order to present themselves to the guards in, and the guards don't bother to reorder the prisoners.)

So what's the other way you botched it? I don't see any other significant difference between your presentation and the one in your link. (You have a thousand hat colors and the link has two, but I can't see how that would matter.)

There also appears to be an error in the link's extension of the problem to an uncountable infinity.

"By the way, what happens if you have an uncountable infinity of prisoners? Say we make them infinitely thin and then squeeze them along the real line so as to populate every point. Each prisoner can see all but a finite number of the other prisoner’s hats."​

That's wrong. Each prisoner can't see the hats on the prisoners behind him. He can see all but a finite amount of the line; but that line segment contains uncountably many prisoners, not a finite number, since the prisoners are infinitely thin and populate every point.

Anyway, I'll stop here. The argument as presented appears on its face to be invalid -- the proposed solution appears to fail even when we assume AC. So the crazy alleged implication is actually no reason to reject AC. But maybe I'm being misled by the second botch, so I'll wait to hear what that is before pointing out the prima facie error in the argument.

 

[Jarhyn]

Write 'a' or 'b' to denote an infinite sequence of hat colors:
a = a1a2a3a4 ...
b = b1b2b3b4 ...
Write a ≈ b to denote that a and b differ at only a finite number of points.

If a is the actual correct sequence (aj is the hat color of prisoner #j) and b is the sequence of guesses, then the prisoners succeed if and only if a ≈ b.

Note that a ≈ b and b ≈ c imply that a ≈ c. This makes '≈' an equivalence relation. This relation partitions the set of all sequences into an uncountable number of equivalence classes. Each prisoner (#j) observes all but a finite number of hats (#1, #2, ..., #j) and therefore knows which equivalence class contains the actual sequence. Only one such class fits; that class will be the same for all prisoners

The really stupid assumption would be that for any A that contains all sequences, you should be able to select a B that is one of the sequences A contains that will start at some finite point in sequence A, so all you have to do is define any one sequence and assume when you see it, you're at the head of it. Or something really dumb like that. Maybe the reverse? At some point the assumption is that one infinite set contains another infinite set as a subset.

This is silliness though and assumes some things about randomness, which is my point going back to the fact that I would like to see @Swammerdami pose a way of defining an infinite set whose foundation cannot be derived or described with visibility on the set.

 

[Swammerdami]

The other botch I made was presenting the setup as though each prisoner sees a finite number of hats instead of an infinite number.

~ ~ ~ ~ ~ ~ ~
@ Jarhyn — I did notice that you were pointed at the solution, but you didn't articulate it completely. And you insisted on randomness, which is irrelevant to the puzzle.

I think you were arguing that solution is impossible, which it is (without the Axiom of Choice). But David Hilbert said "Mathematics is a game played according to certain simple rules with meaningless marks on paper." Play the game!