Mathematical Proof and the Principles of Mathematics/Sets/Power sets

Power sets Power sets allow us to discuss the class of all subsets of a given set , i.e. . That this is a set is the subject of the Power Set Axiom. Axiom Given a set there exists a set of sets such that iff . Theorem Given a set , there exists a unique set whose elements are the subsets of . Proof If and are two such sets of subsets then if and only if . But the same is true of . Thus iff , and so by the Axiom of Extensionality. Definition Given a set , the set of all subsets of is called the power set of . It is denoted . Example If then . Cartesian products Recall the Kuratowski definition of an ordered pair, for and elements of a set . Note that and are both subsets of , i.e. they are elements of the power set . This means that is a subset of , i.e. . We can generalise this slightly with a simple trick. We can define with and for sets and . In order to do this, we simply take the elements and from the union of sets . In other words, we have with and . Theorem The class of all ordered pairs of elements of with and , is a set. Proof The set in question is given by . This is a set by the axioms of Power Set, Union and the Axiom Schema of Comprehension. Definition The set of ordered pairs with and is called the cartesian product of and , and is denoted . Exercises Show that for sets we have . Show that for sets we have . Show that for sets we have . Show that for sets with we have . Classes and foundation Natural numbers