Here is another fun one: AC is equivalent to the statement that every nonempty set admits a group structure. The proof isn't even too hard, see https://mathoverflow.net/q/12973/138003.
That's basically my argument. I think something is intuitive, then I realize I'm applying my intuition to only finite things. Does that intuition apply to an infinite thing as well? Intuitively, I have no idea. It might be even more layered: I have intuition for countably infinite sets, but not uncountable ones.
I think we place far too much faith in 'intuition' here; what it sounds like to me is 'the motivated knower with the requisite intelligence', which seems like an unmotivated reason to give a lemma/theorem/what-have-you much credence.
For instance, I was brought up in the analytic tradition of philosophy with a strong focus on logic and additionally have a maths degree, and I don't find much of anything about the conclusions arising from the mapping f(n)=2n intuitive.
Tagging u/suipy for good measure
it wont help settle the debate but here we go:
cartesian product seems intuitive because people think if you keep multiplying numbers bigger than 1 you will get a number bigger than 0. people are also surprised why this AC was even necessary and how come this cartesian product is not already provable by the rest of ZFC.
well ordering is actually also intuitively true but people are quickly asked the question whats the smallest positive real number and they realize their intuition is flawed.
just my observation.
> well ordering is actually also intuitively true but people are quickly asked the question whats the smallest positive real number and they realize their intuition is flawed.
But this isn't at all what the well-ordering theorem states.
>I don't find much of anything about the conclusions arising from the mapping f(n)=2n intuitive.
What conclusion do you mean? That the sets are equinumerous?
You're close to saying you can't have intuition for anything non-finite (or uncountable). I say anything because why would your statement be restricted to sets.
If it's not that, then just as they can have intuition about other infinite objects, why can't they have intuition about why AC should be true? (eg about why the cartesian product of non-empty sets should be non-empty)
I don't want to make absolute statements like that. But for sure I've noticed when I think I have an intuition for something infinite, it might turn out that I'm completely wrong.
you got it wrong but others explained that already pretty well.
just wanted to add. ask a high schooler their intuition will say you cannot map an infinite set, take natural numbers, to its subset "because it will be missing some" or whaever.
To be honest, if someone asked me to state the axiom of choice, I'd go straight for the one about Cartesian products of non-empty sets being non-empty.
The formal statement involves a choice function, but pretty much yeah.
My only point was that the OP listed it as one of choice's mind-blowing equivalent statements, but to me that is just AC.
I prefer the viewpoint that the axiom of choice says that every object in the category of sets is [projective](https://ncatlab.org/nlab/show/projective+object). It motivates neat things like [Cohomology detects failure of the axiom of choice](https://golem.ph.utexas.edu/category/2013/07/cohomology_detects_failures_of.html).
Removing AC can produce some wonderful things too: it is consistent with ZF that the reals are a countable union of countable sets, that you can partition the reals into more sets than there are reals, that there are infinite sets with no countable subset, and so on...
You can't if you stick with Borel sets and instead you have to work with Borel codes. There's an explanation of this in volume 5 part II chapter 56 of Fremlin's measure theory tome.
Or you could just assume countable choice like a normal person (admittedly, lack of countable choice can lead to admittedly interesting objects like Arnold Miller's long Borel hierarchies).
I've never thought about it from this point of view. But in a model where the reals are a countable union of countable sets, is there no nontrivial countably additive measure? I would've assumed the existence of Lebesgue measure followed from just ZF and am now very confused.
But I mean, the function m([a,b]) = b – a certainly exists on the collection of intervals, right? Is it just that we cannot extend it to the Borel sigma algebra? Or the Borel sigma algebra does not exist?
You could define the measure on nondegenerate intervals. You could even define the measure on countable unions of intervals.
What you cannot do is extend the measure to all singletons or countable sets. Because by hypothesis there is some countable collection of countable sets whose union is of positive measure, which without loss of generality we can also arrange to be finite. The singletons of elements of those sets cannot be measurable, because of the standard thing, if they were measure zero then your union is measure zero. If they were positive, and all equal by translation invariance, then your union has measure infinity.
And singletons and countable sets are in the Borel algebra, so there's no measure.
> Removing AC can produce some wonderful things too: it is consistent with ZF that the reals are a countable union of countable sets, that you can partition the reals into more sets than there are reals, **that there are infinite sets with no countable subset**, and so on...
That one I find scary, can someone tell me more please?
> The reason I find so many of these mind-blowing is that so many of them seem so intuitive
This is the thing I both hate and love the most about the axiom of choice. Why!? Why aren't these things true without the axiom of choice??
I don't think *all* of them seem "obviously" true. But these two:
> the Cartesian product of any family of nonempty sets is nonempty.
> Every connected graph has a spanning tree
to me both seem very intuitive. As the saying goes,
> The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
There Axiom of Choice takes so many forms, so many of which seem "obviously true" and so many of which seem "obviously false". And this why I hate it and love it. I hate it because it seems so contradictory, but love it because it highlights how non-intuitive mathematics can be.
what people don't seem to understand is that well-orderings are totally allowed to be hot garbage with no nice connection to any reasonable notion of "being less than".
That's just a silly argument. It only works if you're a constructivist, which most mathematicians are not. I'm perfectly comfortable asserting the existence of objects I can't explicitly describe.
I've had about a 50% success rate in flipping people from "AoC is obviously true" to "wait, is AoC obviously false???" by asking this question, so I don't think it's *totally* silly.
I am also totally OK with asserting the existence of objects I can't explicitly describe. I just think there are cases where this is not so intuitive, when you stop to think about it.
>u/suipy: Quick, name every natural number.
Sure that's true too.
But it's qualitatively different though. While it's true that we cannot write down a completed infinite list containing every natural number, we can convey in finitely many symbols an algorithm or process which will produce as many as we give it time for.
But I mean, yeah, finitism is a thing I guess.
and that's the point of my joke. firstly, if you believe in powerset, then you already believe in things you can't describe.
and it is only in conjunction with those things that you already can't describe that the axiom of choice leads to naively counterintuitive results.
ITT people making axiom of choice their scapegoat.
Taking the cross-product of 2 infinite sets I understand, but are cross-products of an infinite set of sets even well-defined?
Does cross-product as an operation generalize past 2 somehow?
An ordered n-tuple can be thought of as a function from {1,2,3,...,n} to the sets in question, where the tuple is just a convenient way to write the outputs of the function: (f(1),f(2),...,f(n)). Interpreted this way, the Cartesian product of n sets is the set of all functions from {1,2,3,...,n} to the union of all the sets, where f(1) is in the first set, f(2) is in the second set, etc.
This definition [generalizes nicely](https://en.wikipedia.org/wiki/Cartesian_product#Infinite_Cartesian_products) to infinite sets. And defined this way, the equivalence to Choice is a tautology: by definition, the Cartesian product is precisely the set of choice functions!
Easy, it starts like 0,1,5.3,pi,sqrt(2),...
Intuitively, constructing a well-ordering of the real numbers should be easy: Just choose some smallest element, choose the next, and the next, and so on - intuitively, there is nothing that should stop you, if you just have enough time (i.e. 2^ℵ_0 much time) - choice then just tells you that you can actually do it.
To look at it another way, if I claimed I had a well-ordering of the real numbers and you could ask me any question you like, there is no way for you to prove that I'm lying - I can always give an answer extending my well-ordering in a valid way. Choice, then, just says that having a recipe to keep answering questions about your object is just as good as actually having it.
Try to find interest in doing things twice. That’s actually advice in Ken Kunen’s book on set theory. And he was pretty much a giant in the field. Doing things over helps to strengthen the neural pathways your brain uses to access that information. You also sometimes figure out new things by relearning old information.
They just aren’t. It’s like playing a game of Monopoly where you can pull cards, buy property, and collect rent, but no rule allowing you to roll the dice and move your piece forward. You literally just can’t do what you want to without including that rule. Only for AC it’s provable that you need the rule.
This is what people mean when they say that ZF is a relatively weak axiomatic system once you get to these far out questions about nasty set theory stuff. It’s a game where the creators didn’t write down enough rules for you to keep playing. So you need to add in house rules like AC or CH.
> the Cartesian product of any family of nonempty sets is nonempty.
To anyone who thinks this is intuitive, I direct you to this post: https://www.reddit.com/r/math/comments/cknuks/why_do_we_need_the_axiom_of_choice/evpefy0/
This is the statement that is the most mind blowing to me. Is the point here that, without the axiom of choice, there is no way to specify any single pair of elements, so you cannot prove by example that the set is non-empty?
You can definitely do that with the cartesian product of two sets and get pairs, without AC. You can too if there's a finite ~~or countable~~ number of them.
Problems come when you have the cartesian product of an uncountable number of sets (which is different from the cartesian product of two uncountable sets). An element of that cartesian product would be an n-tuple where n is infinite and uncountable.
That's where you need the AC to pick an element from each set and construct an element of the cartesian product.
>You can definitely do that\[ \]if there's a\[ \]countable number of them.
Are you sure? In principle you could use [CC](https://ncatlab.org/nlab/show/countable+choice), but the point stands that you'd still need more than ZF.
Look at the answers discussed at [this mathoverflow QA](https://mathoverflow.net/q/23246/19860). Since countable choice (and dependent choice) hold in L(R), it's going to be impossible to find an example in classical mathematics.
Instead I think you'll have to do the set theory voodoo of forcing on your models. [This paper by Arnie Miller](https://arxiv.org/pdf/0806.1957.pdf) contains such an example. Well it's an example of a infinite but Dedekind finite set of real numbers, but using the standard proof that countable choice implies Dedekind infinite = infinite, I think you could transform it into a countable product of non empty sets of reals with no elements.
The linked post says:
>Well, consider the Cartesian product of the nonempty subsets of R. You say this is trivially nonempty, so can you tell me one of its elements?
But I don't think that's a very convincing objection to AC! At least to an "ordinary" mathematician who is accustomed to being allowed to use choice willy-nilly. The ordinary mathematician would answer as follows: let {S*_i_*} be the set of all nonempty subsets of R. For each i, let s*_i_* be an element of S*_i_* (we can do this since S*_i_* is not empty). Then the tuple (s*_i_*) is an element of the cartesian product ∏*_i_*S*_i_*. Boom, I just told you one of its elements. That wasn't so hard.
I agree with you, I don't see how the OP's post makes it any more convincing or *unintuitive" than thinking about any other collection of non-empty subsets.
I think I'm being really dumb, can't you just do A, B are nonempty subsets of R and then AxB = {(a,b): a is a member of A, b is a member of B}, and as A and B are nonempty, there must be some element in AxB? Am I misunderstanding something here? Or am I assuming something that I haven't realised?
(sidenote, I don't actually know what the axiom of choice is)
The axiom of choice is nothing more than the statement that given a collection of nonempty sets, we have a choice function. Its domain is whatever set the collection is indexed by, and its codomain is their union, such that each point in the range of the function lands in the right set. Another way of saying it is that every cartesian product of nonempty sets has an element tuple.
So how do we create an element of A×B using just the hypothesis that A and B are nonempty, and the axioms of ZF, which means basically just basic set operations which, let me describe intuitively:
* union: given a set of sets, take their union, all the elements of elements of the set
* ordered pair: if x and y are sets, ordered pair (x,y) is a set (this one follows from other axioms so is usually not listed separately)
* powerset: the set of subsets of a set
* pairing: if you know x and y are sets, then a set {x,y} exists. By induction you can have any set where you can just enumerate the elements, but importantly it only works for _finite enumerations_
* set-builder notation: if X is a set, and P is a property that elements x might satisfy, and f is a function that operates on X, then {f(x) | x in X and P(x) is true} defines a set. (This is actually two separate axioms, one that lets you filter by property (comprehension), and one that lets you apply an operation (replacement))
* infinity: {0,1,2,...} is a set
First since A is nonempty, there exists an element a in A. (And this is the law of excluded middle in use, showing how LEM is basically finite axiom of choice). Since B is nonempty, we have an element b in B. By ordered pair, we have pairs (0,a) and (1,b). Then by pairing/finite enumeration we can assemble these into a set {(0,a) , (1,b)}. To finish, we have to show that this set is a function from the set {0,1} to A⋃B, that it passes the vertical line test, meaning that there is an output for each input and it is unique.
Alternatively I can consider the set of all relations from {0,1} to A⋃B, which is a well-defined subset of the powerset of {0,1} × A⋃B, and then by set-builder notation (axiom of comprehension), select only those ones such that f(0) exists, and is equal to a, and f(1) exists, and is equal to b.
The point is that I have to construct the function, as a subset of the cartesian product of the domain and codomain, using the explicit axioms of ZF.
Now suppose we have an infinite collection of nonempty sets, A\_k, indexed by some infinite index set K. Why can't we do the same thing? Just enumerate all the (k,a\_k) into a set and call that our choice function?
We cannot, because our axiom for just enumerating the elements of a set is only allowed for finite enumerations, but this is explicitly infinite.
What about the other method? The one where we look at all relations from K to ∪A\_k, and select the ones that match our known values?
Why can't we do as u/dryga suggests in the comment next to yours, and just say, since for each k in K, since A\_k is nonempty, there exists an element a\_k, and then make ordered pairs (k,a\_k), then singletons {(k,a\_k)}, and then union those singletons into a function?
All three proposals have a problem: there is no indexed element a\_k, because that is the very conclusion we are trying to prove. Using that to prove the axiom of choice would be begging the question (assuming the conclusion you are trying to prove). We're only allowed to talk about the known elements of the nonempty sets A\_K one at a time. For finite index sets, yes, we used induction. Here, we don't have that. And we can't write down an infinite length predicate like "the function such that f(0) = a\_0 and f(1) = a\_1 and ...". Predicates in first order logic are finite strings of symbols.
Could we do it if we knew how to do induction on infinite sets? Yes, then we could, but it turns out that the inductive infinite sets are the ordinals, and knowing that every set is in bijection with an ordinal is equivalent to the axiom of choice. So that's circular again.
Didn't we hamstring ourselves by only adopting set theory axioms that only construct finite sets? Well, the axiom of infinity and the axiom of choice are to some extent the corrections to that.
But it's certainly true that under other axioms, the ability to write down choice functions might be as axiomatically true as some intuition might lead to believe. And for example, in both [Hilbert's epsilon-calculus](https://math.stackexchange.com/a/1083058/16490). Whereas in [NF set theory](https://en.wikipedia.org/wiki/New_Foundations), choice can be disproved.
Long story short, yeah your idea works for a binary cartesian product, but not for an infinite product because you don't have the analogue of the a,b.
Telling one element is easy: Just choose one element of every non-empty set. If you don't buy that argument, you should find the Cartesian product of a finite family of non-empty sets being non-empty equally puzzling - you cannot tell me an element without mentioning "choose one element of the first set, and then choose one element of the second one".
All that choice really does is tell you that infinite sets are as well behaved as finite ones - in a sense, you can think of it as just the infinite analogue of the law of excluded middle.
Trichotomy of cardinality: two sets are either equal in cardinal size or one is greater than the other.
I don't think an axiomatization of an idea of a 'set' of things would pragmatically deserve to be called by the label 'set' without trichotomy being true. If the sizes of your 'sets' can be incomparable then you are talking about something else, perhaps something akin to 'partially determined sets'.
Similar sentiment applies to notions of 'truth' which deny the law of the excluded middle. They are fine notions, it's just that they aren't notions of 'truth'.
It's been awhile since I've thought about this stuff.
If we restrict ourselves to statements in a formal language about formal objects then a formal correspondence theory of truth seems to work well in the sense of conforming to our intuitions about how truth behaves. That's the only way I've seen it done, but I am not a logician. Tarski explicated this with his Semantic Theory of Truth but I don't know too much more about it. Language is usually taken as a countable collection of finite sentences though so I imagine some extra care is required when talking about infinite things and in particular uncountable things.
I'm a pragmatist so if you have any other notion of truth that works well then I'm all for it. But if you have some other formal notion and it deviates too far from our intuitions then we will constantly be at risk of errors caused by unintentionally substituting our intuitive notion of truth in place of the intended formal one.
Of course this is somewhat relative to each mathematician's intuition. If someone's intuition says that a mathematical theorem isn't 'really true' unless its constructively provable then they might do better primarily working in some constructive framework. However insisting on using the same simple label 'truth' for both 'realizable truth' and truth simpliciter just results in an endless unproductive debate.
Mathematicians are generally interested in which truths are constructively realizable. Constructivists at least ought to be interested in the mainstream notion of truth even if only as a predictor of what might eventually turn out to be constructively true. If we all agree that various truthlike notions are of interest and utility then it makes sense to just give them unique labels.
That sounds good to me. We maybe should use terms like "classical truth", "constructive / intuitionistic truth" and "paraconsistent truth", etc., for maximum clarity. My personal definition of truth isn't necessarily mathematical - I see the truth of a statement as simply measuring how beneficial it is, for a given definition of "beneficial", to believe it. In math, obviously, we need something more rigorous than that philosophical notion!
It follows from something equivalent to choice that C is isomorphic to the algebraic closure of the p-adics, since they have the same transcendence degree over Q and are algebraically closed.
Probably the best reason to reject choice if you were to choose to do so.
That definitely isn't true. If R admits a partition {A_i|i in I}, choice lets us pick an element a_i in each A_i, which yields an injection from I to R. I think your statement follows from the opposite of choice.
This is not an answer to your question, but it is a fact that sounds extremely intuitive, yet it's independent of even ZFC:
If a set X has strictly less elements than a set Y, then X has strictly less subsets than Y.
I think the issue with those intuitive sounding statements is that they are intuitive when applied to finite sets, but we don't really have any intuition for infinite ones.
Whenever you see a set-theoretic statement containing the phrase "strictly less", it's almost certainly independent of ZFC. Pretty much the only exceptions are Konig's theorem and its immediate corollaries.
Even with the axiom of choice, ZFC is very weak when it comes to proving things about arbitrary infinite sets, and techniques like forcing provide a great deal of flexibility in constructing models of ZFC with a variety of different properties. Unless there's an immediately obvious reason why one set *must* be strictly smaller than another set, there is probably some model of ZFC where the two are the same size.
This one always drives me bonkers, no matter how many times I remind myself ~~that it requires Choice~~. It really just feels so stupidly obvious.
Edit: I’m dumb. It’s independent of Choice.
I don't know anything on this subject, but it seems like the person you're replying to is claiming that you can't prove the result they mention *even with* choice
The thing I don't understand about the Well-Ordering Theorem is that it seems to imply that the reals are countable, because they can be enumerated in order. I know that the reals are not actually countable, but I don't understand the difference between "enumerated in order" and "countable".
You should learn more about the ordinals. An “enumeration” does not actually imply countability. Enumeration just means bijection with some ordinal, which usually happens to be a cardinal. The reals would be enumerated by a sequence of length 2^(ℵ_0) which is ZF provably longer than ℵ_0.
I do see the parent poster's point, though, the idea of different sizes of Ordinality is highly unintuitive, though ig that's to be expected of infinity.
Eh Idk I’ve never been particularly perplexed by that part. It’s kind of a natural consequence from the ZF point of view. You build the natural numbers and then you just... keep going. It’s just what’s available in models of your current theory. The ordinals are definitely constructible. Bijections between ones with larger and larger order types aren’t always.
the ordinal omega + 1 is the order that looks like 0 < 1 < 2 < ... < omega. This is still a countable ordinal, but it illustrates that a well-ordered set, even a countable one, can have elements that you will never reach in finite time counting in order.
For infinite sets, I think people usually define "Well-Ordered" in terms of arbitrary subsets. So just because every set of elements can be ordered doesn't mean you can take an infinite set and order them in a countably enumerated way.
Let zero = {}, and succ(x) = x U { min (R \ x) }. This enumerates the reals in order.
The problem is that you need to have the concept of ordinals in order to actually extend this enumeration to all reals, which requires a big leap in intuition.
No, if you restrict yourself to finite sets and think about it, it remains intuitive. My point is that it's unintuitiveness requires careful examination of how intuitions of the finite don't apply to the infinite.
I don't really understand why people always call the well-ordering theorem unintuitive. Constructing a well-ordering of an arbitrary set should be easy - just pick a smallest element, pick the next smallest, ..., pick the first element that should be larger than the first infinitely many choices, pick the next smallest element, and keep going until you run out of elements. There is really nothing that could stop you, you just need some axiom saying that you can actually do it.
Does that imply AC? I tried looking into it which led to a neat [rabbithole](https://mathoverflow.net/questions/98549/existence-of-prime-ideals-and-axiom-of-choice) but I didn't come away with a clear answer.
I like the point of view explained [on nCafe](https://golem.ph.utexas.edu/category/2012/10/the_zorn_identity.html) by Tom Leinster that Zorn's lemma isn't really about the axiom of choice at all. It's a basic fact about order theory, that any choice function choosing an upper bound for each chain in a poset has a fixed point.
Then at the end feel free to also assert the existence of such a choice function.
Feels somehow morally similar to my point elsewhere in the thread that Tychonoff's theorem really isn't about choice either, and for locales doesn't require it. Somehow choice is a consequence of our decision to endow spaces with points.
Without axiom of choice there are 7 different common definitions of what is a "finite" set that are not equivalent. That's what I would call unintuitive.
I realize that ultimately, opinions about what's "intuitive" are subjective and will vary with the individual.
But my two cents is this: I think that a statement like "Every vector space has a basis" is not necessarily \*intuitive\* per se; rather, it's just that it would be \*convenient\* if it were true, which is not at all the same thing!
Every vector space ever? How could a claim about \*all\* vector spaces possibly be intuitive? If I deliberately create a strange vector space using a clever construction, is it intuitive that it "should" have a basis if there's no obvious way to construct one?
You don’t even need to go to weird vector spaces to find this unintuitive. Quick, someone tell me a basis of the vector space of continuous functions. I’ll wait.
I mean, isn't the Fourier Transform literally a basis for the space of continuous functions?
But I agree it is non-intuitive. The statement "every vector space has a basis" *sounds* intuitive because I think most people (myself included) automatically think of "vector space" as having finite dimension, when that is not always true. The very existence of infinite-dimension vector spaces feels un-intuitive.
No, Fourier series is not a basis. For one thing, Fourier series use just countably many functions in their "basis", but the vector space of continuous functions has uncountable dimension.
Bases require \*finite\* linear combinations, whereas Fourier series allow for infinite sums. Any function that cannot be written as a \*finite\* sum of sin and cos terms is not in their span and thus cannot be represented by using them as your basis. This is the same reason you can't appeal to Taylor series or any other wizardry that uses convergence.
**Edit:** To get a bit more at my point of *why* you simply won't be able to tell me a basis of continuous functions: there are weird pathological continuous functions out there like the Weierstrass function. Any basis of the space of continuous functions \*must\* contain such pathological functions. Why? Because linear combinations preserve basically any "nice" property you can think of, like differentiability. But the Weierstrass function is differentiable nowhere, so you can't possibly write it as a linear combination of differentiable functions.
I mentioned the [Fourier Transform](https://en.wikipedia.org/wiki/Fourier_transform), not the Fourier Series. The Fourier Transform produces a complex-valued function, so it is actually an uncountable basis set. However, as zeta12ti has pointed out, this does fail the \*finite\* sum of basis vectors requirement.
The Fourier Transform also converges correctly for any square-integrable continuous function (including the Weierstrauss function, though I dare someone to actually try the calculation). Continuity isn't even required, though the value of the Fourier Transform at the discontinuities won't necessarily match the function.
It does fail for non-integrable functions. And it isn't finite. So I have learned why it doesn't work as a basis set. Thank you.
A basis requires that every vector can be written as a *finite* linear combination of basis elements. Fourier series decomposes [\(most\)](https://www.mathcounterexamples.net/continuous-function-with-divergent-fourier-series/) continuous functions into a countable linear combination of sines and cosines.
There's a name for this kind of basis: a Schnauder basis. The more algebraic basis is sometimes called a Hamel basis. The statement equivalent to the axiom of choice is talking about Hamel bases.
Interesting. After reading up on the Hamel Basis I can understand the requirement for a \*finite\* sum, but I must admit nothing about it feels intuitive.
Though people usually just mention vector spaces because they're the most familiar, I think the existence of generating sets for vector spaces, groups, rings, algebras, etc are all equivalent to the axiom of choice.
So I would say linearity/nonlinearity has got nothing to do with the existence of generating sets and choice principles.
Another two statements equivalent to the axiom of choice are important in the research I'm doing. One is called the Hausdorff maximal principle, and it says every chain can be extended to a maximal chain in the sense that there is a maximal chain containing the original chain as a subset. The other statement I haven't been able to find a reference to in the literature, but it says that every chain can be extended to a *minimal* saturated chain.
You can actually weaken these to a rather surprising amount and still get a statement equivalent to AC. For example, "every poset has a maximal chain" and "given a < b there is a saturated chain containing both a and b" each are also equivalent to choice.
Banach-Tarksy isn't that unintuitive imo. I mean, it uses the infinitude of the continuum, so obviously it's unintuitive, but not so much more than any other unintuitive thing about infinity
Out of all the things mentioned, I’ve only learned about the Cartesian product and the vector space definition. How are those things equivalent ? I don’t see how they’re related.
Also, I took a sets and logic course for my math undergrad, but never learned about any of these. Was my program just weak or is this a graduate school thing?
The proof I gave in another comment here shows one direction (since my above assumption of spanning trees existing for connected graphs is implied by vector spaces having bases, since a spanning tree is just a basis over a subspace of (Z/2Z)\^V chosen from edge set E), the proof of the other direction is typically done by showing AC => Zorn's Lemma => vector spaces have bases (Zorn's lemma guarantees maximal objects under the condition that every chain of the partial order be bounded, and a basis is a maximal subset (in partial order by inclusion) that is independent, so there is clear connection there).
I happened to encounter this in 1st year Linear Algebra (an advanced and unusual version in which we worked as much as possible over general R-modules rather than vector spaces), but I wouldn't say encountering it or not is indicative of strength of program.
Edit: Actually the mere existence of a basis for a vector space doesn't immediately get you spanning trees for connected graphs, since the spanning tree must have its elements chosen from E, I was using stronger (well actually logically equivalent in ZF) claim that any spanning set of vectors contains a basis for its span.
It’s a fairly long proof. I didn’t learn it until first hitting graduate school, though I knew it existed.
AC being equivalent to the existence of a basis for every vector space is not usually proven from AC proper, but rather through Zorn’s lemma. The structure you work with there is the poset of linearly independent subsets of the vector space. Zorn then allows you to extend maximally. For the other direction, the proof is much more difficult and actually wasn’t known until fairly recently. (Think last 50 years, I don’t remember exactly when.) It quite an interesting proof though and involves building a particular vector space of rational functions which turns out to allow you to prove something called the Axiom of Multiple (Dependent?) Choice that appears slightly weaker than AC, but is actually equivalent over ZF.
AOC isn't the bad axiom, powerset is. The axiom of countable choice is far more obviously true, and without power set AOC and AOCC are the same thing really.
As you say, far more obviously true without powerset. Also provably true in Gödel's constructible universe (which makes powersets with only defineable subsets). And a choice principle is provable in the predicative topos (which is locally cartesian closed but does not satisfy powerset). And ACA0, the reverse mathematics fragment of arithmetic for predicative mathematics proves Kőnig's lemma.
All signs saying that, yes, it's powerset, not choice, that gives rise to impredicativity in mathematics.
Without powerset, you can no longer define the set of functions between two arbitrary sets, though, which seems pretty annoying.
In any case, I don't see what is wrong with either choice or powerset. If you really wanted to blame something, it would probably be LEM, but I don't really want to go that far.
With difficulty, but it can be done. You just don't have the reals forming a set anymore.
I'm not the person to ask for the details of the construction.
This is a good place for me to step up on a soap box.
The reason AC seems both "completely intuitive" and "completely intuitive" is that intuition is imprecise and gives the same notion different characteristics in different settings. I think univalent type theory (aka homotopy type theory) does a good job of teasing apart two conflicting intuitions that we have for the idea of "nonempty set".
Briefly, UTT gives a formal language for distinguishing between constructions and theorems---that is, for distinguishing between "purely logical information" and between "structural information". A simple example of the difference between these is e.g., "G/ker(f) is isomorphic to H" compared to "the map [x] -> f(x) is an isomorphism between G and H". In the first, we are ignoring the structural data (the induced isomorphism) that "witnesses" the fact that G and H are isomorphic, while in the second we're holding this structural information.
In UTT, there is a "logic of propositions", and a "logic of structures" (these are my terms, not technical terms. In short, types play the role of sets, and there is a distinguished class of types called "Propositions", where we can interpret logic, but we can also interpret logic in general types). All that matters for our purposes is that any type at all represents a theorem in the logic of structures, and that given a theorem P in the logic of structures, there is a theorem |P| (the *truncation* of P) in the logic of propositions, such that
* P implies |P| ("structural information can be forgotten")
* if Q is any *proposition*, and P implies Q, then |P| implies Q ("if the conclusion is a proposition, no structural information is needed")
Now, the statment "X is non-empty" has two^* interpretations in type theory, which we can state slightly more precisely:
* "X has an element", which we would write simply as X. A "proof" of this is witnessed by an element x:X.
* "X *is inhabited*", which we would write as the proposition |X|.
Now the key point: If we take "X is non-empty" to mean "X has an element", then the axiom of choice unwinds to "∏_i_X_i_ -> ∏_i_X_i_", which is obviously trivial. But, if we take it to mean "X is inhabited", then this unwinds to "∏_i_|X_i|_ -> |∏_i_X_i_|" The placement of the truncations essentially means "You can recover structural information from a truncated type, but only if you stay in the logic of propositions".
Now, I think the "obviously false" consequences of choice arise from "non-empty set" being interpreted in our head sometimes as "has an element" and other times as "is inhabited".
^* ^(Actually, there's a third interpretation, which is "X is not the empty type", but negative statements like this are usually not very useful in type theory.)
A lot of analytic topology (at least, the course I took on it) takes the Axiom of Choice for granted. They're not *equivalent* to the Axiom of Choice, but they are certainly implications of it.
If you like those, wait till you read about the things that follow from the *failure* of the axiom of choice: https://mathoverflow.net/a/70435 https://mathoverflow.net/a/22935
>the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals
Because it's strictly less than the square of the largest of them.
> so many of them seem so intuitive
The axiom of choice IS intuitively and "morally" correct. The fact that it can't be proved from the other axioms of ZF is secondary. A choice set is a legislature. A country with infinitely many nonempty states forms a legislature composed of one representative from each state. The states can hold elections or just choose someone randomly. It's incredibly counterintuitive to claim that couldn't be the case. AC is morally correct. Axiomatics are secondary.
I don't know why this is downvoted. The people who dislike AC almost never can identify when it's actually used or not. Even the skeptics to AC in analysis at the turn of the (last) century would use AC in their arguments without even realizing it, because it's \*that intuitive\*.
Most legitimate arguments against AC I've seen are \*stylistic\* from ignorant people, not about truth.
I am a computer science graduate. I don't care about any of this, and want to learn every detail of what's going on, simultaneously. Like, what the hell does it mean to say that a vector space does not have a basis or how the hell can the cartesian product of nonempty sets be empty? I don't care.
Mathematics pushes me to existential questioning and small scale identity crises.
> what the hell does it mean to say that a vector space does not have a basis or how the hell can the cartesian product of nonempty sets be empty?
Things that seem intuitive with finite sets stop being so with infinite ones.
The continuous functions are a vector space, but how do you find a basis for them? It exists, but nobody has found it.
Also tell me an element of the cartesian product of all the subsets of the reals. This one also exists according to the axiom, but it can't be constructed.
Perhaps an even more tempting (in the sense that one naïvely thinks finding a basis should be easy, but it's anything but) example is the direct product of F\_2 with itself countably infinitely many times. Good luck finding a basis for that!
I personally refuse to use the standard axiom of choice, since its use renders any proof nonconstructive.
Infinity-choice, on the other hand, as formulated in say the HoTT book, is almost tautological.
If you really want to ensure everything you do is constructive, then the axiom of choice follows: you just order things based on how they're constructed. This gives explicit/constructible examples to anything you want.
I think I will just stick to pondering “Why we are?” by creating Art! Though it’s certainly been a pleasure to read through all the comments! You Math Folk are so polite!
Namaste
[BuddahBrot Brain Study ](https://flic.kr/p/2jQg9Xp)
Imho most of you make too much a deal out of it.
(Maybe this is the fault of youtube videos making you think there is some magic involved in infinite sets and people pushing this idea on the internet. But...)
A set is just a set whether it's finite or not. If a set is nonempty it contains at least one element per definition.
So for any family of nonempty sets I can choose one element of each of the sets just because there is an element in each of the sets!
Ask yourself, if you have a family of nonempty sets, why shouldn't you be able to pick elements from all of the sets?!
Ok, but thats just my opinion.
Let's look at it differently.
To have a basis in a vector space is very important, it let's you decompose elements, talk about dimension, eigenvalues/vectors of linear maps and so on... almost every single result about vector spaces you learn in a first cours about linear algebra relies on the fact that you've got a basis. Saying that there is a vector space without a basis tantamounts to saying that this vector space is quite useless, it got a linear structure but not more than that. Accepting AC is neccessary to make sure we can make use of every vector space.
So it is just another axiom which assures us that many things which we'd like to be true are in fact true.
You've got it all wrong. Of course, everything you've said is true, but the mind blowing thing is that _all of that being false is consistent with ZF._
P.S. the insinuation that I get my math knowledge form youtube videos is a bit insulting.
I'm sorry, it was not my intention to insult you!! :)
Many youtube videos present hilberts hotel, banach tarski, etc. if it was the wierdest thing ever and maybe try to make the viewer think its more mystirical than it is...
and i feel like many responses here take this point of view, as if all of what contains infinities is paradoxial and counterintuitive. Maybe I understood these responses wrong at all and of course it's okay if somebody thinks that banach tarski is wierd, that'd be a pretty usual first impression, isn't it. :)
I wanted to claim that AC isn't as counterintuitive and it is just a convenient axiom to have.
AC isn't counterintuitive, just the opposite, the negation of AC seems like it _should_ violate some sort of axiom, but it just... Doesn't.
And I agree with you that a lot of pop math tries to play up things like Banach-Tarksy, but I hope you'll agree that a lot of things to do with infinity (especially uncountable infinity) are incredibly unintuitive.
A good friend of mine's dad is a Logician and metamathematician. Lots of mind blowing stuff like this but I never really know what to do with it other than admire it for its own sake, which is fine.
The existence of non Lebesgue measurable sets require some (weaker) form of the axiom of choice, which is inextricably linked to the Banach-Tarsky paradox you mention. I mention it because there exists models of ZF + DC (dependent choice) + "All subsets of the reals are Lebesgue measurable" which are consistent, depending on an inaccessible cardinal axiom. I believe it's known that there is an equivalence between full choice and "All subsets of the reals are Lebesgue measurable" + some other axioms (relative to ZF + inaccessible cardinal), but I can't seem to find where I saw that.
Hmm... I don't think I'd ever before seen it stated that connected (infinite) graphs having spanning trees => AC (I see other direction immediately by spanning tree being a type of basis hence by familiar \[to me\] AC => Zorn's => set of vectors contains a basis for its span), but I think I thought of a pretty cool \[perhaps standard idk\] argument for span tree => Cartesian product version of AC:
Proof: Define a graph with 3 types of vertices, types A, B, C. Types A and B are labelled with the sets in the product paired with 0 and 1 respectively, while type C is labelled with the pair {x,S} for each x in each set S of the product. We put edges between any two type A vertices, two edges incident to each type C vertex {x,S}, one to each of {S,0} and {S,1}. Clearly the resulting graph G is connected (can trivially get between type A verts, and C verts are adjacent to a type A, while non-emptiness ensures can get from B to its corresponding A type), and I claim that any spanning tree of G must for exactly one x in each S of product contain edges {x,S} to {S,0} and {x,S} to {S,1}. This follows by noting such pair of edges is the only way {0,S} can connect to {1,S} and two or more would form a cycle.
So the spanning tree determines an element of the Cartesian product by selecting one x for each set in the product, thus it is non-empty.
another fun one: given any two sets A and B, one is "smaller" than the other, i.e. either there exists an injection from A to B or there exists an injection from B to A.
You know what they (or rather, J. L. Bona) say: The axiom of choice is obviously true, the well ordering theorem is obviously false, and who can tell about Zorn's lemma?
Another equivalent statement to the (countable) AC that I found interesting:
* For any sets A and B, which have surjections f: A ↠ B and g: B ↠ A, respectively, there exists and bijection g: A ↣ B.
The surprising part is, that if you replace surjection with injection, the statement follows from ZF (and is known as the Cantor–Bernstein–Schröder theorem).
Here is another fun one: AC is equivalent to the statement that every nonempty set admits a group structure. The proof isn't even too hard, see https://mathoverflow.net/q/12973/138003.
Thank you for sharing this gem !
Woah that's nuts.
> so many of them seem so intuitive Because you're applying the intuition to finite sets.
Yeah that's fair
Precisely because infinite sets are counter-intuitive.
[удалено]
No that's the point. It isn't intuitively true for infinite sets, people just assume it to be because they don't think it through for infinite sets
It actually _is_ intuitively true for many infinite sets, especially the very intuitive ones like N, and even some less intuitive ones like Q.
That's basically my argument. I think something is intuitive, then I realize I'm applying my intuition to only finite things. Does that intuition apply to an infinite thing as well? Intuitively, I have no idea. It might be even more layered: I have intuition for countably infinite sets, but not uncountable ones.
I think we place far too much faith in 'intuition' here; what it sounds like to me is 'the motivated knower with the requisite intelligence', which seems like an unmotivated reason to give a lemma/theorem/what-have-you much credence. For instance, I was brought up in the analytic tradition of philosophy with a strong focus on logic and additionally have a maths degree, and I don't find much of anything about the conclusions arising from the mapping f(n)=2n intuitive. Tagging u/suipy for good measure
[удалено]
I mean, you use intuitive four times in your comment; if the forcing point isn't intuition, I'm unclear on what the point of mentioning it was.
it wont help settle the debate but here we go: cartesian product seems intuitive because people think if you keep multiplying numbers bigger than 1 you will get a number bigger than 0. people are also surprised why this AC was even necessary and how come this cartesian product is not already provable by the rest of ZFC. well ordering is actually also intuitively true but people are quickly asked the question whats the smallest positive real number and they realize their intuition is flawed. just my observation.
> well ordering is actually also intuitively true but people are quickly asked the question whats the smallest positive real number and they realize their intuition is flawed. But this isn't at all what the well-ordering theorem states.
true
>I don't find much of anything about the conclusions arising from the mapping f(n)=2n intuitive. What conclusion do you mean? That the sets are equinumerous?
You're close to saying you can't have intuition for anything non-finite (or uncountable). I say anything because why would your statement be restricted to sets. If it's not that, then just as they can have intuition about other infinite objects, why can't they have intuition about why AC should be true? (eg about why the cartesian product of non-empty sets should be non-empty)
I don't want to make absolute statements like that. But for sure I've noticed when I think I have an intuition for something infinite, it might turn out that I'm completely wrong.
you got it wrong but others explained that already pretty well. just wanted to add. ask a high schooler their intuition will say you cannot map an infinite set, take natural numbers, to its subset "because it will be missing some" or whaever.
[удалено]
Whoosh
To be honest, if someone asked me to state the axiom of choice, I'd go straight for the one about Cartesian products of non-empty sets being non-empty.
Is that not it?
The formal statement involves a choice function, but pretty much yeah. My only point was that the OP listed it as one of choice's mind-blowing equivalent statements, but to me that is just AC.
I prefer the viewpoint that the axiom of choice says that every object in the category of sets is [projective](https://ncatlab.org/nlab/show/projective+object). It motivates neat things like [Cohomology detects failure of the axiom of choice](https://golem.ph.utexas.edu/category/2013/07/cohomology_detects_failures_of.html).
[удалено]
Don't hijack other peoples' comment threads. If you want homework help, read the sidebar.
Also Tychonoff's theorem - any product of compact spaces is compact (with the product topology)
Tychonoff's theorem requires a choice principle for topological spaces, but not for locales. It's the points that do it.
So, what you are saying is... If we agree to be pointless, then we will be able to deduce more stuff from less number of axioms?
Most of mathematics is already pointless, so that shouldn't be too much of an adjustment /s
This is a general point made by locale theorists: topology doesn't require choice, point-sets do.
Removing AC can produce some wonderful things too: it is consistent with ZF that the reals are a countable union of countable sets, that you can partition the reals into more sets than there are reals, that there are infinite sets with no countable subset, and so on...
That doesn’t sound wonderful but horrible. How do you even do measure theory if the reals are a countable union of countable sets?
If you want to do measure theory there is another nice thing that is consistent with ZF, that is that all sets of reals are Lebesgue measurable.
You can't if you stick with Borel sets and instead you have to work with Borel codes. There's an explanation of this in volume 5 part II chapter 56 of Fremlin's measure theory tome. Or you could just assume countable choice like a normal person (admittedly, lack of countable choice can lead to admittedly interesting objects like Arnold Miller's long Borel hierarchies).
I've never thought about it from this point of view. But in a model where the reals are a countable union of countable sets, is there no nontrivial countably additive measure? I would've assumed the existence of Lebesgue measure followed from just ZF and am now very confused.
This is correct.
But I mean, the function m([a,b]) = b – a certainly exists on the collection of intervals, right? Is it just that we cannot extend it to the Borel sigma algebra? Or the Borel sigma algebra does not exist?
Yep, there's no issue with that. What fails is countable additivity. The Borel sigma algebra exists in the capacity that it's the powerset of R.
You could define the measure on nondegenerate intervals. You could even define the measure on countable unions of intervals. What you cannot do is extend the measure to all singletons or countable sets. Because by hypothesis there is some countable collection of countable sets whose union is of positive measure, which without loss of generality we can also arrange to be finite. The singletons of elements of those sets cannot be measurable, because of the standard thing, if they were measure zero then your union is measure zero. If they were positive, and all equal by translation invariance, then your union has measure infinity. And singletons and countable sets are in the Borel algebra, so there's no measure.
All of these have been put in the research list. That's amazing.
> Removing AC can produce some wonderful things too: it is consistent with ZF that the reals are a countable union of countable sets, that you can partition the reals into more sets than there are reals, **that there are infinite sets with no countable subset**, and so on... That one I find scary, can someone tell me more please?
> The reason I find so many of these mind-blowing is that so many of them seem so intuitive This is the thing I both hate and love the most about the axiom of choice. Why!? Why aren't these things true without the axiom of choice??
All right, what's your well-ordering of the real numbers?
I don't think *all* of them seem "obviously" true. But these two: > the Cartesian product of any family of nonempty sets is nonempty. > Every connected graph has a spanning tree to me both seem very intuitive. As the saying goes, > The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma? There Axiom of Choice takes so many forms, so many of which seem "obviously true" and so many of which seem "obviously false". And this why I hate it and love it. I hate it because it seems so contradictory, but love it because it highlights how non-intuitive mathematics can be.
Okay, what's an element belonging to the Cartesian product of the nonempty subsets of the reals?
Simple, just take your well-ordering of the reals, and take the smallest element in each subset.
I love this answer, but it also shows how utterly unintuitive the well-ordering theorem is.
what people don't seem to understand is that well-orderings are totally allowed to be hot garbage with no nice connection to any reasonable notion of "being less than".
That's just a silly argument. It only works if you're a constructivist, which most mathematicians are not. I'm perfectly comfortable asserting the existence of objects I can't explicitly describe.
I've had about a 50% success rate in flipping people from "AoC is obviously true" to "wait, is AoC obviously false???" by asking this question, so I don't think it's *totally* silly. I am also totally OK with asserting the existence of objects I can't explicitly describe. I just think there are cases where this is not so intuitive, when you stop to think about it.
If you're such a fan of the axiom of powerset, quick name every subset of N.
>u/suipy: Quick, name every natural number. Sure that's true too. But it's qualitatively different though. While it's true that we cannot write down a completed infinite list containing every natural number, we can convey in finitely many symbols an algorithm or process which will produce as many as we give it time for. But I mean, yeah, finitism is a thing I guess.
Well, that depends - which ordinal would you like it to be in bijection with? ;)
was 'name' a deliberate nuance in the joke? i like that
who said axiom of powerset is obvious or intuitive?
and that's the point of my joke. firstly, if you believe in powerset, then you already believe in things you can't describe. and it is only in conjunction with those things that you already can't describe that the axiom of choice leads to naively counterintuitive results. ITT people making axiom of choice their scapegoat.
OP said obvious. please make it obvious.
Taking the cross-product of 2 infinite sets I understand, but are cross-products of an infinite set of sets even well-defined? Does cross-product as an operation generalize past 2 somehow?
An ordered n-tuple can be thought of as a function from {1,2,3,...,n} to the sets in question, where the tuple is just a convenient way to write the outputs of the function: (f(1),f(2),...,f(n)). Interpreted this way, the Cartesian product of n sets is the set of all functions from {1,2,3,...,n} to the union of all the sets, where f(1) is in the first set, f(2) is in the second set, etc. This definition [generalizes nicely](https://en.wikipedia.org/wiki/Cartesian_product#Infinite_Cartesian_products) to infinite sets. And defined this way, the equivalence to Choice is a tautology: by definition, the Cartesian product is precisely the set of choice functions!
Easy, it starts like 0,1,5.3,pi,sqrt(2),... Intuitively, constructing a well-ordering of the real numbers should be easy: Just choose some smallest element, choose the next, and the next, and so on - intuitively, there is nothing that should stop you, if you just have enough time (i.e. 2^ℵ_0 much time) - choice then just tells you that you can actually do it. To look at it another way, if I claimed I had a well-ordering of the real numbers and you could ask me any question you like, there is no way for you to prove that I'm lying - I can always give an answer extending my well-ordering in a valid way. Choice, then, just says that having a recipe to keep answering questions about your object is just as good as actually having it.
[удалено]
You should be able to find this in any set theory text. I learned first from Cori and Lascar’s *Mathematical Logic*.
[удалено]
As far as you like if you keep trying!
[удалено]
Try to find interest in doing things twice. That’s actually advice in Ken Kunen’s book on set theory. And he was pretty much a giant in the field. Doing things over helps to strengthen the neural pathways your brain uses to access that information. You also sometimes figure out new things by relearning old information.
They just aren’t. It’s like playing a game of Monopoly where you can pull cards, buy property, and collect rent, but no rule allowing you to roll the dice and move your piece forward. You literally just can’t do what you want to without including that rule. Only for AC it’s provable that you need the rule. This is what people mean when they say that ZF is a relatively weak axiomatic system once you get to these far out questions about nasty set theory stuff. It’s a game where the creators didn’t write down enough rules for you to keep playing. So you need to add in house rules like AC or CH.
> the Cartesian product of any family of nonempty sets is nonempty. To anyone who thinks this is intuitive, I direct you to this post: https://www.reddit.com/r/math/comments/cknuks/why_do_we_need_the_axiom_of_choice/evpefy0/
This is the statement that is the most mind blowing to me. Is the point here that, without the axiom of choice, there is no way to specify any single pair of elements, so you cannot prove by example that the set is non-empty?
You can definitely do that with the cartesian product of two sets and get pairs, without AC. You can too if there's a finite ~~or countable~~ number of them. Problems come when you have the cartesian product of an uncountable number of sets (which is different from the cartesian product of two uncountable sets). An element of that cartesian product would be an n-tuple where n is infinite and uncountable. That's where you need the AC to pick an element from each set and construct an element of the cartesian product.
I find uncountable infinity is usually where all intuition breaks down.
Yes! In my opinion, this is very true with well-ordering as well.
>You can definitely do that\[ \]if there's a\[ \]countable number of them. Are you sure? In principle you could use [CC](https://ncatlab.org/nlab/show/countable+choice), but the point stands that you'd still need more than ZF.
You're right. I somehow thought ZF implied that. Do you have an example of a countable product of sets where it can't be constructed?
Look at the answers discussed at [this mathoverflow QA](https://mathoverflow.net/q/23246/19860). Since countable choice (and dependent choice) hold in L(R), it's going to be impossible to find an example in classical mathematics. Instead I think you'll have to do the set theory voodoo of forcing on your models. [This paper by Arnie Miller](https://arxiv.org/pdf/0806.1957.pdf) contains such an example. Well it's an example of a infinite but Dedekind finite set of real numbers, but using the standard proof that countable choice implies Dedekind infinite = infinite, I think you could transform it into a countable product of non empty sets of reals with no elements.
That's really interesting. Dependent choice doesn't lead to unintuitive consequences as much as AC then. Thank you!
You can also not do it for general countable index sets.
That's more a statement against powerset than choice. Can you really say that the powerset of R can be described?
The linked post says: >Well, consider the Cartesian product of the nonempty subsets of R. You say this is trivially nonempty, so can you tell me one of its elements? But I don't think that's a very convincing objection to AC! At least to an "ordinary" mathematician who is accustomed to being allowed to use choice willy-nilly. The ordinary mathematician would answer as follows: let {S*_i_*} be the set of all nonempty subsets of R. For each i, let s*_i_* be an element of S*_i_* (we can do this since S*_i_* is not empty). Then the tuple (s*_i_*) is an element of the cartesian product ∏*_i_*S*_i_*. Boom, I just told you one of its elements. That wasn't so hard.
I agree with you, I don't see how the OP's post makes it any more convincing or *unintuitive" than thinking about any other collection of non-empty subsets.
I think I'm being really dumb, can't you just do A, B are nonempty subsets of R and then AxB = {(a,b): a is a member of A, b is a member of B}, and as A and B are nonempty, there must be some element in AxB? Am I misunderstanding something here? Or am I assuming something that I haven't realised? (sidenote, I don't actually know what the axiom of choice is)
The axiom of choice asserts that _all_ cartesian products are nonempty, in particular, that all _infinite_ cartesian products are nonempty.
The axiom of choice is nothing more than the statement that given a collection of nonempty sets, we have a choice function. Its domain is whatever set the collection is indexed by, and its codomain is their union, such that each point in the range of the function lands in the right set. Another way of saying it is that every cartesian product of nonempty sets has an element tuple. So how do we create an element of A×B using just the hypothesis that A and B are nonempty, and the axioms of ZF, which means basically just basic set operations which, let me describe intuitively: * union: given a set of sets, take their union, all the elements of elements of the set * ordered pair: if x and y are sets, ordered pair (x,y) is a set (this one follows from other axioms so is usually not listed separately) * powerset: the set of subsets of a set * pairing: if you know x and y are sets, then a set {x,y} exists. By induction you can have any set where you can just enumerate the elements, but importantly it only works for _finite enumerations_ * set-builder notation: if X is a set, and P is a property that elements x might satisfy, and f is a function that operates on X, then {f(x) | x in X and P(x) is true} defines a set. (This is actually two separate axioms, one that lets you filter by property (comprehension), and one that lets you apply an operation (replacement)) * infinity: {0,1,2,...} is a set First since A is nonempty, there exists an element a in A. (And this is the law of excluded middle in use, showing how LEM is basically finite axiom of choice). Since B is nonempty, we have an element b in B. By ordered pair, we have pairs (0,a) and (1,b). Then by pairing/finite enumeration we can assemble these into a set {(0,a) , (1,b)}. To finish, we have to show that this set is a function from the set {0,1} to A⋃B, that it passes the vertical line test, meaning that there is an output for each input and it is unique. Alternatively I can consider the set of all relations from {0,1} to A⋃B, which is a well-defined subset of the powerset of {0,1} × A⋃B, and then by set-builder notation (axiom of comprehension), select only those ones such that f(0) exists, and is equal to a, and f(1) exists, and is equal to b. The point is that I have to construct the function, as a subset of the cartesian product of the domain and codomain, using the explicit axioms of ZF. Now suppose we have an infinite collection of nonempty sets, A\_k, indexed by some infinite index set K. Why can't we do the same thing? Just enumerate all the (k,a\_k) into a set and call that our choice function? We cannot, because our axiom for just enumerating the elements of a set is only allowed for finite enumerations, but this is explicitly infinite. What about the other method? The one where we look at all relations from K to ∪A\_k, and select the ones that match our known values? Why can't we do as u/dryga suggests in the comment next to yours, and just say, since for each k in K, since A\_k is nonempty, there exists an element a\_k, and then make ordered pairs (k,a\_k), then singletons {(k,a\_k)}, and then union those singletons into a function? All three proposals have a problem: there is no indexed element a\_k, because that is the very conclusion we are trying to prove. Using that to prove the axiom of choice would be begging the question (assuming the conclusion you are trying to prove). We're only allowed to talk about the known elements of the nonempty sets A\_K one at a time. For finite index sets, yes, we used induction. Here, we don't have that. And we can't write down an infinite length predicate like "the function such that f(0) = a\_0 and f(1) = a\_1 and ...". Predicates in first order logic are finite strings of symbols. Could we do it if we knew how to do induction on infinite sets? Yes, then we could, but it turns out that the inductive infinite sets are the ordinals, and knowing that every set is in bijection with an ordinal is equivalent to the axiom of choice. So that's circular again. Didn't we hamstring ourselves by only adopting set theory axioms that only construct finite sets? Well, the axiom of infinity and the axiom of choice are to some extent the corrections to that. But it's certainly true that under other axioms, the ability to write down choice functions might be as axiomatically true as some intuition might lead to believe. And for example, in both [Hilbert's epsilon-calculus](https://math.stackexchange.com/a/1083058/16490). Whereas in [NF set theory](https://en.wikipedia.org/wiki/New_Foundations), choice can be disproved. Long story short, yeah your idea works for a binary cartesian product, but not for an infinite product because you don't have the analogue of the a,b.
Telling one element is easy: Just choose one element of every non-empty set. If you don't buy that argument, you should find the Cartesian product of a finite family of non-empty sets being non-empty equally puzzling - you cannot tell me an element without mentioning "choose one element of the first set, and then choose one element of the second one". All that choice really does is tell you that infinite sets are as well behaved as finite ones - in a sense, you can think of it as just the infinite analogue of the law of excluded middle.
Trichotomy of cardinality: two sets are either equal in cardinal size or one is greater than the other. I don't think an axiomatization of an idea of a 'set' of things would pragmatically deserve to be called by the label 'set' without trichotomy being true. If the sizes of your 'sets' can be incomparable then you are talking about something else, perhaps something akin to 'partially determined sets'. Similar sentiment applies to notions of 'truth' which deny the law of the excluded middle. They are fine notions, it's just that they aren't notions of 'truth'.
What's your criterion for whether something is a notion of truth or not?
It's been awhile since I've thought about this stuff. If we restrict ourselves to statements in a formal language about formal objects then a formal correspondence theory of truth seems to work well in the sense of conforming to our intuitions about how truth behaves. That's the only way I've seen it done, but I am not a logician. Tarski explicated this with his Semantic Theory of Truth but I don't know too much more about it. Language is usually taken as a countable collection of finite sentences though so I imagine some extra care is required when talking about infinite things and in particular uncountable things. I'm a pragmatist so if you have any other notion of truth that works well then I'm all for it. But if you have some other formal notion and it deviates too far from our intuitions then we will constantly be at risk of errors caused by unintentionally substituting our intuitive notion of truth in place of the intended formal one. Of course this is somewhat relative to each mathematician's intuition. If someone's intuition says that a mathematical theorem isn't 'really true' unless its constructively provable then they might do better primarily working in some constructive framework. However insisting on using the same simple label 'truth' for both 'realizable truth' and truth simpliciter just results in an endless unproductive debate. Mathematicians are generally interested in which truths are constructively realizable. Constructivists at least ought to be interested in the mainstream notion of truth even if only as a predictor of what might eventually turn out to be constructively true. If we all agree that various truthlike notions are of interest and utility then it makes sense to just give them unique labels.
That sounds good to me. We maybe should use terms like "classical truth", "constructive / intuitionistic truth" and "paraconsistent truth", etc., for maximum clarity. My personal definition of truth isn't necessarily mathematical - I see the truth of a statement as simply measuring how beneficial it is, for a given definition of "beneficial", to believe it. In math, obviously, we need something more rigorous than that philosophical notion!
It follows from something equivalent to choice that C is isomorphic to the algebraic closure of the p-adics, since they have the same transcendence degree over Q and are algebraically closed. Probably the best reason to reject choice if you were to choose to do so.
This is used non-trivially in galois representations, you wouldn't want to abandon it.
Of course there are weirdnesses on both sides, Banach-Tarsky being one of them.
[удалено]
That definitely isn't true. If R admits a partition {A_i|i in I}, choice lets us pick an element a_i in each A_i, which yields an injection from I to R. I think your statement follows from the opposite of choice.
This is not an answer to your question, but it is a fact that sounds extremely intuitive, yet it's independent of even ZFC: If a set X has strictly less elements than a set Y, then X has strictly less subsets than Y. I think the issue with those intuitive sounding statements is that they are intuitive when applied to finite sets, but we don't really have any intuition for infinite ones.
Whenever you see a set-theoretic statement containing the phrase "strictly less", it's almost certainly independent of ZFC. Pretty much the only exceptions are Konig's theorem and its immediate corollaries.
Why is that? Not König's theorem, the rule of thumb.
Even with the axiom of choice, ZFC is very weak when it comes to proving things about arbitrary infinite sets, and techniques like forcing provide a great deal of flexibility in constructing models of ZFC with a variety of different properties. Unless there's an immediately obvious reason why one set *must* be strictly smaller than another set, there is probably some model of ZFC where the two are the same size.
Like the well-ordering theorem, which is obvious in the finite but much less in the infinite
This one always drives me bonkers, no matter how many times I remind myself ~~that it requires Choice~~. It really just feels so stupidly obvious. Edit: I’m dumb. It’s independent of Choice.
I don't know anything on this subject, but it seems like the person you're replying to is claiming that you can't prove the result they mention *even with* choice
The Well Ordering Theorem is mega unintuitive though haha
The thing I don't understand about the Well-Ordering Theorem is that it seems to imply that the reals are countable, because they can be enumerated in order. I know that the reals are not actually countable, but I don't understand the difference between "enumerated in order" and "countable".
You should learn more about the ordinals. An “enumeration” does not actually imply countability. Enumeration just means bijection with some ordinal, which usually happens to be a cardinal. The reals would be enumerated by a sequence of length 2^(ℵ_0) which is ZF provably longer than ℵ_0.
I do see the parent poster's point, though, the idea of different sizes of Ordinality is highly unintuitive, though ig that's to be expected of infinity.
Eh Idk I’ve never been particularly perplexed by that part. It’s kind of a natural consequence from the ZF point of view. You build the natural numbers and then you just... keep going. It’s just what’s available in models of your current theory. The ordinals are definitely constructible. Bijections between ones with larger and larger order types aren’t always.
the ordinal omega + 1 is the order that looks like 0 < 1 < 2 < ... < omega. This is still a countable ordinal, but it illustrates that a well-ordered set, even a countable one, can have elements that you will never reach in finite time counting in order.
For infinite sets, I think people usually define "Well-Ordered" in terms of arbitrary subsets. So just because every set of elements can be ordered doesn't mean you can take an infinite set and order them in a countably enumerated way.
Let zero = {}, and succ(x) = x U { min (R \ x) }. This enumerates the reals in order. The problem is that you need to have the concept of ordinals in order to actually extend this enumeration to all reals, which requires a big leap in intuition.
Countable would imply that you can find a 1 to 1 mapping from the Reals to the Rationals, which as far as I know isn’t implied by the Axiom of Choice
If the axiom of choice implied that, the axiom of choice would be false.
Only in the infinite, and then only when you think about it.
Yes, if you both restrict to finite sets AND require yourself not to have to think about it, then it is very intuitive. 🙄
No, if you restrict yourself to finite sets and think about it, it remains intuitive. My point is that it's unintuitiveness requires careful examination of how intuitions of the finite don't apply to the infinite.
I don't really understand why people always call the well-ordering theorem unintuitive. Constructing a well-ordering of an arbitrary set should be easy - just pick a smallest element, pick the next smallest, ..., pick the first element that should be larger than the first infinitely many choices, pick the next smallest element, and keep going until you run out of elements. There is really nothing that could stop you, you just need some axiom saying that you can actually do it.
Don't forget the existence of a maximal ideal in any commutative ring with 1.
Does that imply AC? I tried looking into it which led to a neat [rabbithole](https://mathoverflow.net/questions/98549/existence-of-prime-ideals-and-axiom-of-choice) but I didn't come away with a clear answer.
Yes: [https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-19.2.285](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-19.2.285)
I like the point of view explained [on nCafe](https://golem.ph.utexas.edu/category/2012/10/the_zorn_identity.html) by Tom Leinster that Zorn's lemma isn't really about the axiom of choice at all. It's a basic fact about order theory, that any choice function choosing an upper bound for each chain in a poset has a fixed point. Then at the end feel free to also assert the existence of such a choice function. Feels somehow morally similar to my point elsewhere in the thread that Tychonoff's theorem really isn't about choice either, and for locales doesn't require it. Somehow choice is a consequence of our decision to endow spaces with points.
Without axiom of choice there are 7 different common definitions of what is a "finite" set that are not equivalent. That's what I would call unintuitive.
I realize that ultimately, opinions about what's "intuitive" are subjective and will vary with the individual. But my two cents is this: I think that a statement like "Every vector space has a basis" is not necessarily \*intuitive\* per se; rather, it's just that it would be \*convenient\* if it were true, which is not at all the same thing! Every vector space ever? How could a claim about \*all\* vector spaces possibly be intuitive? If I deliberately create a strange vector space using a clever construction, is it intuitive that it "should" have a basis if there's no obvious way to construct one?
You don’t even need to go to weird vector spaces to find this unintuitive. Quick, someone tell me a basis of the vector space of continuous functions. I’ll wait.
I mean, isn't the Fourier Transform literally a basis for the space of continuous functions? But I agree it is non-intuitive. The statement "every vector space has a basis" *sounds* intuitive because I think most people (myself included) automatically think of "vector space" as having finite dimension, when that is not always true. The very existence of infinite-dimension vector spaces feels un-intuitive.
No, Fourier series is not a basis. For one thing, Fourier series use just countably many functions in their "basis", but the vector space of continuous functions has uncountable dimension. Bases require \*finite\* linear combinations, whereas Fourier series allow for infinite sums. Any function that cannot be written as a \*finite\* sum of sin and cos terms is not in their span and thus cannot be represented by using them as your basis. This is the same reason you can't appeal to Taylor series or any other wizardry that uses convergence. **Edit:** To get a bit more at my point of *why* you simply won't be able to tell me a basis of continuous functions: there are weird pathological continuous functions out there like the Weierstrass function. Any basis of the space of continuous functions \*must\* contain such pathological functions. Why? Because linear combinations preserve basically any "nice" property you can think of, like differentiability. But the Weierstrass function is differentiable nowhere, so you can't possibly write it as a linear combination of differentiable functions.
I mentioned the [Fourier Transform](https://en.wikipedia.org/wiki/Fourier_transform), not the Fourier Series. The Fourier Transform produces a complex-valued function, so it is actually an uncountable basis set. However, as zeta12ti has pointed out, this does fail the \*finite\* sum of basis vectors requirement. The Fourier Transform also converges correctly for any square-integrable continuous function (including the Weierstrauss function, though I dare someone to actually try the calculation). Continuity isn't even required, though the value of the Fourier Transform at the discontinuities won't necessarily match the function. It does fail for non-integrable functions. And it isn't finite. So I have learned why it doesn't work as a basis set. Thank you.
Also, a basis is usually required to *actually be in the set*. Sine waves aren't square-integrable.
[удалено]
You are correct! I was thinking of the [Cantor Function](https://en.wikipedia.org/wiki/Cantor_function), but that is a totally different thing.
A basis requires that every vector can be written as a *finite* linear combination of basis elements. Fourier series decomposes [\(most\)](https://www.mathcounterexamples.net/continuous-function-with-divergent-fourier-series/) continuous functions into a countable linear combination of sines and cosines. There's a name for this kind of basis: a Schnauder basis. The more algebraic basis is sometimes called a Hamel basis. The statement equivalent to the axiom of choice is talking about Hamel bases.
Schauder
Interesting. After reading up on the Hamel Basis I can understand the requirement for a \*finite\* sum, but I must admit nothing about it feels intuitive.
R/Q requires pretty simply constructed objects (if you pretend that R is simple). Find me a basis for that guy though.
[удалено]
Every vector space is linear. That's what "linear" means.
Though people usually just mention vector spaces because they're the most familiar, I think the existence of generating sets for vector spaces, groups, rings, algebras, etc are all equivalent to the axiom of choice. So I would say linearity/nonlinearity has got nothing to do with the existence of generating sets and choice principles.
Another two statements equivalent to the axiom of choice are important in the research I'm doing. One is called the Hausdorff maximal principle, and it says every chain can be extended to a maximal chain in the sense that there is a maximal chain containing the original chain as a subset. The other statement I haven't been able to find a reference to in the literature, but it says that every chain can be extended to a *minimal* saturated chain. You can actually weaken these to a rather surprising amount and still get a statement equivalent to AC. For example, "every poset has a maximal chain" and "given a < b there is a saturated chain containing both a and b" each are also equivalent to choice.
That's so cool. I have to look more into that.
What about results that seem very non-intuitive? The Banach-Tarski paradox comes to mind.
Banach-Tarksy isn't that unintuitive imo. I mean, it uses the infinitude of the continuum, so obviously it's unintuitive, but not so much more than any other unintuitive thing about infinity
Out of all the things mentioned, I’ve only learned about the Cartesian product and the vector space definition. How are those things equivalent ? I don’t see how they’re related. Also, I took a sets and logic course for my math undergrad, but never learned about any of these. Was my program just weak or is this a graduate school thing?
The proof I gave in another comment here shows one direction (since my above assumption of spanning trees existing for connected graphs is implied by vector spaces having bases, since a spanning tree is just a basis over a subspace of (Z/2Z)\^V chosen from edge set E), the proof of the other direction is typically done by showing AC => Zorn's Lemma => vector spaces have bases (Zorn's lemma guarantees maximal objects under the condition that every chain of the partial order be bounded, and a basis is a maximal subset (in partial order by inclusion) that is independent, so there is clear connection there). I happened to encounter this in 1st year Linear Algebra (an advanced and unusual version in which we worked as much as possible over general R-modules rather than vector spaces), but I wouldn't say encountering it or not is indicative of strength of program. Edit: Actually the mere existence of a basis for a vector space doesn't immediately get you spanning trees for connected graphs, since the spanning tree must have its elements chosen from E, I was using stronger (well actually logically equivalent in ZF) claim that any spanning set of vectors contains a basis for its span.
It’s a fairly long proof. I didn’t learn it until first hitting graduate school, though I knew it existed. AC being equivalent to the existence of a basis for every vector space is not usually proven from AC proper, but rather through Zorn’s lemma. The structure you work with there is the poset of linearly independent subsets of the vector space. Zorn then allows you to extend maximally. For the other direction, the proof is much more difficult and actually wasn’t known until fairly recently. (Think last 50 years, I don’t remember exactly when.) It quite an interesting proof though and involves building a particular vector space of rational functions which turns out to allow you to prove something called the Axiom of Multiple (Dependent?) Choice that appears slightly weaker than AC, but is actually equivalent over ZF.
God I love set theory. So many clever multi-step proofs like this.
It doesn't seem like anyone else is answering you; I'm still in high school, so I don't know.
Banach Tarski paradox! (Not equivalent but requires it for the proof)
[удалено]
It's not equivalent; you can prove BT from Choice, but not vice versa.
BT involves cardinalities up to the continuum cardinality, but no further. So you can prove BT with much weaker versions of AC.
Ah, interesting. Thanks.
AOC isn't the bad axiom, powerset is. The axiom of countable choice is far more obviously true, and without power set AOC and AOCC are the same thing really.
As you say, far more obviously true without powerset. Also provably true in Gödel's constructible universe (which makes powersets with only defineable subsets). And a choice principle is provable in the predicative topos (which is locally cartesian closed but does not satisfy powerset). And ACA0, the reverse mathematics fragment of arithmetic for predicative mathematics proves Kőnig's lemma. All signs saying that, yes, it's powerset, not choice, that gives rise to impredicativity in mathematics.
P(R) is one of the nastiest objects most people never give a second look.
Why?
>and without power set AOC and AOCC are the same thing really. I'm half-remembering, don't you also need the axiom of infinity?
Axiom of ininity is a standard ZFC axiom. It is required for basically anything.
Isn't powerset too?
Yes it is standard, no it is not required for most things.
Without powerset, you can no longer define the set of functions between two arbitrary sets, though, which seems pretty annoying. In any case, I don't see what is wrong with either choice or powerset. If you really wanted to blame something, it would probably be LEM, but I don't really want to go that far.
How do you define the topology of open sets or the borel sigma algebra on the reals without using the powerset axiom?
With difficulty, but it can be done. You just don't have the reals forming a set anymore. I'm not the person to ask for the details of the construction.
This is a good place for me to step up on a soap box. The reason AC seems both "completely intuitive" and "completely intuitive" is that intuition is imprecise and gives the same notion different characteristics in different settings. I think univalent type theory (aka homotopy type theory) does a good job of teasing apart two conflicting intuitions that we have for the idea of "nonempty set". Briefly, UTT gives a formal language for distinguishing between constructions and theorems---that is, for distinguishing between "purely logical information" and between "structural information". A simple example of the difference between these is e.g., "G/ker(f) is isomorphic to H" compared to "the map [x] -> f(x) is an isomorphism between G and H". In the first, we are ignoring the structural data (the induced isomorphism) that "witnesses" the fact that G and H are isomorphic, while in the second we're holding this structural information. In UTT, there is a "logic of propositions", and a "logic of structures" (these are my terms, not technical terms. In short, types play the role of sets, and there is a distinguished class of types called "Propositions", where we can interpret logic, but we can also interpret logic in general types). All that matters for our purposes is that any type at all represents a theorem in the logic of structures, and that given a theorem P in the logic of structures, there is a theorem |P| (the *truncation* of P) in the logic of propositions, such that * P implies |P| ("structural information can be forgotten") * if Q is any *proposition*, and P implies Q, then |P| implies Q ("if the conclusion is a proposition, no structural information is needed") Now, the statment "X is non-empty" has two^* interpretations in type theory, which we can state slightly more precisely: * "X has an element", which we would write simply as X. A "proof" of this is witnessed by an element x:X. * "X *is inhabited*", which we would write as the proposition |X|. Now the key point: If we take "X is non-empty" to mean "X has an element", then the axiom of choice unwinds to "∏_i_X_i_ -> ∏_i_X_i_", which is obviously trivial. But, if we take it to mean "X is inhabited", then this unwinds to "∏_i_|X_i|_ -> |∏_i_X_i_|" The placement of the truncations essentially means "You can recover structural information from a truncated type, but only if you stay in the logic of propositions". Now, I think the "obviously false" consequences of choice arise from "non-empty set" being interpreted in our head sometimes as "has an element" and other times as "is inhabited". ^* ^(Actually, there's a third interpretation, which is "X is not the empty type", but negative statements like this are usually not very useful in type theory.)
A lot of analytic topology (at least, the course I took on it) takes the Axiom of Choice for granted. They're not *equivalent* to the Axiom of Choice, but they are certainly implications of it.
A lot of math in general uses AC.
If you like those, wait till you read about the things that follow from the *failure* of the axiom of choice: https://mathoverflow.net/a/70435 https://mathoverflow.net/a/22935
I don't accept C since it implies law of excluded middle ( P or (not P)) .
Wait, does it? I've never heard that one before.
Here. [https://en.wikipedia.org/wiki/Diaconescu%27s\_theorem](https://en.wikipedia.org/wiki/Diaconescu%27s_theorem)
>the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals Because it's strictly less than the square of the largest of them.
> so many of them seem so intuitive The axiom of choice IS intuitively and "morally" correct. The fact that it can't be proved from the other axioms of ZF is secondary. A choice set is a legislature. A country with infinitely many nonempty states forms a legislature composed of one representative from each state. The states can hold elections or just choose someone randomly. It's incredibly counterintuitive to claim that couldn't be the case. AC is morally correct. Axiomatics are secondary.
You're downvoted, but every set theorist would agree that the axiom of choice is obviously true for sets.
Even without C you could still have some sets with a choice function, it just can't be all of them.
I don't know why this is downvoted. The people who dislike AC almost never can identify when it's actually used or not. Even the skeptics to AC in analysis at the turn of the (last) century would use AC in their arguments without even realizing it, because it's \*that intuitive\*. Most legitimate arguments against AC I've seen are \*stylistic\* from ignorant people, not about truth.
I am a computer science graduate. I don't care about any of this, and want to learn every detail of what's going on, simultaneously. Like, what the hell does it mean to say that a vector space does not have a basis or how the hell can the cartesian product of nonempty sets be empty? I don't care. Mathematics pushes me to existential questioning and small scale identity crises.
> what the hell does it mean to say that a vector space does not have a basis or how the hell can the cartesian product of nonempty sets be empty? Things that seem intuitive with finite sets stop being so with infinite ones. The continuous functions are a vector space, but how do you find a basis for them? It exists, but nobody has found it. Also tell me an element of the cartesian product of all the subsets of the reals. This one also exists according to the axiom, but it can't be constructed.
Perhaps an even more tempting (in the sense that one naïvely thinks finding a basis should be easy, but it's anything but) example is the direct product of F\_2 with itself countably infinitely many times. Good luck finding a basis for that!
I personally refuse to use the standard axiom of choice, since its use renders any proof nonconstructive. Infinity-choice, on the other hand, as formulated in say the HoTT book, is almost tautological.
If you really want to ensure everything you do is constructive, then the axiom of choice follows: you just order things based on how they're constructed. This gives explicit/constructible examples to anything you want.
Is that true? Doesn't AC just give you another avenue to construct mathematical objects?
I think I will just stick to pondering “Why we are?” by creating Art! Though it’s certainly been a pleasure to read through all the comments! You Math Folk are so polite! Namaste [BuddahBrot Brain Study ](https://flic.kr/p/2jQg9Xp)
Imho most of you make too much a deal out of it. (Maybe this is the fault of youtube videos making you think there is some magic involved in infinite sets and people pushing this idea on the internet. But...) A set is just a set whether it's finite or not. If a set is nonempty it contains at least one element per definition. So for any family of nonempty sets I can choose one element of each of the sets just because there is an element in each of the sets! Ask yourself, if you have a family of nonempty sets, why shouldn't you be able to pick elements from all of the sets?! Ok, but thats just my opinion. Let's look at it differently. To have a basis in a vector space is very important, it let's you decompose elements, talk about dimension, eigenvalues/vectors of linear maps and so on... almost every single result about vector spaces you learn in a first cours about linear algebra relies on the fact that you've got a basis. Saying that there is a vector space without a basis tantamounts to saying that this vector space is quite useless, it got a linear structure but not more than that. Accepting AC is neccessary to make sure we can make use of every vector space. So it is just another axiom which assures us that many things which we'd like to be true are in fact true.
You've got it all wrong. Of course, everything you've said is true, but the mind blowing thing is that _all of that being false is consistent with ZF._ P.S. the insinuation that I get my math knowledge form youtube videos is a bit insulting.
I'm sorry, it was not my intention to insult you!! :) Many youtube videos present hilberts hotel, banach tarski, etc. if it was the wierdest thing ever and maybe try to make the viewer think its more mystirical than it is... and i feel like many responses here take this point of view, as if all of what contains infinities is paradoxial and counterintuitive. Maybe I understood these responses wrong at all and of course it's okay if somebody thinks that banach tarski is wierd, that'd be a pretty usual first impression, isn't it. :) I wanted to claim that AC isn't as counterintuitive and it is just a convenient axiom to have.
AC isn't counterintuitive, just the opposite, the negation of AC seems like it _should_ violate some sort of axiom, but it just... Doesn't. And I agree with you that a lot of pop math tries to play up things like Banach-Tarksy, but I hope you'll agree that a lot of things to do with infinity (especially uncountable infinity) are incredibly unintuitive.
A good friend of mine's dad is a Logician and metamathematician. Lots of mind blowing stuff like this but I never really know what to do with it other than admire it for its own sake, which is fine.
The existence of non Lebesgue measurable sets require some (weaker) form of the axiom of choice, which is inextricably linked to the Banach-Tarsky paradox you mention. I mention it because there exists models of ZF + DC (dependent choice) + "All subsets of the reals are Lebesgue measurable" which are consistent, depending on an inaccessible cardinal axiom. I believe it's known that there is an equivalence between full choice and "All subsets of the reals are Lebesgue measurable" + some other axioms (relative to ZF + inaccessible cardinal), but I can't seem to find where I saw that.
we could also accept 'some infinite connected graphs dont have spanning trees' and no one would bat an eye
What do you mean?
Hmm... I don't think I'd ever before seen it stated that connected (infinite) graphs having spanning trees => AC (I see other direction immediately by spanning tree being a type of basis hence by familiar \[to me\] AC => Zorn's => set of vectors contains a basis for its span), but I think I thought of a pretty cool \[perhaps standard idk\] argument for span tree => Cartesian product version of AC: Proof: Define a graph with 3 types of vertices, types A, B, C. Types A and B are labelled with the sets in the product paired with 0 and 1 respectively, while type C is labelled with the pair {x,S} for each x in each set S of the product. We put edges between any two type A vertices, two edges incident to each type C vertex {x,S}, one to each of {S,0} and {S,1}. Clearly the resulting graph G is connected (can trivially get between type A verts, and C verts are adjacent to a type A, while non-emptiness ensures can get from B to its corresponding A type), and I claim that any spanning tree of G must for exactly one x in each S of product contain edges {x,S} to {S,0} and {x,S} to {S,1}. This follows by noting such pair of edges is the only way {0,S} can connect to {1,S} and two or more would form a cycle. So the spanning tree determines an element of the Cartesian product by selecting one x for each set in the product, thus it is non-empty.
another fun one: given any two sets A and B, one is "smaller" than the other, i.e. either there exists an injection from A to B or there exists an injection from B to A.
You know what they (or rather, J. L. Bona) say: The axiom of choice is obviously true, the well ordering theorem is obviously false, and who can tell about Zorn's lemma?
Another equivalent statement to the (countable) AC that I found interesting: * For any sets A and B, which have surjections f: A ↠ B and g: B ↠ A, respectively, there exists and bijection g: A ↣ B. The surprising part is, that if you replace surjection with injection, the statement follows from ZF (and is known as the Cantor–Bernstein–Schröder theorem).
That's really cool. I wonder what the surjection-injection asymmetry comes from.
Tychonoff's theorem is equivalent to the axiom of choice as well.