Reasons to disbelieve the Axiom of Choice

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

 

[steve_bank]

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.

You can manipulate infinite sets. I am not fluent in set notation.

a = {1.0 2.0} b = (3.0 4.0} and one might say c = a + b means c is twice the infinity of a or b. That does not mean the sets are countable.

Mathematics as well as science comes down to a physical test. To me math that cannot in some way be tested in physical relity is an abstraction.

A company I wored for in the 80s sent me to reliability engineering training. As I got into setting up quakity and reliabilty tests the VP, a farmer from Oregon, when I told him statistacs does not give me a priori knowledge. You can't apply probabilities without an enumeration.


Adding to my last post the definition of a probability distributions is that the area under the curve from minus to plus infinity must be 1. For a disc rte distribution this simply means the probabilities of all events must equal 1.

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

You might be able to set up the problem as a limit of a sequence as it goes to infinity. You can test for convergence.

Whenever I was puzzled by a prbem I set up a simulation.

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.

You might wish indeed to say the set of odds is "half as big" as the set of all natural numbers, but it is actually the same size, and this has been found to be true between the sizes of all infinite partitions of the natural numbers.

The way I saw it first presented is to think of a house with infinite rooms. Every room is filled with an "odd" number.

Wish to add the evens? Well, just ask the guy in the second room to move his neighbor over by one, and all the way counting down the line. There are infinite rooms, after all.

Now there's space to place 2 for to count it. But the thing is, 2 is already in a room that you counted when counting all the odds. So you haven't used ANY more rooms counting to 1,2,3 than counting 1,3,5.

It's the same size: countable infinity.

The lecture in which I first saw this treated was in fact a discussion on the axiom of choice!

My response in the past was show me an infinite set equated to a finite number if you can.

Put 6 colored balls in a box. The odds of picking 1 color is 1/6 and the toral probaility space is 6/6 = 1.

Put an infinite number of different colored balls in a box and the odds of picking one color are 1/inf which is undefined, inf is not a number.

6/6 is valid, inf/inf = 1 is meaningless.


Infinite sets being countable pr not is mathematical philosophy and metaphysics not tied to reality.

Arutnetic, claculus, geomery, trigonomtery can be tied to physical reality. What do infinite countable sets model?

 

[Jarhyn]

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.

You can manipulate infinite sets. I am not fluent in set notation.

a = {1.0 2.0} b = (3.0 4.0} and one might say c = a + b means c is twice the infinity of a or b. That does not mean the sets are countable.

Mathematics as well as science comes down to a physical test. To me math that cannot in some way be tested in physical relity is an abstraction.

A company I wored for in the 80s sent me to reliability engineering training. As I got into setting up quakity and reliabilty tests the VP, a farmer from Oregon, when I told him statistacs does not give me a priori knowledge. You can't apply probabilities without an enumeration.


Adding to my last post the definition of a probability distributions is that the area under the curve from minus to plus infinity must be 1. For a disc rte distribution this simply means the probabilities of all events must equal 1.

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

You might be able to set up the problem as a limit of a sequence as it goes to infinity. You can test for convergence.

Whenever I was puzzled by a prbem I set up a simulation.

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.

You might wish indeed to say the set of odds is "half as big" as the set of all natural numbers, but it is actually the same size, and this has been found to be true between the sizes of all infinite partitions of the natural numbers.

The way I saw it first presented is to think of a house with infinite rooms. Every room is filled with an "odd" number.

Wish to add the evens? Well, just ask the guy in the second room to move his neighbor over by one, and all the way counting down the line. There are infinite rooms, after all.

Now there's space to place 2 for to count it. But the thing is, 2 is already in a room that you counted when counting all the odds. So you haven't used ANY more rooms counting to 1,2,3 than counting 1,3,5.

It's the same size: countable infinity.

The lecture in which I first saw this treated was in fact a discussion on the axiom of choice!

My response in the past was show me an infinite set equated to a finite number if you can.

Put 6 colored balls in a box. The odds of picking 1 color is 1/6 and the toral probaility space is 6/6 = 1.

Put an infinite number of different colored balls in a box and the odds of picking one color are 1/inf which is undefined, inf is not a number.

6/6 is valid, inf/inf = 1 is meaningless.


