Thread: Axiom of Choice Question (Basic)

My name is Annatala. I'm a graduate student in computer science, and in my spare time I study Set Theory for fun (I'm weird).

I've been slooooowly going through Jech's wonderfully dense Set Theory book, with occasional Wolfram and/or Wikipedia reference. I have a question about AC that I'm not quite certain about, despite how simple it is. (I insist I have a fairly good understanding of basic set theory despite how stupid I'm about to sound!)

I'm curious why AC is not trivially true. I'm not asking for Cohen's forcing proof of ZF+ AC; I'm asking for something much simpler.

Let's say we have a countably infinite family of nonempty sets S = {A, B, C, ...} and want to show a choice function f exists where f = { (A, a), (B, b), ... }, with a being an element of A, etc. Clearly, if f exists, f S S. Since this Cartesian product must include every possible combination of S and the elements of the elements of S, it seems "intuitively true" that a satisfactory f must be one of these combinations. But we cannot deduce its existence when S is not "well-orderable", even if all sets X in S have cardinality 2 (unless, that is, we already have a constructive way to select from each X).

Even weirder, I hear tell that AC is equivalent to the statement: "the Cartesian product of any family of nonempty sets is nonempty". This is rather mind-boggling as the Cartesian product is well-defined with a simple formula, and the only way (again, intuitively) you can get an empty product is if one of the sets is empty.

My best guess about all this is that perhaps it is because ZF does not admit as sets collections which cannot be constructed via separation. Is this the right track? And wouldn't this make the Universe rather...well, tiny?

If this is the case, it certainly makes downward Lowenheim-Skolem straightforward to grasp!

Anyway; any advice, pearls of wisdom, or Pinkie Pie references are greatly appreciated. Thanks!

Anna

Originally Posted by Annatala

I'm curious why AC is not trivially true.

There is a distinction between "true" and "provable in ZF".

It is not the case that AC is provable in ZF.

Meanwhile, there are two senses of "true" we would consider in this question. One is that of a formal notion of truth, i.e. "true in a given model of ZF". The other is that of an informal notion of what is basically true about sets. As to the formal notion, AC is true in some models of ZF and AC is false in other models of ZF. As to the informal notion, many people DO consider AC to be quite apparently true. Yet, (probably) a small percentage of mathematicians consider AC to be false (note that in set theory without the logical principle of excluded middle, AC implies the principle of excluded middle).

Originally Posted by Annatala

I'm not asking for Cohen's forcing proof of ZF+ AC

What Cohen proved is that ZF+~AC is consistent, i.e., that there is a model of ZF+~AC. That is, there is a model in which all the axioms of ZF are true while AC is false. So Cohen proved that AC is not provable in ZF.

Originally Posted by Annatala

ZF does not admit as sets collections which cannot be constructed via separation.

ZF has also the axioms of union, power, infinity, and schema of replacement by which to prove the existence of certain sets.

Originally Posted by MoeBlee

There is a distinction between "true" and "provable in ZF".

I understand the difference, I'm just not used to discussing it. I meant "provable under ZF". :P

Originally Posted by MoeBlee

ZF has also the axioms of union, power, infinity, and schema of replacement by which to prove the existence of certain sets.

Of course. Let me try to rephrase my question because I'm still not entirely getting at what I want to (although I think I do know the answer now):

I understand that ZF CC is false. If my interpretation of this is correct, the only sets which must exist in a model of ZF are those we can derive from ZF in a "constructive"(?) manner.

If all we have is ZF, wouldn't that imply there need exist only a countable number of sets under Set Theory? There are only a countable number of formulae we can apply to Separation/Replacement. It would still need to be true that there exists no surjection from ℕ to ℝ, so that must be one of those non-constructible sets.

Is my intuition on this right? It seems like the Universe of sets implied by ZF is much smaller than I had imagined. This should presumably apply to ZFC as well.

Follow-up: Is there an axiomatization of Set Theory that is known to admit no countable models?

Anna

Originally Posted by Annatala

the only sets which must exist in a model of ZF are those we can derive from ZF in a "constructive"(?) manner

The problem there is that it's not clear what it means to say "MUST exist" [emphasis added].

