The Axiom of the Power Set

[dmuthuk]

Hey everyone,

I am currently trying to learn a bit of set theory from Halmos' book "Naive Set Theory" since I have recently been concerned with the general notion of existence in various fields of mathematics.

Now, I am reading the "axiom of the power set" and I do find it a little troubling because I think that it might be possible to derive the existence of the power set from the axiom of specification (forming subsets), axiom of unions, axiom of pairing, and axiom of extentionality. So, I know have definitely gone wrong somewhere. Can someone help me find a flaw in the following argument:

Let E be a set. Each subset x of E exists by the axiom of specification. Then, each singleton set {x} exists by the axiom of pairing. By the axiom of unions, the union of this collection of singleton sets, each containing a subset of E as its only element, exists as a set. So, this is our desired power set. [QED]

Aside from this, I was wondering if anyone knows how to interpret the primitive relations of "equality" and "set membership" between any two sets. Can we think of these as "relations" on the set of all sets (which does not exist technically)?

Thanks,

Dilip

 

[AKG]

How do you know that the collection of singleton sets exists?

 

[dmuthuk]

Well, we know by the axiom of pairing that given any two sets x and y, there exists a third set {x,y}. We can always assume these sets are equal, can't we? Then, we can say that given any set x, {x,x} exists which is simply {x}.

 

[dmuthuk]

Oh, sorry, I think I misunderstood your question. When I say collection, I am not treating this collection as a set just yet. We can always consider a "collection" of sets, I assume. So, for instance, we have the collection of singleton sets , {x}, {y}, and {z}. The axiom of unions says that the set {x,y,z} exists.

 

[Hurkyl]

Oh, sorry, I think I misunderstood your question. When I say collection, I am not treating this collection as a set just yet. We can always consider a "collection" of sets, I assume. So, for instance, we have the collection of singleton sets , {x}, {y}, and {z}. The axiom of unions says that the set {x,y,z} exists.

The union of a collection of sets is merely a collection; you cannot assume it is a set.

This is desired behavior -- the union of the collection of all singleton sets is the collection of all sets. If we could prove that was a set, then we could derive a contradiction via Russel's paradox.

The axiom of union says that the union of a set of sets is a set.

 

[honestrosewater]

Aside from this, I was wondering if anyone knows how to interpret the primitive relations of "equality" and "set membership" between any two sets. Can we think of these as "relations" on the set of all sets (which does not exist technically)?

If you are perched above in some meta-structure, meta-theory, or meta-whatever, sure, the identity and membership relations are relations on your domain (the set or class containing all of the individuals in your structure).

All of your axioms and the rules that you use to prove things from them make up a set theory. And the world of objects that you consider as existing and being related to each other in ways described by your set theory make up a mathematical structure of sets.

Mathematical structures are studied in model theory, and the usual definition of a structure is simply a set (your domain) with some relations and operations on it, relations and operations having their familiar definitions. You can also allow the domain to be a proper class rather than a set, as I have seen done specifically when defining a structure of sets. In that case, some of your relations might also have to be considered proper classes. But I have never bothered to understand the technical reasons for this (it strikes me as superfluous, but what do I know), so I can't help you there.

 

[dmuthuk]

The union of a collection of sets is merely a collection; you cannot assume it is a set.

This is desired behavior -- the union of the collection of all singleton sets is the collection of all sets. If we could prove that was a set, then we could derive a contradiction via Russel's paradox.

The axiom of union says that the union of a set of sets is a set.

Thanks for clarifying this. I didn't realize that the collection of all singleton sets {x} where x is a subset of E, has to be a set in order to apply the axiom of unions. So, I guess I had misunderstood this axiom (i.e. collection=set). Thanks, again.

 

[Hurkyl]

Thanks for clarifying this. I didn't realize that the collection of all singleton sets {x} where x is a subset of E, has to be a set in order to apply the axiom of unions. So, I guess I had misunderstood this axiom (i.e. collection=set)Thanks, again.

Incidentally, I would avoid the word "collection" if I could -- the word set and class are fairly well established. Every set is a class, and a proper class is a class that is not a set.

The word "collection" isn't standardized (as far as I know) -- one has to guess if you are using it to mean set or class. I'm assuming you are using it to mean class. (So I continued with that terminology)

 

[AKG]

Thanks for clarifying this. I didn't realize that the collection of all singleton sets {x} where x is a subset of E, has to be a set in order to apply the axiom of unions. So, I guess I had misunderstood this axiom (i.e. collection=set). Thanks, again.

