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

From Wikibooks, open books for an open world
< Mathematical Proof and the Principles of Mathematics‎ | Sets
Jump to navigation Jump to search

Power sets[edit]

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[edit]

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[edit]

  • 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