[HN Gopher] What is the Axiom of Choice?
___________________________________________________________________
What is the Axiom of Choice?
Author : luu
Score : 162 points
Date : 2021-07-14 18:18 UTC (2 days ago)
(HTM) web link (jaydaigle.net)
(TXT) w3m dump (jaydaigle.net)
| bvoq wrote:
| Really good article.
|
| > You don't have to explain how you're choosing elements. We'll
| just assume you can make it work somehow.
|
| Very interesting remark. The way I think about it now after
| reading your article is: If you prove something with the axiom of
| choice, all you need to do is provide an ordering to get
| practical results from it. If you fail to do so, _oh well_.
|
| That being said, I don't think you need R (the reals) for
| practical applications, countably infinite sets like IQ
| (intervals over Q) are enough and the well-ordering rule doesn't
| seem paradoxical anymore (countably infinite sets can be ordered
| as there is a bijection to N).
|
| Example: Pi can be approximated arbitrarily close with a lower
| and upper bound on Q. The functions used to derive the lower and
| upper bound with arbitrary precision (also a number in Q) are Pi
| in this sense
| iammisc wrote:
| Interesting article... The derivative problem is particularly
| enlightening I think. A derivative is a limit. Thus the answer
| you get for a derivative is also a limit.
|
| For example, if you have the real speed of a car at every point
| in time as well as the position, then nominally, in infinite
| world, the speed is just the derivative of the position curve.
|
| But if you are in finite world, then the derivative curve in
| infinite world is the limit of the speed curve (and note that
| limit does not mean upper bound).. it just is a useful tool for
| reasoning what will happen if you take a more fine grained set of
| measurements.
|
| For some fineness of measurement, there will be a point at which
| your observed speed curve is always within epsilon of the ideal
| one.
|
| Good article
| antonzabirko wrote:
| > Let's assume there is a first person in the line, so it's not
| infinite in both directions; you have infinitely many people in
| front of you, but only finitely many behind
|
| Is this even possible? One of the premises in the article. Won't
| it be infinity backwards for the nth person?
| magneticnorth wrote:
| They're just describing a set of people you could consider
| ordered by positive integers. The first person has no one
| behind them, the nth person has n-1 people behind them
| antonzabirko wrote:
| But how can that hold when you're approaching infinity? It
| would only apply to sets finite in both directions.
| magneticnorth wrote:
| The natural numbers (positive integers) are the numbers 1,
| 2, 3 , 4, 5, ....
|
| The "..." signifies that there are infinitely many such
| numbers, so there is no largest natural number but there is
| a smallest (1 is smallest). In that sense it is infinite in
| only one direction - written here it is infinite to the
| right but has an end at the left.
|
| Nothing special happens as you "approach infinity" and in
| fact that's not a thing you can do. No matter how high you
| count, you have only have counted finitely many numbers and
| there are an infinite set more that you have not counted.
| antonzabirko wrote:
| ok thanks
| dwheeler wrote:
| It's interesting to look at how people have handled the axiom of
| choice in Metamath, since the axiom of choice has long had some
| controversy.
|
| Metamath lets you state your axioms, then show that proofs build
| from their axioms. Each such collection of axioms & proofs is
| called a "database". There are Metamath databases that build on
| intuitionistic logic <http://us.metamath.org/ileuni/mmil.html>
| and New Foundations <http://us.metamath.org/nfeuni/mmnf.html>
| among others.
|
| The largest Metamath database by far uses ZFC (Zermelo-Fraenkel
| Set Theory with the Axiom of Choice). That's the Metamath Proof
| Exporer (MPE) database:
| <http://us.metamath.org/mpeuni/mmset.html>. But even in that
| database, it's avoided where possible. Its conventions say, "We
| prefer proofs that depend on fewer and/or weaker axioms, even if
| the proofs are longer. In particular, we prefer proofs that do
| not use the axiom of choice where such proofs can be found. The
| axiom of choice is widely accepted, and ZFC is the most commonly-
| accepted fundamental set of axioms for mathematics. However,
| there have been and still are some lingering controversies about
| the Axiom of Choice. Therefore, where a proof does not require
| the axiom of choice, we prefer that proof instead. E.g., our
| proof of the Schroeder-Bernstein Theorem (sbth) does not use the
| axiom of choice. In some cases, the weaker axiom of countable
| choice (ax-cc) or axiom of dependent choice (ax-dc) can be used
| instead." <http://us.metamath.org/mpeuni/conventions.html>
| CompMan411 wrote:
| Veritasium describes a similar situation (not the AOC); a hotel
| that has infinite rooms and what happens when an infinite number
| of buses each with an infinite number of guests pulls up.
|
| https://youtu.be/OxGsU8oIWjY
| twic wrote:
| > So here are a few things that don't cause controversy:
|
| > * If we have one set, we can definitely pick an element from
| it.
|
| Can we? How?
|
| The point of a set is that it doesn't distinguish between its
| elements in any way. It's not ordered, there is no special
| element, etc. So how can you pick one element from a set?
|
| If you pick a total ordering over the elements in the set, then
| you can easily pick the smallest, or largest. But that's not
| picking an element from a set, it's picking an element from a
| specific ordering of that set! You can't do that without coming
| up with an actual ordering!
|
| Is picking an element from a single finite set something you can
| build using ZF? Or is it another, less controversial, axiom? What
| do constructivists think about this? Is there a flavour of
| mathematics where this axiom is not assumed? What are the
| consequences of that?
| [deleted]
| nnamtr wrote:
| All formulas and statements are expressed in first-order logic.
| It has no such phrase as "pick". But picking (in the axiom of
| choice) means: Finding a function that maps every set to an
| element of this set.
|
| What is a function: It's a set of tuples where every tuple (x,
| y) means: x is mapped to y. Of course there must be exactly one
| tuple for every "x".
|
| (Tuples btw are usually a short notion for {{x}, {x,y}}. They
| exist always by the axiom of pairing. By the axiom of
| extensionalty, they fulfill the universal property of pairs,
| i.e. (x, y) = (z, w) iff x = z and y = w.)
|
| Assume x is a single nonempty set. Picking means: Finding a
| function {x} -> x. But this is easy: [?]y(y[?]x) because x is
| nonempty, and then we can build our function, which consists
| just of the single tuple (x, y).
|
| It also works for finite sets of sets since you can do it
| manually n times, the formula just gets longer.
| twic wrote:
| Okay so if x is {potato, tomato}, what is the tuple for x,
| and how did you decide that?
| ambulancechaser wrote:
| A tuple (ordered pair commonly called) is `(x,y)`. The
| standard set theory definition underpinning this is that
| `(x,y)` is shorthand for the set of two elements `{ {x},
| {x, y} }`. Where the "first coordinate" is the set with one
| element, and the "second coordinate" is the element in the
| set with two items that is not in the set with one item.
|
| It's a standard definition that means we can talk about
| ordered pairs but still ground it in set theory.
| siraben wrote:
| > Is picking an element from a single finite set something you
| can build using ZF?
|
| In ZF it's tautological by the axiom of regularity[0]. If you
| have a non-empty set X, there is an element y such that y [?] X
| and X and y are disjoint.
|
| [0] https://en.wikipedia.org/wiki/Axiom_of_regularity
| twic wrote:
| It seems to me that there is a huge difference between "a set
| X must have an element y" and "given a set X, you can get an
| element y".
|
| If set theorists do not make that distinction, then that is
| the answer to my question!
| l33t2328 wrote:
| What do you mean "you can get"?
|
| Being precise is especially important in math.
| ceh123 wrote:
| _I think the commenter means that just because you know
| an element with a certain property is in the set, we can
| 't conclude that there is a way to "choose" such an
| element. All we know is there exists at least one of
| these elements, there could be one (in which case we have
| a choice function that is well defined, choose the one
| element that satisfies the property) or there could be
| infinitely many such elements and we're stuck back at the
| beginning to construct a choice function._
|
| Edit: I think the above might be wrong actually, I
| haven't had a proper set theory course yet but it looks
| like "existential instantiation" [0] is what allows you
| to "choose" the element here (possibly?) but this sits
| within the logic that proceeds ZF set theory.
|
| Also see [1] for a decent discussion on AOC for finite
| sets.
|
| [0]
| https://en.wikipedia.org/wiki/Existential_instantiation
| [1] https://math.stackexchange.com/questions/132717/do-
| we-need-t...
| edflsafoiewq wrote:
| Constructively, a proof that a set is inhabited is exactly an
| element of that set, so if we know the set is inhabited we can
| just pick that element.
|
| OTOH, if we only know the set is non-empty we cannot pick an
| element from it. Because assume we could. Let P be a truth
| value and let S={x in {1} | P}. From not not P, prove S is non-
| empty, so by assumption we can pick an element of it, so it is
| inhabited. If it is inhabited, then P. We've just proved P from
| not not P.
| bschne wrote:
| I know next to nothing about set theory, but. If you have a
| single set, you must know its elements or some rule that
| defines its elements. You can then just pick an arbitrary
| element that is part of the set at will and let that be your
| choice.
|
| Since it's just one set and not a collection of sets, you don't
| need some general rule that will give you a well-defined
| element from each set in your collection.
|
| Am I missing something?
| twic wrote:
| But _how_ do you pick that one element? Remember, a set does
| not distinguish between its elements. So if you 're going to
| pick one, you need to introduce some method to do that. Do
| mathematicians consider "just pick an arbitrary element"
| sufficient?
|
| If so, why can't you do that to fully order any set? Just
| pick an arbitrary element - that's the smallest one. Now take
| the original set minus that element, and repeat. Bingo, an
| ordering!
|
| Maybe you can? Maybe it's only infinite sets where this
| doesn't work?
| veltas wrote:
| I think you can already pick an element.
|
| But what does it mean to pick an element infinitely many
| times? You have to be very careful about your assumptions
| there, an inductive proof would only prove you can pick an
| arbitrarily large number of such elements. To say that you
| can make a set picking one element each from a infinite
| collection of sets, even countably infinite, is something you
| cannot prove inductively. It requires another axiom.
|
| And admitting this axiom suddenly paradoxes like Banach-
| Tarski are possible.
| bschne wrote:
| Yes but as I read it, the parent comment was not asking
| about that, but about whether we could even assume we could
| pick from a single set.
| veltas wrote:
| You're right, sorry.
| dandanua wrote:
| The example of equivalence classes of sequences from the
| article (in the problem with hats) is very demonstrative. If
| I give you a class somehow - how are you gonna pick an
| element from it?
| skissane wrote:
| Let me give a more concrete example. Take the set of
| uncomputable real numbers. You can write out a formal
| definition of that set, you can prove that it is infinite and
| uncountable. But you can't produce any element of it. So you
| can't actually pick an arbitrary element of it, since you
| can't know what any of the elements are. Is there even any
| general rule you can use to pick out a single element? - you
| can't pick the smallest or largest element, since for every
| element there will be a smaller or larger one; nor can you
| pick the element closest to zero, since for every element
| there will be one closer to zero, and zero itself is not an
| element.
|
| I suppose, if one had a Turing machine with an oracle for the
| halting problem, it could produce some elements of this set.
| And then you could ask, what is the shortest program which
| generates an element of this set. And then if you had
| multiple shortest programs, you could order them
| lexicographically. So that's a way you could pick out a
| single element in principle, even though it is impossible in
| practice.
|
| Another example would be the set of numbers that are first-
| order undefinable. (Meaning, numbers for which there does not
| exist any sentence in first-order logic which is true only
| for that number). There is no way using first-order logic to
| pick out a unique element of that set. But I suppose there is
| some number which is second-order definable but not first-
| order definable, and hence we could use a sentence of second
| order logic to uniquely locate a member of the set of first-
| order undefinable numbers.
|
| As a generalisation - you can define a set such that you
| can't pick out any individual member of it _using certain
| resources_. But it seems like there is always some way to
| pick out a unique member of such a set using more resources
| (a higher Turing degree, higher order logic, etc). Can you
| define a set so you can 't pick out an individual member of
| it no matter how much resources you use? I think the answer
| to that is "no".
| ColinWright wrote:
| Less comprehensive, more specific:
|
| https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...
|
| Also submitted as a separate item:
|
| https://news.ycombinator.com/item?id=27855143
|
| Broadly (and as this article explains), AC says that given _any_
| collection of non-empty sets, you 're allowed to "choose" a set
| that contains one thing from each of them. In set theory terms,
| the "product" of non-empty sets is non-empty.
|
| This has some uncomfortable consequences.
| [deleted]
| nixpulvis wrote:
| Best quote so far:
|
| > If we have infinitely many pairs of shoes we don't need the
| axiom of choice, since we can just take the left shoe from each
| pair; but if we have infinitely many pairs of socks, we do need
| the axiom of choice.
|
| - Bertrand Russell
|
| So randomness seems like a good fit for "choice" here, no? Or
| maybe call it ambivalence, or indifference. If the objects are
| truly unidentifiable, can it possibly matter which one you
| choose?
|
| As the argument surely goes...
| siraben wrote:
| > So randomness seems like a good fit for "choice" here, no?
|
| The axiom of choice is exactly the thing that tells us that we
| can make "random" choices. The way set theory works is that you
| have axioms to talk about intuitions of sets. So you might say
| that such a reasonable intuition is that we can make "make
| unlimited random choices", but this is exactly the axiom of
| choice!
|
| It's not about a choice from an infinity but an infinity of
| choices.
| patrickthebold wrote:
| My favorite quote:
|
| > The Axiom of Choice is obviously true, the well-ordering
| principle obviously false, and who can tell about Zorn's lemma?
|
| [1]https://en.wikipedia.org/wiki/Jerry_L._Bona#Quotes
| Ostrogodsky wrote:
| I have always thought that Mr Russell is wrong with that cheeky
| quote. With the socks you also dont need the AOC. Why? because
| if you have a pair of identical socks (I think that was what
| Russell had in mind) then effectively you have a set of
| cardinality 1.If the socks are different, choose the lightest,
| if there is a tie between them choose the longest, and so on,if
| for all the tests the socks are tied declare them the same and
| back to point 1.
|
| This is my preferred quote about the AOC:
|
| > The Axiom of Choice is obviously true, the well-ordering
| principle obviously false, and who can tell about Zorn's lemma?
|
| Jerry Bona. https://en.wikipedia.org/wiki/Jerry_L._Bona
| naveen99 wrote:
| Atoms are able to select which indistinguishable electrons will
| fill the lowest energy orbitals.
| nixpulvis wrote:
| Or might this imply that the electrons are actually
| distinguishable in some way? Or maybe I should re-phrase;
| could each electron actually have some (possibly hidden)
| identity?
| naveen99 wrote:
| Also if the universe is infinite, is it the one with or
| without axiom of choice ?
|
| Can you always pick the center of each universe in a
| universe of infinite universes ? Any point can be the
| center, you just need to pick one.
| nixpulvis wrote:
| I'm sorry if this is a stupid question... but what on
| earth is the center of the universe? Must there even be
| such a concept? If the universe is truly infinite, I
| would think that implies it can be both expanding and
| centerless at the same time.
| dsr_ wrote:
| A circle has a center which is a point in that circle
| such that the distance(s) from the center to every point
| on the boundary of the circle is the same. The center is
| within the space of the circle but not on the boundary.
|
| A sphere has a center which is in that sphere but not on
| the surface (boundary) of the sphere.
|
| A 4-sphere has a center which is in that hypersphere but
| not in the volume boundary of the hypersphere.
|
| ...
|
| It is entirely possible that the universe is a 3s1t shape
| which is part of the boundary of an NsNt shape, and there
| is a center to it which is not usefully accessible -- or
| even discoverable -- from anywhere in the universe.
| nixpulvis wrote:
| Ah yes, the center of the universe is obviously an
| inaccessible real point. I actually really like this
| idea.
|
| Still centerless seems like it could carry less baggage
| and be just as "correct", but IDK.
| handrous wrote:
| > Or might this imply that the electrons are actually
| distinguishable in some way?
|
| I mean... they're not in exactly the same position and
| state at exactly the same time, no? That would seem to
| distinguish them.
| nixpulvis wrote:
| Position of an electron is actually not quite the same as
| position of a rock or bouncy ball. I've heard it
| described as an electron "cloud".
| handrous wrote:
| OK, but does that affect my point? I didn't delve into
| that because it seemed irrelevant.
| nixpulvis wrote:
| I'm not really qualified to go into this, but maybe read
| a little bit about the Pauli-Exclusion Principle works. I
| get the feeling that might be illuminating.
| comicjk wrote:
| I don't think they do. The electrons are indistinguishable -
| there is no "which" and no need for selection.
| shadowgovt wrote:
| It can definitely matter---if I mutate one of the socks and the
| mutation doesn't show up on the other, I've got a problem if
| I'm assuming equivalence is equality.
|
| I suspect that's key to why the axiom of choice has to be an
| axiom (and how this may pop up from time-to-time in the realm
| of computer science problems).
| nixpulvis wrote:
| How can _you_ mutate it if _you_ can 't select it?
| shadowgovt wrote:
| Something I'm unclear on is whether the axiom of choice
| implies determinism.
|
| if it does, then "I select one at random." That could be
| accomplishable without a guarantee that I can tell you how
| to select (in finite time) the same element I selected.
| jodrellblank wrote:
| Why can't we take the left sock from each pair?
| bmm6o wrote:
| Because there isn't a left/ right distinction with socks.
| jodrellblank wrote:
| I have never considered that there might not be a
| distinction, it always seems to me that the heels are
| different at least. Feet are different, shoes are
| different, so why would socks not also be shaped for the
| feet and mirrored left/right in the same way?
|
| Turns out, it depends which socks you buy - there are makes
| which are different, and ones which aren't. examples at
| https://www.quora.com/Is-there-a-left-and-right-sock-in-a-
| pa... including toe-socks but not limited to them.
| lmm wrote:
| The original statement of the axiom I heard was "it's possible
| to make an infinite number of _arbitrary_ choices " - I think
| that's a good word for what you're getting at. Of course it
| doesn't matter which you choose - the axiom doesn't tell you
| anything about which you can choose - but whether you _can_
| choose at all is important. E.g. Hilbert 's basis theorem
| relies on the idea that given an infinite-dimensional space you
| can always "start somewhere" - it doesn't matter specifically
| where, but it matters that you can pick a specific point in the
| space to start from.
|
| (The first journal he submitted it to rejected the paper with
| the comment "this is not mathematics, this is theology")
| nixpulvis wrote:
| The axiom of arbitrarity has an interesting ring to it...
| slightly avoiding the theological connotation, while being a
| bit bleak.
|
| Anyway, I hope they gave him a Ph.D for that comment, lolol.
|
| Oh and yikes, did Hilbert just bring roots of polynomials
| into the mix?
| exmadscientist wrote:
| My favourite statement of the Axiom of Choice, from AlienAtSystem
| via https://www.irregularwebcomic.net/4035.html :
|
| > As there are infinitely many sets, instead of going through
| them manually, you have to find an algorithm [to select an item
| from each set]. So Person A tells the other player an algorithm
| to select an element. Then that other player finds a set where
| the algorithm fails.
|
| > If you, for example say: "Take the smallest element", then I
| say "One of my sets is all negative integers, it doesn't have a
| smallest element."
|
| > Then maybe you say: "Take the smallest element, or if it does
| not have that, take the largest." Then I say "One of my sets is
| all integers, which has neither". Then maybe you add: "If it has
| neither, take the element closest to 0 (in case of tie, take the
| larger one)". Then I say: "What about the set of all integers and
| all their reciprocals? It doesn't have an element closest to 0
| either."
|
| > When Person A gives up and says: "Look, there's _some_
| algorithm that does it, right, why do I have to recite it
| manually? ", then that person has taken the Axiom of Choice. If
| they say "Okay, fine, you win, there's no algorithm you can't
| find a counterexample to", then that person rejects the Axiom of
| Choice.
| jleahy wrote:
| Is that not the axiom of finite choice, which holds in ZF set
| theory without AC?
| lupire wrote:
| How is it finite? Integers are infinite.
|
| It's Countable Choice, and of course the essence of
| Countability (why it's our favorite cardinality) is that
| almost all of our intuition about finite numbers can be
| correctly applied to countable infinities.
|
| Uncountable Choice (a set for every Real number, a choice
| from every set) is where thing ago off the rails and ZF looks
| substantially different from ZFC.
| oscardssmith wrote:
| Can't you get countable choice with zf? Countable means
| there is a bijection to the naturals, so you can always
| pick the element that corresponds with 0.
| ubercow13 wrote:
| How do you choose the bijection?
| kmill wrote:
| No:
| https://en.wikipedia.org/wiki/Axiom_of_countable_choice
| [deleted]
| YetAnotherNick wrote:
| For (any subset of)rational numbers there exist many simple
| algorithms to form an ordering. eg. Take the number is reduced
| for `(+/-)a/b`. A number is smaller if its `a+b` is smaller. In
| case of tie number is smaller if its `a` is smaller. Even in
| case of tie positive number is smaller.
|
| I don't know the proof but there could be no algorithm like
| that for real numbers.
| wizzwizz4 wrote:
| $<$ gives an ordering over the reals. It's an ordering with a
| _first element_ that 's the tricky bit.
| richardwhiuk wrote:
| I think in the last example, you need "the set of all integers,
| except 0, and all their reciprocals", otherwise the answer is
| well-defined.
| eeegnu wrote:
| One of the many reasons for defining the natural numbers to
| begin at 1. I didn't even notice they said integers and
| thought they said naturals.
| coldtea wrote:
| > _If you, for example say: "Take the smallest element", then I
| say "One of my sets is all negative integers, it doesn't have a
| smallest element."_
|
| Why would a set of "negative numbers" not have a smallest
| element?
|
| Negative numbers are also ordered in a number line (-5 is
| smaller than -2 for example).
| Filligree wrote:
| It's the set of _all_ negative numbers. That doesn 't have a
| smallest number, because negative infinity is not a number.
| coldtea wrote:
| This makes sense. I read the set being "all negative
| numbers" in the sense of a set of numbers all of which are
| negative, not in the sense "the set that has every negative
| number".
| nixpulvis wrote:
| [3] (from OP) directly contradicts this, though I am also
| very confused why real numbers are somehow unorderable,
| while the integers are not.
| https://jaydaigle.net/blog/what-is-the-axiom-of-
| choice/#fn:3
| jfengel wrote:
| It's not just about ordering, but well-ordering. Which
| says not just that you can put them in order, but that
| you can put them in order with a first element (one
| that's always less than all of the others).
|
| So you can have a set like "all real numbers greater than
| 0". It doesn't have an obvious first element, even though
| you can always compare any two numbers and say "this one
| is less than that one".
|
| There may be a non-obvious first element, i.e. some
| strategy for picking a first element that applies to all
| sets. That's the Well-Ordering Principle. Which feels
| false to most mathematicians, but it's equivalent to the
| Axiom of Choice, which feels true.
| joppy wrote:
| The set of positive integers starts {1, 2, 3, ...} and
| there are no positive integers smaller than 1. On the
| other hand the set of positive real numbers has no
| smallest element, since for any positive real number x,
| the number x/2 is smaller and still a positive real. It's
| not that the reals are unorderable (they are most
| certainly ordered), it's that certain subsets of the
| reals do not necessarily contain a minimum/maximum.
| Sharlin wrote:
| How does it contradict that? The set of negative integers
| does not have a least element, and neither does the set
| of negative reals. (But the former does have a greatest
| element (-1) while the latter doesn't have that, either.)
| nanis wrote:
| > why real numbers are somehow unorderable
|
| They are orderable ... For all x, y in R, either x >= y
| or x < y.
|
| But R is not bounded (no inf, sup) and therefore has no
| minimum and no maximum.
| threatofrain wrote:
| What's the consequence of extending the reals with
| infinities, as my textbook for real analysis does?
| rocqua wrote:
| That every closed set has a maximum and a minimum.
|
| Relatedly, every set gets a supremum and an infumum. (The
| first two must be members of the set. The second two can
| lie outside the set).
|
| Without the extension, you need to make an exception for
| unbounded sets with the above rules.
| nixpulvis wrote:
| Oh dear, I dropped the critical word "positive" from this
| in my reading. My bad.
| pron wrote:
| > ... then that person rejects the Axiom of Choice.
|
| You're looking at it from a philosophical perspective where
| people care about whether the axiom is "true" or not. Other
| approaches to mathematics don't care, because they view its
| value not in some metaphysical notion of truth but in utility.
| They might say: this proof requires the axiom of choice and
| that proof doesn't, without assigning either one any value
| beyond utility (where utility might be, in some case, just
| their intellectual edification). I think this is what the
| article is trying to drive at as well. We can't "accept" or
| "reject" the axiom of choice based on some philosophical
| grounds, because those philosophical grounds would need to
| involve infinities [1], which, themselves, are not
| philosophical but mathematical. We either choose to use it or
| not based not on where we come from but on where we want to go.
|
| [1]: The view that mathematical philosophy could be derived
| from core basic principles outside of mathematics was called
| Logicism, and was favoured by Bertrand Russell. Unfortunately,
| mathematical systems without some mathematical (i.e.
| non-"logical") axioms are quite limited, and almost all of them
| include at least one mathematical axiom, usually one that is
| equivalent to the existence of the natural numbers.
| cannabis_sam wrote:
| >they view its value not in some metaphysical notion of truth
| but in utility.
|
| Isn't this a philosophical perspective?
| pron wrote:
| It is a perspective in the philosophy of mathematics that
| rejects the idea that all of mathematics is necessarily
| anchored in philosophical truths beyond itself.
| cannabis_sam wrote:
| > It is a perspective in the philosophy of mathematics
|
| So it is a philosophical perspective...?
| pron wrote:
| Of course. I think you may have misread my original
| comment, which compared two philosophical perspectives on
| mathematics, one philosophical perspective that views
| mathematics as an expression of some truth beyond
| mathematics, and another philosophical perspective that
| sees mathematics as a tool to achieve some ends.
| cannabis_sam wrote:
| > not in some metaphysical notion of truth but in
| utility.
|
| So one is not metaphysical because it is a tool to
| achieve ends?
|
| (Sorry, if I come across as argumentative, I don't mean
| to. I'm genuinely just curious.)
| pron wrote:
| For some reason you keep skipping the qualifiers in what
| I write. It does not say "some metaphysical notion" but
| "some metaphysical notion _of truth_ ". In other words,
| what matters isn't whether an axiom is "true" or not in
| some way that is external to mathematics, but what use
| could be made of that axiom. You did the same above; I
| didn't write "from a philosophical perspective" but "from
| a philosophical perspective _where_ ... "
| jfengel wrote:
| It is a metaphysical statement about whether metaphysics
| is important in this instant, rather than being dispensed
| with in favor of something useful. It's picking a
| particular metaphysics rather than being bogged down in
| the meta-metaphysical question of the necessity of
| metaphysics.
|
| Or at least, that's the way I read it. The question of
| the value of metaphysics is an open one, which easily
| comes to dominate other questions if allowed to. I think
| the OP is saying, "I'm going to make a metaphysical
| commitment, and let other people worry about whether
| doing so is good metaphysics." (And there's good reason
| to think that it isn't -- but it's unclear whether that
| matters, or should matter.)
| eeegnu wrote:
| > Unfortunately, mathematical systems without some
| mathematical (i.e. non-"logical") axioms are quite limited
|
| What's an example without any axioms? It doesn't seem like
| you can do anything without say [?]x: x=x (which I believe is
| reciprocal identity.)
| shadowlight wrote:
| The algorithm that executes an element from the set of all
| algorithms one at a time until an algorithm succeeds to select
| an element from a set will work on any set and itself?
| a = the algorithm A = set of all selection algorithms
| b = any set def a(x): while True:
| f = a(A) # you have to select an algorithm from the set of
| selection algorithms result = f(x)
| if result is None: A = A - f # set of all
| selection algorithms without f continue
| else: return result a(b) #will
| always return a result or not terminate for any choice of b?
|
| Obviously there's problems with this because I'm not a
| mathematician and I'm just making stuff up off the top of my
| head. But would any one who's an expert care to explain what's
| the issue with the above?
|
| I'm looking at it and such an algorithm is defined in terms of
| itself (like a factorial, which is legal) and may never
| terminate (which also legal because an algorithm selecting the
| smallest number from all sets that only contain positive
| numbers will never terminate either).
|
| Wait but then if you look at the code it provably will never
| terminate because A does not shrink as it recurses.
| Avshalom wrote:
| if the set of all selection algorithms is infinite you need
| the axiom of choice to guarantee that you can even select an
| algorithm from it.
| tshaddox wrote:
| Can't the algorithms be enumerated? For example, you could
| take their source code and sort them alphabetically.
| shadowlight wrote:
| This is the weird fuzzy part with math.
|
| I can say arbitrary stuff like the set of all sets with
| positive numbers but when I say the set of all algorithms
| written in English and C++ suddenly I'm getting too
| specific. Where is the line drawn?
| tshaddox wrote:
| I'm not sure what you mean. There's nothing too specific
| about that.
| shadowlight wrote:
| Your assuming all algorithms are defined in terms of
| English that's how you can order them alphabetically.
| English is an arbitrary language that comes from human
| culture. Same with a programming language. You are
| defining a set in terms of concepts that are cultural.
|
| Algorithms themselves have no specific order. In order to
| define enumeration you must first start off by
| *selecting* which algorithm gets the first enumeration.
| This is a completely arbitrary choice.
| tshaddox wrote:
| No, I'm not assuming any particular encoding of an
| algorithm. I'm just assuming by "algorithm" you mean a
| computable function, and we know there are only countably
| many computable functions. This is not a cultural notion.
|
| And yes, which _particular_ encoding you decide to use is
| arbitrary, but the point is that you _can_ enumerate the
| set of all algorithms, and thus you can select one
| without needing the axiom of choice.
| shadowlight wrote:
| Your own example used the word "alphabetical." So your
| example is false because it uses a "particular" encoding.
|
| Try to select an algorithm out of the set of all
| algorithms without using an encoding. If you must use an
| encoding, please ensure that it's not a "particular"
| encoding.
|
| You can't.
|
| The point is all encodings in the known universe are
| "particular."
|
| Additionally, to even use an encoding you have to
| *select* and encoding from the set of all encodings.
| tshaddox wrote:
| Yes, I chose one arbitrary method of enumeration. That's
| not important to the point, which is that algorithms are
| enumerable and thus you don't need the axiom of choice to
| select one out of the set of all algorithms.
| shadowlight wrote:
| Yeah I think that's the problem.
| rocqua wrote:
| I think that such an algorithm, if the order of algorirthms
| tried is random, is almost surely (so with probability 1)
| never going to terminate.
|
| Moreover, you'd probably want to limit the tries to
| algorithms that terminate. But that brings you into the
| halting problem.
| openasocket wrote:
| You can run a countably infinite sequence of algorithms in
| parallel and stop when one of them terminates without
| running into the halting problem. Say you have a set of
| algorithms, numbered 1, 2, 3, ... and each algorithm
| consists of a sequence of instructions (with jumps and
| gotos), where each instruction takes a finite amount of
| time to run. The algorithm is as follows: run the first
| instruction for algorithm 1, then the next instruction for
| algorithm 1, then the instruction for algorithm 2, then 1
| again, then 2, then 3, then 1, 2, 3, and 4, and you can see
| the pattern now. If any of them reaches the halt
| instruction halt. Even if all but one of these algorithms
| runs forever, you'll still eventually halt when that one
| algorithm completes. I believe this approach is called dove
| tailing
| shadowlight wrote:
| Can you iterate through a set without * selection *? I'm
| confused about this part. It seems to me in order to use
| an algorithm from the set of all algorithms you need to
| invoke the axiom itself.
|
| I think us programmers think in terms of time. But in
| math there is no time so whether you do things in
| parallel or procedural is irrelevant. That's why you can
| discuss infinities in math.
| openasocket wrote:
| > It seems to me in order to use an algorithm from the
| set of all algorithms you need to invoke the axiom
| itself.
|
| Nope, you don't need the axiom of choice to define the
| sequence of all algorithms. The axiom of choice allows
| you to order any arbitrary set, but you don't need it for
| things you can construct an explicit order for, like the
| natural numbers. In the case of all algorithms, it's
| somewhat straightforward to construct the set of all of
| them. You can construct the sequence of all strings,
| right? You can construct them as "", "a", "b", "c", ...
| "y", "z", "aa", "ab", ... "ay", "az", "ba", "bb", ...
| Now, pick a programming language, like C. Given any valid
| string, you can determine if it is a valid C program in
| finite time, and if so you can convert it into a set of
| instructions to use in the dove-tailing procedure in
| finite time. Take the list of all strings in the manner
| described above. For each one interpret it as a C
| program, or if it's got invalid syntax interpret it as a
| program that immediately halts. Now you've got an
| enumerable sequence of algorithms. Since C is Turing
| complete you'll find every single algorithm in that
| sequence. There will be a ton of duplicates (for whatever
| notion of equivalence you want to use) but all the
| algorithms will be there, and in a well-defined order
| that you can enumerate through.
| ketralnis wrote:
| The assertion that at least one selection algorithm succeeds
| without presenting that algorithm _is_ the axiom of choice.
|
| By _assuming_ that program terminates, you are yourself
| taking the axiom of choice.
|
| If it _does_ terminate, then it's not an axiom anymore it's a
| proof.
| shadowlight wrote:
| Yeah, this clarifies the logic. So because the algo above
| doesn't terminate it is not a proof.
|
| The axiom of choice is an assumption that is neither known
| to be true or false.
| jaydaigle wrote:
| ketralnis is right that this only terminates if an algorithm
| exists, so the claim that this terminates is equivalent to
| the axiom of choice.
|
| But I'd also add that you can have a choice function that
| isn't an "algorithm". An algorithm, at least in the sense I'd
| generally interpret the word, has finitely many instructions
| and at most countably many steps. If we have uncountably
| infinitely many uncountably infinite sets, it is possible to
| have a choice function that can't be described in a finite
| algorithm.
|
| Like, think about a well-ordering of the reals. If you
| believe the axiom of choice, then one exists. But you can't
| tell me what it is, because that would involve handing me
| infinite amounts of information. And similarly you can't
| write down an algorithm to produce it, without writing down
| infinite amounts of data.
| shadowlight wrote:
| So to simplify basically the algorithm I wrote above is bad
| because it's in spirit equivalent to this:
| def a(x): return a(x)
| ASalazarMX wrote:
| Instructions for a Banach-Tarski theorem demo:
|
| 1. Find any solid object.
|
| 2. Divide that object in infinite, dimensionless fragments.
|
| 3. Make as many copies as you want with the infinite fragments.
|
| 4. Reform the original object with the remaining fragments.
|
| ... I still have fragments please help.
| ColinWright wrote:
| I assume you're joking, but in case anyone thinks your
| description is accurate, it's wrong in a significant way.
|
| Point (2) is fundamentally wrong in a critical way. The whole
| point of the Banach-Tarski Theorem is that you only have
| finitely many pieces. Of course these pieces are composed of
| infinitely many points, but it's a finite number of "pieces".
|
| Others may find it amusing, sense of humour vary widely.
| Usually I just shrug and move on, but in the essence of this
| "joke" you've genuinely misrepresented _the entire point._
| ASalazarMX wrote:
| I tried to joke about how real objects don't have an
| infinite number of surface points.
|
| This theorem is often quoted as "mathematically-proven way
| to deconstruct a sphere and build two identical spheres",
| but this can't translate to reality in any way, it's an
| abstract thought exercise. Of course, "mathematically-
| proven way to deconstruct a sphere and build two identical
| spheres in your imagination" doesn't sound as cool.
| ColinWright wrote:
| For anyone still following, the theorem is perhaps best
| described like this:
|
| We model spheres as collections of points, and given a
| collection of points there is a fairly obvious way to
| model the idea of moving that collection around in a way
| that reflects moving a physical object. The problem is,
| given a sphere, we can partition the points into six
| sets, move those sets around, and recombine them to give
| us two spheres the same size as the initial one. In a
| very real sense, in this model we can "cut up" a sphere,
| then rearrange the pieces to make two spheres. We've
| doubled our volume.
|
| Clearly this is nonsense, and it shows the limitations of
| the model. But equally, it tells us something important
| about the maths we use every day to model buildings,
| bridges, fluid flow, and more.
|
| All models are wrong, some models are useful. -- George
| E. P. Box
|
| I would add:
|
| Some things are nonsense, but sometimes the nonsense can
| tell us useful things about the way the models are wrong.
| PaulHoule wrote:
| I don't believe it.
|
| Steve Wolfram should grow some balls and say he doesn't believe
| it either.
| soVeryTired wrote:
| I don't think it's a question of 'belief'. AOC is logically
| independent of the other ZF axioms: you may find it
| aesthetically ugly (a viewpoint I'm sympathetic to). But you
| can't disbelieve it any more than you can disbelieve Euclid's
| parallel postulate.
| naveen99 wrote:
| Interestingly politicians (like AOC) are also independent of
| logic.
| PaulHoule wrote:
| But I don't have to use it, or I can deprecate it.
|
| Particularly I think those "real" numbers are phony compared
| to the integers and rationals. (At least the latter have
| names)
| threatofrain wrote:
| Here's a professor of math in some Australian university
| who has pursued a philosophy of mathematics while basically
| rejecting infinities, axiom of choice, and reals.
|
| https://www.youtube.com/watch?v=U75S_ZvnWNk
| siraben wrote:
| Somewhat not well known among all mathematical circles, but
| Diaconescu's theorem states that the law of the excluded middle
| follows from the axiom of choice[0]. This means if you wish to
| work in constructive mathematics (which has great overlap with
| computer science), not only you must not take LEM as given but
| also not take choice as given.
|
| There is much to say--mathematically, computationally and
| philosophically--on the axiom of choice and its variants
| (countable choice, dependent choice) and subtle interactions with
| other axioms.[1][2][3]
|
| From my experience most mathematicians accept the axiom of choice
| (or an equivalent statement such as Zorn's lemma[4][5] or
| Teichmuller-Tukey[6]) because of its pervasiveness and usefulness
| in many areas of math, such as completeness of first-order logic,
| existence of a basis of any vector space, showing products of
| compact topological spaces are compact, and more.
|
| [0] Diaconescu's theorem
| https://en.wikipedia.org/wiki/Diaconescu%27s_theorem
|
| [1] Exposition of choice, LEM, etc. in Coq
| http://adam.chlipala.net/cpdt/html/Universes.html
|
| [2] Choice vs. countable choice
| https://mathoverflow.net/questions/22990/choice-vs-countable...
|
| [3] Martin-Lof on choice
| https://raw.githubusercontent.com/michaelt/martin-lof/master...
|
| [4] Zorn's lemma https://en.wikipedia.org/wiki/Zorn%27s_lemma
|
| [5] How to use Zorn's lemma
| https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lem...
|
| [6] Teichmuller-Tukey lemma
| https://en.wikipedia.org/wiki/Teichm%C3%BCller%E2%80%93Tukey...
| veltas wrote:
| Why does AoC implying LEM mean you can't use LEM in
| constructive maths?
|
| EDIT: misread
| siraben wrote:
| I said that if you don't want to use LEM in constructive
| maths you must also give up AOC, since AOC -> LEM.
| veltas wrote:
| Oh right. Also hi siraben didn't notice it was you.
| siraben wrote:
| Hello! Nice to see another IRCer :)
| reuben364 wrote:
| Constructive mathematics by it's nature does not use LEM. The
| idea is that proof of existance must be done by construction
| of the object in question. LEM implies DNE, which means
| existance can be shown by showing non-existance is not the
| case.
|
| EDIT: Apologies, misunderstood.
| jerf wrote:
| Unsurprisingly, I'm biased in the direction of the Computer
| Science flavor of mathematics, which leads me to say: Of course
| the Axiom of Choice is _useful_. Why _wouldn 't_ an axiom that
| allows you to wave your hand and produce infinite amounts of
| information that you have no mechanism to produce any of be
| _useful_? Of course it 's useful to invoke infinite amounts of
| information from thin air. Indeed, uncountably infinite amounts
| of information, or any aleph-X you please amounts of
| information.
|
| I agree and understand that it's not a matter of "right" or
| "wrong", but I do find myself looking a bit askance at "proofs"
| of statements in which a mathematician writes the equivalent of
| a few kilobytes of proof statements (in a suitable encoding),
| which has to be paired with an infinite number of unknowable
| bits, which the mathematician is not only incapable of
| providing in practice but often incapable of providing even in
| _theory_ , to be "true". Mathematicians often claim to find the
| axiom aesthetic; I find it to be quite the contrary. When you
| look at proofs from an information-theoretic point of view, the
| Axiom of Choice is literally an infinitely-sized wart on the
| side of any proof that uses it.
| myWindoonn wrote:
| Confused about this. Isn't the comp-sci perspective to use
| the effective topos and computable partial functions? In that
| case, LEM fails and so must AOC; instead, we have Markov's
| Principle.
| jerf wrote:
| I mean a computer science perspective on the Axiom of
| Choice itself.
|
| While I am naturally much more sympathetic to
| intuitionistic/constructible mathematics than the general
| math community is, I won't go so far as to insist it is the
| only one true math, since I don't think there is such a
| thing. I just think that from an information theoretic
| perspective, calling the instantiation of infinite
| unknowable amounts of information into a proof "aesthetic"
| is, well, not a term I'd use. I find Axiom of Choice
| generally gross.
| lalaithion wrote:
| This isn't necessarily true; you can also limit which sets
| are valid sets in a way that guarantees that choosing an
| element from these sets is well defined. For example, the
| Axiom of Constructibility basically limits which sets exist,
| in a way that allows you to always use the Axiom of Choice
| because your sets have a specific fine grained structure you
| can use to well-order them.
|
| For example, if I were to require "all sets are finite", then
| the Axiom of Choice is trivial. The Axiom of Constructibility
| still allows infinite sets (and even uncountable sets), but
| it's still limited enough that the Axiom of Choice holds.
|
| You can almost think of it as requiring all sets to have
| source code, and then just alphabetizing the source code in
| order to pick a set.
| jerf wrote:
| Yes, it's true that you can use the Axiom of Choice in ways
| that don't invoke infinite information, and yes, those
| would be OK with me from an aesthetic point of view. (Again
| let me emphasize my complaint here is not that it is
| "invalid" but that I find it very _unaesthetic_ , contra
| many conventional mathematicians.) But things like the
| Banach-Tarski paradox definitely require infinite amounts
| of information (uncountable infinite in this case, I
| believe) with, as far as I know, no mechanism for producing
| it. As far as I know, it's just an existence proof.
|
| When discussing hypothetical FTL technologies, I often like
| to say that it's no great surprise that if you allow one
| impossibility (negative mass) it's no surprise that you get
| another (FTL). Similarly, if you allow an uncountably
| infinite amount of information to be magicked into your
| proof, it's no surprising that you may get a confusing
| result like the Banach-Tarski paradox. From my perspective,
| the confusing step isn't when you have two spheres where
| you used to have one, the confusing step is when you made
| uncountably-infinitely-precise cuts with no ability to
| produce the cuts in question. I'm not confused by the end
| result, I'm confused at that step. So to speak. I'm not
| literally confused, obviously, only my sense of aesthetics
| is.
| mxwsn wrote:
| I am not a fan of the axiom of choice, and open-minded about
| truth values beyond true and false. So I'm really curious about
| the progress of constructive mathematics, regarding proving
| known results with non-ZNF axioms, and maybe establishing some
| more "intuitively satisfying" (whatever that may mean) results
| where ZNF gives subjectively bogus results like Banach-Tarski?
| The_suffocated wrote:
| Is the existence of basis in every vector space really useful?
| I think in analysis, people mostly work with Schauder basis
| rather than Hamel basis. I am not aware of any important result
| that uses the existence of Hamel basis in an infinite-
| dimensional vector space. This is not a criticism about your
| comment, but an honest question.
| dandanua wrote:
| To me, the Axiom of Choice is absolutely natural - if we can pick
| one element of a set then we surely can pick elements from a
| collection of sets, who cares that this collection can be
| infinite.
|
| The problem with this axiom is that it can't be formally proven
| from ZF axioms. But there are a lot of other natural things that
| can't be proven in ZF. For example, the consistency of ZF can't
| be proven in ZF due to Godel's incompleteness.
| xiaodai wrote:
| What's yellow and equivalent to the Axiom of Choice? Zorn's lemon
| einpoklum wrote:
| What is the axiom of choice... hmm... maybe a way to claim
| legitimacy for the recent spate of US presidents?
| shadowgovt wrote:
| Is there a missing "deterministically" in the axiom of choice
| statement?
|
| I can imagine the common-sense "Of course you can choose one
| element" assumption breaks down if we add the constraint that you
| need to in some way be able to have another actor choose the same
| element. Because for an uncountably-infinite-sized set of
| uncountably-infinite-sized sets, perhaps there is no way to label
| individual elements such that if I choose A, someone else can
| also choose A (how will we know they're the same A?).
| thethimble wrote:
| Ah this is super helpful. I'm here stuck thinking "just pick
| any element at random". Needing to have deterministically
| consistent pickings from infinite sets makes the problem clear
| and much more interesting.
| shadowgovt wrote:
| I think that's why the "infinite socks vs. infinite shoes"
| are mentioned---because the socks are equivalent so you can't
| tell by the 'label' which one you grabbed.
| dkarl wrote:
| The article leans pretty hard on the hat problem to show that the
| Axiom of Choice has intuitively unacceptable consequences, but I
| don't see why the solution is so "ridiculous," as they put it.
| Here's one "intuitive" way of looking at the problem: every
| person in the line sees an infinite number of hats in front of
| them, but not the finite number behind them. Intuitively, they
| see 100% of the information in the problem. The amount of
| information each of them can see is infinite, and the amount they
| can't see is finite. Is it so strange then that they only make a
| finite number of wrong guesses, and an infinite number of correct
| ones?
|
| I think the article artfully uses a framing of the problem that
| hides the inherent, inexorable alienness of infinite sets under a
| familiar-seeming surface just long enough for it to come bursting
| out in the solution. It's a trick of timing. If your brain
| lingers on the problem long enough, you realize that the problem
| itself violates our ordinary intuitions, independent of the
| solution. The idea of an infinite number of people agreeing on
| and memorizing representative members of R^N from each
| equivalence class and then determining the relevant equivalence
| class by reading an infinite number of real numbers from an
| infinite number of hats is completely fantastical. How could any
| solution to this problem not be nuts?
|
| More to the point, if the problem is presented without a bonkers
| framing that already violates our intuition, is the solution from
| the Axiom of Choice still counterintuitive? I didn't find it to
| be so when I first encountered it in class. Maybe the
| intuitiveness depends entirely on the metaphor used to bring
| intuition to bear.
| rssoconnor wrote:
| To build upon the "Just relax" section: by Shoenfield's
| absoluteness theorem[1], if ZFC proves some Sigma^1_3 statement,
| then ZF also proves it. In particular, the Axiom of Choice has no
| arithmetic consequences, and thus has no effect on number theory,
| nor what you are able to prove about the correctness of any
| particular algorithm, etc.
|
| [1]
| https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_abso...
| jkhdigital wrote:
| > Similarly, if we could prove the axiom of choice from the ZF
| axioms, we would have to either accept it as true, or completely
| rework all the foundations of math.
|
| And the footnote following this statement:
|
| > At the beginning of the 20th century, Bertrand Russell and
| others found deep contradictions in the naive version of set
| theory in use at the time, and the ZF axioms were developed to
| avoid those problems. But we'd rather avoid doing it again.
|
| My understanding is that the "constructive" mathematicians
| objected strenuously to these proposed foundational "solutions".
| It's starting to look like they may have been on to something, as
| there is an ongoing effort (since 2013 at least) to recast the
| foundations in a manner that accommodates both traditional and
| intuitionistic approaches.
|
| Short anecdote to confirm that this might gain traction: I'm a
| comp sci PhD student (focus on cryptography) and just yesterday I
| met with a math professor to ask her to serve on my advising
| committee. I had some brief run-ins with Homotopy Type Theory
| (the proposed "new foundations") and was hoping she might be
| familiar with it--as it turns out, some of her own students had
| recently convinced her to start a weekly jam session where they
| gradually work through the HoTT textbook. She invited me to join
| them and I eagerly accepted :-)
| hebrox wrote:
| Is this [1] perhaps the book you'll work through?
|
| [1] https://homotopytypetheory.org/book/
| jkhdigital wrote:
| Yes, exactly. She actually had a physical copy of it
| pklausler wrote:
| Goodness, a mathematics hardcover for $21? I'm in!
| hsn915 wrote:
| Why is it only a problem when you have to choose from an infinite
| amount of sets? Why isn't the problem that you can get an
| infinite number of sets in the first place?
| Twisol wrote:
| If you allow yourself the infinite set of the natural numbers,
| you can pretty easily get an infinite set of sets. For
| instance, for every natural N, take the set of naturals less
| than N. Or greater than N, if you'd like an infinite set of
| infinite sets.
|
| As the article notes, these particular infinite families are
| easy to produce a choice function for: just take the least
| element of each set. But not all infinite families have enough
| determined structure for that kind of rule.
|
| If we tried to make it impossible to construct an infinite
| family of sets, we'd have to disallow relatively reasonable
| families like the ones I described above. Those are pretty
| useful, though, so it makes sense to address the problem
| further downstream.
|
| (I suppose another avenue is to try to isolate the features
| that make the above families "reasonable" and others
| unreasonable, so that only reasonable families can be
| constructed. That seems somewhat fraught, though.)
| hsn915 wrote:
| What's wrong with just choosing a random set element?
| rssoconnor wrote:
| If you have a finite number of non-empty sets you can construct
| a choice function by induction. Of course induction won't get
| you beyond a finite amount of sets.
| tel wrote:
| It happens regularly when, surprise, you deal with infinities
| in some other place.
|
| A good, fairly intuitive example is integration where, I think,
| it's common to prove convergence using AoC in the
| multidimensional case.
|
| More or less, you want to integrate a function over, say, a
| square. We'll do it with a generalization of the Riemann sum by
| arbitrarily dividing up that square into little squares,
| measuring the function at one place in each square, multiplying
| the areas by those measurements, and summing.
|
| Then we take that process to its infinite limit. We have to be
| smart here, but we end up with an infinite set of contiguous
| pieces of our original square. Or, an infinite set of sets.
| We'd like to measure our function once from each of those
| pieces, so we need to choose one point from each piece. Which
| is easily dispatched with AoC.
|
| (In 1-dimensional integration, each subdivision of the domain
| has a total ordering, so you don't necessarily need AoC.
| _Technically_ my example of a square also has a total ordering,
| so we could get away with not using AoC, but as you start to
| twist coordinates in the domain space more and more you can
| imagine places where seeking out an ordering of the space might
| be challenging. But no matter, AoC still works!)
| ColinWright wrote:
| Consider all the "real" numbers x that are in the range 0 <= x
| < 1. We can talk about what the real number are separately, but
| you can think of them as being infinite decimals starting with
| "zero point ...". We consider two decimals to represent the
| same number if one ends with all 9s and the other is identical
| except for the last non-nine number, and has "n+1" in that
| place, then all zeros. So these decimal sequences represent the
| same number: 0.35578439999999999999...
| 0.35578440000000000000...
|
| OK, now say that two of these numbers are _related,_ they are
| in the same _family,_ if their difference is a rational number.
| So these numbers are all related:
| 0.35578440000000000000... 0.45578440000000000000...
| 0.85578440000000000000... 0.35578233333333333333...
|
| ... and so on. These number are all in the same family. We can
| show that if _a_ is related to _b_ , and _b_ is related to _c_
| , then _a_ is related to _c_ ... being in the same family is
| _transitive._
|
| There are infinitely many families.
|
| Now suppose that there is a council meeting, and every family
| needs to send one representative. To do so you need to choose
| one number from each family, and it's not clear how to do that.
| I invite you to try to think of a rule that works for _all_
| families.
|
| So to choose one number from each family we need the Axiom of
| Choice.
| hsn915 wrote:
| I understand the idea that real numbers are uncountable
| infinite. (there's an infinite number of real numbers between
| any two random real numbers).
|
| My question is: why is it problematic only when you have to
| choose?
|
| I mean, what's wrong with choosing a random element from
| every set? Why do you need a rule?
|
| Where is the "problem"?
| ColinWright wrote:
| The axioms of ZF set theory don't let you say "Just choose
| one at random from each of these uncountable many sets." To
| simply "choose one at random" you need an axiom to say that
| you are allowed to do that.
|
| If it's only finitely many sets, finitely many choices,
| people are usually pretty happy with: "Well, choose one,
| then another, then another, and in a finite amount of time
| you'll be done, so that's OK."
|
| If it's countably many sets then many people are happy
| saying: "Well, choose your first one in an hour, then the
| next one in 1/2 an hour, then the next in 1/4 of an hour,
| and so on, and after 2 hours you'll have made all your
| choices, so that's OK."
|
| But with uncountably many sets neither of those works, and
| so you need an axiom to tell you that this is a permitted
| operation.
|
| BTW, it's a separate issue, but in your first line, the
| part in parentheses does not imply, and is not an
| explanation of, the first part. These statements:
| A: The reals are uncountably infinite; B:
| There's an infinite number of real numbers between any two
| random real numbers.
|
| These are largely unconnected. If you think otherwise then
| you might want to be a bit more careful and precise in your
| thinking. You might, of course, have simply mis-spoken
| yourself, in which case it's not a big deal.
|
| (To start you off, the second statement is true of the
| rationals, and of the algebraics, both of which are
| countable).
| hsn915 wrote:
| That doesn't answer the question though.
|
| I could understand the objection if one objected to the
| concept of infinity in the first place. Like "infinity is
| not real therefore any logical statement you make about
| it is non-sense".
|
| What I don't understand is the mindset that would accept
| to be presented with an infinite number of sets but then
| not accept that you can choose an element from each set,
| because "the procedure will never be done" or something
| like that.
| ColinWright wrote:
| I can present you with a definition that specifies an
| infinite set. If you ask for an element, I can give you
| one. If you present me with a thing, I can tell you if
| it's in the set. In a very real sense it is completely
| specified.
|
| Similarly defining an infinite collection of sets.
|
| However, if I have an uncountable collection of non-empty
| sets, sometimes you can tell me how to choose one from
| each (for example, if I have uncountably many pairs of
| shoes then you can just say "pick the left one"), but
| within the axioms of set theory, if all you know is that
| there are infinitely many non-empty sets, the ZF axioms
| don't allow you to declare that there is a function which
| when given one of the sets, returns to you an element
| from that set.
|
| Your statements seem to be saying "If you accept that
| there are infinite sets then you must accept that the
| Axiom of Choice is 'True'."
|
| That turns out not to be the case. There are sets of
| axioms that result in systems that have infinite sets but
| in which the Axiom of Choice is not 'True'.
|
| Perhaps I've mis-characterised your position.
___________________________________________________________________
(page generated 2021-07-16 23:03 UTC)