I would suggest first looking at it very basically (and throughout I'll use the tacit assumption that ZF is consistent):

As you know, ZF has many models, and in some of those models, AC is true and in other of those models, AC is false.

Also, given ANY set S, that set is a member of some model of ZF.

And in some of the models of ZF the symbol 'e' [for epsilon here] might not be interpreted as membership. In such models, we can't necessarily take AC, or any theorem of ZF, to "assert" what we ordinarily take it to assert as we "read off" the theorem in ordinary conversation.

Meanwhile, ZF proves many existence theorems, which are theorems of the form ExP where P is a formula ['E' here standing for the existential quantifier]. For each such existence theorem, and each model of ZF, there is a member of the universe of the model such that P is true, per that model, of that member. But for ANY set there is a model in which P is true of that set.

Originally Posted by Annatala

If all we have is ZF, wouldn't that imply there need exist only a countable number of sets under Set Theory?

What does it mean to say "there NEED exist only"? To be clear about all this, I would suggest formulating such questions in rigorous mathematical terms. It's too vague, at least for me, to talk about what "needs" to be.

Originally Posted by Annatala

There are only a countable number of formulae we can apply to Separation/Replacement.

Yes, so there are only countably many existence theorems. But that does not entail that a given model of ZF may have only countably many members in the universe of the model.

Originally Posted by Annatala

It seems like the Universe of sets implied by ZF is much smaller than I had imagined.

The problem there is it is not clear what is meant by your definite description "THE universe of sets impied by ZF".

First, what does it mean to say "a certain set is implied by ZF" or even "the existence of a certain set is implied by ZF". ZF proves existence theorems. Those are sentences of the form ExP, and given a model of ZF, there is a member of the universe of the model such that P is true, per that model, of that member. But given such a model, and any set, there is another model in which P is true of that set.

Second, there is no "the" universe of sets implied by ZF, since there are many different models of ZF each with a different universe from another.

Originally Posted by Annatala

Is there an axiomatization of Set Theory that is known to admit no countable models?

I think you mean is there a set theory that has no countable model? Well, what is "a set theory"? As long as it's a theory that has an infinite model, then, by downward Lowenheim-Skolem, it's a theory that has a countable model.

Originally Posted by Annatala

I understand that ZF CC is false. If my interpretation of this is correct

Did you mean 'AC' for axiom of choice or 'CC' for countable choice? In any case what it means to say:

It is not the case that G |= S

is that there is a model in which all the sentences (we'll confine to sentences, not formulas in general, for convenience) in the set of sentences G are true but in which the sentence S is false.

If you try to go past that basic meaning to some other conclusion, then you need to be very careful that you're not slipping in some unwarranted assumptions or non-defined rubric.

Originally Posted by MoeBlee

The problem there is that it's not clear what it means to say "MUST exist" [emphasis added].

I apologize for my unclear use of terminology. Can you tell I'm mostly self-taught? (Yeah, I took three 600-level classes for a Theory minor, but it's kind of a blur.)

I guess the bright side of all this is that despite my lack of clarity you seem to be tracking reasonably closely to my intent.

Originally Posted by MoeBlee

Also, given ANY set S, that set is a member of some model of ZF.

Er, now I'm confused again. How can you be "given a set" without a model? I can describe sets for which no existence proof is true in any model of ZF, assuming ZF is consistent (irregular sets, the set of all cardinals, etc). So I wouldn't say "any set is a member of some model of ZF", exactly, and I'm not quite certain what that means. I recognize I may not be fully grasping the correct relationship between a theory and its models.

Originally Posted by MoeBlee

And in some of the models of ZF the symbol 'e' [for epsilon here] might not be interpreted as membership. In such models, we can't necessarily take AC, or any theorem of ZF, to "assert" what we ordinarily take it to assert as we "read off" the theorem in ordinary conversation.

I didn't think the symbol used in the model was important as far as the isomorphism of models is concerned, but membership has to have a symbol because all of the axioms refer to it. Can you clarify?

Originally Posted by MoeBlee

What does it mean to say "there NEED exist only"? To be clear about all this, I would suggest formulating such questions in rigorous mathematical terms. It's too vague, at least for me, to talk about what "needs" to be.

First, what does it mean to say "a certain set is implied by ZF" or even "the existence of a certain set is implied by ZF". ZF proves existence theorems. Those are sentences of the form ExP, and given a model of ZF, there is a member of the universe of the model such that P is true, per that model, of that member.

When I talk about the existence of a certain set, I mean that every model consistent with ZF proves x , where is a well-formed formula under first-order logic in which only x is unbound.

Originally Posted by MoeBlee

But given such a model, and any set, there is another model in which P is true of that set.

Wait. You mean x x is true of all sets in some consistent model?

Originally Posted by MoeBlee

Second, there is no "the" universe of sets implied by ZF, since there are many different models of ZF each with a different universe from another.

Right, I understand this part very well. When I say "sets that must exist" I mean "sets for which an existence proof exists in ANY model of ZF which is consistent". For example, ZF ( x | x = { }). The empty set exists in any model of ZF (Infinity proves some set exists; apply separation to x x).

I understand my language is imprecise, but hopefully you have the ability to see what I'm trying to say!

Originally Posted by MoeBlee

I think you mean is there a set theory that has no countable model? Well, what is "a set theory"? As long as it's a theory that has an infinite model, then, by downward Lowenheim-Skolem, it's a theory that has a countable model.

Really? I thought that only held for first-order theories.

Originally Posted by MoeBlee

Did you mean 'AC' for axiom of choice or 'CC' for countable choice?

I meant CC. I was trying to back off to the simplest example (in a sense).

Originally Posted by MoeBlee

It is not the case that G |= S

is that there is a model in which all the sentences (we'll confine to sentences, not formulas in general, for convenience) in the set of sentences G are true but in which the sentence S is false.

So (A B) A B. Got it.

Originally Posted by MoeBlee

If you try to go past that basic meaning to some other conclusion, then you need to be very careful that you're not slipping in some unwarranted assumptions or non-defined rubric.

I agree. Eventually I want to know this stuff like the back of my hand, so it's important for me to learn to be precise.

I think I'm a little rusty on the basics of model theory. Is there a source I can go to you would recommend? I hate to keep bothering you, though you have been most gracious.

Anna

Originally Posted by Annatala

Can you tell I'm mostly self-taught?

Of course that's okay. I'm pretty much self-taught also. And I'm not an expert at all. At a certain point, not far from this level of discussion, I have to say that I'm not qualified for those more advanced matters.

How can you be "given a set" without a model?

I don't mean 'given' in any special sense. I could have said, "For all S" instead of saying "given a set S".

I can describe sets for which no existence proof is true in any model of ZF

I don't know what is meant by "proof true in a model". What are true or false in a model are sentences. The sentences in the language of ZF that are true in every model of ZF are exactly the theorems of ZF. The sentences that are not true in any model of ZF are exactly the negations of theorems of ZF. The sentences that are true in some models of ZF but false in other models of ZF are exactly the sentences that are independent of ZF.

assuming ZF is consistent (irregular sets, the set of all cardinals, etc)

ZF proves the theorem "~Ex x is irregular", but that does no preclude that there is a set theory T other than ZF to serve as a metatheory regarding ZF such that in T we prove that that there is a model of ZF and such that one of the members of the universe of the model is an irregular set. (2) You refer to "the set of all cardinals", but in what theory do you prove "Ex(x is a set & Ay(y is a cardinal -> y in x))"? Of course, though, in certain theories, such as NBG, we prove ExAy(y is a cardinal -> y in x) but we still don't prove in NBG "Ex(x is a set & Ay(y is a cardinal -> y in x))".

So I wouldn't say "any set is a member of some model of ZF", exactly, and I'm not quite certain what that means.

Let's agree for our purposes at hand that we have some set theory T that we're using as a metatheory in which to prove things about the object theory ZF. Now, in a reasonable T, it we can prove "If ZF has a model, then for any S, there is a model M of ZF such that S is a member of the universe for M". It might be a highly unusual model in which 'e' is not interpreted as membership on the universe, but still it is a model of ZF.

I didn't think the symbol used in the model was important as far as the isomorphism of models is concerned,

I'm not referring to a symbol used in a model except that 'e' (or whatever typographical representation) is a primitive 2-place relation symbol of the language of ZF.

but membership has to have a symbol because all of the axioms refer to it. Can you clarify?

'e' is just a symbol. We don't have to interpret 'e' as membership on the universe of the model. There are models of ZF in which 'e' is not interpreted as membership on the universe but rather 'e' is interpreted as some other binary relation on the universe.

When I talk about the existence of a certain set, I mean that every model consistent with ZF proves x , where is a well-formed formula under first-order logic in which only x is unbound.

(1) By "model consistent with ZF" mabye you mean "model OF ZF". Further, I would say that ZF proves there exists a set having a property described by 'P' (or 'phi' or whatever). ZF is a theory, which is a syntactical thing, a certain set of sentences, the theorems. Among the theorems are those of the form ExP(x). Then, as to semantics, any model of ZF must be such that ExP(x) is true in that model. But the meaning of 'P' per that model might not come out in the way we ordinarily "read it off", since 'e' might be interpreted per the model in a radically different way from the membership relation on the universe of the model.

You mean x x is true of all sets in some consistent model?

Of course not. Given that we use the standard semantics for '=', there is NO model in which ~x=x is satisfied. What I said (and this is in a reasonable metatheory for ZF):

For any S, and any model M of ZF, there exists a model M* of ZF such that S is a member of the universe of M*.

When I say "sets that must exist" I mean "sets for which an existence proof exists in ANY model of ZF which is consistent".

(1) I don't know what is meant by "a proof exists in a model". (2) Models aren't things we talk about as being consistent or not consistent.

I thought that [Lowenwheim-Skolem] only held for first-order theories.

ZF is a first order theory. (There are higher order versions of ZF too, but when we say 'ZF' without qualifying, we mean the first order theory.)

So (A B) A B.

No, I'm not saying that at all. Go back to exactly what I said:

"It is not the case that G |= P" means "There is a model of G that is not a model of P".

That is VERY different from saying:

If it is not the case that G |= P, then G |= ~P.

Is there a source I can go to you would recommend?

If your basic first order predicate logic skills are in good shape, I'd go to Enderton's 'Elements Of Set Theory' supplemented by Suppes's 'Axiomatic Set Theory'. Then I'd got to Enderton's 'A Mathematical Introduction To Logic' (make sure to get the errata sheets at his (now posthumous) web site).

If you first need to brush up on your predicate logic skills, I'd go to 'Logic: Techniques Of Formal Reasoning' by Kalish, Montague, and Mar.

I hate to keep bothering you

You're not bothering me. But, yes, I do think you need to get a more clear understanding of the fundamentals.

Thank you! This has been very illuminating. My understanding of predicate logic is sufficient, but I need to review Enderton's Elements for information on models. I own it and was planning on returning to it after my obviously perplexity arose in this conversation regarding models.

I enjoy using Jech's thick book as a resource for Set Theory facts, but it's a very slow and dense read, and it presupposes the reader is already well-equipped with model theory. Fortunately, it doesn't address models directly until Chapter 12, which is far past where I'm lingering as I'm trying to solve each problem using only the information provided "so far" (which has been fun and very educational; it's good to see what can be shown without CC and how, for example). But yeah, Jech is not a good first resource.

Thanks tendered.

Anna

Originally Posted by Annatala

Enderton's Elements for information on models

He does talk about inner models in that book, for the basics of models, go to his 'A Mathematical Introduction To Logic'. Also, one might consider the "bible" of model theory to be 'Model Theory' by Chang & Keisler. But for beginning and basic purposes, I'd do with Enderton first.

Yeah, Elements is not at all the book I thought it was. It's way below my level; I already know everything this book is trying to teach me, and I do not particularly like the informal nature of its discussions. I'm not sure why I have it, because I'm certain it's not one I used in my classes. I probably purchased it for one of the theory classes as a supplemental reference and never needed it.

As luck would have it, I also have A Mathematical Introduction to Logic, and I think this is the book I remember that covered these topics. I'll keep Model Theory in mind for later, but Enderton may suffice for the background I need to get through the first section of Jech.

Anna