Register to reply

The Axiom of the Power Set

by dmuthuk
Tags: axiom, power
Share this thread:
matt grime
#19
May17-07, 06:19 AM
Sci Advisor
HW Helper
P: 9,396
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
#20
May17-07, 10:05 PM
P: 41
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
#21
May17-07, 10:16 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Quote Quote by dmuthuk View Post
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
#22
May17-07, 10:30 PM
P: 41
Quote Quote by Hurkyl View Post
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 [tex] f:A \to \{0,1\} [/tex] is an indicator function for a subset of [tex]A[/tex] 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
#23
May18-07, 06:14 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by dmuthuk View Post
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
#24
May19-07, 09:17 AM
P: 90
Quote Quote by dmuthuk View Post
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
#25
May23-07, 01:43 AM
P: 41
Quote Quote by fopc View Post
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
#26
May23-07, 04:47 AM
P: 90
"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?


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