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

Power setsEdit

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 productsEdit

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  .

ExercisesEdit

  • 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