Infinite sets being countable pr not is mathematical philosophy and metaphysics not tied to reality.

Arutnetic, claculus, geomery, trigonomtery can be tied to physical reality. What do infinite countable sets model?

Infinite countable sets are there to model systems of behavior, for the purpose of understanding systems which have some way they behave on a fundamental level.

As such, people use them extensively when discovering relationships in physics and in transforming the solutions to different problems across their axis of difference to solve intersections of the problem without needing to do direct experimentation to fill out lookup tables.

 

[steve_bank]

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.

You can manipulate infinite sets. I am not fluent in set notation.

a = {1.0 2.0} b = (3.0 4.0} and one might say c = a + b means c is twice the infinity of a or b. That does not mean the sets are countable.

Mathematics as well as science comes down to a physical test. To me math that cannot in some way be tested in physical relity is an abstraction.

A company I wored for in the 80s sent me to reliability engineering training. As I got into setting up quakity and reliabilty tests the VP, a farmer from Oregon, when I told him statistacs does not give me a priori knowledge. You can't apply probabilities without an enumeration.


Adding to my last post the definition of a probability distributions is that the area under the curve from minus to plus infinity must be 1. For a disc rte distribution this simply means the probabilities of all events must equal 1.

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

You might be able to set up the problem as a limit of a sequence as it goes to infinity. You can test for convergence.

Whenever I was puzzled by a prbem I set up a simulation.

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.

You might wish indeed to say the set of odds is "half as big" as the set of all natural numbers, but it is actually the same size, and this has been found to be true between the sizes of all infinite partitions of the natural numbers.

The way I saw it first presented is to think of a house with infinite rooms. Every room is filled with an "odd" number.

Wish to add the evens? Well, just ask the guy in the second room to move his neighbor over by one, and all the way counting down the line. There are infinite rooms, after all.

Now there's space to place 2 for to count it. But the thing is, 2 is already in a room that you counted when counting all the odds. So you haven't used ANY more rooms counting to 1,2,3 than counting 1,3,5.

It's the same size: countable infinity.

The lecture in which I first saw this treated was in fact a discussion on the axiom of choice!

My response in the past was show me an infinite set equated to a finite number if you can.

Put 6 colored balls in a box. The odds of picking 1 color is 1/6 and the toral probaility space is 6/6 = 1.

Put an infinite number of different colored balls in a box and the odds of picking one color are 1/inf which is undefined, inf is not a number.

6/6 is valid, inf/inf = 1 is meaningless.


Infinite sets being countable pr not is mathematical philosophy and metaphysics not tied to reality.

Arutnetic, claculus, geomery, trigonomtery can be tied to physical reality. What do infinite countable sets model?

Infinite countable sets are there to model systems of behavior, for the purpose of understanding systems which have some way they behave on a fundamental level.

As such, people use them extensively when discovering relationships in physics and in transforming the solutions to different problems across their axis of difference to solve intersections of the problem without needing to do direct experimentation to fill out lookup tables.

That is yi\our usual philosophical metaphysical double talk.

My guess is you are just quote mining.

To the posed OP problem, random sampling fom an infnite population is undefined, no probability can be assigned.

 

[lpetrich]

The axiom of choice is independent of the other axioms of set theory for infinite sets, and this is only one of the paradoxes of infinite sets.

For finite sets, one can prove this axiom from the rest of set theory: Axiom:Axiom of Choice for Finite Sets - ProofWiki - ProofWiki has lots of mathematical proofs

A simple way is to use ordering. Match every element of a set onto a positive integer, with no elements having the same one. Then for every subset, one can find the element mapped onto the smallest number.

This proof also works for countably-infinite sets, because countable subsets of the positive integers will always contain their minimum, from integers being discrete. But it does not work for the real ones, because one can find sequences of them that are bounded from below, but do not contain their lower bound. Like 1, 1/2, 1/4, 1/8, 1/16, 1/32, ... all its members are positive, meaning that its limit, 0, is not a member of it. In fact, every member has some member less than it.

 

[lpetrich]

