Register to reply 
The Axiom of the Power Set 
Share this thread: 
#1
May1607, 06:46 PM

P: 41

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 


#2
May1607, 07:18 PM

Sci Advisor
HW Helper
P: 2,586

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



#3
May1607, 07:23 PM

P: 41

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}.



#4
May1607, 07:29 PM

P: 41

The Axiom of the Power Set
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.



#5
May1607, 07:47 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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. 


#6
May1607, 09:17 PM

PF Gold
P: 2,330

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. 


#7
May1607, 09:35 PM

P: 41




#8
May1607, 09:38 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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) 


#9
May1607, 09:45 PM

Sci Advisor
HW Helper
P: 2,586

[tex]\cup x =_{def} \{y\ :\ (\exists z \in x)(y\in z)\}[/tex] The union axioms then says [itex](\forall x)(\exists y)(y = \cup x)[/itex]. 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 [itex](\forall x)[/itex] 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. 


#10
May1607, 09:47 PM

P: 41




#11
May1607, 10:26 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

x in SingletonSet iff there exists a y such that x = {y}.We usually use the setbuilder 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. 


#12
May1607, 10:42 PM

P: 41

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? 


#13
May1607, 10:50 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

{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. 


#14
May1607, 10:55 PM

PF Gold
P: 2,330

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 what Wikipedia has to say about limitation of size. They list a book about it too.



#15
May1607, 11:45 PM

P: 41




#16
May1707, 12:53 AM

PF Gold
P: 2,330

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.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 finitelength proofs, can you ever prove the existence of any infinite set that way (assuming you didn't already have one)?) 


#17
May1707, 04:40 AM

Sci Advisor
HW Helper
P: 9,396




#18
May1707, 06:04 AM

PF Gold
P: 2,330




Register to reply 
Related Discussions  
Axiom of Choice  Calculus & Beyond Homework  3  
The axiom of choice. Help  General Math  9  
Do mathematicians believe in axioms . . . .  General Discussion  4  
Completeness Axiom  General Math  12 