Zermelo Fraenkel Choice

[@natepolidoro4565]

Great series. I was anticipating this video!

[@Kocomohouse]

At 12:20, in presenting Fraenkel's construction of a model of ZFA "without the axiom of choice", isn't it more accurate to call this a model of ZFA + (negation)AC rather than a model of ZFA - AC?

[@caspermadlener4191]

Not only isn't this a problem of rigour, but the negation symbol is Boolean algebra, not group theory.

[@mimzim7141]

Can you use the axiom of choice to construct the real numbers in the decimal framework: 0.12323322348... where you can make an independant choice for each of the decimals and repeat that as many times as you want and for each integer part? And reverse question. Dont you need the axiom of choice to get the real numbers since those real number are almost all uncomputable and can be obtained (i guess) only be infinite choice?

[@tomkerruish2982]

You don't need choice to construct the reals from the rationals. Dedekind cuts are a popular option, although I prefer equivalence classes of Cauchy sequences.

[@mimzim7141]

@@tomkerruish2982 how do you find a dedekin cut or a cauchy sequence for an uncomputable real?

[@tomkerruish2982]

@mimzim7141 Well, you can't, explicitly, by definition. What you can do is simply take the set of all cuts (or equivalence classes) and show that it satisfies the axioms for the set of real numbers (complete ordered field). It can then be shown that any two sets satisfying the axioms are isomorphic to each other, which essentially means that there is only one set of reals. You can then show such cuts must exist by the same methods used to show such numbers exist in the first place

[@williamzame3708]

The Axiom of Dependent Choice (sometimes called the Axiom of Countable Dependent Choice) is only powerful enough to deal with analysis in *separable* spaces. For example, it is enough to prove the Hahn-Banach theorem for *separable* Banach spaces but not for spaces such as L^\infty, which are not separable.

[@moshecallen]

A statement is made in the video which seems to say that the Axiom of Choice is equivalent to an axiom that the Cartesian product of sets is empty if and only if at least one of the sets in the product is empty. Is this a correct understanding? Why is an axiom of choice preferred to this formulation, as it seems to be?

[@billh17]

Moshe Callen asked "Why is an axiom of choice preferred to this formulation, as it seems to be?" One reason would be that you don't have to define Cartesian product (and ordered pairs) in order to state the axiom.

[@martinepstein9826]

No real reason. A member of the Cartesian product A1 x A2 x A3 x... is a sequence (a1, a2, a3, ...) which is just the function mapping 1 -> a1, 2 -> a2, 3 -> a3, ... which is a choice function on {A1, A2, A3, ...}. So it's easy to see the equivalence.

[@MikeRosoftJH]

@@martinepstein9826 Sure, but that will only give you countable choice. If you want to state the full axiom of choice in terms of a Cartesian product of an arbitrary collection of sets, one could do it as follows: Let I be an index set. Let i(•) be a function whose domain is I (this function defines the sets whose Cartesian product we want to do; the reason for the roundabout definition is that we may want to do a product of a set with itself, like A×A - a set can be repeated in the collection). Then Cartesian product of the sets i(•) is the set of all functions f from I, such that for all x∈I, f(x) is an element of i(x).

[@James-kg8fp]

Fantastic series on the axioms! Are any model theory videos on the way? I'm interested to know more about models. It seems like a delicate area, since models seem to be sets, do model theory proofs themselves still use ZFC as the underlying system?

[@billh17]

James asked "do model theory proofs themselves still use ZFC as the underlying system?" On the newsgroup sci.logic long ago, one logician seems to say that this is the case. At least, that was my understanding of his comment.

[@skallos_]

Do you have further resources on the Axiom of Choice for n element sets?

[@pmcate2]

If I am not mistaken, the axiom of choice for finite sets can be proven form the other axioms. It is only necessary for infinite sets.

[@skallos_]

@@pmcate2 I'm referring to the part mentioned at the end of the video. Axiom of Choice for 2 element sets can imply Axiom of Choice for 4 element sets, but not 3 element sets.

[@fnbk2]

"AXIOM OF CHOICE FOR FINITE SETS." by Andrzej Mostowski

[@skallos_]

@@fnbk2 Thanks! I'll take a look.

[@MikeRosoftJH]

@@pmcate2 Axiom of choice for a finite collection of arbitrary sets is a theorem of ZF; it's a consequence of the principle of induction (which follows from how natural numbers are defined in set theory). But axiom of choice for an infinite collection of finite sets is not - it's consistent that there exists a countably infinite collection of two-element sets, which doesn't have a choice function.

[@linorum]

9:00 Defining definability turns out to be a quite tricky problem.

[@caspermadlener4191]

Why are there people who reject this AC? They have no choice! Honestly, as long as it is still being consistent, mathematics should always strive to be as powerful as possible. Having an elementary proof is second priority. I often even prever non-elementary proofs, since they are often very interesting.