You define the union of a class x to be the class

$$\cup x =_{def} \{y\ :\ (\exists z \in x)(y\in z)\}$$

The union axioms then says $(\forall x)(\exists y)(y = \cup x)$. You're trying to use this axiom by letting x be the collection of singletons, which will make y the power set. But when you see $(\forall x)$ in set theory, it means "for all sets x" so you can only apply this axiom when x is a set. The union axioms says that the union of every set exists (and in set theory, to exist means to be a set), not that the union of every class exists. That would be absurd. In particular, it would imply that a universe exists, i.e. there exists a set containing all sets. And you know this to lead to the classical paradoxes of naive set theory.

 

[dmuthuk]

If you are perched above in some meta-structure, meta-theory, or meta-whatever, sure, the identity and membership relations are relations on your domain (the set or class containing all of the individuals in your structure).

Mathematical structures are studied in model theory, and the usual definition of a structure is simply a set (your domain) with some relations and operations on it, relations and operations having their familiar definitions. You can also allow the domain to be a proper class rather than a set, as I have seen done specifically when defining a structure of sets. In that case, some of your relations might also have to be considered proper classes. But I have never bothered to understand the technical reasons for this (it strikes me as superfluous, but what do I know), so I can't help you there.

I haven't studied "classes" yet, but I assume they are pseudo-sets of a sort that fail to be sets becuase they violate some axiom? For example, is the universal "set" and the "set" of all sets that are not members of themselves classes? And, so the functions and relations that are defined on these classes (which we usually think of as subsets of cartesian products) are now classes as well, I assume.

 

[Hurkyl]

I haven't studied "classes" yet, but I assume they are pseudo-sets of a sort that fail to be sets becuase they violate some axiom? For example, is the universal "set" and the "set" of all sets that are not members of themselves classes? And, so the functions and relations that are defined on these classes (which we usually think of as subsets of cartesian products) are now classes as well, I assume.

A class is indeed formally similar to a set. The simplest description is that a class is something defined by a logical formula. For example, the class of singleton sets:

x in SingletonSet iff there exists a y such that x = {y}.​

We usually use the set-builder notation for classes too:

SingletonSet := { x in Set | There exists y such that x = {y} }.​

The axiom of replacement works for classes and logical functions, so you can write it in the simpler fashion:

SingletonSet := { {x} | x in Set }.​

But note that we cannot carry out Russell's paradox: we can form the class

Russell := { x in Set | x is not in x },​

but all we can prove is that Russell is not a set, and thus must be a proper class.

 

[dmuthuk]

Incidentally, I would avoid the word "collection" if I could -- the word set and class are fairly well established. Every set is a class, and a proper class is a class that is not a set.

The word "collection" isn't standardized (as far as I know) -- one has to guess if you are using it to mean set or class. I'm assuming you are using it to mean class. (So I continued with that terminology)

Hey, I had a thought. We have established that it doesn't make sense to take the union of a "collection" of sets unless we can be sure that such a collection defines a set. But, is it possible to use the axiom of pairing to somehow turn this collection into a set? I know it's not possible since otherwise we wouldn't have the power set axiom, but why so? For instance, can we somehow generalize the pairing scheme to an arbitrary collection of sets rather than just two. For instance, if we had the singletons {x}, {y} and {z}, can we argue that {{x},{y},{z}} exists?

Now, surely, if we were only interested in singleton sets to begin with, then we wouldn't need the power set axiom to argue that the power sets of singleton sets exist. We can just use the axiom of pairing since singleton sets like {x} have only two subsets, x, and the empty set, and so we can just pair them up into a set using the axiom of pairing. So, why can't we generalize the pairing axiom?

 

[Hurkyl]

For instance, if we had the singletons {x}, {y} and {z}, can we argue that {{x},{y},{z}} exists?

Yes:
{x} is a set
{y} is a set
{{x}, {y}} is a set
{z} is a set
{{z}} is a set
{ {{x}, {y}}, {{z}} }
{ {x}, {y}, {z} }

You can extend this to any finite number of singletons, but you need more to move onto infinite sets.


Here's a quick fact that might convince you of the necessity of something like the power set axiom it: once you start dealing with infinite sets, the axiom of the power set is the only way to make "bigger" sets. Without it, there is no way to prove the existence of an uncountable set. e.g. the union of countably many countable sets is countable.

 

[honestrosewater]

