The way mathematics is taught it's easy to think that there's only one notion of truth and logical justification. For mathematics of finite objects that can be a very compelling story. Once you let infinity in, and you will because infinity is where all the fun's at, there are a multiplicity of concepts of truth.
The axiom of choice is an incredibly powerful statement about infinite objects in a system, namely logic, which is inherently finitary[1]. Any strong statements about how infinity works is going to imply bizarre things to us finite mortals.
For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre!
AC and not AC are both independent of ZF, which makes sense because ZF is an axiom system for reasoning about monstrously infinite objects. Stronger infinities are harder and harder to say anything about.
In a constructive mathematical universe (yet another notion of truth that's perfectly good), as usual, you have to be careful in how you state the axiom of choice. One formulation is a theorem and another implies law of excluded middle. The latter one ought to be considered the right importation of classical AC into constructive universes [2].
[1] There are infinitary logics but they don't magically allow you to perform infinite amounts of reasoning. All physically plausible logical reasoning is inherently a finite process.
>For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre!
Intuitively, that's not "obviously" false to me.
Similarly, when I first encountered AC it wasn't obviously true to me.
> Intuitively, that's not "obviously" false to me.
That's fair -- intuitions are pretty personal things. It is "obviously" false to me, and Bertrand Russell fairly well articulated the reason why by calling AC the "multiplicative axiom".
If you have sets A, B with 3 and 5 elements, respectively, the Cartesian product has 15 elements.
So, if we have an infinite series of sets, each with at least one element, I'd expect there to be something in the infinite Cartesian project just by multiplication -- the number of elements should (and I say "should" here to clearly denote my intuition) be in some sense the product of each of the individual numbers of elements. (I avoided the word "cardinality" here explicitly because I'm talking intuitively).
The idea that there's a collection of non-empty sets whose Cartesian product is empty is therefore akin to saying that you can multiply numbers bigger than zero and end up with a zero result.
Write down what it means for the Cartesian product of some collection of sets to be nonemtpy. You'll see that it's exactly identical to saying there's a choice function on that collection of sets.
Quote: "One possibility is to treat AC as a powerful drug and take it only when necessary. Theorems should come with consumer labels saying what went into them. So if you see a box on the shelf of 'Banach and Tarski’s Miracle Duplicator! Feed Multitudes!', it will say on the back of the box 'Contains AC'."
Indeed, many mathematicians are sensitive to this and try to point out when they invoke the Axiom of Choice, and there are other mathematicians who deliberately seek non-AC-powered variants of theorems in order to put them on less nebulous and more constructive ground.
Personally, I view AC as another reason to consider more generalized foundations of mathematics. For example, if you know anything about topoi, it turns out that we can view set theory as a topos on a point, and any topos on a complete Boolean algebra comes pre-equipped with an inherent axiom of choice! [0]
>But it also implies that ZF is consistent. This sounds nice, too, but is actually a disaster. It means that we can’t prove the consistency of AD with ZF (assuming the consistency of ZF).
I don't think this is strictly speaking correct. For instance, Con(ZF) itself trivially implies that ZF is consistent (which is literally what it says). But we can prove that ZF+Con(ZF) is consistent, assuming that ZF itself is consistent. (For that matter, we can prove that ZF+not(Con(ZF)) is consistent, again assuming that ZF itself is consistent. Don't ask.) So just because something implies Con(ZF) doesn't mean we can't prove that it plus ZF is consistent, assuming ZF is consistent.
If ZF is allowed access to Con(ZF) it can prove a great many things that ZF alone cannot, without generating any paradoxes, as far as I know.
I may be missing something, this always blows my brain.
Perhaps I'm naive, but doesn't that violate the incompleteness theorem? Surely you could only prove such a statement in ZF + Con(ZF) + Con(ZF + Con(ZF)) or something equivalent?
In regards to what you quoted, the incompleteness theorem says that because ZF is provable in AD+ZF then AD is not provable in ZF otherwise ZF would prove its own consistency.
You're not proving it formally, you're proving that if ZF is consistent, then that system is consistent as well.
> AD is not provable in ZF
That's not what it said. It said you can't prove the consistency of AD (presumably AD+ZF). But under the same conditions (assuming Con(ZF) that doesn't rule it out and definitely not for the reason it states.
Edit: a meta proof that ZF+Con(ZF) is consistent if ZF is consistent:
Suppose it wasn't consistent. Then ZF+Con(ZF) proves anything. But then we can prove not(Con(ZF) from ZF as well:
1. Assume Con(ZF)
2. Prove contradiction using ZF.
3. Therefore, not(Con(ZF)), proof by contradiction.
But if ZF proves that it isn't consistent, clearly it can't be consistent. But by assumption ZF is consistent.
Therefore, if ZF is consistent, so is ZF+Con(ZF).
I think this proof works but again, mind blowing material so I can never be 100%.
That means the model you're investigating isn't ZF+Con(ZF). It's ZF+Con(ZF)+Not(Con(ZF)) because you've added the extra axiom as part of your proof by contradiction. Obviously you trivially get not(Con(ZF)) from this model, let alone anything else via the principle of explosion.
ZF+Con(ZF)+Not(Con(ZF)) is not consistent and it shouldn't surprise you that you can use it to trivially derive contradictory results.
Ultimately, Godel's second incompleteness theorem says that you can't prove the consistency of a formal system within that system. The Wikipedia article is dense and awful to read but has a reasonably succinct statement of the theorem. https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
EDIT: "mind blowing material" - on that we can both agree. This is something I really wish I got to study more back in uni.
Of course! Thankyou, that makes me much more comfortable. ZF+Con(ZF)+not(con(ZF+con(ZF)) is an example of what's sometimes called the self hating theory, which is known to be consistent if ZF+Con(ZF) is consistent (you said much the same thing in your original comment). As it's known to be consistent, you can't apply the principle of explosion to produce Not(Con(ZF)).
EDIT: Obviously I'm not really the sort of person to talk about this stuff with you because of how much of a neophyte I am. Perhaps this lecture would make it clearer? http://www.scottaaronson.com/democritus/lec3.html
In particular, the excerpts:
The Second Incompleteness Theorem establishes what we maybe should have expected all along: that the only mathematical theories pompous enough to prove their own consistency, are the ones that don't have any consistency to brag about! If we want to prove that a theory F is consistent, then we can only do it within a more powerful theory -- a trivial example being F+Con(F) (F plus the axiom that F is consistent). But then how do we know that F+Con(F) is itself consistent? Well, we can only prove that in a still stronger theory: F+Con(F)+Con(F+Con(F)) (F+Con(F) plus the axiom that F+Con(F) is consistent). And so on infinitely. (Indeed, even beyond infinitely, into the countable ordinals.)
On the other hand, again by the Second Incompleteness Theorem, ZF can't prove its own consistency. If we want to prove Con(ZF), the simplest way to do it is to posit the existence of infinities bigger than anything that can be defined in ZF. Such infinities are called "large cardinals." (When set theorists say large, they mean large.) Once again, we can prove the consistency of ZF in ZF+LC (where LC is the axiom that large cardinals exist). But if we want to prove that ZF+LC is itself consistent, then we need a still more powerful theory, such as one with even bigger infinities.
Nope -- unfortunately, the voting analogy is a poor way to understand ultrafilters. Essentially, filters (a dual to ideals) are structures that tell you which subsets of a partially ordered set are "big", and ultrafilters are maximal filters. A pathological example that can help illuminate the idea is that of a principal ultrafilter ("on x"), which is all subsets of a partially ordered set containing x as a least element. The elements of the ultrafilter are the majorities, and their complements the minorities -- clearly the union of two sets not containing x will not contain x, and the intersection of two sets containing x will always contain x.
Choice gives you the existence of a nonprincipal ultrafilter, that is, a structure on the integers without a specific least element which correctly identifies all "big" subsets of the integers in a way that provides that the intersection of "big" sets is still "big". I'd highly recommend the treatment in Just and Weese if you're interested in learning more.
The other way around is already implied by the previous property.
Maybe it helps to consider finite sets. A finite set should clearly a minority, and the union of two finite sets, though bigger, is still finite; similarly, the intersection of two co-finite sets is smaller, but still co-finite. Minority and majority are generalizations of finite and co-finite, respectively. (A set is co-finite if the set of elements in some universe that it doesn't contain is finite).
I think you're right. For example, if you have U={A, B, C, D, and E}, then given minority m₁={A, B} and m₂={B, C}, m₁∩m₂={B} is also a minority. Given majority M₁={A, B, C} and majority M₂={B, C, D}, M₁∪M₂={A, B, C, D} is also a majority.
This should be clear in finite sets because |m₁∩m₂|≤|m₁|, while |M₁∪M₂|≥|M₁| (you can only make sets smaller or unchanged by intersecting them with other sets, while you can only make sets larger or unchanged by taking their union with other sets).
Note that this is a definition of majority/minority, not a theorem proved about them. It's indeed true that by definition, there are no majorities for finite sets.
I didn't quite understand your reply. Did you mean to say that there are no majorities for infinite sets?
Edit: It sounds elsewhere like the whole point of this may be the distinctive, counterintuitive properties of infinite sets (in this case especially under AC), but I'm continuing to be a bit confused by the presentation and context.
The article has taken the word "majority" and redefined it to be something counterintuitive, and only partly related to the standard use of the word majority.
A under "normal" usage, the words majority / minority have this property:
> The intersection of two minorities is a minority, and the union of two majorities is a majority
As the GP points out in his reply to my original comment, you can get this property from
>If a vote is held and the Ayes have it, and then any number of voters switch from Nay to Aye, the Ayes still have it
Now the author is redefining the terms minority and majority so they have this property:
> The union of two minorities is a minority, and the intersection of two majorities is a majority
But that's not possible unless you have infinite votes. As GP points out, it's clearest when you take "minority" to mean finite, and "majority" to mean "infinite, with finite opposition".
https://mathoverflow.net/questions/22990/choice-vs-countable...
The way mathematics is taught it's easy to think that there's only one notion of truth and logical justification. For mathematics of finite objects that can be a very compelling story. Once you let infinity in, and you will because infinity is where all the fun's at, there are a multiplicity of concepts of truth.
The axiom of choice is an incredibly powerful statement about infinite objects in a system, namely logic, which is inherently finitary[1]. Any strong statements about how infinity works is going to imply bizarre things to us finite mortals.
For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre!
AC and not AC are both independent of ZF, which makes sense because ZF is an axiom system for reasoning about monstrously infinite objects. Stronger infinities are harder and harder to say anything about.
In a constructive mathematical universe (yet another notion of truth that's perfectly good), as usual, you have to be careful in how you state the axiom of choice. One formulation is a theorem and another implies law of excluded middle. The latter one ought to be considered the right importation of classical AC into constructive universes [2].
[1] There are infinitary logics but they don't magically allow you to perform infinite amounts of reasoning. All physically plausible logical reasoning is inherently a finite process.
[2] https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e137...