[@cgibbard]

There are two kinds of power though: there's power through specificity, where you're able to prove more results about fewer things by way of making more assumptions, and there's power through generality, where you might prove fewer things, but be able to interpret your results in more settings. So there's a balance to be struck in choosing your axioms.

[@weierstra5326]

Horrors with and without the Choice!!

[@annaclarafenyo8185]

The axiom of choice isn't controversial because it's somehow less obvious then other axioms, it's rather because it's obvious that the real numbers can't be well ordered, so Zermelo's proof must be wrong. Brouwer was trying to popularize intuitionistic logic, and there the principle of excluded middle was the thing creating non-constructive proofs, so he searched for a non-constructive principle Zermelo was using which looked like excluded middle, and found choice. It was like excluded middle uncountably many times, because in the choice-function construction, you are using that each set is either empty, or has an element, i.e. excluded middle. So that's what Brouwer focused on like a laser, ignoring everything else, and that's what people accepted as the main issue in the proof, at least at first. While this is partly true, removing choice does leave a system which is closer to intuition, it's not really what is going wrong at all, not from a philosophical point of view. But this is why choice became controversial, it was seen as excluded middle on steroids. But excluded middle is really fine, in more careful examination of intuitionistic logic, it just gets shoved up to the double-negation level. So if you just redefine 'classically true' to mean 'double-negation true', then classical logic sits inside intuitionistic logic, intuitionistic logic is simply more nitpicky about the details. The idea is that excluded middle is still satisfied in a weaker sense at a higher level of reflection, so if you reflect transfinitely many times, you should have the axiom of choice also. To see what's REALLY going wrong with Zermelo's proof, you need to look at the guts. To show R can be well-ordered, first pick an element from every nonempty subset of R (choice), then start a transfinite induction by associating to the first ordinal 0 the element you picked corresponding to the subset R of R, then for any ordinal A, you take the union of all the elements associated to ordinals less then A and remove them from R. If there's nothing left, you're done, R is well ordered. If not, you continue the transfinite induction using the element you chose from the remainder of R. There's now only two ways for this induction to end. You either run out of ordinals, or you finish well-ordering R. In the real world, you always run out of ordinals before you ever well order the real numbers. This is why Cohen says that the continuum should be seen as bigger than any infinite completed totality, it is easy to stuff an entire universe of any first order theory inside the real numbers. But in a set theory, unlike in reality, you obviously can't run out of ordinals, because if you did, then all possible well-orderings defined over R would bound all the ordinals. This means that you could define the set of all ordinals using separation over the powerset of R with well orderings defined on these (the well-orderings would involve higher powersets of R). Since there can't be a set of all ordinals, QED. That last proof by contradiction is the heart of the problem, not the choice step. To avoid Zermelo's conclusion, it is essential to no longer think of R as a set, but as a proper-class which can bound all ordinals. If one comes to this conclusion, you simply renounce uncountable sets in your theory, and you declare a 'set' to be a collection of integers (or textual names). This point of view I believe resolved the choice issue in most people's minds in the 1920s, as Hilbert's school moved away from defining set theory in the Cantor and Zermelo way, towards explicitly defining countable collections in the Grundlagen's second order arithmetic. Second order arithmetic is a proper foundation, in that it is a clear reflection of first order arithmetic using a principle of set collection which is itself does not leave the realm of absolute truth. The only issue with a countable foundation like second-order arithemetic is that it is obviously weaker than ZFC, or even just Z, because you can prove the consistency of second order arithmetic in Z. Further, there are extensions of ZFC by inaccessibles, Mahlos, an 'measurables' which make systems which are vastly stronger. Those need a translation to the real world of second-order arithmetic, preserving all their power. Nobody will ever give up proof strength for any reason, and nobody should have to. There is no reason to sacrifice proof strength, in fact, one must strive for EVEN MORE proof strength than what is provided by extensions of ZFC. Those are limited in ways that actual mathematical truth cannot be. You simply need to reformulate the axioms of higher infinity, powerset, then inaccessibles, then Mahlo's, then measurables, inside the language of second-order arithmetic. The first step is to reformulate powerset. I believe the appropriate axiom is "the axiom schema of models of function types"--- for every collection of function types (defined by a second-order set of names of types definable in the theory), there exists a model of second-order arithmetic (a set of names) which is deductively closed to including all names for all functions of these types. I believe this axiom is equivalent to powerset, if not, it should be possible to tweak it to make it equivalent, as it is doing an equivalent thing. It is defining iterates of powerset as function types by matching to already existing countable sets, then it is (automatically) cutting down to a countable model by Skolemization. You don't even need to say that, because the sets are always countable in second order arithmetic. For inaccessibles, I believe you just repeat the same idea for typed SOA, now you speak about models of tSOA in the axiom schema. Iterating the idea, you should get to Mahlos. Measurables need a new idea. This probably should be formulated as (countable) sets defining (countable) elementary embeddings of models into models. I don't know enough to know how this should work in detail. The usual measurable is just used to define an ultrafilter for an ultraproduct model and the consequences of strength come from the associated elementary embeddings. These activities of defining higher models should never get stuck at any point, there should always be new principles of higher infinity that are consistent. The set theory procedure has been stuck at Reinhardt cardinals for nearly 50 years, with no new progress at all, probably because Reinhardt cardinals are powerful enough to reach a contradiction for choice/powerset schema. When people reached such a contradiction step for V=L at measurables, they threw away V=L. Now it's time to throw away choice-powerset.