There is an interesting curiosity about the axiom of choice. It related to the cardinalities of the integers (aleph-0) and of the real numbers (C). Georg Cantor, who developed the modern theory of infinite sets, tried to settle the question of whether there were any cardinalities in between. He conjectured that there aren't, that C = aleph-1 (the next one), but he was unable to prove that conjecture. Later mathematicians proved that it was independent of the Zermelo-Fraenkel formulation of set theory, and also that it was independent of the axiom of choice.

BTW, C is the cardinality of the power set of the positive integers, the set of all subsets of them. The power set of the real numbers has the cardinality of the set all functions from real numbers to real numbers.

• beth-0 -- N (positive integers)
• beth-1 -- PS(N) ~ R (real numbers)
• beth-2 -- PS(R) ~ all functions f(R) -> R

No identifications for higher beth numbers are known.

PS = Power Set
Continuum hypothesis: beth-1 = aleph-1

Generalized continuum hypothesis: no cardinality between |S| and |PS(S)| for all infinite sets S.

For finite sets, however, there is no intermediate cardinality only for sizes 0 and 1: 2⁰ = 1 and 2¹ = 2. This is from |PS(S)| = 2^|S|

 

[Jarhyn]

There is an interesting curiosity about the axiom of choice. It related to the cardinalities of the integers (aleph-0) and of the real numbers (C). Georg Cantor, who developed the modern theory of infinite sets, tried to settle the question of whether there were any cardinalities in between. He conjectured that there aren't, that C = aleph-1 (the next one), but he was unable to prove that conjecture. Later mathematicians proved that it was independent of the Zermelo-Fraenkel formulation of set theory, and also that it was independent of the axiom of choice.

BTW, C is the cardinality of the power set of the positive integers, the set of all subsets of them. The power set of the real numbers has the cardinality of the set all functions from real numbers to real numbers.

• beth-0 -- N (positive integers)
• beth-1 -- PS(N) ~ R (real numbers)
• beth-2 -- PS(R) ~ all functions f(R) -> R

No identifications for higher beth numbers are known.

PS = Power Set
Continuum hypothesis: beth-1 = aleph-1

Generalized continuum hypothesis: no cardinality between |S| and |PS(S)| for all infinite sets S.

For finite sets, however, there is no intermediate cardinality only for sizes 0 and 1: 2⁰ = 1 and 2¹ = 2. This is from |PS(S)| = 2^|S|

Holy shit. You've closed a few questions I'd been having on the cardinality of functions of real numbers.

What happens when these concepts intersect into the complex plane?

 

[Bomb#20]

What happens when these concepts intersect into the complex plane?

Real or complex makes no difference -- the set cardinalities are the same. You can make a 1-to-1 mapping between the reals and the complexes, like this:

Real: 0.12345678... <-> Complex: 0.1357... + i * 0.2468...

 

[Jarhyn]

What happens when these concepts intersect into the complex plane?

Real or complex makes no difference -- the set cardinalities are the same. You can make a 1-to-1 mapping between the reals and the complexes, like this:

Real: 0.12345678... <-> Complex: 0.1357... + i * 0.2468...

I see.

 

[lpetrich]

Beth-0 = aleph-0, the cardinality of the positive integers. Also of the nonnegative integers (every finite cardinality), the integers, the rational numbers, and the algebraic numbers.

Also for every finite p, the Cartesian product of p N's, the set of all p-vectors (arrays, tuples) of elements of N: N^p. (aleph-0)^p = (aleph-0). Vectors can be interpreted as functions, with the vector values as functions of the index values. So

|all f: f(A) = B| = |B|^|A|

for functions f over elements of set A giving elements of set B.

The power set of a set can be interpreted as a set of functions where each function corresponds to a subset by returning true or false depending on whether the set element is also a subset element. Thus,

|PS(A)| = 2^|A|
|PS(A)| > |A|

Real numbers R have the same cardinality, C = beth-1 = 2^aleph-0, as the real numbers over some interval: {a,+infty), (-infty,a}, {a,b} where { is either [ or (, and likewise for }. Their cardinality is the same as that of the power set of the positive integers. For base 2, if a digit is 1, then its location is a member of the corresponding subset, and if a digit is 0, then its location is not a member.

By interleaving the digits for R([0,1]), one can show that finite powers p of R, R^p, have the same cardinality. Thus, the full set of complex numbers has cardinality C, while the complex integers, complex rational numbers, and complex algebraic numbers have cardinality aleph-0.