5 ms·

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

by hsn915 5y ago

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 5y ago
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 5y ago
  What's wrong with just choosing a random set element?
tel 5y ago
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 5y ago
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 5y ago
  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 5y ago
    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).
rssoconnor 5y ago
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.

by hsn915 5y ago

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 5y ago

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 5y ago
What's wrong with just choosing a random set element?

tel 5y ago

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 5y ago

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 5y ago
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 5y ago
  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).

rssoconnor 5y ago

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.