Choose Your Paradox – the downside of the Axiom of Choice
billwadge.wordpress.com
billwadge.wordpress.com
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...
Intuitively, that's not "obviously" false to me.
Similarly, when I first encountered AC it wasn't obviously true 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.
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]
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.
> 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.
Further editing to clean up some minor errors.
No. It's ZF+Con(ZF)+not(con(ZF+con(ZF)). Which is, in fact consistent (assuming ZF is).
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.
Is that a typo? Shouldn't it be the other way around?
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.
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).
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).
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.
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".
Of the following three equivalent extensions to ZF:
* Axiom of Choice
* Zorn's Lemma
* Well-ordering Principle
"The Axiom of Choice is obviously true, the Well-ordering Principle obviously false, and who can tell about Zorn's Lemma?"