[@gunhasirac]

Thank you for your comment! It’s very interesting to see that validity of axiom of choice actually have something to do with the continuum hypothesis. Although it is not all that clear to me how “Reals is well-ordered” is obviously false and why should we always run out of ordinals, it does look suspicious how the proof ends. It almost look like the result was forced by assuming the induction will end. I do not understand any of the rest but these looks very interesting indeed.

[@Suav58]

Why can't I see anybody criticising the finitists, then? Why protagonists on the side of infinity do not bluntly pin down the limitations of finitistic approach? Is there a chance of some reasonable mathematical theory of learning emerging, as I hear, that the statistical theory of learning seems not to be able to explain effectiveness of its own machine implementations? To my eyes, there is a huge problem behind these questions. It might be the case, that we are cutting off the branch, on which we are sitting, namely prohibiting access of the young generation to the body of ideas and methods for which we have no replacement.

[@mariogamer1088]

Did you read a few of Nik Weaver's papers? If I recall, he has some trouble with powerset (although generally also "strongly prefers" predicativism, where I word it like that because I don't want tot say anything dumb about his views). It's not necessarily that he thinks ZFC is inconsistent (see this thread of math stack exchange: mathoverflow.net/questions/437195/does-anyone-still-seriously-doubt-the-consistency-of-zfc and see his answer). And I'm going to stop here before I say some stupid thing.

[@roys4244]

One question that occurs from this lecture and that on the Infinity axiom is the role, if any, of the axiom of choice in ZFC-- Infinity (+¬ Infinity). Is this theory equivalent to ZF-- Infinity (+¬Infinity)? The models in ZFC--Inf were Hereditary Finite sets. Can a choice function play a role here? Does the Godel-Cohen proof reduce down to a ZF--Inf version? Maybe a choice function only plays a role amongst the non-standard models of ZFC--Inf?

[@thephysicistcuber175]

You should make videos on mathematical logic and model theory.

[@justinshin2279]

Axiom of Choice is not named because it’s the favorite axiom

[@joshforevergreen]

Fire

[@sachalucienmoserferreira2233]

Thanks for share with us our knowledgment!

[@newtonswig]

Wow! Did not know the constructable heierarchy could do the choice nasties! That reads like a moral victory for choice in my book. Does anybody know if the contradiction on measurability comes from the same route as Vitali? (ie. we find a set which must simultaneously have measure 0 and infinity) If so, it sounds like a decisive moral victory- If the problem is the sets we are picking from (rather than some technical issue to do with sigma algebras?? Cf my earlier question), we surely expect (if we assume 1st order logic) the constructable universe to be a sort of shadow, soundly modelling the putative ‘platonic set theory’. Otherwise we are saying that maths can’t track reality, right, because when we’re actually looking at examples of things, we’re looking in the constructable universe.

[@emilyliedtke7059]

Vitali is literally where this comes from - you can only show the existence of Vitali sets by using the axiom of choice

[@migarsormrapophis2755]

yeeeeeeeeeeeee

[@tranehigh]

Several other books that I don't have *yet* 😂

[@yuitocheng4971]

|X*X|=|X| for infinite X is equivalent to axiom of choice but |X+X|=|X| is not

[@additionaddict5524]

Really wish KZbin wouldn’t default to the lowest quality on math videos

[@cycklist]

It doesn't.

[@probablyshadman]

Sir, please make a series about (transition from calculus to real analysis for beginners) with all the prerequisites(logic, set theory) A request from Bangladesh.

[@NewCalculus]

What a load of rubbish. Set theory is not mathematics. It's anti-mathematical BS.

[@hengzhou4566]

Any math instruction is pointless and just a waste of time without exercise. Simply talking about existing theorems and their proofs makes no sense. I expect discussion on problems and extra exercises with keys.

[@user-ct1ns6zw4z]

Hilariously entitled comment

[@jb31842]

@@user-ct1ns6zw4z The discussion of the theorem is itself the exercise