Power sets allow us to discuss the class of all subsets of a given set
A
{\displaystyle A}
{
U
|
U
⊆
A
}
{\displaystyle \{U\;|\;U\subseteq A\}}
Axiom
Given a set
A
{\displaystyle A}
S
{\displaystyle S}
U
∈
S
{\displaystyle U\in S}
U
⊆
A
{\displaystyle U\subseteq A}
Theorem Given a set
A
{\displaystyle A}
A
{\displaystyle A}
Proof If
S
1
{\displaystyle S_{1}}
S
2
{\displaystyle S_{2}}
U
∈
S
1
{\displaystyle U\in S_{1}}
U
⊆
A
{\displaystyle U\subseteq A}
S
2
{\displaystyle S_{2}}
U
∈
S
1
{\displaystyle U\in S_{1}}
U
∈
S
2
{\displaystyle U\in S_{2}}
S
1
=
S
2
{\displaystyle S_{1}=S_{2}}
◻
{\displaystyle \square }
Definition Given a set
A
{\displaystyle A}
A
{\displaystyle A}
power set of
A
{\displaystyle A}
P
(
A
)
{\displaystyle {\mathcal {P}}(A)}
Example If
A
=
{
a
,
b
,
c
}
{\displaystyle A=\{a,b,c\}}
P
(
A
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
c
}
,
{
a
,
b
}
,
{
a
,
c
}
,
{
b
,
c
}
,
{
a
,
b
,
c
}
}
{\displaystyle {\mathcal {P}}(A)=\{\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}}
Recall the Kuratowski definition of an ordered pair,
(
a
,
b
)
=
{
{
a
}
,
{
a
,
b
}
}
{\displaystyle (a,b)=\{\{a\},\{a,b\}\}}
a
{\displaystyle a}
b
{\displaystyle b}
A
{\displaystyle A}
{
a
}
{\displaystyle \{a\}}
{
a
,
b
}
{\displaystyle \{a,b\}}
A
{\displaystyle A}
P
(
A
)
{\displaystyle {\mathcal {P}}(A)}
This means that
(
a
,
b
)
{\displaystyle (a,b)}
P
(
A
)
{\displaystyle {\mathcal {P}}(A)}
(
a
,
b
)
∈
P
(
P
(
A
)
)
{\displaystyle (a,b)\in {\mathcal {P}}({\mathcal {P}}(A))}
We can generalise this slightly with a simple trick. We can define
(
a
,
b
)
{\displaystyle (a,b)}
a
∈
A
{\displaystyle a\in A}
b
∈
B
{\displaystyle b\in B}
A
{\displaystyle A}
B
{\displaystyle B}
a
{\displaystyle a}
b
{\displaystyle b}
A
∪
B
{\displaystyle A\cup B}
In other words, we have
(
a
,
b
)
∈
P
(
P
(
A
∪
B
)
)
{\displaystyle (a,b)\in {\mathcal {P}}({\mathcal {P}}(A\cup B))}
a
∈
A
{\displaystyle a\in A}
b
∈
B
{\displaystyle b\in B}
Theorem The class of all ordered pairs
(
a
,
b
)
{\displaystyle (a,b)}
A
∪
B
{\displaystyle A\cup B}
a
∈
A
{\displaystyle a\in A}
b
∈
B
{\displaystyle b\in B}
Proof The set in question is given by
{
x
∈
P
(
P
(
A
∪
B
)
)
|
x
=
(
a
,
b
)
,
a
∈
A
and
b
∈
B
}
{\displaystyle \{x\in {\mathcal {P}}({\mathcal {P}}(A\cup B))\;|\;x=(a,b),a\in A\;{\mbox{and}}\;b\in B\}}
◻
{\displaystyle \square }
Definition The set of ordered pairs
(
a
,
b
)
{\displaystyle (a,b)}
a
∈
A
{\displaystyle a\in A}
b
∈
B
{\displaystyle b\in B}
cartesian product of
A
{\displaystyle A}
B
{\displaystyle B}
A
×
B
{\displaystyle A\times B}
Show that for sets
A
,
B
,
C
,
D
{\displaystyle A,B,C,D}
(
A
∩
B
)
×
(
C
∩
D
)
=
(
A
×
C
)
∩
(
B
×
D
)
{\displaystyle (A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)}
Show that for sets
A
,
B
,
C
{\displaystyle A,B,C}
A
×
(
B
∩
C
)
=
(
A
×
B
)
∩
(
A
×
C
)
{\displaystyle A\times (B\cap C)=(A\times B)\cap (A\times C)}
Show that for sets
A
,
B
,
C
{\displaystyle A,B,C}
A
×
(
B
∪
C
)
=
(
A
×
B
)
∪
(
A
×
C
)
{\displaystyle A\times (B\cup C)=(A\times B)\cup (A\times C)}
Show that for sets
A
,
B
,
C
{\displaystyle A,B,C}
A
⊆
B
{\displaystyle A\subseteq B}
A
×
C
⊆
B
×
C
{\displaystyle A\times C\subseteq B\times C}
← Classes and foundation · Natural numbers →
