[HN Gopher] An intutive counterexample to the axiom of choice
___________________________________________________________________
An intutive counterexample to the axiom of choice
Author : lisper
Score : 96 points
Date : 2023-01-23 12:17 UTC (10 hours ago)
(HTM) web link (blog.rongarret.info)
(TXT) w3m dump (blog.rongarret.info)
| [deleted]
| mannykannot wrote:
| I suspect this posting might have been prompted by the recent one
| of Colin Wright's "The Point of the Banach-Tarski Theorem."[1]
| Regardless, Colin has also written about the axiom of choice, in
| "In Defense Of The Axiom Of Choice"[2] and "A Point Against The
| Axiom Of Choice."[3]
|
| [1]
| https://www.solipsys.co.uk/new/ThePointOfTheBanachTarskiTheo...
| https://news.ycombinator.com/item?id=34482226
|
| [2]
| https://www.solipsys.co.uk/new/InDefenseOfTheAxiomOfChoice.h...
|
| [3]
| https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...
| [deleted]
| [deleted]
| rtpg wrote:
| since everyone here is bike shedding about the axiom of choice...
| I have this axiom of choice book (by Thomas Jech). It includes
| the following:
|
| > if F is a finite family of nonempty sets, then there is a
| choice function (to show this one uses induction on the size of
| F; naturally a choice function exists for a family which consists
| of a single nonempty set).
|
| could someone lay out how one would "correctly" describe a choice
| function for a family with a single nonempty set? I feel like I
| understand theoretically this idea that choosing isn't about
| providing the value, but some... logical instantiation? What is
| the piece of the puzzle I'm missing here to understand why the
| choice function exists "naturally"?
| hgsgm wrote:
| Sets are defined by their members. If you have a nonempty set,
| you must have defined a member when you proved it was nonempty.
| Take any convenient one.
|
| This works for any finite or countable family, because you can
| repeat the process for each set, any set you can think of will
| be processed eventually.
|
| But for an uncountable set, _almost every_ set will _never_ be
| processed, and _almost every_ set is impossible to describe in
| finite time (per set!), unless you just assume that you can do
| it on one magical oracle bulk selection.
| rtpg wrote:
| Is the correct way to see this is that logic has to be
| specified in a finite number of terms? For countable families
| there's some sort of meta logic like "for the Nth element I
| induct to that"?
|
| I believe to understand that idea (since it comes up in real
| analysis to some extent, basically acknowledging there isn't
| really infinite sums except as limits of finite sums), but is
| there a specific sort of text that lays out this idea
| specifically?
| quchen wrote:
| Good question, I'm confused about this as well! Take for
| example the single-element set containing the set of R-R
| functions, so { {f | f: R-R} }. The author seems to suggest
| there's a natural choice for those functions. To me this sounds
| as hard as choosing from a larger set-of-sets.
| housecarpenter wrote:
| I don't think Jech is using "naturally" as in "natural
| choice"; he's just using it as a synonym for "obviously". If
| X is non-empty set then there exists an x in X, because
| that's what it means for X to be non-empty. The choice is
| arbitrary: if X is the set of all functions from R to R then
| you could take the exponential function, the x^2 function,
| etc., whatever you like; the point is that it is certainly
| possible to make _some_ choice.
|
| Doubting the axiom of choice means thinking that when you
| have infinitely many sets to choose from, it is possible that
| not only is there is no _natural_ choice function, but there
| is _no choice function at all_.
| rtpg wrote:
| But why do we need the axiom of choice at all? By this
| logic I have any family of non-empty sets then I'm good?
| But surely there's a distinction here
| Aardwolf wrote:
| But even if you have the set of all reals not describable with a
| finite amount of symbols, I can still imagine what happens e.g.
| if you multiply all its values by 2, or what the cartesian
| product of this set with another is like. At least, I can reason
| sbout that result in a way that's not worse than reasoning about
| the set itself. Using axiom of choice on it does not make things
| harder than the set itself already is
| hgsgm wrote:
| AoC lets you ignore how bad the set it.
|
| Banach-Tarski says: Take a measurable set. Split it up into 2
| unmeasurable sets. Recombine them into a set with twice the
| measure of the original.
|
| OK, you can do that, but you've lost the ability to make any
| reasonable theorems about measure of measurable sets, unless
| you add qualifications of the form "this theorem does not apply
| if you introduce a set of uncountable sets" which. What's the
| benefit? To get a bunch of "proofs" for things that are only
| true because of the axiom, and don't model anything else we
| care about?
| voldacar wrote:
| The axiom of choice is not really about assigning names to
| objects using finite strings of symbols. In this example, you
| take R, remove countably infinitely many elements, and end up
| with a set with uncountably many elements. From a set theoretic
| perspective, it is not any more difficult or unintuitive to
| select an element from this set using AoC than it would be for R.
| When we use AoC, we are not really assigning a name to anything
| or doing any computation. We merely claim that a function exists
| which returns some element from the set. AoC doesn't compute or
| describe this function.
| horsawlarway wrote:
| > We merely claim that a function exists which returns some
| element from the set.
|
| Isn't this where the challenge lies, though?
|
| What if you have a set for which there is no function which
| returns some element from the set, but the set is non-empty?
| hgsgm wrote:
| It's only a challenge if you want to actually do it.
| Mathematicians figured out that it's impossible to actually
| do, so they decided to pretend it's possible, because nothing
| else breaks if they just pretend it's possible.
| Mathematicians like pretending.
| drdeca wrote:
| For any set S which is non-empty, there is an element x of
| that set. For any set S and any x, the set S * {x} is a
| function which sends every element of S to x.
|
| Therefore, for every non-empty set S, there is a function
| with domain S, and range a single element of S.
|
| Did you mean a set S of sets such that there is no f : (A in
| S) -> A ?
| raldi wrote:
| Even more intuitive: What's the first positive real number?
|
| If you can't tell me that, or even be sure that it even exists,
| how can you be sure you can identify the first item in any set?
| Chinjut wrote:
| As others have noted, this has little to do with the Axiom of
| Choice per se. The Axiom of Choice is not needed to prove that
| one can make a choice from a single inhabited set, where this
| boils down to the tautology "If a set has at least one element,
| then it has at least one element". The Axiom of Choice is only
| needed for making infinitely many choices at once.
|
| (There IS a sense in which what is going on here is the
| distinction between what category theorists call "internal" and
| "external" Choice, but I'll not get into that for now since I
| think the following is more important to point out first.)
|
| The result/paradox here has more to do with Tarski's
| indefinability theorem, under which no suitable formal language
| is able to define the concept of definability in that same
| language.
|
| See also https://mathoverflow.net/a/44129/3902 for more
| discussion on what goes wrong in attempting to formally prove
| that "undefinable" numbers exist by this common but naive
| argument from uncountability.
|
| The gist of the above MathOverflow link and of Tarski's
| indefinability theorem is that we must keep in mind that Cantor's
| famed diagonal argument for uncountability is a constructive
| argument. Given any function from N to 2^N, it defines an
| explicit element of 2^N not in the range of that function. So
| there would be something paradoxical in concluding that this
| explicitly defined value is not definable.
| malaya_zemlya wrote:
| A slightly more elaborate setup which showcases the weirdness of
| the Axiom of Choice.
|
| Consider a group of countably infinite wizards w_1, w_2,... A
| king has put a number 0 or 1 on their backs and ordered the
| wizards to stand in a single file, such that wizard w_n can only
| see the numbers on the backs of all wizards with higher numbers
| (w_n+1, w_n+2...). As is the tradition, the king gave them a
| challenge: if you can guess the number on your back, your life is
| spared, otherwise off with your head. The wizards can discuss
| their actions beforehand, but no communications is allowed after
| the numbers have been assigned.
|
| The wizards cannot see their own numbers, they cannot exchange
| information, yet, if we assume the Axiom of Choice, they still
| can work out a strategy, such that all but a finite number of
| wizards survive.
|
| The trick is to break the space of all 0-1 sequences into
| equivalence classes, whre X is equivalent to Y if they disagree
| only in finite number places. (in other words, they fully agree
| starting from some index k). That's an equivalence relation, as
| you can easily verify.
|
| Then the wizards use the Axiom of Choice to remember one
| representative sequence from each class (there are infinitely
| many such sequences, but our wizards are infinitely wise). During
| the test, each wizard would look at what numbers they see in
| front of them, pick the representative sequence that is
| equivalent to what they are seeing, and guess the number that
| corresponds to their place in the sequence.
|
| All wizards will agree on what representative sequence will need
| to be picked (because the king's sequence belongs to a single
| equivalence class), and that sequence will agree with the king's
| sequence everywhere except for a finite number of places. Boom!
| voldacar wrote:
| >Then the wizards use the Axiom of Choice to remember one
| representative sequence from each class
|
| I don't think AoC is enough here becuase the wizards need to
| evaluate the choice function to get the representative from
| each equivalence class. AoC merely states that there is some
| function that maps each equivalence class to some element
| within that equivalence class. It doesn't tell you how to
| actually evaluate it, which is what the wizards need to do.
| CaptainNegative wrote:
| What's the role of restricting the number domain to binary
| here? Can't they each have a real-valued number on their back
| (or worse, something from a larger set) with the same argument
| still going through?
| IngoBlechschmid wrote:
| Indeed, it works as long as the class of labels forms a set
| instead of a proper class.
| hackandthink wrote:
| I would pick Chaitin's constant.
|
| It is not only transcendantal like Pi, it is even uncomputable,
| so it would be part of his counterexample set.
|
| (Pi is computable, so you can describe it with an algorithm
| (finite number of characters))
| moron4hire wrote:
| But can't Chaitin's constant be described using a finite set of
| symbols, those symbols being in the set [achinost'] (at least,
| in English)?
| hackandthink wrote:
| OK, original poster doesn't speak about computable numbers:
| "consider the set of numbers that cannot be described using
| any finite collection of symbols"
|
| But I have a hard time accepting numbers, which can only be
| described in natural language.
| tromp wrote:
| Sure; a simple definition is at https://tromp.github.io/cl/Bi
| nary_lambda_calculus.html#Halti...
| _hark wrote:
| These kinds of non-constructive results are almost always present
| when you invoke choice (when it's actually relevant), and this is
| a well-known example of the non-intuitiveness of choice. If you
| don't like this, you're probably a constructivist and may also
| disagree with the law of the excluded middle. A classic
| quote/joke on the topic:
|
| "The Axiom of Choice is obviously true, the well-ordering
| principle obviously false, and who can tell about Zorn's lemma?"
| NotYourLawyer wrote:
| > the set of numbers that cannot be described using any finite
| collection of symbols
|
| Not clear that this is a well-defined set.
| hgsgm wrote:
| It's probably not well-defined.
|
| https://en.m.wikipedia.org/wiki/Richard's_paradox
| [deleted]
| sylware wrote:
| If I recall properly, at the time I was "building maths from the
| ground up (aka axioms)", I was very uncomfortable with THE
| axioms: this mixing between discret/finite concepts/objects and
| infinite concepts/objects was too easy for my taste.
| phkahler wrote:
| I've always called BS on the math community for this. Let's talk
| about real numbers between. 0 and 1 (because we can map all of
| them to this range anyway). I can (count) enumerate all of them.
| Simply flip the digits over the decimal point, so 0.14159 become
| integer 95141. Done. Now you ask where pi sits? It's infinitely
| far down the list of integers. It's position is as precise as
| your definition.
|
| We can extend this to (I forget the terminology) enumerate the
| numbers that can be named, by converting the names to integers.
| Now pi has several location in this mapping, as do a lot of real
| numbers.
|
| Infinite sets are interesting, but I've never been convinced that
| there are more reals than integers. It seems plausible but I
| don't think pi not mapping to a _specific_ integer in the above
| scheme invalidates the mapping.
| 101008 wrote:
| If you sort this set after you apply your transformation,
| what's the number that comes right after pi?
| dsr_ wrote:
| You can begin looking for it knowing just two facts: the last
| digit of pi, and the magnitude of that digit.
|
| Easy!
|
| [sarcasm]
| phkahler wrote:
| This is all related to the ability to name a specific
| number. If there are reals that can't be named in a finite
| number of symbols, why can't there be integers like that as
| well?
| davrosthedalek wrote:
| Because a property of the numbers we call integers is
| that we can name them. You can certainly rename some of
| the numbers which are indescribable and call that set
| your integers, but these are different integers than what
| everyone else talks about.
| chriswarbo wrote:
| > Simply flip the digits over the decimal point, so 0.14159
| become integer 95141
|
| This sounds similar to an interesting (and often counter-
| intuitive) way of writing down numbers called 'p-adic numbers'
| (although that terminology usually requires 'p' to be prime; in
| your case you'd want the '10-adic' numbers, since you're using
| base-10)
|
| See e.g. https://en.wikipedia.org/wiki/P-adic_number (here's a
| video specifically about 10-adic numbers
| https://www.youtube.com/watch?v=XXRwlo_MHnI )
| alecbz wrote:
| Don't want to pile on too much, but my attempt at an
| explanation:
|
| > Simply flip the digits over the decimal point, so 0.14159
| become integer 95141
|
| They key here is that both 0.14159 and 95141 contain a _finite_
| number of symbols/digits. There are infinitely many numbers
| like this, but each of those numbers are themselves finite.
|
| The decimal expansion of pi, OTOH, is _itself_ infinite. The
| decimal expansion of any irrational number is infinite. There
| are infinitely many of these things, each of which are
| themselves infinite.
|
| This is the key thing that causes uncountability. Each of the
| numbers has infinitely many "parameters" that can be tweaked.
| If you try to produce an infinite (countable) list that
| contains all of these infinite numbers, I can always tweak a
| different parameter for each number in your list and be
| guaranteed to have produced a number that your list missed.
| iroddis wrote:
| "Flip around the decimal"... you haven't accounted for
| irrational numbers. The reals are not countably infinite.
|
| Even if they were, pi is not between zero and one, so would not
| appear in your list.
|
| The rest of your argument is difficult to parse. If you're
| interested in this kind of stuff though, I'd really recommend
| picking some good books on set theory and maybe number theory.
| Set theory in particular will cover a lot of what you're
| talking about.
| [deleted]
| SantalBlush wrote:
| You can't flip irrationals over the decimal the way you
| described, because their decimals have infinitely many non-
| repeating values. You would end up with an infinite sequence of
| numbers, not a real number.
| phkahler wrote:
| You mean there aren't infinity large integers? Hmm, that
| seems weird.
| xvkektjdicou wrote:
| All integers are by definition finite. Positive integers
| are defined by S(S(S(...S(0)...))) a finite number of
| times, where S is the successor function. (And negatives in
| the obvious way.)
| SamBam wrote:
| Your method is not a 1:1 mapping of reals to integers, because
| you can't even define the position of a single irrational
| number with your method. You don't know the final digit, so you
| don't know the leading digit in your system. You have
| absolutely no idea the ordering of literally any pair of
| irrational numbers in your system.
|
| > It's position is as precise as your definition.
|
| This wand-waving is actually transforming irrational numbers
| into rational numbers, and so means you are not actually
| working with irrational numbers. You can't just say "this works
| with all irrational numbers, like Pi, so long as we call Pi
| '3.14'."
|
| Pi is _not_ 3.14, so any mapping system that depends on you
| cutting off your precision at some finite number of digits is
| worthless.
| phkahler wrote:
| >> Your method is not a 1:1 mapping of reals to integers,
| because you can't even define the position of a single
| irrational number with your method. You don't know the final
| digit, so you don't know the leading digit in your system.
| You have absolutely no idea the ordering of even a single
| irrational number in your system.
|
| That is my point exactly. Why do we accept that there are
| real numbers that cannot be defined by a finite string of
| symbols, but there are no integers of that nature.
|
| Getting back to the axiom of choice thing. How do you pick a
| specific item from one of those ill-defined sets that include
| numbers that don't have finite descriptions? How do you
| choose something you can't name? It's absurdity all the way
| down. ;-)
| WastingMyTime89 wrote:
| > Why do we accept that there are real numbers that cannot
| be defined by a finite string of symbols
|
| We don't accept it. It's easy to prove that it's the case.
|
| I think you are unfamiliar with how R is defined. The
| traditional definition of R is a completion of Q with
| respect to the metric |x-y| (getting all Cauchy sequences
| to converge). That's larger than infinite sequence of
| decimals.
| SamBam wrote:
| That did not seem in any way to be your point. You said
|
| > I've never been convinced that there are more reals than
| integers
|
| I'm explaining that your method of mapping reals to
| integers is flawed, and so does not prove that reals and
| integers have the same cardinality.
| jacobmartin wrote:
| Where is 1/3? Is it before or after (pi - 3)?
| phkahler wrote:
| We need to switch to the scheme that converts
| name/description to an integer for that. If you mean the
| repeating decimal, I don't know if it's before or after pi
| because I can't identify (name) their locations.
|
| It's the same argument. If I can accept that there are more
| reals than reals with finite descriptions, why can't there be
| integers without finite descriptions/positions?
| jacobmartin wrote:
| > If I can accept that there are more reals than reals with
| finite descriptions, why can't there be integers without
| finite descriptions/positions?
|
| Because the integers are _defined_ as the finite successors
| to the number 0 and their additive opposites. See, for
| instance, the construction section of:
| https://en.m.wikipedia.org/wiki/Integer
|
| You can start talking about numbers that can't be
| constructed in this way, but then you've ceased to be
| talking about the integers.
| phkahler wrote:
| Is the size of the set of integers an integer?
| jacobmartin wrote:
| No, usually the cardinalities of infinite sets are
| represented by things called aleph numbers:
| https://en.m.wikipedia.org/wiki/Aleph_number.
|
| But it isn't, in any case, an integer.
| kjaa wrote:
| I believe you are confusing rational for real numbers. Rational
| numbers really do map to the integers, but I believe I can
| "break" any purported isomorphism from reals to ints, by taking
| two adjacent ints and asking what number the midpoint between
| the corresponding reals map to.
| phkahler wrote:
| Please be specific. I never said the mapping has nice
| properties regarding the ordering.
|
| BTW I know rational numbers map to integers, and hence any
| length tuple can be mapped to integers by pairwise combining
| them in similar ways. But if any length tuple of integers can
| map to a single integer, why can't an infinitely long set of
| integers map to an integer? Like the string of digits in an
| irrational number represented as a decimal?
| Warwolt wrote:
| The problem with mapping the reals to the integers is that
| a list of real numbers is infinite in "two directions".
| Each real can be potentially described with an infinite
| number of digits, and you can have an infinite list of real
| numbers (i.e. infinite sequences of digits). This is, I
| believe, the basis for Cantor's diagonal argument, which is
| a quite beautiful proof of there being more reals than
| integers.
|
| https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
| boole1854 wrote:
| > Let's talk about real numbers between. 0 and 1 (because we
| can map all of them to this range anyway). I can (count)
| enumerate all of them. Simply flip the digits over the decimal
| point, so 0.14159 become integer 95141.
|
| Every integer has a finite number of numerals. Proof: by
| definition, each natural number is either 0 or a successor to
| 0. 0 is finite. And if _n_ is a finite length, then _n + 1_ is
| a finite length. So by mathematical induction, all natural
| numbers have finite length. A similar argument covers the
| negative numbers, so all integers have finite lengths.
|
| Since the decimal expansion of certain rational numbers are
| infinite (e.g., 1/3 = 0.333...), the strategy of mapping each
| number between 0 to 1 to an integer by flipping digits over the
| decimal point does not work for all rationals, let alone all
| reals.
| jinpa_zangpo wrote:
| I believe the definition of this set is contradictory. The set is
| defined as all numbers that cannot be described with a finite
| number of symbols. But that set must have a member whose value is
| closest to zero. So you can describe at least one member of this
| supposedly indescribable set.
| less_less wrote:
| It would at least require some careful setup to be coherent.
| Like you won't be able to define "the least positive integer
| that can't be uniquely described in fewer than fifteen words".
| Basically your language won't be consistent if it allows you to
| talk about things that can / can't be uniquely described in the
| language itself.
|
| My disagreement about this post is: I don't see what it has to
| do with the axiom of choice. The only "choice" used here is
| that this nonempty set of non-describable numbers (if indeed we
| can define it at all) contains at least one element. That's a
| tautology and doesn't require choice.
|
| Also, the author may be interested in Skolem's paradox: in
| particular, if the theory of the real numbers is consistent,
| then there must be a construction with only countably many
| reals, and so if I understand correctly, they would all be
| describable.
| johnnny wrote:
| > But that set must have a member whose value is closest to
| zero
|
| This is not true for real numbers with the usual "less-than"
| relation. In fact, considering real numbers, no open subset of
| R admits a lower member.
|
| According to Zorn's lemma, there exist some order relation
| where your assertion is true, but I seem to remember from my
| math course a few (!) years ago that Zorn's lemma is equivalent
| to the axiom of choice.
| ablob wrote:
| This doesn't work for rational numbers either. Take any
| rational a/b, then 0 < a/(2b) < a/b is both closer to zero,
| and it is also a rational number.
| WastingMyTime89 wrote:
| According to the well-ordering theorem which is equivalent to
| the axiom of choice (and Zorn's lemma), you can well-order
| any set. That's usually when people start doubting the axiom
| of choice because, well, that's quite unintuitive. There is a
| joke about it which has already been posted here.
| BeetleB wrote:
| You can well order any set, but you need to have the
| "right" ordering to do so. As your parent is pointing out,
| the usual ordering on the reals is _not_ a well ordering,
| and one cannot achieve a well ordering of the reals using
| that ordering.
| Slow_Dog wrote:
| "the member whose value is closest to zero" is described by
| those 14 symbols within the speech marks. As you say, the
| definition is contradictory.
| tsimionescu wrote:
| Except no such member need exist. For example, there is no
| number that corresponds to the description "the smallest
| positive real number greater than 0".
|
| Edit: note that even "the smallest positive _rational_ number
| greater than 0 " doesn't exist, even though the rationals are
| merely countably infinite.
| tuatoru wrote:
| This (no smallest positive element of Q) is sensible. But
| how can you have a procedure that requires making an
| infinite number of choices?[1] It's not an algorithm; they
| have to terminate.
|
| 1. Wikipedia explanation of the axiom of choice.
| tsimionescu wrote:
| I was only pointing out the problem with your argument
| not arguing that the AoC is necessary or intuitive.
|
| Also, algorithms that don't terminate are still
| algorithms - especially if they keep emitting pieces of a
| solution, instead of producing the whole solution at the
| end.
|
| For example, here is an algorithm for printing all of the
| natural numbers: i <- 0 while true:
| print(i) i <- successor(i)
|
| Finally, computability is not typically considered
| necessary for a mathematical construct to exist or be
| useful. Just like geometry sometimes studies shapes that
| can't be constructed in the physical world, other kinds
| of mathematics sometimes studies concepts that can't be
| computed (at least not given known models of
| computation).
| scythe wrote:
| The definition of this set _is_ contradictory, but not for the
| reason you 've suggested. Rather, it is impossible to construct
| the set of numbers which _can_ be defined by a finite string of
| symbols, due to Richard 's paradox:
|
| http://en.wikipedia.org/wiki/Richard's_paradox
|
| Hence, it is also impossible to construct the complement of
| this set. In fact, Richard's "diagonal argument" chooses
| precisely the sort of number we ought not to be able to choose,
| according to the blog post (but again, this just shows the set
| is not well-defined).
| hummusandsushi wrote:
| I believe you are mistaken. This set of numbers is just the set
| of reals minus the countable infinity of finitely representable
| numbers. This set should still be densely ordered and so for
| any member that could be chosen from this set, there is an
| infinite number of elements closer to zero.
| randallsquared wrote:
| > _But that set must have a member whose value is closest to
| zero._
|
| Must it? Is there a real number closest to zero?
| xen0 wrote:
| _> But that set must have a member whose value is closest to
| zero._
|
| Must it?
|
| "Let x be the smallest element of the half-open interval (0,
| 1]" isn't really something that you can say *.
|
| * Assuming the standard ordering of reals; sure you can say
| it's defined for some well-order, but then you require the
| Axiom of Choice anyway.
| xen0 wrote:
| The OP's argument seems to be just that you cannot always
| construct a choice function.
|
| But the entire point of the axiom of choice is to say "that's
| fine; you're still allowed to use 'unconstructed' choice
| functions in your proofs".
|
| Would the OP reject the statement "let x be an element of the set
| of numbers that cannot be defined with finitely many symbols";
| such a statement does not depend on the AoC, but I think the OP
| complains about making even a single choice.
| lisper wrote:
| > The OP's argument seems to be just that you cannot always
| construct a choice function.
|
| No, the argument is that _if you cannot describe the choice_
| then you have a problem. My argument does not assume anything
| about the choice function, it 's merely an informal observation
| about its output.
| xen0 wrote:
| So the statement "let x be an element of y" is already
| problematic?
|
| If so, your problem is not with the axiom of choice.
|
| Edit: "Not being able to describe the choice a choice
| function makes" and "not being able to construct it" are
| really the same thing.
| rini17 wrote:
| How is that different from claiming, say, there's an integer
| betwen three and four, oh we can't construct it but that's not
| a problem, gonna use it in the proofs anyway?
| xigoi wrote:
| An axiom has to be consistent with other axioms (that is,
| adding it doesn't introduce a contradiction).
| xen0 wrote:
| That would let me derive your mother's phone number.
| https://xkcd.com/704/
|
| It's different because there's nothing that says such a
| choice function _cannot_ exist (short of an axiom that says
| explicitly so).
| jbnicolai wrote:
| That's essentially what axioms are. Wether it's reasonable or
| not depends on your intuition of both axiom & implications.
|
| This is where the axiom of choice is interesting; many people
| feel that it seems intuitively reasonable, but the
| implications are counterintuitive (e.g. banach-tarski)
| contravariant wrote:
| Well an integer between three and four is going to cause some
| contradictions, depending on your definition of 'integer'.
|
| You _can_ assume there exists a number between 3 and 4
| though, no problems there.
| jacobmartin wrote:
| This is an interesting question that gets to the heart of the
| constructivism debate, which I won't touch on here.
|
| As for the integer example, the integers are all easily
| (finitely) constructed (successors to 0 and their additive
| opposites), so it isn't a consistent concept to say "This is
| an unconstructable integer." Sets, on the other hand, are not
| necessarily always constructable, unless you only take the
| constructivist axioms.
| wizeman wrote:
| Perhaps we should start admitting to ourselves that infinity is
| not really something that actually exists but instead it's just
| an imaginary concept that we created but that has no
| correspondence to anything that makes sense in our universe?
|
| Or at least, some versions of infinity (I will leave which ones,
| exactly, to the experts).
|
| Hence all the paradoxes that derive from it.
|
| I mean, perhaps we can work with _some_ version(s) of infinity,
| without creating a plethora of paradoxes.
|
| The natural numbers, for example, might be something that is
| infinite and makes sense. However, perhaps talking about a
| _single set_ that contains an infinite amount of natural numbers
| might not make sense (or perhaps it still might?). Or perhaps we
| just need a new language for talking about infinite things
| without re-using the language we use for describing (finite)
| sets, so that we don 't try to reuse concepts from finite objects
| with infinite objects.
|
| Or perhaps the only objects that exist (and can be meaningfully
| talked about) are the computable ones. And/or perhaps "computable
| function" is one that can use infinite amounts of time but only
| finite amounts of storage (rather than infinite amounts of
| storage).
|
| Would it make sense to go back to classical finitism and re-
| evaluate some of the choices that were made along the way to
| where we are now?
|
| I can't help but think about the many paradoxes that arise from
| the very (supposed) existence of infinity.
|
| For example, everybody thinks the halting problem is undecidable.
| The halting problem is clearly not undecidable on finite-state
| machines (i.e. real computers), it's only undecidable if you use
| imaginary Turing machines (which supposedly can have literally
| infinite state) as a model. But of course, Turing machines cannot
| exist in our universe.
|
| So it's rather ironic that people say the Halting problem is
| undecidable, when this is only true for (impossible to construct)
| imaginary machines but it's not true for the real machines that
| we actually have and that are possible to construct.
|
| Or think about Hilbert's paradox of the Grand Hotel.
|
| Or the Banach-Tarski paradox.
|
| Or Galileo's paradox.
|
| Or other such paradoxes that only exist if you believe that
| imaginary infinite objects could possibly exist.
|
| Most people will tell you "well, it's just that our intuition
| doesn't work for infinite things", but in this specific instance,
| it's really hard for me to believe that it's our intuitions that
| are mistaken rather than that we actually made some conceptual
| mistakes along the way. To me, this argument sounds more like
| gaslighting rather than a real convincing argument.
|
| I'm not saying our intuition is always correct, though. For
| example, the quantum properties of our universe are clearly not
| intuitive but it's hard to argue that our universe is not
| quantum, after all the scientific experiments that have clearly
| verified this to be true.
|
| I don't think that invalidates my argument, though, because the
| convincing argument in that case is not "sorry, you must believe
| my theory that the universe is quantum" despite not existing any
| evidence that this was true, but rather, "sorry, but here's all
| this real evidence that our universe truly is quantum".
|
| Am I crazy here?
| tsimionescu wrote:
| The thing is, infinity is extremely useful for taking things to
| the extreme. The halting problem is a very good example: as you
| rightly point out, the halting problem is trivially decidable
| for any finite Turing machine. However, the core of the
| argument remains true, we just need to complicate it
| significantly if we want to remain within the realm of finite
| machines: instead of saying "there is no TM that can decide if
| any arbitrary TM halts", we need to say something like "there
| is no finite TM that can decide if any TM smaller than itself
| halts in an amount of time less than that TM". They are
| equivalent concepts on some level, but the second one is
| significantly more complex, and harder to prove (assuming you
| don't appeal to the infinite version, from which it easily
| follows).
|
| That is, even if you seek to do maths on finite but unbounded
| sets, you will find mostly the same properties that infinite
| sets have, but you'll have a much harder time working with the
| concepts. It's true that there are some problems that infinite
| sets have that unbounded finite sets don't, but those may well
| be a worthy price to pay.
|
| And either way, regardless of intuition, the logic is valid.
| The Banach-Tarski "paradox" is perfectly logically valid,
| though unintuitive. So, even if you could say that it's useless
| and a result that we should avoid having in our theories, you
| can't say that it's wrong, since it doesn't violate any rule of
| logic.
| wizeman wrote:
| I can't really give a substantial response to your first
| argument, as I'm not certain about all the implications that
| you mention.
|
| Your second argument, though, doesn't sound very convincing
| to me.
|
| There are many possible consistent logical frameworks
| (perhaps an infinite amount of them? hah!) that are clearly
| not adequate for describing our universe. Or at least, they
| wouldn't make sense for us.
|
| For a trivial (and perhaps stupid) example, consider an
| alternate universe where we decided to use a logical
| framework which can represent natural numbers, but where the
| digit "2" is represented as "9" and the digit "9" is
| represented as "7", etc. Let's say you have a 1-to-1 mapping
| from one digit to another, compared to our usual
| representation.
|
| Or perhaps the mapping is a lot more complicated than that,
| and not just about digits, but about entire numbers.
|
| Let's say we decided to do that, for no good reason. Or maybe
| there was a good reason at the time, but since then we have
| figured out that it doesn't make sense anymore.
|
| Yes, you could do exactly the same math in this logical
| framework as we do in our usual ones, and no contradictions
| would arise.
|
| However, would that really be a wise idea? Wouldn't that just
| lead to making unnecessary mistakes, sometimes even
| conceptual ones, when considering that we would be prone to
| confusing numbers in this system with the numbers that we use
| normally?
|
| I think language is also important here, not just logical
| soundness. Especially if we want our intuitions to be
| helpful.
|
| Just to bring this back to something less abstract again, I
| will just mention the following:
|
| > However, the core of the argument remains true, we just
| need to complicate it significantly if we want to remain
| within the realm of finite machines: instead of saying "there
| is no TM that can decide if any arbitrary TM halts", we need
| to say something like "there is no finite TM that can decide
| if any TM smaller than itself halts in an amount of time less
| than that TM".
|
| Well, I don't believe the core of the Halting problem to be
| true, and that's exactly the language problem that I'm
| talking about: confusing language leads us to making
| conceptual mistakes.
|
| For example, time is not necessarily relevant here.
|
| I could argue that what the Halting problem really
| demonstrates is that to analyze whether a finite-state
| machine (FSM) halts, you need to use an FSM that can have
| more state than the machine being analyzed (which is why it
| stops working if you believe you can have infinite state).
|
| This FSM with more state would always be able to decide
| whether the other FSM halts in finite time, regardless of
| whether the other machine halts or whether it never does.
|
| In fact, that's exactly what cycle-detection algorithms do,
| such as the tortoise and hare algorithm.
| tsimionescu wrote:
| The biggest problem with finite sets is that most
| operations don't work nicely in finite sets.
|
| For example, if we take the naturals to be a finite set,
| and arbitrarily define some number G that is the largest
| number, then common operations stop being
| commutative/associative/distributive (e.g. x-y+z is no
| longer equal to x+z-y, if x>G-z; or xx(y-z) [?] xxy - yxz).
| Lots of simple equations stop having solutions at all. The
| finite rationals also get similar problems. Your models
| also have all these arbitrary parameters - the largest
| positive integer, the largest negative integer, the
| smallest fraction, the largest allowed amount of non-
| repeating digits in a decimal representation of a fraction
| - things like these become independent parameters, and can
| be arbitrarily chosen to be different.
|
| > Well, I don't believe the core of the Halting problem to
| be true, and that's exactly the language problem that I'm
| talking about: confusing language leads us to making
| conceptual mistakes.
|
| But it is - you still can't, in practice, construct a
| useful program that depends on solving the "finite halting
| problem", since you will need too much memory/time for
| anything but the most trivial of examples. If you don't
| beleive this, than it should be doable for you to create a
| program that checks whether P=NP if we limit it to programs
| that can run on, say, an 8086 processor and only use 16 KB
| of RAM, right?
| wizeman wrote:
| > The biggest problem with finite sets is that most
| operations don't work nicely in finite sets.
|
| I didn't necessarily mean to suggest that we should not
| work with infinite sets, only that perhaps we should not
| call them "sets" (so as to not confuse them with the
| finite ones), but rather something else, like "domains"
| or whatever.
|
| So perhaps you could say that those
| commutative/associative operations are valid over the
| domain of natural numbers. But you couldn't say, "X"
| represents the cardinality of the set of natural numbers,
| because there's no such thing as the set of natural
| numbers.
|
| Or, maybe the set of infinite natural numbers and
| infinite rationals makes sense but the set of real
| numbers doesn't (as they have different infinite
| properties?).
|
| I don't know exactly what would be a better solution
| here, as I'm not a mathematician. I'm only trying to
| suggest that there might be a better solution than what
| we have right now, even if it would simply amount to just
| using different language and not necessarily changing the
| logical properties of the theory, so as to not arrive at
| confusing conclusions.
|
| > But it is - you still can't, in practice, construct a
| useful program that depends on solving the "finite
| halting problem", since you will need too much
| memory/time for anything but the most trivial of
| examples.
|
| But the decidability of the Halting problem is not
| actually a question of how long it takes for an algorithm
| to solve it, is it?
|
| The decidability of a problem is a matter of whether it's
| actually possible _at all_ to construct an algorithm that
| solves it, no matter how long the algorithm takes to
| solve it.
|
| That is, whether this algorithm is computable and
| finishes in a _finite amount of steps_.
|
| So I will say again that yes, the Halting problem is
| decidable, as long as you don't use an absurd model to
| answer the question (i.e. a model that does not represent
| anything that can possibly be built in our universe even
| in theory?).
|
| The tortoise and hare algorithm solves the Halting
| problem for FSMs in a finite amount of time and it only
| needs twice the amount of storage as the underlying FSM
| that is being analyzed.
|
| > If you don't beleive this, than it should be doable for
| you to create a program that checks whether P=NP if we
| limit it to programs that can run on, say, an 8086
| processor and only use 16 KB of RAM, right?
|
| The P=NP is a problem regarding the resources required
| during computation to solve a given problem, as far as I
| understand.
|
| I am not entirely sure how exactly this relates to the
| decidability of the Halting problem when applied to
| finite-state machines, though.
|
| I mean, it's clear that the currently-known algorithms
| that solve the Halting problem on FSMs, such as the
| tortoise and hare algorithm, in the worst case take a
| time to solve that is proportional to the cycle length of
| non-halting FSMs.
|
| But also note that these currently-known cycle detection
| algorithms don't even try to analyze the FSM to decide
| whether it halts, except by testing their states for
| equality. This is due to the inherent definition of the
| cycle detection problem.
|
| So they can definitely be made more efficient, perhaps
| for a large set of useful FSMs, even, as long as they
| would be allowed to inspect the FSM's state transition
| table. I'm not sure how efficient they could be, in
| theory.
|
| I would be cautious in taking any computational
| complexity theory results at face value when we know that
| they use Turing machines as models, which can give you
| results that are the opposite of the results that apply
| to FSMs. But I'm not an expert and admittedly, I'm not
| entirely sure of what I'm talking about here.
|
| Regardless, even if you can trust the computational
| complexity results, to me this is an entirely different
| question than the decidability of the Halting problem,
| which is a "yes/no" problem.
| housecarpenter wrote:
| I agree that infinity doesn't exist in the universe, but this
| isn't a problem for mathematics. Mathematics isn't about what
| exists in the universe, it's about what exists in the realm of
| concepts. Some concepts are more interesting than others, sure.
| Cantor's work made it clear that infinite sets are pretty
| interesting.
| wizeman wrote:
| The Flying Spaghetti Monster is also an interesting concept.
|
| It can even be useful as a concept, in certain
| discussions/contexts.
|
| Should we take the Flying Spaghetti Monster as a core axiom
| of our theories of physics?
|
| Wouldn't this lead to us logically concluding for example,
| that there has to exist something else beyond the universe
| that we know about, even if this is not really true?
|
| I mean, I know that I'm exaggerating and that the analogy is
| not necessarily very good.
|
| But I'm also not entirely sure how different is the Flying
| Spaghetti Monster from the infinite objects that
| mathematicians talk about and that lead us to logically
| arrive at certain conclusions (that I would argue might not
| really be true, in terms of things we can understand).
|
| I'm not saying that I'm right and that most mathematicians
| are wrong, necessarily. Perhaps it's just a linguistic issue,
| I don't know.
| dang wrote:
| The thread this post is continuing:
| https://news.ycombinator.com/item?id=34484011
| boole1854 wrote:
| The argument here seems to rely on a natural language intuition,
| or perhaps even a physical or computational intuition, about what
| it mean to "choose" something from a collection.
|
| However, remember that the axiom of choice is technically a
| statement about the _existence of certain functions_ ,
| specifically functions that map from any set of non-empty sets to
| elements of those sets. Whether or not the existence of those
| functions says something about the possibility of "choosing" is
| more of a terminological question about how to connect informal
| natural language to mathematics than it is a substantive
| mathematical question.
|
| Turning to the mathematical question itself, it seems to me that
| the author's intuitions fare poorly. The author argues that we
| apparently cannot "choose" an element from a set that contains
| only numbers that are not finitely describable. But the
| mathematical question is about the existence of a mapping
| function, and it seems that whether or not the numbers in each
| set are finitely describable is irrelevant to this question:
|
| Consider the function _f(x) = x + 1_. This function is defined
| for all real numbers _x_. It maps each real number to another
| real number. Note that the domain of the function includes even
| those real numbers that are not finitely describable. The meaning
| of the function itself is nevertheless clear and the function is
| easy to write down. The fact that the domain of the function
| includes indescribable numbers is not relevant to the question of
| whether such a function exists mathematically.
| Retric wrote:
| f(x) = x + 1 is insufficiently defined here.
|
| It's easy to pretend math is some universal language but it's
| really several mutually exclusive languages.
|
| Infinity is not a number. You can pretend it is and there are
| several ways to build a mathematical system around such a
| choice, but it isn't inherently correct. So in your example
| f(x) may no longer include negative infinity and there is no
| paradox, it may include multiple infinite numbers and the
| lowest of them are now excluded, or you can say x and f(x) are
| the same etc.
|
| In the end there is no deeper truth here just the results of
| various completely arbitrary definitions.
| pdonis wrote:
| _> Infinity is not a number._
|
| It's not a real number, true. But that has no bearing at all
| on the validity of f(x) = x + 1, since that function is well-
| defined with both its domain and its range as all real
| numbers and no others. You don't need infinity to be a number
| to define that function.
| jjgreen wrote:
| _Infinity is not a number_
|
| It depends on what you think a number is. Most people who
| think about it agree a number is the name that we give to
| equinumerate sets, so two eggs and two ducks are
| equinumerate, we can give a bijection between these sets;
| they have the same property, "twoness" and we abstract
| twoness to the number 2. If so, then infinity is a number, it
| this the number-ness of the set {1, 2, 3, ... }
| quchen wrote:
| > It depends on what you think a number is.
|
| Let's not mix up teminology and semantics. What a number
| here is is quite clear, we're all talking about relatively
| standard math, the standard axiom of choice, and not some
| opinion on numbers. Sure, you can also say a planet is a
| mammal >>depending on what you think a mammal is<<, but
| that doesn't lead to any sort of fruitful discussion.
| jjgreen wrote:
| So what would you say a number is if not a name for the
| equivalences of set bijections? Genuinely interested,
| what is 2?
| vcxy wrote:
| There is no bijection between the natural numbers and the
| power set of the natural numbers. When talking about
| bijections to study the sizes of sets, there is clearly not
| just one infinity. Also consider the extended real line,
| this makes infinity a perfectly good number as well in a
| different way.
|
| My point is that infinity is certainly not an individual
| number. It represents quite a few concepts, all of which
| have some number like qualities.
| jjgreen wrote:
| Indeed, but when people say "infinity is not a number"
| they generally mean 0, and that is (in my view) as much a
| (cardinal) number as 2. Once you have that established,
| then you go on to discuss the higher s and the continuum
| hypothesis ...
| vcxy wrote:
| > when people say "infinity is not a number" they
| generally mean aleph-0
|
| Sure, maybe. I think saying "infinity is a number" is
| wrong regardless. I'm happy with aleph-0 being a number,
| and I'm happy with it having a label of infinity. I'm
| just not happy with treating infinity as a single thing.
| We're totally on the same page in every way that matters
| though. I'm also certainly with you on questioning
| Retric's comment for a number of reasons, haha.
|
| edit: Actually...I'm not so sure they mean aleph-0. I
| think frequently they mean the infinity of the extended
| real line. Maybe it depends on the context of the
| conversation.
| jjgreen wrote:
| It's actually a great ice-breaker for first-year maths
| undergrads, when talking about limits or whatever drop in
| "... to infinity and beyond!", laughter follows, then say
| "You think I'm joking? Put down your pens ..." and
| informally outline the aleph hierarchy, then things get
| rather quiet.
| vcxy wrote:
| Ahh I wish I had gotten the chance to interact with new
| math majors more often. In grad school most of my
| students were engineering majors. I'm not super likely to
| end up back in academia. My published research
| is...sparse. I have post-doc opportunity but it's not the
| greatest, and the route to life stability is not so
| clear. Are you a math professor?
| jjgreen wrote:
| No, a developer; I spent several years as applied maths
| researcher though, and UK universities love to use
| researchers as cheap lecturers (not that I'm complaining,
| rather enjoyed it).
| vcxy wrote:
| Cool. I have a second interview for a software developer
| position at a quantum computing place this week.
| Hopefully I'll be following you into the field!
| syzarian wrote:
| Your post doesn't make sense mathematically. As a function
| from the reals to the reals the function f(x) = x+1 doesn't
| "include negative infinity" (have no idea what that is
| supposed to mean). Negative infinity is not a real number and
| is not in the domain of the function or its range. If you
| think "infinity" (which one?) is not a number then do you
| believe there are no infinite ordinals? How do you justify
| the view that countably infinite ordinals don't exist?
| Retric wrote:
| You are making assumptions, define the lowest real number.
| syzarian wrote:
| There are well defined models of the real numbers. You
| don't know enough mathematics to comment intelligently on
| this topic. What you wrote above makes no sense.
|
| EDIT: There is no least real number under the standard
| ordering. There is a least real number for a given well
| ordering. If you are asking me to define a well ordering
| on the reals then your request question should have been
| stated differently.
| Retric wrote:
| You said models not model here, so you acknowledge there
| isn't a single universal definition.
|
| I've seen some truly bizarre definitions of the reals
| which are internally consistent and include things like
| the lowest possible number.
| syzarian wrote:
| You don't know enough set theory and model theory. Of
| course there are different models of the real numbers.
| There are non isomorphic models of the first 4 axioms of
| Euclidean geometry even. A given set of axioms can have
| lots of different models.
|
| The widely accepted first order axioms of the natural
| numbers have nonstandard models. Of course each such
| model has an isomorphic initial segment. There are two
| things going on. There is the set of axioms and there are
| models for those axioms. I think in your usage: "define
| real number" corresponds to "give the axioms for the real
| numbers". I'm not sure though.
| Retric wrote:
| Non standard models of arithmetic really takes me back.
| Anyway, axiom/models is the common terminology though I
| recall a rather long rant that postulate is better once
| you start talking about multiple incompatible systems.
| messe wrote:
| Please consider that the poster telling you that you do
| not know enough to comment intelligently about this topic
| may be correct.
|
| > Anyway, axiom/models is the common terminology though I
| recall a rather long rant that postulate is better once
| you start talking about multiple incompatible systems.
|
| Model has a very specific definition in this area of
| mathematics. This sentence is nonsense.
| Retric wrote:
| I am describing an actual event with that sentence. Are
| you suggesting that someone can't rant about such things?
| Arkhaine_kupo wrote:
| The negative reals are an infinite set, that doesn't make
| "negative infinity" a real number though. Negativy
| infinity is a concept, that can be used in some math
| frameworks, but it is not defined within R.
|
| See this exchange for details
|
| https://math.stackexchange.com/questions/2812355/does-
| infini...
| Retric wrote:
| I am trying to allude to transfinite numbers and annoy
| mathematicians without losing a general audience, feel
| free to ignore such things.
| JackFr wrote:
| I'm not sure you've shown anything. _f(x) = x + 1_ is a mapping
| from the reals to the reals. A choice function, with respect to
| the axiom of choice, is a mapping from the set to an element.
| boole1854 wrote:
| The point of my example is to show that the functions can
| exist even if their domain includes "indescribable" numbers.
| It shows that trivially the "indescribable-ness" of numbers
| in the domain of the function is not relevant to whether the
| function exists.
|
| The author's argument relies on "indescribable-ness" somehow
| blocking the ability to "choose" an element. But that trades
| on a vague, intuitive understanding of "choosing", which
| doesn't capture what the AC is about. The AC is about the
| existence of certain functions. Since the "indescribable-
| ness" of the domain of a function is not relevant to its
| existence, the author's argument doesn't successfully attack
| the AC.
| lisper wrote:
| > The point of my example is to show that the functions can
| exist even if their domain includes "indescribable"
| numbers.
|
| But that is not at issue. What is at issue is whether or
| not a function exists whose domain is an (infinite) _set_
| of indescribable numbers and whose range is a member of the
| set. The existence of such a function is far less clear.
|
| Of course you can postulate the existence of such a
| function. But you can also postulate the existence of an
| oracle for the halting problem. My gut tells me that these
| two ideas have a lot in common.
| boole1854 wrote:
| Remember that I am not here trying to argue for the truth
| of the AC; I'm arguing against the author's argument. The
| author's argument, as I read it, relies on an intuition
| that "choosing" an element that is not-finitely-
| describable is problematic. However, the mathematical
| meaning of "choosing", in the context of the AC, is a
| statement about the mathematical existence of a certain
| function. To respond to the author's intuition requires
| only showing that not-finitely-describable domains are
| not a "problem" for the existence of functions. Maybe it
| is difficult to "choose", in some natural language sense,
| an input to f(x) = x + 1 such that the output x + 1 is a
| real number (e.g., you can't write down such an input one
| digit at a time on a piece of paper, even an infinitely
| long piece of paper). But this does not mean it is
| problematic for the function to exist in the mathematical
| sense.
| lisper wrote:
| FYI, I am the author.
|
| > Remember that I am not here trying to argue for the
| truth of the AC; I'm arguing against the author's
| argument.
|
| Yep, I get that.
|
| > The author's argument, as I read it, relies on an
| intuition that "choosing" an element that is not-
| finitely-describable is problematic.
|
| Not quite. Choosing an element from a set where _all_ of
| the members are not-finitely-describable is problematic.
|
| > However, the mathematical meaning of "choosing", in the
| context of the AC, is a statement about the mathematical
| existence of a certain function.
|
| Yep, I get that.
|
| > To respond to the author's intuition requires only
| showing that not-finitely-describable domains are not a
| "problem" for the existence of functions.
|
| No, you would have to show that defining a function on
| _this particular set_ is not a problem. Note that this is
| _not_ the same thing as defining a function on _elements_
| of this set. That is obviously not a problem. But
| defining a (non-trivial) function _on the set itself_ is.
| riversflow wrote:
| I just don't see what describability, or as jiggawatts
| calls it, naming, has to do with AC. AC is built upon an
| indexed set[1]. That way you can just reference the
| index. It seems extremely contrived to me to argue that
| being finitely nameable has any bearing on underlying
| mathematical principle, nothing about any form of
| infinity is relatable to the physical confines of this
| universe, of which language is a member, but the concept
| of infinite is very useful.
|
| [1]https://en.wikipedia.org/wiki/Axiom_of_choice
| syzarian wrote:
| There are models of ZFC in which every real number is
| definable. You may be interested in the top answer at
| this mathoverflow.net question:
|
| https://mathoverflow.net/questions/44102/is-the-analysis-
| as-...
| lisper wrote:
| That is very interesting (have an upvote!) but I don't
| see how it invalidates my argument. If every real is
| definable then the set of non-definable reals is empty
| and AoC does not apply at all.
| syzarian wrote:
| The notion of countable and not countable does have some
| nuance. In the models that every real is definable that
| model, from within, believes it is uncountable since
| there is no bijection with a countable set from within
| that model. However, from the outside that model is
| countable.
|
| The point is there is a lot of nuance and no matter what
| one believes regarding choice there will be unintuitive
| results. For instance, when the axiom of choice fails you
| can have an infinite set with not countably infinite
| subset. The reals can be a countable union of countable
| sets. There is a set that can be partitioned into
| strictly more equivalence classes than the original set
| has elements, and a function whose domain is strictly
| smaller than its range. In fact, this is the case in all
| known models.
| Kranar wrote:
| We need to be careful with the language here. It's not
| true that there are models of ZFC where the real numbers
| are actually definable. What's true is there are models
| of ZFC where what is considered a "real number" from
| within that model is always definable (but will not be
| definable within that model). However, those sets do not
| form the actual real numbers, they are simply sets that
| from within the model satisfy a given definition of the
| reals without actually being the reals.
|
| A similar result is that there are models of the reals in
| ZFC that are countable, even though the reals are not
| countable. How can this be? Well it's similar to the
| above argument, those models do not represent the actual
| real numbers.
|
| All this means is that it's not possible to categorically
| define real numbers in first order ZFC. Any axiomatic
| definition of the reals in first order ZFC will have some
| models that satisfy those axioms but are not actually
| real numbers.
| syzarian wrote:
| I'm not a logician or set theorist. I studied commutative
| algebra and, naturally, accept the axiom of choice. When
| you say, _"the actual reals"_ I think you mean the
| standard notion of a real number that we all are used to
| using. But those models that we are talking about are
| models of the axioms of the reals. So, they are the
| actual real numbers as far as that model is concerned,
| right?
| Kranar wrote:
| You got it, absolutely. So yes there are models where as
| far as the model is concerned there is a set that
| satisfies the axioms of real numbers, and furthermore all
| elements of that set are actually definable (but not
| definable from within that model), but that set is not
| the standard notion of real numbers. It's just that it's
| impossible to provide a set of axioms that defines the
| real numbers and only the real numbers (in first order
| logic), so for any definition of the real numbers you end
| up with a model that will satisfy that definition but
| doesn't actually model the "standard notion of real
| numbers".
|
| The reason I brought this up is because when you said
| that there are models of ZFC where every real is
| definable, those reals are only definable from outside of
| the model. From within that model there are still
| undefinable reals and hence I don't think it matters too
| much to the point lisper is making.
|
| Maybe to put it another way, there is no model of the
| reals where within that model all reals are definable,
| and hence lisper's point stands.
| syzarian wrote:
| Understood. I wasn't trying to address lisper's directly
| as such. My poorly stated goal was to point out that
| intuition regarding uncountable sets is shaky at best.
| There are weird results regardless of one's views because
| of nonstandard models.
| cgio wrote:
| Intuitively I would argue the definition of
| indescribability is loaded with semantics that can
| sprinkle paradoxes at will. A set from my perspective has
| at least two interfaces, one to populate it and one to
| query it. By making the population interface
| "indescribable" you get an "indescribable" method to
| query. Worst case you start from a describable superset
| of the indescribable one and test the "indescribable "
| set population method to get you an indescribable set
| member. Which makes the indescribable actually
| describable in terms of this process. "?" on this whole
| statement, late night intuition from an indescribably bad
| at math sleepy guy.
| recursive wrote:
| > one to populate it and one to query it
|
| I'm not a math expert, but "populating" a set strikes me
| as an imperative programming mindset. In math, I
| understand a set more like a function returning a boolean
| that indicates membership. If the contents of the set
| change, then it's just a new set.
| lisper wrote:
| Yeah, this. A set does not have "two interfaces", it only
| has one: a membership function that takes an object and
| returns a boolean indicating if the object is a member of
| the set or not. Note that this function need not be
| computable, only well-defined.
| loicd wrote:
| The nature of the elements of the set does not matter,
| since the existence of a choice function on the set A
| guarantees the existence of a choice function on the set
| B as soon as there is a bijection between A and B. Thus,
| no matters how counter-intuitive or unnatural one finds
| the elements of a set, or whether they model physical
| reality, what matters for the axiom of choice is whether
| one can construct a bijection with a set that has a known
| choice function.
|
| By the way, it is worth keeping in mind _how_ Godel
| proved the consistency of the axiom of choice. Roughly
| speaking, the steps are: start with a model of ZF, build
| from it an inner model where all sets are definable (in a
| sense) in terms of ordinals, that model (called the
| "constructible universe") satisfies the axiom of choice.
| In other words, the axiom of choice holds as soon as you
| assume that _all_ sets are constructible.
| 6gvONxR4sf7o wrote:
| It seems like the validity of what you're saying is
| intertwined with the axiom itself. You're going from a
| comment about the domain (the domain includes indescribable
| elements) to a comment about specific arguments (arguments
| may be indescribable).
|
| Ultimately, you're saying that if we have an indescribable
| x, then x+1 is conditionally describable (to abuse
| terminology). But I think that just sidesteps the question.
| Even then, if we're taking a computability lens, then
| indescribable(x) implies indescribable(x+1), which would
| seem to imply that applying your function to indescribable
| x's is a moot point.
|
| The fact that your function is finitely describable even
| though we can't describe each of its applications is
| admittedly a mindfuck.
| jvanderbot wrote:
| Like f(x) = 5?
| yaakov34 wrote:
| Wouldn't work, since 5 is not a member of the set of
| indescribable numbers. I am still not sure that the
| original example is good, since serious difficulties with
| the axiom of choice have to do with infinite collections of
| sets, especially uncountably infinite, not with choosing a
| member of a single difficult-to-describe set. But you can't
| handle these non-describable numbers very easily.
| [deleted]
| davrosthedalek wrote:
| That's fine. The point is that the x is also not in the
| set of indescribable numbers (because you have described
| it with f(x)=5), assuming f is describable.
| davrosthedalek wrote:
| The problem is that for every finite description of f, the
| x that fulfills f(x)=5 is not in the set of numbers than
| cannot be described by a finite set of symbols. (I assume
| here that there is only one solution of f(x)=5)
| kazinator wrote:
| Let's pin it down!
|
| To choose an element from every one of a set of sets, we must
| describe the method of choice as a halting algorithm executable
| by a Turing Machine.
| ketzu wrote:
| I wonder if the set of undescribable numbers is well defined at
| all. It seems to run into the same problem as the "minimum un-
| interesting number is interesting" as a function chosing a
| number from that set would be a finite description of that
| number, removing it from the set. (This already happens if you
| could select a finite subset of those numbers, as finite
| numbers could be ordered and you could just select the
| minimum.)
|
| edit: Hm... thinking about it. The finitely-many-symbols
| argument also only holds if you consider finitely many
| interpretations of those symbols and if there actually are only
| finitely many symbols.
| LegionMammal978 wrote:
| It's not too mind-boggling: we can describe the set as a
| whole without any issues, we just can't _uniquely_ describe
| any particular number in the set. That doesn 't stop us from
| generalizing over all numbers in the set, or even over all
| numbers in a describable subset, such as "the set of all
| undescribable primes".
| ketzu wrote:
| > we can describe the set as a whole without any issues
|
| But it does not mean the set is well defined. The
| description is not necessarily clear an unambigious. It
| might not be consistent under the generalizations we come
| up with.
|
| > "the set of all undescribable primes"
|
| Interesting example, because the set is trivially empty
| under the assumption that we can describe any finite
| natural number by writing down its decimal expansion.
| (Based on that you can either argue that the primes are a
| subset of the natural numbers or that the primes are
| countable.)
|
| I see no reason to believe that "undescribable" is a well
| defined property so far.
| resource0x wrote:
| To me, the expression "The set of undescribable numbers" is
| meaningless. While discussing plausible-sounding, but
| meaningless, linguistic constructs like this, we descend to
| the intellectual level of chatGPT. My conjecture is that one
| can design a prompt to chatGPT such that the output would
| become a decent PhD thesis with no internal contradictions,
| but a complete BS otherwise.
| librexpr wrote:
| I think if we take "description of a number" to mean "ZF
| formula that uniquely picks out that number", then that
| cannot be defined, because a formula picks out a number when
| it is true for that number and false for all others, but by
| Tarski[0], the truth predicate cannot be defined inside the
| logic itself. So "the set of all numbers which cannot be
| described" cannot be talked about using ZF.
|
| However, there is a way around it, by taking as axiom that ZF
| is consistent, choosing some model M of ZF, and then talking
| about the set S of numbers inside M that cannot be described.
|
| [0] https://en.wikipedia.org/wiki/Tarski%27s_undefinability_t
| heo...
| actually_a_dog wrote:
| Bingo. The issue here is that ZF and ZFC are both first
| order theories. They can only talk about things that _can
| be_ defined within them, not things that _cannot_ be
| defined within them. The wiki article talks about that
| where it says:
|
| > Informally, the theorem says that the concept of truth of
| first-order arithmetic statements cannot be defined by a
| formula in first-order arithmetic. This implies a major
| limitation on the scope of "self-representation". It is
| possible to define a formula True(n){\displaystyle True(n)}
| whose extension is T*,{\displaystyle T^{*},} but only by
| drawing on a metalanguage whose expressive power goes
| beyond that of L.L. For example, a truth predicate for
| first-order arithmetic can be defined in second-order
| arithmetic. However, this formula would only be able to
| define a truth predicate for formulas in the original
| language L.L. To define a truth predicate for the
| metalanguage would require a still higher metametalanguage,
| and so on.
| mckeed wrote:
| That's the point though, right? Without Choice, there need be
| no way to select a number or subset from the set, so there's
| no paradox.
| planede wrote:
| I think the resolution is along the lines of this:
|
| * ZFC does not have a unique model that satisfies the axioms.
|
| * Each of those models have different "undescribable numbers"
| with different properties.
|
| But it was a long time I touched model theory, and it was
| just an optional extra course at uni.
|
| https://en.wikipedia.org/wiki/Model_theory
| hilbertseries wrote:
| https://en.m.wikipedia.org/wiki/Computable_number
| mannerheim wrote:
| There are uncomputable numbers which can still be defined.
|
| https://en.wikipedia.org/wiki/Chaitin%27s_constant
| [deleted]
| kybernetikos wrote:
| > But the mathematical question is about the existence of a
| mapping function, and it seems that whether or not the numbers
| in each set are finitely describable is irrelevant to this
| question:
|
| If it's possible to construct the set at all, then there is by
| definition no function that can be described in a finite number
| of symbols that can select an element from the set (since if a
| finitely describable function can define a member of the set,
| it shouldn't be in the set - you'd define the element as being
| the result of the function).
|
| I don't know what the scholarly view is on relying on functions
| that _cannot be defined in any human language, including
| mathematics_. I would intuitively lean towards not allowing
| them in proofs, but perhaps they 're useful mathematically?
|
| Another interesting aspect - these are numbers, so presumably
| there is a smallest one, but identifying that is definitionally
| ruled out too, since 'smallest element in the set of numbers
| indescribable in a finite sequence of symbols', is itself a
| finite sequence of symbols.
| hackandthink wrote:
| "The well-ordering theorem together with Zorn's lemma are the
| most important mathematical statements that are equivalent to
| the axiom of choice"
|
| This is all crazy stuff, but it would be consistent:
|
| No axiom of choice -> no well-ordering -> no smallest number.
| syzarian wrote:
| Consider the interval (0, 1). This set of real numbers
| contains no smallest element. It is not true that all sets of
| real numbers have or should have a least element. It is a
| property of the standard model of the nonzero integers that
| all subsets have a least element.
|
| It should be noted that there are models of ZFC in which each
| real number is definable. You may be interested in reading
| the top answer on this mathoverflow.net question:
|
| https://mathoverflow.net/questions/44102/is-the-analysis-
| as-...
| [deleted]
| huitzitziltzin wrote:
| This part:
|
| > 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.
|
| That's clearly wrong. The real numbers between 0 and 1 (an
| uncountable collection) are describable with a finite collection
| of symbols - the digits between 0 and 9. Each real number is an
| equivalence class of sequences with the same limit. (It's been a
| while since I took real analysis but I believe this is the
| construction due to Weierstrass?)
| danbruc wrote:
| The author means finite sequence over finite alphabet, i.e. the
| finite collection of symbols does not refer to the alphabet.
| [deleted]
| johnnny wrote:
| The set of numbers that can be written with a finite number of
| 0-9 digits is countable. That set is called the decimal
| numbers, and is a subset of the rational numbers which itself
| is countable too.
| huitzitziltzin wrote:
| The set of numbers which can be written _with finitely many_
| members of a finite set of symbols is countable, sure.
|
| That doesn't sound like the claim the author is making in the
| sentence I quoted but maybe I am being uncharitable?
| johnnny wrote:
| If you allow infinitely long descriptions, then I don't
| know what's the score. In the case of "descriptions" that
| amount to (potentially infinite) decimal expansions, I
| think an argument akin to Cantor's diagonal will show that
| you can't possibly describe all real numbers (or all
| numbers between 0 and 1), but I'm not confident I can
| assert this to be true.
| renewiltord wrote:
| This doesn't make sense. That's not what AoC means. It is a
| statement that the cartesian product is non-empty if the sets are
| non-empty.
|
| One might as well say "Well, if I were to lobotomize you, you
| would not be able to choose". The "choice" here is a term of art.
| There is no actual "choosing" going on here.
| Sankozi wrote:
| "consider the set of numbers that cannot be described using any
| finite collection of symbols" - isn't that set empty?
|
| If "numbers" mean "real numbers" then I can describe easily
| "smallest positive number in the set" and "biggest negative
| number in the set" - so neither negative, 0 nor positive real
| numbers might be in the set.
| norrius wrote:
| What is the "smallest positive number" in the set {x | x in
| reals and 0 < x < 1}?
| tsimionescu wrote:
| It's trivial to prove that the number you are describing
| doesn't exist:
|
| Let x be the smallest positive real greater than 0. Since x >
| 0, x/10 < x, and x/10 > 0. But now we have a contradiction,
| since x was supposed to be the smallest positive real number.
| So, x doesn't exist.
|
| Edit: note that this doesn't even require real numbers. Even
| for the rational numbers, with common definitions of less-than,
| there is no smallest positive rational number >0, per the same
| logic.
| mjburgess wrote:
| The axiom of choice is intuitive because its seems one should
| always be able to take many aggregates of elements and make a new
| aggregate.
|
| The axiom of choice is counter-intuitive because it provides no
| reason to, in the case of a uniform aggregate, choose one element
| over another. Nor a reason to suppose in the case of a "complex
| aggregate" that "choice" is even well-defined.
|
| Perhaps one way of thinking of the issue here is the tension
| between the discrete and continuous. Of course, one can always
| recombine even inifnite number of discrete things.
|
| But what does it mean to "choose" a "point" on a "line" ? Can one
| "choose" pi?
|
| One could, for example, take the view that the very notion of
| membership, "choice", etc. is conceptually inadequate for
| handling geometrical matters such as the reals.
| orlp wrote:
| > 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.
|
| Why is almost no one more critical of this? A 'number' you can't
| describe or do computation with? Why do we still call this a
| number? If I ask Google to define number I get
|
| > an arithmetical value, expressed by a word, symbol, or figure,
| representing a particular quantity and used in counting and
| making calculations.
|
| Almost all (in the mathematical sense) 'real' 'numbers' can not
| be expressed, nor can be used for counting or making
| calculations.
|
| Over the years I'm becoming more and more convinced we should
| reject the 'real' numbers as our default mathematical object for
| numbers, and switch to a basis that has a computable foundation.
| There is some work being done in this area, but not nearly enough
| in my opinion:
| https://en.wikipedia.org/wiki/Computable_number#Use_in_place...
| mik1998 wrote:
| Real numbers are interesting and math is not about computation,
| counting or calculation.
| hgsgm wrote:
| math is not _only_ about computation, counting or
| calculation.
| hgsgm wrote:
| Mathematicians hijacked numbers.
|
| Computer scientist don't accept noncomputable objects.
| Mathematicians do.
|
| To a scientist, existence means "you, or someone, can find it,
| at least potentially". To a non-constructive mathematician (the
| common kind) existence means "you can't prove it _doesn 't_
| exist, and I choose to believe it does, at least in the current
| game I am playing."
|
| Mathematicians use the term "real numbers" to describe
| precisely the set of numbers you get when you take all the
| numbers that could plausibly be computed, _and then declare
| that all the holes between numbers we can individually compute
| /describe are completely full of numbers._ This is justified
| because you can't prove that any specific one of them is
| impossible to write.
|
| (But there are some so called "real" numbers that are
| impossible to calculate, even approximately, like Chaitin's
| constant https://en.m.wikipedia.org/wiki/Chaitin%27s_constant
| but you could write it in infinite time if God told you the
| digits.)
| drdeca wrote:
| > Computer scientist don't accept noncomputable objects.
|
| People who study computability certainly do, and I would
| think they count as computer scientists.
| shkkmo wrote:
| > But there are some so called "real" numbers that are
| impossible to calculate, even approximately, like Chaitin's
| constant https://en.m.wikipedia.org/wiki/
|
| Just because you can create a definition, doesn't mean that
| definition names a thing. We can define "the set of all sets
| that do not contain themselves", but such a definition is
| nonsensical in that trying to apply it creates a
| contradiction. To me, the incomputability of Chaitin's
| constant seems very similar, except it's contradiction is
| buried inside the halting problem.
| bmitc wrote:
| > Computer scientist don't accept noncomputable objects.
| Mathematicians do.
|
| Computer scientists don't have a choice. And not all
| mathematicians do accept non-computable objects. Constructive
| and intuitionistic mathematics are two approaches that bring
| some questions (doubt?) of the continuum.
| dia80 wrote:
| You are going to love this:
|
| How real are real numbers?
|
| https://arxiv.org/abs/math/0411418
| [deleted]
| moron4hire wrote:
| A variable name and the thing it points to are not the same
| thing. Symbols aren't numbers. They are a means to communicate
| numbers.
| psychoslave wrote:
| Naming is not a requirement to selecting. I can pick a tool, and
| even use a tool, without having to name it. Most selection
| process out there work without relying on any explicit name.
|
| In the theory of natural selection for example, specimens are
| selected without being named.
| cousin_it wrote:
| > _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._
|
| Maybe you already know, but this argument is wrong, see Hamkins
| "Pointwise definable models of set theory". It's a triple whammy:
| 1) You can't state the argument formally, because the property of
| describability is undefinable (Tarski's undefinability of truth).
| 2) Whatever your theory claims about uncountability, from the
| outside there's always a countable model of it (Lowenheim-
| Skolem). 3) And if you have a countable model, there's nothing
| stopping you from having a finite formula for every member of it
| (making it a "pointwise definable model"). All the details are
| worked out in the paper: yes Virginia, there are models of ZFC
| whose every member - every set, every function, every real number
| - is definable by a finite formula.
|
| Also a lot of nice counterexamples in this reddit thread:
| https://www.reddit.com/r/math/comments/d9sp9h/the_math_tea_a...
|
| For example:
|
| > _" Take your favorite real in some model M. We can take a
| forcing extension to a model M[G] in which the real is coded in
| the continuum function below aleph_omega. Now it's definable."_
|
| Or:
|
| > _" There is a computable real that ZFC doesn't prove is a
| computable real."_
| tel wrote:
| AC fails to exist, in its normal form, in constructive or
| intuitionistic formulations of math. This post appeals to that
| sort of mathematics and thus correctly identifies that it
| wouldn't make sense there.
|
| There are weaker forms of AC which do exist, though. And
| formulations of math where AC is necessary and obvious, but
| doesn't really imply the same thing as classical AC. But these
| formulations of math are very unlike the classical one we
| normally enjoy.
|
| For instance, they often disallow the construction of the Reals
| altogether.
| quchen wrote:
| Why does it fail to exist? It's an axiom that can be added to
| intuitionistic axiom systems just as well as for classical
| ones, no? It's orthogonal to the law of the excluded middle
| after all. In constructive mathematics with AC, you would just
| call the selected set element AC(your-set).
| tel wrote:
| It's been a while so I've forgotten the details, but I
| believe in some versions of constructive mathematics AC is
| enough to derive LEM.
| n4r9 wrote:
| This has a similar feel to Russell's paradox:
|
| Let R be the set of all sets that are not members of themselves.
| If R is not a member of itself, then its definition entails that
| it is a member of itself; if it is a member of itself, then it is
| not a member of itself, since it is the set of all sets that are
| not members of themselves.
|
| https://en.m.wikipedia.org/wiki/Russell's_paradox
|
| Also the Lowest Uninteresting Number paradox:
|
| If there exists a non-empty set of uninteresting natural numbers,
| there would be a smallest uninteresting number - but the smallest
| uninteresting number is itself interesting because it is the
| smallest uninteresting number,
|
| https://en.m.wikipedia.org/wiki/Interesting_number_paradox
|
| I suspect that the resolution boils down to what it means to
| "describe" a number.
| pavlov wrote:
| I'm not a mathematician but I wonder why the Lowest
| Uninteresting Number paradox can't be resolved by simply
| adjusting the definition of "interesting"? After all that's a
| purely human concept. If we say a number isn't interesting
| simply due to its proximity to other interesting numbers, then
| we can draw the boundary.
|
| It seems a bit like making a list of important cities. Borders
| are very important to countries, but not every border city is
| economically or historically important. It's not unreasonable
| to say that a city must meet other criteria than simply being
| close to a border.
| mannykannot wrote:
| Yes... when I first saw this paradox, the author of the
| article I was reading (maybe Martin Gardner?) pointed out
| that 'uninteresting' is itself not well-defined.
| tuatoru wrote:
| The set of uninteresting numbers is probably empty.
| hgsgm wrote:
| Please define "uninteresting" and "probably".
| kybernetikos wrote:
| I think the uninteresting number one can be described
| without worrying about 'interestingness'. It works out as
| the same as saying something like _the set of numbers that
| are not the smallest number in any set in some arbitrary
| collection of sets including this one_.
|
| It's the 'including this one' part that is causing the
| trouble, not which other sets are included in the arbitrary
| collection.
| [deleted]
| tomp wrote:
| This is not intuitive at all.
|
| I have a masters in math. Concrete numbers are irrelevant to me,
| and their explicit representation is even less relevant. _Any_
| number can easily be described by _x_.
|
| Btw this is just the standard reason for the existence of the
| Axiom of Choice. _If_ there exists a procedure to describe
| _which_ number to choose (i.e. an algorithm /formula), you don't
| need AC at all.
|
| IMO the only "intuitive" anti-AC argument is, that you can get
| most of math with Axiom of _Countable_ Choice, while you avoid
| paradoxes like Banach-Tarski.
| davrosthedalek wrote:
| Question: While the standard construction of the set for
| Banach-Tarski requires AOC, is it proven that without AOC,
| Banach-Tarksi isn't true?
| tomp wrote:
| Not sure,
|
| but if you replace AC with a weaker axiom, Axiom of
| _Dependent_ Choice, you can construct a model in which all
| subsets of reals are measurable (called the _Solovay model_
| ), which precludes the Banach-Tarski paradox (which requires
| non-measurable sets).
|
| Could BT be constructed without AC but with other way of
| ensuring there exist non-measurable sets? No idea.
| Kranar wrote:
| Depends what you mean by without AOC. If you just mean
| whether Banach-Tarski can be proven in ZF the answer is no.
| But you also don't need the full power of AOC to prove
| Banach-Tarski.
| throwaway81523 wrote:
| By "without AC" I think you mean "with the negation of AC".
| It turns out that BT+ZF is equivalent to ZF + a weaker
| version of AC called the Ultrafilter Lemma, iirc. There is
| more info in the Wikipedia article about BT. Also, the Hahn-
| Banach theorem (plus ZF) proves BT.
| pdpi wrote:
| > you can get most of math with Axiom of Countable Choice
|
| Wait, I think you just made me realise that my intuition for
| AoC is wrong and actually matches AoCC instead, and that I'd
| never stopped to consider that the collection of sets you're
| choosing from could be uncountable. If that's correct, that
| explains so much.
| NotYourLawyer wrote:
| How do you feel about this example?
|
| https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...
| lisper wrote:
| > If there exists a procedure to describe which number to
| choose (i.e. an algorithm/formula), you don't need AC at all.
|
| The problem here is not that there does not exist a procedure
| to describe which number to choose, the problem is that there
| does not exist any way to describe which number you _chose_.
| Those are not the same thing.
| civilized wrote:
| Can you give an example in which these two things are
| different?
| lisper wrote:
| I'm not sure I understand what you are asking. One is a
| description of a _procedure_ and the other is a description
| of a _number_ so obviously these are two different things.
| mckeed wrote:
| When you say "Any number can easily be described by x" aren't
| you already using Choice? And doesn't "let x be one of those
| numbers from the set of numbers that cannot be described with
| finite symbols" seem a bit like a paradox?
| [deleted]
| CamperBob2 wrote:
| An object exists prior to being named. If the act of naming (or
| "counting") the object is all it takes to move it to a different
| set, then the paradox vanishes, no?
|
| What does it even mean to refer to a "set" of named/unnamed
| objects or counted/uncounted numbers?
| bannedbybros wrote:
| [dead]
| tshaddox wrote:
| > 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.
|
| But wait. It's true that there are only countably many "symbolic
| descriptions," and uncountably many real numbers, but it doesn't
| follow that there are _specific_ real numbers which cannot be
| described using a finite collection of symbols, does it?
|
| You can, of course, have a computer algebra system that includes
| a symbol for a non-computable number like a Chaitin constant
| (with a well-defined encoding). Wouldn't it be the case that you
| could define symbols for _any_ countably infinite set of non-
| computable numbers?
|
| It doesn't seem to me that there is a _fixed_ set of specific
| non-computable numbers that cannot be referred to by a symbol.
| Instead, it's just that any particular countably infinite set of
| symbols can only refer to a countably infinite set of non-
| computable numbers.
| hgsgm wrote:
| That's right, we are talking about non computable numbers, so
| they can't actually be "specific".
|
| Say you have a no computable number A (Chaitin's constant), and
| I have an uncomputable number B Chaitin's constant but the the
| trillionth digit is equall to the most common digit in the
| infinite decimal expansion of Chaitin's constant). How can you
| tell if they are the same or different? In general, you can't.
| So what does "specific" even mean?
| tshaddox wrote:
| I'm not sure if that's relevant. You're pointing out that
| ordering of the reals is not computable, which is true, but
| ordering _of the computable numbers_ isn 't even computable.
| This isn't relevant to whether a symbol in a computer algebra
| system can refer to a particular number (whether computable
| or not).
| rcme wrote:
| > But wait. It's true that there are only countably many
| "symbolic descriptions," and uncountably many real numbers, but
| it doesn't follow that there are specific real numbers which
| cannot be described using a finite collection of symbols, does
| it?
|
| It does follow because the set of finite collections of symbols
| is countable.
| tshaddox wrote:
| I'm not sure what you mean, because you just repeated the
| first part of my sentence. The fact that one set is countable
| and the other is uncountable doesn't mean there are
| _specific, fixed_ numbers in the uncountable set which cannot
| be paired with any element in the first set.
|
| Consider the usual example of the natural numbers (countable)
| and the reals (uncountable). It doesn't follow that there is
| some _specific, fixed_ real number which cannot be part of a
| bijection of the naturals and the reals. Name any real number
| and I can give you a bijection of the naturals and the reals
| which contains your real number.
| jerf wrote:
| This is close to why I'm not in love with the Axiom of Choice. I
| don't _hate_ it, and I don 't "mind" it, but I do think
| mathematicians are perhaps more comfortable with it than they
| should be. The reason is, I think proofs of the form:
| 1. A 132 bit (in the information theory sense) definition of
| something. 2. A 98 bit definition of something else.
| 3. A 4 bit procedure that puts them together. 4. A 2883
| bit object of interest. 5. An uncountably infinite number
| of bits added to the objects in 3 and 4, with no
| mechanism for determining any of them even in theory.
| 6. Therefore, a 76 bit conclusion of interest.
|
| is just intrinsically more _icky_ to me than mathematicians in
| general think. You know, mathematically icky. It 's a technical
| term. There's a step here that sticks out like a sore thumb.
|
| Sure, there's a whole lot of fuzziness around measuring the size
| of a statement in bits, but no matter how you slice it, you're
| not going to get away from a certain amount of distinction
| between the statements that are finite, and probably even fairly
| small in absolute terms, versus the invocation of infinite
| numbers of bits of information.
|
| (Note that having a decision procedure to determine something,
| e.g., "here's the set of the primes", is a _finite_ number of
| bits, and in fact, not even a very large number of them. The set
| of the primes is completely computable. It may not be
| "efficiently" computable but it completely computable. It's not
| just "infinite sets" in general that cause the issue I complain
| about in general. The axiom of choice specifically invokes
| infinite numbers of _bits_ , if not uncountably infinite numbers
| of bits, out of the ether.)
|
| Now, does that make it "invalid"? No. As the article says, it's
| an axiom, it is what it is. And I don't go to the extreme of
| tossing it out and completely going to the belief that
| constructivism is the only valid mathematics. I just am nowhere
| near _as_ comfortable with it as mathematicians in general are.
| hgsgm wrote:
| AoC is a hacky shortcut. It gives right answers when it is
| supposed to, and wrong answers when they don't care.
|
| (Most, non-constructivist) Mathematicians are comfortable with
| it, because they don't _care_ that it contradicts physical
| reality, as long as it doesn 't contradict _itself_. They aren
| 't physicists.
|
| On the flip side, physics don't care about being mathematically
| correct, as long their errors approximate reality.
|
| "comfort" isn't really useful here. You say you don't toss it
| out, so what does your discomfort mean? Is there some result
| you refuse to believe? Or do you simply prefer to study non-AoC
| math? I like algebra. That doesn't mean I'm not "comfortable"
| with geometry existing.
| karpierz wrote:
| Where is infinite information invoked?
| jerf wrote:
| The Axiom of Choice is that I can have an infinite number of
| sets and I can "choose" a value from each of them. A choice
| from a set is basically what a bit is (give or take the
| question of probabilistic weighting of the values in the set,
| which is important in the finite case but can't save you in
| this case so it's a distraction here). Invoking the Axiom of
| Choice, which is only interesting in the infinite case, is
| injecting an infinite number of bits into the proof that uses
| it, as it involves an infinite number of choices.
|
| At best the invocation has an acceptance procedure, but it
| does not come with a procedure for making the choice.
| Probably in most cases it doesn't even have an acceptance
| procedure, which is to say, if we were presented with the
| choices (or a finite subset of them, since we can't handle
| the infinite set) we couldn't even tell if they are
| "correct". So it is not the case that it's just like the
| primes case, which I mentioned is distinctly finite in bits
| even if the set is infinite in cardinality. The Axiom of
| Choice is an infinite (even uncountably infinite or more)
| number of selections with no way given of representing that
| in any finite manner. In many cases the Axiom of Choice is
| invoked when we can't even define the sets we are choosing
| from, if not most or all of them.
|
| So, from my computer science, information theory point of
| view, proofs involving the Axiom of Choice are proceeding
| along nicely, finite statement here, finite statement there,
| finite logic done on these finite statements, everything's
| all nice and finite and comprehensible and then _BANG_ an
| infinite number of unknownable bits are dumped on me, and
| then we proceed along like nothing weird has happened and do
| some more finite logic on finite values based on this
| infinite pile of unknownable bits. It is what it is, but what
| it is is strange. I mean, it 's not news to mathematicians
| that it can be a bit strange, but I think this "infinite
| number of bits" is one of the _better_ ways to see how
| strange it is.
|
| Another way to look at it is, the AoC is generally invoked
| without even a theoretical decision procedure to make the
| choices. It just has a demonstration that such a choice
| exists. So it amounts to "and then god chooses a value in
| these sets for us in accordance to our criteria". Lowercase
| on purpose. A more conventional term in computer science is
| "oracle". Every invocation of the AoC is basically adding
| this mathematical entity of such incredible power that we
| can't determine anything about how it does its thing, or
| whether or not it is correct. Again. Legal. But something I
| think is taken more casually than I would like, and I think
| doing mathematics without scattering infinitely knowledgeable
| (if only in very constrained ways) and powerful oracles
| around everywhere with the same casualness as one might do a
| disjunction or implication in all our proofs is
| underrespected as a discipline within mathematics in general.
| karpierz wrote:
| Let's see if I can clear this up:
|
| An equivalent way to phrase the Axiom of Choice is: there
| exists a function that takes in any non-empty set, and
| returns an element of that set.
|
| IE, this exists: choose a :: NonEmptySet a -> a
|
| That's it. All of this stuff about "take a choice from a
| countable number (IE, list) of sets" is fluff; once you
| have choose, you can make a function that takes in an
| Iterator (NonEmptySet a) and produces (NonEmptySet a), such
| that the output will contain every element.
|
| oneFromEachSet :: Iterator (NonEmptySet a) -> NonEmptySet a
|
| oneFromEachSet iter = NonEmptySet (choose (first iter)) <>
| (oneFromEachSet (rest iter))
|
| Where '<>' is set union.
|
| Does that fix your issue with an "infinite" number of
| choices? Or do you take issue with assuming 'choose'
| exists, now that it's a single function?
| jsmith45 wrote:
| From a programmatic viewpoint that would be describing
| the axiom of countable choice, since such recursion can
| only occur countably infinite number of times.
|
| Even if we ignore that by allowing for syntax where we
| fanout uncountably many times with each recursion, the
| construction as shown requires the collection of sets to
| be orderable, to be able to do have a "first", unless we
| are implementing first in terms of choose itself.
| (Alternatively one could also argue in terms of Axiom of
| Choice implying the well-ordering theorem, allowing up to
| pick a minimum via some such ordering (although you may
| need to use the choice function to pick one such
| ordering), but this won't fully help here anyway).
|
| But even if you do that (implement iterator's first in
| terms of choose) it is not immediately obvious that you
| really have covered everything some full statements of
| the axiom of choice does. The axiom of choice is
| generally phased in terms of collections or families of
| sets, not sets of sets, but obviously the choose function
| takes in a set, not a more general family or collection.
|
| It is easy enough to dismiss away certainly non-set
| collections of sets, like multisets of sets, since
| "choose" being a function will return the same value
| every time from a repeated input, and in the above
| formulation we are returning a set of results, so such
| duplicates won't matter. We could even handwave away a
| version where we return a multiset without too much
| trouble.
|
| But the more expansive versions of the axiom of choice
| allow us to do something like "choose one element from
| each set in the class of non-empty sets." This is a real
| problem, as the "class of non-empty sets" is pretty well
| known to not be a set, and thus trying to implement
| iterator first in terms of it would not even be possible
| for that scenario.
| karpierz wrote:
| "First" in this case was just getting the first element
| of the iterator, it wasn't related to choosing a value
| from the set.
|
| The Axiom of Choice is equivalent to the following:
|
| 1) "For any set A, there exists a function from non-empty
| elements of the power set of A to elements of A."
|
| Which is equivalent to:
|
| 2) "There exists a function that takes a non-empty set as
| input, and returns an element of that set"
|
| 2 -> 1, since we can take the function 2 defines, and use
| it to define the function from 1.
|
| 1 -> 2 since we can define 2 as such:
|
| For a set A, take the power set of A. Then take the
| function that 1 claims exists. Use that function to get
| an element of A, since A is an element of its power set.
|
| But back to your core point:
|
| But I agree that Iterator is a bad fit for the axiom of
| choice, since we have an (uncountable) number of sets to
| pick from.
|
| Here's a way to phrase it programmatically that allows
| for uncountable sets-of-sets:
|
| The axiom of choice claims that given a set of non-empty
| sets, you can construct a new set which contains an
| element from each of the sets.
|
| pickOneFromEach :: Set (NonEmptySet a) -> NonEmptySet a
|
| If you have a function:
|
| choose :: NonEmptySet a -> a
|
| And a function:
|
| map :: (a -> b) -> Set a -> Set b
|
| then you can define pickOneFromEach as follows:
|
| pickOneFromEach setOfSets = map choose setOfSets
| [deleted]
| otikik wrote:
| You can say:
|
| "The first number that can't be described using a finite number
| of symbols"
|
| But then you have just used a finite number of symbols to
| describe it, haven't you?
| karpierz wrote:
| This assumes your numbers are well ordered (IE, any set of
| numbers has a "first"), which is called Zorn's Lemma. It's
| equivalent to the axiom of choice.
| WastingMyTime89 wrote:
| You can't say that unambiguously, no. You haven't defined a
| well order which would allow you to talk about a first element
| (well, smallest).
| psychoslave wrote:
| Saying something doesn't imply saying something about a
| denotable entity.
| IngoBlechschmid wrote:
| You do not need to worry about the axiom of choice because:
|
| (1) Provably so in a very weak (and hence trustworthy)
| metatheory, assuming the axiom of choice does not result in any
| new inconsistencies. More precisely: The systems ZFC (Zermelo-
| Fraenkel set theory with the axiom of choice) and ZF (ZFC but
| without choice) are equiconsistent; if ZF is consistent, then so
| is ZFC.
|
| (2) There is a mechanical procedure for transforming ZFC-proofs
| of number-theoretic statements into ZF-proofs. That is, appeals
| to the axiom of choice can always be mechanically eliminated from
| proofs of number-theoretic statements, even if those proofs rely
| on results in other areas which crucially depend on the axiom of
| choice.
|
| You should worry about the axiom of choice because:
|
| (3) Assuming the axiom of choice imposes an undue restriction on
| the scope of your results: Any theorem proven without the axiom
| of choice and without the law of excluded middle (which is
| implied by the axiom of choice) automatically also applies to
| continuous families. For instance, the theorem "every real
| symmetric matrix has an eigenvalue" has a proof avoiding AC and
| LEM. Hence it also holds that for every continuous family of
| symmetric matrices, locally on the parameter space, there is a
| continuous eigenvalue-picking function.
|
| PS: One could also wonder whether one should worry about the law
| of excluded middle. One should not because: (1') The systems ZF
| and IZF (ZF but without LEM) are equiconsistent. (2') There is a
| mechanical procedure for transforming ZF-proofs of number-
| theoretic statements of the special kind "for every numer x,
| there exists a number y such that some equation holds" into IZF-
| proofs. On the other hand, one should worry because of (3).
|
| PPS: The axiom which one should truly worry about is the
| inconspicuous powerset axiom. In contrast with ZFC, ZF and IZF,
| which are all equiconsistent, removing the powerset axiom results
| in a drastically weaker system. The proof-theoretic strength of
| Kripke-Platek set theory (ZF without powerset) is a reasonably
| large ordinal, whereas we are lacking the technology to even
| fathom the ordinal calibrating the strength of IZF/ZF/ZFC.
| hackandthink wrote:
| I am confused:
|
| "From a proof-theoretic perspective, Heyting's calculus is a
| restriction of classical logic in which the law of excluded
| middle and double negation elimination have been removed" (1)
|
| "Intuitionistic logic can be understood as a weakening of
| classical logic, meaning that it is more conservative in what
| it allows a reasoner to infer" (1)
|
| How is this compatible with:
|
| "The systems ZF and IZF (ZF but without LEM) are
| equiconsistent." ?
|
| (1) https://en.wikipedia.org/wiki/Intuitionistic_logic
|
| Seems to be quite subtle (proof theoretic strength and
| consistency strength)
|
| (2)
| https://mathoverflow.net/questions/126002/interpretability-a...
| librexpr wrote:
| You might want to check out the Godel-Gentzen negative
| translation[0], which is an interpretation of classical logic
| in intuitionistic logic, which can be (somewhat inaccurately)
| summarized as "if P is provable in classical logic, then not
| not P is provable in intuitionistic logic".
|
| [0] https://en.wikipedia.org/wiki/G%C3%B6del%E2%80%93Gentzen_
| neg...
| drdeca wrote:
| I think "equiconsistent" just means that (one can prove that)
| if one is consistent, then the other is also consistent.
|
| Doesn't mean the collections of things they can prove can't
| differ.
|
| For a weak example, aiui, a formal system is equiconsistent
| with any conservative extension of it, but the conservative
| extension can (in the cases one would usually speak of) prove
| some statements that aren't in the language of the original
| system.
| hackandthink wrote:
| Thanks, I'm not confused anymore.
| zaroth wrote:
| You can't say you can't chose an item from a set because you
| can't describe the item.
|
| If it is sufficiently impossible to describe the number, how did
| it get _in_ the set.
|
| Irrational numbers are not impossible to identify symbolically,
| so if you stuff them in a bag and ask me to pick one, I'll just
| take sqrt(2) thanks.
| vintermann wrote:
| > If it is sufficiently impossible to describe the number, how
| did it get in the set.
|
| It got added along with infinitely many others!
|
| That's the thing, it's no problem dealing with "hairy" reals as
| long as you deal with infinitely many of them at a time. You
| can say, "all the numbers between zero and one", and the fact
| that it will include numbers whose decimal expansion can't be
| described by any rule shouldn't cause any trouble.
|
| But if I ask you, "show me _one_ of these numbers whose decimal
| expansion can 't be described by any rule", then by definition,
| you can't.
| hgsgm wrote:
| How did God create universe?
|
| Does your (non) answer imply that Universe doesn't exist?
| quchen wrote:
| > You can't say you can't chose an item from a set because you
| can't describe the item.
|
| Or rather: the whole point of the axiom is giving you such a
| description.
| heinrichhartman wrote:
| The axiom of choices is about picking elements of infinitely many
| sets at once.
|
| In the example we are talking about a single set. The deduction
| "the set is non-empty => we can pick an element" is much more
| basic than AC.
| nhatcher wrote:
| Yeah, that is not the axiom of choice and even if it were their
| conclusion is not correct. You can't characterize a set as non
| being described by finite symbols.
|
| On the other hand, it's always refreshing to see someone
| pushing us to think in this constructs.
|
| Logic is hard!
| lheck wrote:
| True. It's always good to see someone thinking about math
| concepts in critical ways to understand them. But this post
| doesn't really have a place here on hacker news as it's just
| born of faulty premises and of misunderstanding what the Axiom
| of Choice states.
|
| The actual HARD PART about the axiom of choice is that the
| thing f that picks from the collection of sets to its elements
| that has to exist must be a function. The axiom of choice does
| not have any reference to f being "described using any finite
| collection of symbols", or "computable". f must not be
| computable or graspable or describable, these are not
| constraints put onto f by the Axiom of Choice. But it must be a
| function!
|
| Why is "being a function" a constraint for f at all? Not
| everything that goes from set A to set B is a function.
| Functions have to be able to be described in terms of sets, and
| not every collection of items is a set. The notion that every
| collection is a set is called naive set theory, and it does not
| work (see Russel's paradox). This is the hard part about the
| axiom of choice.
|
| So if someone invokes some argument over complex concepts about
| computability, or being stateable, that's not even true of
| stuff outside of the Axiom of Choice and definitely not why
| specifically the AoC is hard.
| quchen wrote:
| Thanks for pointing out that the _f must be a function_ part
| is particularly difficult. Is this only a problem for
| infinite sets (of sets to pick from)? Is it trivial to
| construct a function that picks a single element from an
| arbitrary set that's not ordered numbers (say, the real
| endomorphisms)?
| bell-cot wrote:
| Reaction: "Intuition" works about as well with the Axiom of
| Choice as it does with brain surgery, nuclear physics, and rocket
| science.
| [deleted]
| bmitc wrote:
| The axiom of choice is not a definition or theorem or problem. It
| is an axiom. You either take it or leave it.
| auggierose wrote:
| > 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.
|
| But there are uncountably many finite collections of symbols.
| Sorry, you will have to take the axiom of choice out of my dead
| cold hands. Banach-Tarski just tells us if we use un-measurable
| sets, they don't have much to do with our understanding of
| physical space. But that's fine, because sets are just
| collections, and physical space is undoubtedly more than that.
| lisper wrote:
| > there are uncountably many finite collections of symbols
|
| Only if there are uncountably many symbols. But this is a fair
| point. I'll need to define what I mean by "symbol" more
| clearly.
| karpierz wrote:
| There are countably many finite collections of symbols.
|
| There are uncountably many countable collections of symbols.
|
| Edit:
|
| The above is true if your symbols are countable. If they are
| uncountable, then obviously there are uncountable finite sets
| of your symbols (As the singleton sets are a subset, and those
| are uncountable).
| sebzim4500 wrote:
| >But there are uncountably many finite collections of symbols
|
| How do you mean? Because there are uncountably many symbols?
| I'm not really sure what a symbol means in this context.
| auggierose wrote:
| I just picked on one of the points in the post that make no
| sense without further explanation. Just take each real number
| as a symbol.
| davrosthedalek wrote:
| It's normally assumed that the number of symbols is finite.
| ceceron wrote:
| The number of symbols in the language may countable, but the
| number of sets of symbols will be indeed uncountable, i.e.
| AFAIR the number of sets of natural numbers is uncountable --
| you can even construct real numbers as sets on rational
| (still countable) numbers.
| [deleted]
| drdeca wrote:
| The set of all sets of natural numbers is uncountable, but
| the set of all _finite_ sets of natural numbers, is
| countable.
| ceceron wrote:
| True, that's why I haven't used 'finite' in my comment.
|
| Apparently I've missed that the parent referred to the
| finite collections and in fact was wrong making my
| previous comment misplaced. Thanks for pointing it out :)
| shellothere wrote:
| There are countably many finite strings of a fixed, finite
| collection of symbols. That's the point the author is making --
| it becomes more intuitively obvious that there might be trouble
| "choosing" when you design the set you'd like to choose from to
| consist solely of the "nameless" reals.
| drdeca wrote:
| There are uncountably many _(countably) infinite_ collections
| of symbols from within a countably infinite set of possible
| symbols.
|
| The set of finite subsets of a countably infinite set, is
| countably infinite.
|
| There is a computable bijection between the set of natural
| numbers and the set of finite sequences of natural numbers.
| BeetleB wrote:
| > But there are uncountably many finite collections of symbols.
|
| As others have pointed out, that depends on how big the set of
| possible symptoms are.
|
| If the set is finite, then there are a countable number of
| finite collections (the countable union of countable sets is
| still countable).
|
| If the set is countably infinite, then there are still
| countably many _finite_ collections.[1]
|
| If the set is uncountably infinite, then you're right. However,
| the author is probably talking about all symbols known to
| humanity, which clearly is not only not uncountable, but it is
| finite.
|
| [1] https://math.stackexchange.com/questions/200389/show-that-
| th...
| jonathanstrange wrote:
| I don't think we could talk about numbers that cannot be
| described by finitely many symbols (let alone a countably
| infinite number of symbols).
___________________________________________________________________
(page generated 2023-01-23 23:02 UTC)