A-1 Law and order: Cartesian product, power sets 501
Example A.3 (Power set).
The power set as the set of all subsets of a set A may be demonstrated by the set A = {1, 2, 3}, whose
complete list of subsets read
M 1 = ∅ ,
M 2 = {1}, M 3 = {2}, M 4 = {3} ,
M 5 = {1, 2}, M 6 = {2, 3}, M 7 = {3, 1} ,
M 8 = {1, 2, 3} ,
(A.8)
namely built on 8 elements:
power(M ) =
∅, {1}, {2}, {3}, {12}, {13}, {23}, {123}
.
(A.9)
End of Example.
Exercise A.2 (Power set).
If n is the number of elements of a set A for which we write |A| = n, then
|power(A)| = 2
n ,
(A.10)
namely the power set of A has exactly 2
n elements. The result motivates the name power set. The
proof is based on complete induction:
A
∅ 1 2 3 4 5 6 . . . n
power(A) 1 2 4 8 16 32 64 . . . 2
n .
(A.11)
End of Exercise.
Example A.3 and Exercise A.2 have already used the following definition.
Definition A.3 (Power set).
The power set of a set A, shortly written power(A), is by definition the set of all subsets M of A:
power(A) := {M | M ⊆ A}
(A.12)
End of Definition.
power(A) is a set sytem whose elements are just all subsets of A. If A is a set of first kind, power(A)
is a set of second kind. Inclusions of the above type can be illustrated by Hasse diagrams, also called
order diagrams (H. Hasse 1896–1979). In such a diagram, two sets M 1 and M 2 are identified by two
points and are connected by a straight line if the lower set M 2 is a subset of M 1 or M 2 ⊆ M 1 . In this
way, a set M is contained in any set which is above of M , illustrated by an upward line.
Example A.4 (Hasse diagram).
For the set A = {1, 2, 3}, |A| = 3:
power(A) =
∅, {1}, {2}, {3},
{12}, {13}, {23}, {123}
,
|power(A)| = 8 .
(A.13)
End of Example.