Adding a tiny bit to what Hurkyl said, a nice thing about sets is that you can think of a set as a single object. Some classes are not so nice, so to avoid problems, you start out assuming that every "collection" is a class and is not nice enough to be a set until you can prove that is it. See http://en.wikipedia.org/wiki/Limitation_of_size" . They list a book about it too.

 

[dmuthuk]

Yes:
{x} is a set
{y} is a set
{{x}, {y}} is a set
{z} is a set
{{z}} is a set
{ {{x}, {y}}, {{z}} }
{ {x}, {y}, {z} }

You can extend this to any finite number of singletons, but you need more to move onto infinite sets.

Hi, thanks guys. So, I guess the power set axiom is not needed for any finite set.

 

[honestrosewater]

Hi, thanks guys. So, I guess the power set axiom is not needed for any finite set.

Well, stepping back from a specific axiomatization of set theory for a second, there are 3 ways to define a set (or class) (haha, I've said this exact thing before here, so I'll just copy+paste):

1) Extension -- name all members of S.
2) Intension -- name a definite property that all members of S have.
3) Induction/Recursion

a) basis clause -- name at least one member of S.
b) induction clause -- give rule(s) to get more members from those in (a) -- if x is in S, then x' is in S.
c) extremal clause -- says that nothing else is in S.​

If the set is finite, you can simply list its members. I imagine you don't need very liberal axioms to allow that. Maybe it would be a useful exercise to look at each axiom and identify which method it uses. For example, the Axiom of Pairing uses (1).

Oh, I should probably try to head off any confusion or complaints by noting that a proof is usually defined to be finite in length.

Also, (1) will only give you a finite set, if that wasn't clear. (If you can furthermore only invoke a (1)-type axiom a finite number of times, as is the case for finite-length proofs, can you ever prove the existence of any infinite set that way (assuming you didn't already have one)?)

 

[matt grime]

... the axiom of the power set is the only way to make "bigger" sets. Without it, there is no way to prove the existence of an uncountable set. e.g. the union of countably many countable sets is countable.

There isn't a way to prove there are uncountable sets with it either. This is Skolem's paradox - the are countable models for ZF. It's only when you give a model and state what the power set is that you get uncountable sets. At least that is my lax understanding of Skolem.

 

[honestrosewater]

There isn't a way to prove there are uncountable sets with it either. This is Skolem's paradox - the are countable models for ZF. It's only when you give a model and state what the power set is that you get uncountable sets. At least that is my lax understanding of Skolem.

I'm going to tack a question on here in case anyone comes along to comment. I thought it was more that the "uncountable" set contained in the countable model was, from the outside, a countable set, and it was only uncountable within the model because the model contained no bijection between that set and N. Hm, that doesn't really make sense as I say it. I have cleared this up with myself before, but the clarifications I have tried have apparently not stuck.

 

[matt grime]

That sounds familiar - it is uncountable in the sense of 'there does not exist a bijection with the inductive set (i.e. N, or whatever it should be called) within the model' but there is a bijection in some extended model.

Of course - Cantor's 'diagonal' method works for any set to show there is no bijection between X and P(X) - assume f is any injection from X to P(X), and define S:={x in X : x not in f(x)}, then S is in P(X) and S is not in Im(f).

So I was talking nonsense, earlier.

 

[dmuthuk]

Now, how exactly can we use the power set axiom to argue that for any "collection" or class of sets, there exists a set that contains them all as elements? Is this even possible or does this lead to a paradox? We already know that we can construct this set for a finite collection without the power set axiom.

 

[Hurkyl]

Now, how exactly can we use the power set axiom to argue that for any "collection" or class of sets, there exists a set that contains them all as elements?

If you could, do you see how to construct a set of all sets? (And thus a contradiction)


A sample use of the power set axiom is, given two (possibly infinite) sets A and B, to construct the set of all functions from A to B.

Another use is to construct the set of all unary relations on A.

Can you see how the power set axiom is equivalent to the statement

The class of all functions from A to B is a set?​

The power set axiom is the reason why set theory is interesting. Without it, we might as well just be doing logic.


Have you seen first-order logic yet? What about second-order logic?

 

[dmuthuk]

If you could, do you see how to construct a set of all sets? (And thus a contradiction)

A sample use of the power set axiom is, given two (possibly infinite) sets A and B, to construct the set of all functions A --> B.

In fact, the notion of "a subset of A" is essentially the same thing as the notion of "a function from A to {0, 1}". Do you see how? In fact, the power set axiom is equivalent to the statement

