http://blog.rongarret.info/2023/01/an-intutive-counterexample-to-axiom-of.html Rondam Ramblings Preaching the gospel of evidence, experiment and reason since 2003. Monday, January 23, 2023 An intutive counterexample to the axiom of choice Time for some hard-core geeking-out. This comment on HN by /u/jiggawatts struck me as a brilliant idea: it's an intuitive counter-example to the axiom of choice, which seem intuitively obvious, but leads to weird results like the Banach-Tarski paradox. For those of you who are not hard-core geeks, the axiom of choice says (more or less) that if you are given a collection of non-empty sets, you can choose a member from each of those sets. That seems eminently plausible. How could it possibly not be true? Here's how: consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. So not only are there numbers that cannot be described using a finite number of symbols, there are vastly more of these than numbers that can be so described. And yet... how would you describe such a number? By definition it is not possible! And so it is not at all clear (at least not to me) what it would even mean to "choose" a number from this set. This is, of course, not a proof that the axiom of choice is wrong. It's an axiom. It can't be wrong. But it is a good example for casting doubt in its intuitive plausibility, and that feels like progress to me. Posted by Ron at 1/23/2023 04:17:00 AM # # Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest 7 comments: [blo] Unknown said... I wonder if such a set really can exist. First, an element that cannot be described by using _any_ finite collection of symbols might not exist. The number of finite collections of symbols is not neccesarity countable (symbols themselves are not really countable: if a symbol is e.g. a trace of a pen on paper, it's a curve in 2D space). Second, if we can denote the set of these undescribable elements with a symbol, then we can probably agree on a notation for a specific element from this set (a_1), thus creating a paradox. But if thus the set itself can not be noted, then we probably cannot use a collection of non-empty sets including this set, because we'll not be able to write that one down, and thus we won't be able to use the axiom of choice :) 1/23/2023 5:03 AM [icon_delet] [bla] [duc] Kaa1el said... I assume by "description" it means the "definable set" (https:// en.wikipedia.org/wiki/Definable_set) or "definable number" (https://en.wikipedia.org/wiki/Definable_real_number) in model theory using some finitary language like FOL. So they have explicit definition in mathematics. It is a countable set by definition, however it is only "countable" under the context of ZFC, which means, by FOL or similar deduction system, there is no deduction of the form ZFC |- exists a 1-1 mapping from N to R- {definable numbers}. On the other hand, it is conservative to have a countable transitive model (ctm) of ZFC (M |= ZFC, and |M| <= |N|), such M |= not exists a 1-1 mapping from N to R- {definable numbers}, but you can construct a 1-1 mapping between N with the relativization of R-{definable numbers} in M (probably with the help of AC). Btw you can have uncountably infinite definable set of numbers using infinitary logic (https://en.wikipedia.org/wiki/ Infinitary_logic). 1/23/2023 5:28 AM [icon_delet] [blo] Simon said... Great start, but I think this misses the final step. There's no particular problem with claiming, in isolation, to have picked one element from some infinite collection of non-empty sets. The problem arises when you try to use that to construct an argument or proof. In each step where your argument depends on the existence of some set of unambiguous specific choices , then, if you are dealing with things like indescribable reals, there is no way, in principle, for the reasons you outline, to check or confirm that you are still talking about the same items. That is why we need the axiom of choice. 1/23/2023 5:37 AM [icon_delet] [blo] Ron said... @Unknown: > symbols themselves are not really countable Symbols have to be drawn from a finite set. That is part of the standard definition of a symbol. @ Kaa1el: > I assume by "description" it means the "definable set" (https:/ /en.wikipedia.org/wiki/Definable_set) or "definable number" (https://en.wikipedia.org/wiki/Definable_real_number) in model theory using some finitary language like FOL. I haven't thought this all the way through, but the reason I went with "definable" rather than "computable" was to eliminate uncomputable but definable numbers like Chaitin's constant from the set. I'll have to think more deeply about the rest of your comment. @Simon: > There's no particular problem with claiming, in isolation, to have picked one element from some infinite collection of non-empty sets. Sure, just as there is no problem in postulating an oracle for the halting problem. You can assume anything in math. Like I said, the intent here was not to *disprove* the AoC, just to offer an intuition as to how a reasonable person might choose to reject it. 1/23/2023 7:18 AM [icon_delet] [blo] Guy said... I don't think your example has anything to do with the axiom of choice, which informally states that "given any collection of sets, you can pick an element from each of them". Set theory has no problem picking elements from a _single_ set, even without choice, provided you can prove that it is non-empty! And indeed, ordinary set theory (even without choice) proves that the reals are not countable. You can "construct" a non-describable real as follows using a diagonalization argument: let xi be the real number given by the i'th description in whatever system you like. Then define a real number y by choosing it's i'th digit so that it is different from the i'th digit of xi. Clearly y is different from any of your describable reals! But I've just described it, so what gives? The trick is that, once you unroll my previous paragraph, y has an infinite description. Nevertheless I can reason about this real number y just fine, so personally I'm okay with this state of affairs. Maybe your example just highlights the strangeness of allowing infinities into mathematics? It's not to everyone's taste! 1/23/2023 7:43 AM [icon_delet] [blo] CCubed said... Special irrationals like pi and e are described by their specialness. Doesn't the diagonal argument for irrationals being a higher order of infinity depend on the Axiom of Choice? Maybe the problem is not with Choice but continuity. 1/23/2023 7:55 AM [icon_delet] [blo] Ron said... [Corrected version] @Guy: > Clearly y is different from any of your describable reals! But I've just described it, so what gives? What gives is that your original description system "whatever system you like" was incomplete, as all such description systems necessarily are. But that doesn't matter to my argument, which includes *all possible* description systems, including diagonalization. No matter how many times you diagonalize and meta-diagonalize you will still be left with uncountably infinite undescribable reals. Note that I don't have to actually *construct* this set (that is not possible). All I have to do is prove that it exists and it's not empty. Existence is easy: it's just the complement of the (countable) set of describable reals. And since it's uncountable, it's obviously not empty, QED. 1/23/2023 10:36 AM [icon_delet] Post a Comment Older Post Home Subscribe to: Post Comments (Atom) Subscribe to [arrow_drop] [icon_feed1] Posts [subscribe-] [subscribe-] [icon_feed1] Atom [arrow_drop] [icon_feed1] Posts [arrow_drop] [icon_feed1] Comments [subscribe-] [subscribe-] [icon_feed1] Atom [arrow_drop] [icon_feed1] Comments Followers Blog Archive * V 2023 (2) + V January (2) o An intutive counterexample to the axiom of choice o I am offended by Muslims being offended * > 2022 (4) + > November (3) + > April (1) * > 2021 (13) + > September (1) + > June (1) + > May (1) + > March (1) + > February (1) + > January (8) * > 2020 (33) + > November (1) + > September (3) + > August (4) + > July (4) + > June (1) + > May (3) + > April (8) + > March (8) + > February (1) * > 2019 (25) + > October (5) + > August (1) + > July (2) + > June (3) + > May (3) + > April (5) + > March (4) + > January (2) * > 2018 (66) + > December (2) + > November (5) + > October (5) + > September (7) + > August (8) + > July (13) + > June (7) + > May (7) + > April (5) + > March (4) + > February (2) + > January (1) * > 2017 (77) + > December (4) + > November (8) + > October (3) + > September (2) + > August (4) + > July (5) + > June (4) + > May (3) + > April (4) + > March (5) + > February (6) + > January (29) * > 2016 (61) + > December (1) + > November (6) + > October (2) + > September (1) + > August (7) + > July (4) + > June (7) + > May (3) + > April (4) + > March (3) + > February (6) + > January (17) * > 2015 (63) + > December (14) + > November (1) + > October (3) + > September (1) + > August (4) + > July (4) + > June (2) + > May (2) + > April (5) + > March (4) + > February (15) + > January (8) * > 2014 (38) + > December (6) + > November (2) + > October (3) + > September (4) + > August (8) + > July (3) + > May (3) + > April (5) + > February (2) + > January (2) * > 2013 (101) + > October (2) + > September (4) + > August (13) + > July (10) + > June (24) + > May (5) + > April (10) + > March (7) + > February (18) + > January (8) * > 2012 (28) + > December (6) + > November (1) + > February (2) + > January (19) * > 2011 (154) + > December (5) + > November (9) + > October (13) + > September (11) + > August (14) + > July (22) + > June (15) + > May (11) + > April (17) + > March (15) + > February (13) + > January (9) * > 2010 (135) + > December (20) + > November (18) + > October (24) + > September (5) + > August (4) + > July (7) + > June (3) + > May (9) + > April (9) + > March (11) + > February (16) + > January (9) * > 2009 (140) + > December (7) + > November (9) + > October (26) + > September (22) + > August (18) + > July (11) + > June (16) + > May (1) + > April (12) + > March (10) + > February (7) + > January (1) * > 2008 (100) + > December (6) + > November (15) + > October (13) + > September (8) + > August (2) + > July (14) + > June (8) + > May (9) + > April (4) + > March (1) + > February (12) + > January (8) * > 2007 (88) + > December (7) + > November (23) + > October (11) + > September (10) + > August (7) + > July (11) + > June (4) + > April (4) + > March (3) + > February (2) + > January (6) * > 2006 (162) + > December (9) + > November (19) + > October (28) + > September (12) + > August (21) + > July (15) + > June (10) + > May (18) + > April (12) + > March (10) + > January (8) * > 2005 (30) + > December (9) + > November (6) + > October (3) + > September (4) + > August (6) + > April (1) + > March (1) * > 2004 (68) + > November (1) + > October (4) + > September (2) + > August (3) + > July (4) + > June (11) + > May (5) + > April (9) + > March (6) + > February (9) + > January (14) * > 2003 (86) + > November (18) + > October (7) + > September (17) + > August (39) + > July (5) About Me Ron View my complete profile Simple theme. Powered by Blogger.