Reasons to disbelieve the Axiom of Choice

[Jarhyn]

Countable vs uncountable infinity is generally seen as the difference between a series of numbers that can each be enumerated one to the next in series, and a series in which this is impossible because there are things between each of the things, and you can always find another thing to set between any two.

Having more things between any two things isn't what makes a set uncountable. Between any two rational numbers there are more rationals; for instance (A + B) / 2 is in between A and B. But the rational numbers are a countable infinity.

And this exercise is similar to setting aside the odd numbers for the evens, setting aside the 1's for the 1/2s, setting aside for the 2/3's and the 1/3's, etc, each also ending up the same set

To get to uncountable you need something that doesn't order as a count but rather as an evolving operation on a count, as per numbers like pi, where 3, into 1, into 4....

So you were right insofar as I described it badly.

We don't end up uncountable until irrational numbers start happening, numbers which are defined in terms of a recursive or internally iterative process.

 

[Bomb#20]

And this exercise is similar to setting aside the odd numbers for the evens, setting aside the 1's for the 1/2s, setting aside for the 2/3's and the 1/3's, etc, each also ending up the same set

Yes, exactly.

To get to uncountable you need something that doesn't order as a count but rather as an evolving operation on a count, as per numbers like pi, where 3, into 1, into 4....

So you were right insofar as I described it badly.

We don't end up uncountable until irrational numbers start happening, numbers which are defined in terms of a recursive or internally iterative process.

Actually even that isn't enough to get to an uncountable set; that only gets you to the "computable numbers". You can still put numbers like pi and the square root of 2 in a discrete sequence, based on putting the programs that systematically generate their digits into alphabetical order. Since there are only a countable infinity of finite programs, there can only be a countable infinity of computable numbers. To get an uncountable set you need to include numbers that need infinitely long programs to generate their digits.

 

[Jarhyn]

And this exercise is similar to setting aside the odd numbers for the evens, setting aside the 1's for the 1/2s, setting aside for the 2/3's and the 1/3's, etc, each also ending up the same set

Yes, exactly.

To get to uncountable you need something that doesn't order as a count but rather as an evolving operation on a count, as per numbers like pi, where 3, into 1, into 4....

So you were right insofar as I described it badly.

We don't end up uncountable until irrational numbers start happening, numbers which are defined in terms of a recursive or internally iterative process.

Actually even that isn't enough to get to an uncountable set; that only gets you to the "computable numbers". You can still put numbers like pi and the square root of 2 in a discrete sequence, based on putting the programs that systematically generate their digits into alphabetical order. Since there are only a countable infinity of finite programs, there can only be a countable infinity of computable numbers. To get an uncountable set you need to include numbers that need infinitely long programs to generate their digits.

If you need an infinitely long program to generate any digit of a number, is it a number?

A while back I looked into numbers that were not computable and all the instances I saw indicated that everything considered such a number is on the lines of a universal constant.

The issue is that the geometry of the universe seems such that the properties they derive from are finite in nature, though very large.

This is on, as I understand it, the nature of spacetime expansion, and the speed of light. At some point, if expansion continues accelerating, eventually each locality will be cleaved, but the sum total of "visibility expansion" will be finite right up until visibility starts ripping away, at which point causal influence shrinks to nothing as every last virtual particle is moving away from ever other virtual particle at superluminal speeds.

This means that there will be a finite total of observation by any particle in all of it's history from pop to rip.

As such, the granularity and the limitations of observation amount to a situation where the universe we experience is going to produce ultimately calculable states, were you to have a computer big enough to calculate on it.

Godel's Incompleteness Theorem says we can't ever actually do that work, since we can't get a big enough computer to accomplish it.

And this means that even universal constants with very precise values (or perhaps in this case particular constants, although there's little difference at that point) would even be "calculable".

So there's some question out in fact as to whether the idea of an incalculable number exists.

 

[Swammerdami]

The prima facie hole in the argument is here: "During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

The Axiom of Choice guarantees that such a choice function exists; it doesn't guarantee that prisoners can all agree on one. In general there will be infinitely many choice functions for a prisoner to choose from among. By what mechanism will the prisoners be able to pick out one from all the possibilities and ensure that they're all going to use the same choice function when it comes to deciding what color to say their hats are?

Is this objection to the mathematical abstraction, or to "real-world" limitations? For example, instead of an infinite number of prisoners, could we postulate a Hydra-like creature with a single brain to come up with the choice function, but that had to use his infinitely-many fire-walled brainlets during the guessing phase?

Or maybe you've hit on the fundamental flaw (or elusiveness) in the Axiom of Choice: It's one thing to say "There exists a choice function" and another thing to actually hold that function in your hands, or be able to write it down.

Having more things between any two things isn't what makes a set uncountable. Between any two rational numbers there are more rationals; for instance (A + B) / 2 is in between A and B. But the rational numbers are a countable infinity.

The rationals are proven to be countable if they can be mapped one-to-one to a subset of the natural numbers. An inelegant brute-force way is to map each a/b to (2^a3^b). (Multiply this by 5 to represent -a/b.) Insist that a/b be in lowest terms to avoid duplication.

I think that a similar approach can be used to show that each of the equivalence classes I introduced upthread is countable (though this demonstration uses AC at the outset). If 'a' is in the class whose chosen representative is 'b' then 'a' has a finite number of "misguesses" (m₁. m₂ ...) each of the form (i,j) where i and j are natural numbers: — 'i' is the location of the misguess, 'j' is the wrong guess.

(i,j) can be represented with the integer (m = 2ⁱ3^j). 'b' itself can be denoted (given knowledge of its class's representative) by
2^m₁3^m₂5^m₃7^m₄ ...
That is, the k'th misguess is encoded as the exponent of the k'th prime.

If this is correct — and by now I'm giving myself at best a 30% chance — then it means we are using only a weak form of the Axiom of Choice in the proof upthread: We are imposing a choice function on an (uncountable) collection of COUNTABLE sets.

 

[Jarhyn]

The prima facie hole in the argument is here: "During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

The Axiom of Choice guarantees that such a choice function exists; it doesn't guarantee that prisoners can all agree on one. In general there will be infinitely many choice functions for a prisoner to choose from among. By what mechanism will the prisoners be able to pick out one from all the possibilities and ensure that they're all going to use the same choice function when it comes to deciding what color to say their hats are?

Is this objection to the mathematical abstraction, or to "real-world" limitations? For example, instead of an infinite number of prisoners, could we postulate a Hydra-like creature with a single brain to come up with the choice function, but that had to use his infinitely-many fire-walled brainlets during the guessing phase?

Or maybe you've hit on the fundamental flaw (or elusiveness) in the Axiom of Choice: It's one thing to say "There exists a choice function" and another thing to actually hold that function in your hands, or be able to write it down.

Having more things between any two things isn't what makes a set uncountable. Between any two rational numbers there are more rationals; for instance (A + B) / 2 is in between A and B. But the rational numbers are a countable infinity.

The rationals are proven to be countable if they can be mapped one-to-one to a subset of the natural numbers. An inelegant brute-force way is to map each a/b to (2^a3^b). (Multiply this by 5 to represent -a/b.) Insist that a/b be in lowest terms to avoid duplication.

I think that a similar approach can be used to show that each of the equivalence classes I introduced upthread is countable (though this demonstration uses AC at the outset). If 'a' is in the class whose chosen representative is 'b' then 'a' has a finite number of "misguesses" (m₁. m₂ ...) each of the form (i,j) where i and j are natural numbers: — 'i' is the location of the misguess, 'j' is the wrong guess.

(i,j) can be represented with the integer (m = 2ⁱ3^j). 'b' itself can be denoted (given knowledge of its class's representative) by
2^m₁3^m₂5^m₃7^m₄ ...
That is, the k'th misguess is encoded as the exponent of the k'th prime.

If this is correct — and by now I'm giving myself at best a 30% chance — then it means we are using only a weak form of the Axiom of Choice in the proof upthread: We are imposing a choice function on an (uncountable) collection of COUNTABLE sets.

And this is what I attack as well: that you declare there is a CHOICE function that can create an infinite series that satisfies your requirements for absolute randomness.

My postulate is that the prisoners don't need to even prearrange on the sequence they are looking for. Rather they have to formulate a strategy for effectively attacking infinite randomness until the strategy starts predicting values, and when it starts predicting with high enough statistical certainty, check self.

Because we have postulated a computer that can process infinite sets, we can have perfect certainty. Anything less and it would be a gamble over who halts at lower computational complexity, the guard or the prisoner.

In such a world zero prisoners die.

I'm not quite sure whether there exists a strategy to "lie" for every prisoner given a finite known halting point in check depth: to plan a sequence which, if they checked their solution to (their n)+x=N, it will lie about their hat color 100% of the time, and if they checked their solution to N+x would have found the correct sequence for that N. Such that if prisoner.1 saw 2,3,4,6,7,8,9,0,1,2,3... And said "aha, it counts from 1" it wouldn't work because the Algorighm cycles in such a way as to miss 1 and actually start with 0, in some epoch, so prisoner 1 dies... And so on such that 2, while seemingly apparent, is at some later stage implied to be a 1, but not in the epoch where it is 2... And so on?

And if so, what is the bound of this halting problem conflict?

There's a lot more interesting math in this than the pinwheel problem.

I really wish I could have drawn that solution that I saw out, and you would have seen how it was a proof...

 

[Swammerdami]

Jarhyn — If I understand correctly, you are using the idea that Non-constructible numbers cannot be constructed. And that since the prison warden constructed the sequence 'b', it must be a constructible (computable) object. Is that basically the idea? Non-computable numbers do not exist?

I think this would put you in good company: The great mathematician 'Leopold Kronecker, one of the early critics of set theory was famously quoted as responding to a paper describing the properties of π by saying, roughly, "Why are you wasting your time studying something which doesn't exist?"' (Although π may be a bad example since it has finite Kolmogorov complexity.)

Although my work has been in simple applied math, and always with simple constructible objects, I guess I'm philosophically more in tune with David Hilbert. Mathematics is just a game; and we can make up our own rules!

 

[Jarhyn]

Jarhyn — If I understand correctly, you are using the idea that Non-constructible numbers cannot be constructed. And that since the prison warden constructed the sequence 'b', it must be a constructible (computable) object. Is that basically the idea? Non-computable numbers do not exist?

I think this would put you in good company: The great mathematician 'Leopold Kronecker, one of the early critics of set theory was famously quoted as responding to a paper describing the properties of π by saying, roughly, "Why are you wasting your time studying something which doesn't exist?"' (Although π may be a bad example since it has finite Kolmogorov complexity.)

Although my work has been in simple applied math, and always with simple constructible objects, I guess I'm philosophically more in tune with David Hilbert. Mathematics is just a game; and we can make up our own rules!

Indeed we can make up our own rules, but we still have to be able to make those rules.

 

[steve_bank]

ok, thanks Jaryn.

In the past some on the forum argued an infity can be equated to a finite count.

Mathematically for an infinite number of possibilities the probability of any one occurrence is zero.

That's not the case for a countable infinity, i.e. if the number of possibilities is the same as the number of integers. The probabilities can all be nonzero. For example, the probability can be 50% for the first possibility, 25% for the second, 12.5% for the third, and so forth. The infinite number of finite probabilities must all add up to 100%, which won't be the case if they're all zero.

But for a continuous probability distribution over an uncountable infinity, yes, you're correct.

I looked at this a ways back on thread on infinities. I don't think a countable infinity means a finite representation of an infinite set.

Countable and infinite are mutually exclusive. Infinity is not a number and means uncountable.

I was using technical jargon instead of writing in plain English, sorry. Infinities come in a lot of different sizes. When mathematicians say "countable", what they mean is the smallest kind of infinity there is: an infinity of discrete members that's the same size as the set of integers. They're distinguishing that kind of infinity from all the other kinds of bigger infinities, such as a continuous infinity the same size as the set of real numbers. For historical reasons the smallest infinity is called "countable", but it's a stupid name that always causes confusion.

Tossing a die with an infinite number of faces can not have a probability.

True; but that just means a die is the wrong machine for selecting from an infinite number of discrete possibilities. Instead, use a "Wheel of Fortune" wheel with an infinite number of slots for the flipper-thing to end up in. Each slot has a finite nonzero probability proportional to the angle between its sides. Of course the slot angles can't all be equal. But if you install a slot of some width in the wheel, and then make the next slot take up part of the unused space, and go on in this way, with each slot taking up part of what's unused but never once using up all of it, then you can keep doing that an infinite number of times and end up with a wheel where each slot has a probability. (Never mind that most of the slots are smaller than an atom -- we're doing math here, not engineering. )

Thanks for that. I know little in number and set theory but I do know statistics.

The crux of the problem seems to be predicting the problem of assigning a pobability to a sampleg from and infinite set. If you have a bucket of infinite objects you can reach in and pick one, but you cant't assign a probility

Put 90 red balls and 10 blue balls in a box. Shake and pick one. Put it back, shake, and pick again. Over time you will get blue balls 10% of the time. If you put an infinite number of red balls in the box and 10 red, mathematically the probabilty is undefined.

The probability of a die is 1/6. The ttoal prbality space is 6/6. inf/5 has no meaning.

I think infinity is a bit divide by zero. Electronically we can add, subtract, multiply, and divide with analog and digital circuits. However there is no circuit that can fivide by zero. There is also no circuit that can add, subtract, multiply, or divide with an infinity. There is no physical representation. In an anlog divider as the denominator goes to zero infnity is asymptoivally approched limied by curcuit voltges.

The same as lim x->0 1/x asymptotically goes to infinity.

I'll invoke Turing Machines. From Theory Of Computation for a problem to be solveable it must be Turing computable. In todays terms that means cding ito n a PC.


I'm not a good theroretical math perosn. If I were to approch the problem I would try and reduce it to an algorith. My guess woud br you will run up against ad impossible math condition. Metaphysics do give me a headache .

 

[Jarhyn]

My guess woud br you will run up against ad impossible math condition

My guess is that you are right, on account of the whole argument from my point being that if you can't reduce it to an algorithm such that it allows expression of any part of it, what is the basis for even proclaiming it is there? No part of it, by definition, allows expression! Which would mean including itself.

 

[Jarhyn]

@Swammerdami it appears your discussion might touch on the question about the (widely considered nonsensical) hypothetical set U in math, "the set that contains all sets", as this touches on the equivalence class issue, and the idea of a number of such "infinite complexity"

 

[Bomb#20]

The prima facie hole in the argument is here: "During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

The Axiom of Choice guarantees that such a choice function exists; it doesn't guarantee that prisoners can all agree on one. In general there will be infinitely many choice functions for a prisoner to choose from among. By what mechanism will the prisoners be able to pick out one from all the possibilities and ensure that they're all going to use the same choice function when it comes to deciding what color to say their hats are?

Is this objection to the mathematical abstraction, or to "real-world" limitations? For example, instead of an infinite number of prisoners, could we postulate a Hydra-like creature with a single brain to come up with the choice function, but that had to use his infinitely-many fire-walled brainlets during the guessing phase?

Whoa![/keanureeves]

Maybe that plugs the hole in your proof; I'm not sure. Either way, full marks for creativity!

Or maybe you've hit on the fundamental flaw (or elusiveness) in the Axiom of Choice: It's one thing to say "There exists a choice function" and another thing to actually hold that function in your hands, or be able to write it down.

Elusiveness I'd say, not flaw. The choice functions you can hold in your hands and write down, you don't need an extra axiom for. The whole point of the axiom is to make the elusive ones available.

The rationals are proven to be countable if they can be mapped one-to-one to a subset of the natural numbers. An inelegant brute-force way is to map each a/b to (2^a3^b). (Multiply this by 5 to represent -a/b.) Insist that a/b be in lowest terms to avoid duplication.

I think that a similar approach can be used to show that each of the equivalence classes I introduced upthread is countable (though this demonstration uses AC at the outset). ...
If this is correct — and by now I'm giving myself at best a 30% chance — then it means we are using only a weak form of the Axiom of Choice in the proof upthread: We are imposing a choice function on an (uncountable) collection of COUNTABLE sets.

It's clear that each equivalence class is countable and that there are uncountably many of them. But I don't think that means you're only using a weak form of AC. There's a known weak form called the Axiom of countable choice, but that asserts the existence of choice functions on countable sets of sets, not on uncountable sets of countable sets. I haven't heard that limiting the size of the member sets to countable infinities makes the axiom any weaker.

 

[Swammerdami]

@Swammerdami it appears your discussion might touch on the question about the (widely considered nonsensical) hypothetical set U in math, "the set that contains all sets", as this touches on the equivalence class issue, and the idea of a number of such "infinite complexity"

I think U is the "Grothendieck Universe" which is an "inaccessible" cardinal. Just as AC cannot be proven or refuted with the ZF axioms, so ZF+AC is agnostic on whether inaccessible cardinals even exist. There are also "Woodin cardinals" — are they even more inaccessible than the inaccessibles? I think Woodin won a prize for suggesting that AC follows from an assumption that inaccessible cardinals exist, as long as those inaccessibles are inaccessible enough! Anyway, I don't think our discussion relies on such big sets. Do we need anything beyond P(ℵ₀) ?

But all this is way WAY beyond my pay-grade. I have enough trouble just trying to tell the difference between ℵ₀ and P(ℵ₀).


By the way, Google will conjure up things like "Wiles's proof [of Fermat's Last Theorem] relies on Grothendieck's universes whose existence requires large cardinals, namely strongly inaccessible cardinals." I don't know if this claim has been submitted to PolitiFact, but I think they're just blowing smoke! Grothendieck, wanting maximum generality, assumed the existence of U in his theorems, so anyone relying on his theorems gets the assumption of inaccessible cardinals thrown in for free!

 

[Jarhyn]

@Swammerdami it appears your discussion might touch on the question about the (widely considered nonsensical) hypothetical set U in math, "the set that contains all sets", as this touches on the equivalence class issue, and the idea of a number of such "infinite complexity"

I think U is the "Grothendieck Universe" which is an "inaccessible" cardinal. Just as AC cannot be proven or refuted with the ZF axioms, so ZF+AC is agnostic on whether inaccessible cardinals even exist. There are also "Woodin cardinals" — are they even more inaccessible than the inaccessibles? I think Woodin won a prize for suggesting that AC follows from an assumption that inaccessible cardinals exist, as long as those inaccessibles are inaccessible enough!

But all this is way WAY beyond my pay-grade. I have enough trouble just trying to tell the difference between ℵ₀ and P(ℵ₀).


By the way, Google will conjure up things like "Wiles's proof [of Fermat's Last Theorem] relies on Grothendieck's universes whose existence requires large cardinals, namely strongly inaccessible cardinals." I don't know if this claim has been submitted to PolitiFact, but I think they're just blowing smoke! Grothendieck, wanting maximum generality, assumed the existence of U in his theorems, so anyone relying on his theorems gets the assumption of inaccessible cardinals thrown in for free!

Swammerdami, I don't think you should consider this above your pay grade?

This is exactly the same discussion of the same thing viewed through different lenses.

At any rate this was the subject of the video I watched on the sizes of infinite sets, and whether there were numbers larger than uncountably I finite sets and how this relates to AC.

I don't think the AC ought be allowed to interact with choices that cannot be completed. On the other hand if one rejects all choice on strongly inaccessible cardinals, the problem goes away: AC is only necessary in such spaces.

This problem also seems to have some interactions as regards the halting problem.

The problem itself though poses exposure to a strongly inaccessible cardinal, which kind of contradicts with the very idea of the thing. If it's strongly inaccessible you can't properly pose to have exposed one and used it in your thought experiment.

So if one accepts that one can't access such strongly inaccessible cardinals to make the problem exist, and that the prisoners don't have to worry about the halting problem, then none of them die.

To me the AC reeks strongly of metaphysics.

 

[Bomb#20]

I think U is the "Grothendieck Universe" which is an "inaccessible" cardinal. Just as AC cannot be proven or refuted with the ZF axioms, so ZF+AC is agnostic on whether inaccessible cardinals even exist. There are also "Woodin cardinals" — are they even more inaccessible than the inaccessibles? I think Woodin won a prize for suggesting that AC follows from an assumption that inaccessible cardinals exist, as long as those inaccessibles are inaccessible enough! Anyway, I don't think our discussion relies on such big sets. Do we need anything beyond P(ℵ₀) ?

"During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

That's the prisoners selecting one function from among P(P(ℵ₀)) possible options. I think.

But all this is way WAY beyond my pay-grade. I have enough trouble just trying to tell the difference between ℵ₀ and P(ℵ₀).

Likewise.

 

[Swammerdami]

Anyway, I don't think our discussion relies on such big sets. Do we need anything beyond P(ℵ₀) ?

"During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

That's the prisoners selecting one function from among P(P(ℵ₀)) possible options. I think.

You're right. I even knew that myself when I started the thread.
These big numbers make me dizzy!


Speaking of big numbers, am I the only one who thinks "Ho-hum" about numbers like P(P(ℵ₀)) or even P(P(P(P(ℵ₀)))), or even Grothendieck's U, but regards big finite numbers like Graham's number as mind-boggling and preposterous?

 

[Bomb#20]

Speaking of big numbers, am I the only one who thinks "Ho-hum" about numbers like P(P(ℵ₀)) or even P(P(P(P(ℵ₀)))), or even Grothendieck's U, but regards big finite numbers like Graham's number as mind-boggling and preposterous?

You aren't -- it's more about complexity than raw size. I recall a discussion board exchange I had with some guy who said some astronomical number was unimaginably large. I couldn't stop myself from correcting him -- his name was Ackermann.

 

[Jarhyn]

Anyway, I don't think our discussion relies on such big sets. Do we need anything beyond P(ℵ₀) ?

"During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence."

That's the prisoners selecting one function from among P(P(ℵ₀)) possible options. I think.

You're right. I even knew that myself when I started the thread.
These big numbers make me dizzy!


Speaking of big numbers, am I the only one who thinks "Ho-hum" about numbers like P(P(ℵ₀)) or even P(P(P(P(ℵ₀)))), or even Grothendieck's U, but regards big finite numbers like Graham's number as mind-boggling and preposterous?

Well big numbers like Graham's number are made to be arbitrarily mind bogglingly large and preposterous. It's more of a mathematical dick measuring than anything useful...

At least discussing things like U, we get closer to discussions of computability and accessibility that actually take us places, like discussions of the halting problem, the sizes of sets, and things like proofs of Fermats Last Theorem.

 

[Bomb#20]

Well big numbers like Graham's number are made to be arbitrarily mind bogglingly large and preposterous. It's more of a mathematical dick measuring than anything useful...

At least discussing things like U, we get closer to discussions of computability and accessibility that actually take us places, like discussions of the halting problem, the sizes of sets, and things like proofs of Fermats Last Theorem.

Graham's number itself wasn't made to be preposterous; it was made to show you couldn't have an arbitrarily large graph without it necessarily having a certain combinatorial property. This sort of thing is mathematicians' daily bread and butter; Graham's number was so big only because in this case it happened to be really hard to prove a smaller upper bound than that.

If you want to see actual mathematical dick measuring, check out this article by Douglas Hofstadter. It's the story of a reader contest he ran back when he was working for Scientific American. Hofstadter's point was to explore people's Prisoners' Dilemma psychology, but the magazine readers spoiled it and turned it into a dick measuring contest about who could specify the biggest integer.

Long story short, the top few entries used such abstruse but powerful mathematical concepts that Scientific American was unable to figure out who had won.