For any set A, the class of functions from A to {0, 1} is a set​

So, I assume $$f:A \to \{0,1\}$$ is an indicator function for a subset of $$A$$ that we have in mind (i.e. a way to sort out which elements are in our subset and which aren't).

I wish Halmos' book talked more about "classes". I actually picked this book up because I started questioning the validity of existence theorems in my analysis and algebra courses, and I thought set theory would answer some of these questions, and it does straighten some of these ideas out.

 

[honestrosewater]

I wish Halmos' book talked more about "classes".

What do you want to know about them? Did you read about limitation of size?

Here is my understanding. I could be mistaken, of course, so take it with a grain of salt.

Suppose that you start with some vague concepts of objects and membership. You want objects to be able to contain other objects as members, and you would ideally like to treat all objects as the same type with respect to membership. But it turns out that this causes problems, and you need to have at least two types of objects. So you rename your objects, or whatever you've been calling them, "classes", and you call your two types of classes "sets" and "proper classes".

Now you have some options about how to remake your theory of sets. You know one thing for sure: proper classes can't be members of sets. So you can push proper classes completely aside and pretend like they don't even exist as far as your set theory is concerned. This, I think, is basically what ZF does. You can also allow both sets and proper classes into your set theory and work in the rule that proper classes cannot be members of sets (by modifying the definition of the membership relation, introducing a limitation of size axiom, etc.). This is what some other set theories do, e.g., NBG.

P.S. Yes, I'm pretty sure the indicator/characteristic function is what Hurkyl had in mind.

 

[fopc]

Hey everyone,

I am currently trying to learn a bit of set theory from Halmos' book "Naive Set Theory" since I have recently been concerned with the general notion of existence in various fields of mathematics.

Now, I am reading the "axiom of the power set" and I do find it a little troubling because I think that it might be possible to derive the existence of the power set from the axiom of specification (forming subsets), axiom of unions, axiom of pairing, and axiom of extentionality. So, I know have definitely gone wrong somewhere. Can someone help me find a flaw in the following argument:

Let E be a set. Each subset x of E exists by the axiom of specification. Then, each singleton set {x} exists by the axiom of pairing. By the axiom of unions, the union of this collection of singleton sets, each containing a subset of E as its only element, exists as a set. So, this is our desired power set. [QED]

Aside from this, I was wondering if anyone knows how to interpret the primitive relations of "equality" and "set membership" between any two sets. Can we think of these as "relations" on the set of all sets (which does not exist technically)?

Thanks,

Dilip

Too many posts to read, but I can comment on your opening post.

Powerset axiom: You picked on the wrong axiom to derive from the others. Try deriving pairing axiom from the rest.

Flaw in argument? It went bad in sentence two.
Specification doesn't give you license to say that.

Belonging:
A primitive binary relation on the set under discussion U and its powerset P(U).
That makes it a subset of U x P(U).

Equality:
He merely says its a binary relation between sets "perhaps"
more elementary than belonging. Well belonging
is taken as a primitive, so what could be more
elementary than a primitive? (I think he was just joking.)
Really what I think he's saying is that equality is essentially identity, and that everything is made all right by the underlying predicate logic that comes equipped with identity. If you track it down, I think in the end you'll find Leibniz's law. Anyway he (Halmos) uses '=' freely from then on.

For Halmos, no distinction is made between a collection of sets and a set of sets, or a family of sets (ch.9) for that matter.

 

[dmuthuk]

Too many posts to read, but I can comment on your opening post.

Flaw in argument? It went bad in sentence two.
Specification doesn't give you license to say that.

If I understand the Specification axiom correctly, it says that given a set A, and some logical sentence that doesn't necessarily have to depend on the members of A, then those members of A for which this sentence is true is a set. Now, the way I understand the word "subset" is simply a "bunch" of elements that are also members of A and that satisfy some logical sentence, which by Specification, is a set. So, I am not sure where I went wrong with the second sentence.

 

[fopc]

"Let E be a set. Each subset x of E exists by the axiom of specification."

Specification (loosely by ZF) says for such an (arbitrary) E, there exists a set B [given any X (X member of B) iff
(X member of E and P(X))].

It doesn't say anything about the existence of each (i.e., every) subset x of E.
It's an axiom schema. How many axioms? One for each predicate. Suppose E=N (set of natural numbers). Now how many subsets? But you feel specification declares the existence of all subsets of any arbitrary set (N in this case). This would result in how many axioms?