User:Addemf/sandbox/Technical Reasoning/Naive Set Theory 2

Basic Set Operations

Pairwise Union

A pictorial representation of the union of sets A and B. The pentagon is in both sets, but in the union we only need to represent it once.

Think of a set as like a bucket of elements. Then the union of two sets is like dumping them together into a combined bucket.

Consider, for example, the sets

A=\{1,2,3\}

B=\{2,3,4\}

The union is then

A\cup B=\{1,2,3,4\}

Note that there is no need to repeat any duplicated elements. As we discussed earlier, a set is defined by membership, so repeating elements does not change what the set is.

Definition: union

If X and Y are any two sets then their union is defined as

X\cup Y=\{z:z\in X{\text{ or }}Y\}

Exercise for Unions of Sets of Strings

Consider the character set {'0','1'}.

Let A be the set of all strings of length 1, and B the set of all strings of length 2.

List the elements of the set $A\cup B$ .

Solution

TODO

Exercise for Pairwise Union

Suppose that A has 3 elements and B has 6.

If $A\subseteq B$ then how many elements are in $A\cup B$ ?

If A and B have no shared elements, then how many elements are in $A\cup B$ ?

Solution

TODO

Exercise for Emptyset Union

If A is any set then what is $A\cup \emptyset$ ?

Solution

TODO

Exercise for Algebra of Sets?

Can we solve set equations the way that we solve algebraic equations?

Suppose that X is some set which satisfies the equation

X\cup \{1,2,3\}=\{-2,1,2,3,4\}

Can we determine what X must be?

If we cannot infer what X is, then can we at least make some inference about some of the elements of X?

Solution

TODO

Pairwise Intersection

A pictorial representation of the intersection of sets A and B.

If the union $A\cup B$ forms the set of all elements in A or B, then the intersection forms the set of all elements which are in both A and B.

If $A=\{1,2,3\},B=\{2,3,4\}$ then their intersection is

A\cap B=\{2,3\}

Definition: intersection

If X and Y are sets, then their intersection is the set

X\cap Y=\{z:z\in X{\text{ and }}z\in Y\}

Exercise for Basic Intersection

Let A be the set of all numbers divisible by 3, and B the set of all numbers divisible by 5.

Find the first three elements of $A\cap B$ .

Solution

TODO

Exercise

Let A be any set, and find $A\cap \emptyset$

Solution

TODO

Exercise

Let

A=\{{\text{‘a’, ‘b', ‘c'}}\}

B=\{{\text{‘b',‘c'}}\}

C=\{{\text{‘b',‘c'}}\}

Compute

A\cap (B\cup C)

and

(A\cap B)\cup C

Solution

TODO

Exercise

Consider the equation

A\cap (B\cup C)=(A\cap B)\cup C

for sets A, B, C.

Is this always true? That is to say, is it true for every choice of A, B, C?

Is it sometimes true? That is to say, is it true for some choice of A, B, C?

Solution

TODO

Exercise

If A has 3 elements and B has 6, what is the maximum number of elements in $A\cap B$ ? What is the minimum number?

Solution

TODO

Set-Difference

A pictorial representation of the relative complements, for sets A and B.

If A and B are sets then $A\smallsetminus B$ represents the elements of A, but removing the elements which are in B.

If $A=\{1,2,3\},B=\{2,3,4\}$ then "A set-difference B" is

A\smallsetminus B=\{1\}

and "B set-difference A" is

B\smallsetminus A=\{4\}

Definition: set-difference

Let A and B be sets. Then A set-difference B is defined as

A\smallsetminus B=\{z:z\in A{\text{ and not }}z\in B\}

Exercise

For any set A, find

A\smallsetminus \emptyset

and

\emptyset \smallsetminus A

Solution

TODO

Exercise

For any sets A and B, find

(A\smallsetminus B)\cap (B\smallsetminus A)

Solution

TODO

Exercise

For any sets A and B, consider the equations

A\cup B=(A\smallsetminus B)\cup B

A\cup B=(A\smallsetminus B)\cup (B\smallsetminus A)

For each equation, is it always true?

Is it sometimes true?

Solution

TODO

Universal Set and Complement

A pictorial representation of the complement of a set.

In many settings, we will be exclusively interested in sets which are all subsets of a single set.

For instance, in some settings we will only be interested in the natural numbers, and all of the sets that we consider will be subsets of it.

Or we might only be interested in the set of real numbers, or other kinds of sets, like the set of all matrices.

Whenever we restrict our interests to the subsets of one particular set, we call that one set the "universal set". We may choose the universal set to be any set that we like.

Once we specify a universal set, we can then define the notion of "the complement of a set".

Suppose that we choose the universal set $U=\{0,1,2,3,4\}$ and consider the subset $A=\{2,3\}$ . Then the complement of A is the set of all elements in the universe which are not in A.

A^{c}=\{0,1,4\}

Notice that the choice of universal set will affect the complement of a given set. If the universal set is $U=\{1,2,3,4\}$ and $A=\{2,3\}$ then

A^{c}=\{1,4\}

Exercise

Show that for any universal set U and subset $A\subseteq U$ ,

A^{c}=U\smallsetminus A

Exercise

Consider the universal set $U={\mathbb {N}}$ and subsets $A=\{2,4,6,\dots \}$ and $B=\{1,2\}$ .

Find the following sets.

(1.) $A^{c}$

(2.) $B^{c}$

(3.) $A^{c}\cap B^{c}$

(4.) $(A\cup B)^{c}$

We can now state an important relationship between the union, intersection, and complement.

Theorem: U-C De Morgan's

Suppose the universal set is U with subsets A and B. Then

(A\cup B)^{c}=A^{c}\cap B^{c}

In order to prove that two sets are equal, we must prove that every element in the left set is in the right set; and every element in the right set is in the left set.

In short, the fundamental way to prove a set equality, $X=Y$ , is to prove two subset relations.

X\subseteq Y

and

Y\subseteq X

We now do just that, with X identified with the left side, $(A\cup B)^{c}$ . Y is identified with the right side, $A^{c}\cap B^{c}$ .

Proof of of U-C De Morgan's

(1.) If $x\in (A\cup B)^{c}$ then $x\in A^{c}\cap B^{c}$ .

(1.1.) Let $x\in (A\cup B)^{c}$ .

(1.2.) So $x\notin A\cup B$ .

(1.3.) So x is not in A or B.

(1.4.) So $x\notin A$ and $x\notin B$ .

(1.5.) So $x\in A^{c}$ and $x\in B^{c}$ .

(1.6.) So $x\in A^{c}\cap B^{c}$ .

(2.) So $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ .

(3.) If $x\in A^{c}\cap B^{c}$ then $x\in (A\cup B)^{c}$ .

(3.1.) Let $x\in A^{c}\cap B^{c}$ .

(3.2.) So $x\in A^{c}$ and $x\in B^{c}$ .

(3.3.) So $x\notin A$ and $x\notin B$ .

(3.4.) So x is not in A or B.

(3.5.) So $x\notin A\cup B$ .

(3.6.) So $x\in (A\cup B)^{c}$ .

(4.) So $A^{c}\cap B^{c}\subseteq (A\cup B)^{c}$ .

(5.) So $(A\cup B)^{c}=A^{c}\cap B^{c}$ .

Audit: U-C De Morgan's

(1.)

If

x\in (A\cup B)^{c}

then

x\in A^{c}\cap B^{c}

.

From	Toward
Proved on lines (1.1.) to (1.6.).	$(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ .

(1.1.)

Let

x\in (A\cup B)^{c}

.

From	Toward
Assumption.	$x\in A^{c}\cap B^{c}$ .

(1.2.)

x\notin A\cup B

.

From	Toward
(1.1) by definition of complement.	Exchanging formal for logical expressions.

(1.3.)

x is not in A or B.

From	Toward
(1.2.) by definition of union.	Exchanging formal for logical expressions.

(1.4.)

x is not in A, and x is not in B.

From	Toward
(1.3.) by logical inference.	Rephrasing, in terms of "and".

(1.5.)

x\in A^{c}

and

x\in B^{c}

.

From	Toward
(1.4.) by definition of complement.	The desired formalized expression.

(1.6.)

x\in A^{c}\cap B^{c}

.

From	Toward
(1.5.) by definition of intersection.

(2.)

(A\cup B)^{c}\subseteq A^{c}\cap B^{c}

.

From	Toward
(1.) by definition of subsets.	$(A\cup B)^{c}=A^{c}\cap B^{c}$ .

(3.)

If

x\in A^{c}\cap B^{c}

then

x\in (A\cup B)^{c}

.

From	Toward
Proved on lines (3.1.) to (3.6.).	$A^{c}\cap B^{c}\subseteq (A\cup B)^{c}$ .

(3.1.)

Let

x\in A^{c}\cap B^{c}

.

From	Toward
Assumption.	$x\in (A\cup B)^{c}$ .

(3.2.)

x\in A^{c}

and

x\in B^{c}

From	Toward
(3.1.) by definition of intersection.	Exchanging formal for logical expression.

(3.3.)

x\notin A

and

x\notin B

.

From	Toward
(3.2.) by definition of complement.	Exchanging formal for logical expression.

(3.4.)

x is not in A or B.

From	Toward
(3.3.) by logical inference.	Rephrasing to use "or".

(3.5.)

x\notin A\cup B

.

From	Toward
(3.4.) by definition of union.	Toward the desired formal expression.

(3.6.)

x\in (A\cup B)^{c}

.

From	Toward
(3.5.) by definition of complement.

(4.)

A^{c}\cap B^{c}\subseteq (A\cup B)^{c}

.

From	Toward
(3.) by definition of subsets.	$(A\cup B)^{c}=A^{c}\cap B^{c}$ .

(5.)

(A\cup B)^{c}=A^{c}\cap B^{c}

.

From	Toward
(2.) and (4.) by definition of set equality.

A representation of the I-C De Morgan's law. The notation

{\overline {A}}

is an alternate notation for the complement,

A^{c}

.

Notice that the way that this proof flows, is to start from formal statements, like "Let $x\in (A\cup B)^{c}$ " or "Let $x\in A^{c}\cap B^{c}$ ."

From there, we progressively "unpack" this formalism, into a language which is more like a logical or natural language. For example, from " $x\in (A\cup B)^{c}$ ", we eventually arrive at " $x\notin A\cup B$ " and then "x is not in A or B".

At this point we have almost entirely exchanged the formalism for logical expressions. Complements (formal) have all been exchanged for negations (logical). Union (formal) has been exchange for disjunction (logical).

Now that we have exchanged formalism for logical expression, we are free to reason logically. We use that freedom to reason that "x is not in A or B" is logically equivalent to "x is not in A and x is not in B".

After this, we return everything to formalism. At the end of this sequence, we ultimately arrive at the goal: $x\in A^{c}\cap B^{c}$ .

In the following proof, we repeat a very similar flow. However, the logic required is a bit different from the above proof.

Theorem: I-C De Morgan's

Let A and B be two sets with universe U. Then

(A\cap B)^{c}=A^{c}\cup B^{c}

As is common with set equalities, we again prove two subset relations.

Proof of of I-C De Morgan's

(1.) If $x\in (A\cap B)^{c}$ then $x\in A^{c}\cup B^{c}$ .

(1.1.) Let $x\in (A\cap B)^{c}$ .

(1.2.) So $x\notin A\cap B$ .

(1.3.) So x is not in A and B.

(1.4.) So either $x\notin A$ , or $x\notin B$ .

(1.5.) If $x\notin A$ then $x\in A^{c}\cup B^{c}$ .

(1.5.1.) Assume $x\notin A$ .

(1.5.2.) Then $x\in A^{c}$ .

(1.5.3.) Then $x\in A^{c}$ or $x\in B^{c}$ .

(1.5.4.) Then $x\in A^{c}\cup B^{c}$ .

(1.6.) If $x\notin B$ then $x\in A^{c}\cup B^{c}$ .

(1.6.1.) Repeat, mutatis mutandis, lines (1.5.1.) to (1.5.4.).

(1.7.) In all cases, we have $x\in A^{c}\cup B^{c}$ .

(2.) So $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$ .

(3.) If $x\in A^{c}\cup B^{c}$ then $x\in (A\cap B)^{c}$ .

(3.1.) Let $x\in A^{c}\cup B^{c}$ .

(3.2.) So $x\in A^{c}$ or $x\in B^{c}$ .

(3.3.) So $x\notin A$ or $x\notin B$ .

(3.4.) If $x\notin A$ then $x\in (A\cap B)^{c}$ .

(3.4.1.) Assume $x\notin A$ .

(3.4.2.) Then x is not in A and B.

(3.4.3.) Then $x\notin A\cap B$ .

(3.4.4.) Then $x\in (A\cap B)^{c}$ .

(3.5.) If $x\notin B$ then $x\in (A\cap B)^{c}$ .

(3.5.1.) Repeat, mutatis mutandis, steps like (3.4.1.) through (3.4.4.).

(3.6.) Therefore, in all cases, $x\in (A\cap B)^{c}$ .

(4.) Therefore $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ .

(5.) Therefore $(A\cap B)^{c}=A^{c}\cup B^{c}$ .

Audit: I-C De Morgan's

(1.)

If

x\in (A\cap B)^{c}

then

x\in A^{c}\cup B^{c}

.

From	Toward
Proved on lines (1.1.) to (1.7.).	$(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$ .

(1.1.)

Let

x\in (A\cap B)^{c}

.

From	Toward
Assumption.	$x\in A^{c}\cup B^{c}$ .

(1.2.)

x\notin A\cap B

.

From	Toward
(1.1) by definition of complement.	Exchanging formal for logical expressions.

(1.3.)

x is not in A and B.

From	Toward
(1.2.) by definition of intersection.	Exchanging formal for logical expressions.

(1.4.)

x\notin A

, or

x\notin B

.

From	Toward
(1.3.) by logical inference.	Rephrasing, in terms of "or".

(1.5.)

If

x\notin A

then

x\in A^{c}\cup B^{c}

.

From	Toward
Proved on lines (1.5.1.) to (1.5.4.).	One case, in a proof by cases.

(1.5.1.)

Assume

x\notin A

.

From	Toward
Assumption.	$x\in A^{c}\cup B^{c}$ .

(1.5.2.)

x\in A^{c}

.

From	Toward
(1.5.1.) by definition of complement.	$x\in A^{c}\cup B^{c}$ .

(1.5.3.)

x\in A^{c}

or

x\in B^{c}

.

From	Toward
(1.5.2.) by logical inference.

(1.5.4.)

x\in A^{c}\cup B^{c}

.

From	Toward
(1.5.3.) by definition of union.

(1.6.)

If

x\notin B

then

x\in A^{c}\cup B^{c}

.

From	Toward
Proved on lines (1.6.1.) to (1.6.4.).	Second case in a proof by cases.

(1.6.1.)

Repeat, mutatis mutandis the lines (1.5.1.) to (1.5.4.).

From	Toward

(1.7.)

x\in A^{c}\cup B^{c}

.

From	Toward
(1.4.) and (1.5.) and (1.6.) by proof by cases

(2.)

(A\cap B)^{c}\subseteq A^{c}\cup B^{c}

.

From	Toward

(3.)

If

x\in A^{c}\cup B^{c}

then

x\in (A\cap B)^{c}

.

From	Toward
Proved on lines (3.1.) to (3.6.).	$A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ .

(3.1.)

Let

x\in A^{c}\cup B^{c}

.

From	Toward
Assumption.	$x\in (A\cap B)^{c}$ .

(3.2.)

x\in A^{c}

or

x\in B^{c}

.

From	Toward
(3.1.) by definition of union.	Exchange formal for logical expressions.

(3.3.)

x\notin A

or

x\notin B

.

From	Toward
(3.2.) by definition of complement.	Exchanging formal for logical expressions.

(3.4.)

If

x\notin A

then

x\in (A\cap B)^{c}

.

From	Toward
Proved on lines (3.4.1.) through (3.4.4.)	First case in a proof by cases.

(3.4.1.)

Assume

x\notin A

.

From	Toward
Assumption.	$x\in (A\cap B)^{c}$ .

(3.4.2.)

x is not in A and B.

From	Toward
(3.4.1.) by logical inference.	$x\in (A\cap B)^{c}$ .

(3.4.3.)

x\notin A\cap B

From	Toward
(3.4.2.) by definition of intersection.

(3.4.4.)

x\in (A\cap B)^{c}

.

From	Toward
(3.4.3.) by definition of complement.

(3.5.)

If

x\notin B

then

x\in (A\cap B)^{c}

.

From	Toward
Proved on line (3.5.1.).	Second case in a proof by cases.

(3.5.1.)

Repeat, mutatis mutandis, steps like (3.4.1.) through (3.4.4.).

From	Toward

(3.6.)

In all cases,

x\in (A\cap B)^{c}

.

From	Toward
(3.3.) and (3.4.) and (3.5.) by proof by cases.

(4.)

A^{c}\cup B^{c}\subseteq (A\cap B)^{c}

.

From	Toward
(3.) by definition of subset.	$(A\cap B)^{c}=A^{c}\cup B^{c}$ .

(5.)

(A\cap B)^{c}=A^{c}\cup B^{c}

.

From	Toward

Exercise

In the style of the proofs above, prove the so-called "distribution laws"

A\cap (B\cup C)=(A\cap B)\cup (A\cap C)

and

A\cup (B\cap C)=(A\cup B)\cap (A\cup C)

for any sets A, B, C.

Exercise

Prove all of the following set identities, for sets A and B with universe U.

I have named some of the identities, to indicate an analogy between sets and familiar number properties. In many ways $\emptyset$ acts like the number zero, and U acts like one. Continuing the analogy, often, $\cup$ acts like plus, and $\cap$ acts like times.

Keep in mind that the analogy is just that, an analogy. It is not perfectly accurate, and is important to notice the ways in which the analogy breaks down.

The zero identities.

(1.) $A\cup \emptyset =A$

(2.) $A\cap \emptyset =\emptyset$

The one identities.

(3.) $A\cup U=U$

(4.) $A\cap U=A$

The idempotence identities.

(5.) $A\cup A=A$

(6.) $A\cap A=A$

Double-negation identity.

(7.) $(A^{c})^{c}=A$

Complement identities.

(8.) $A\cup A^{c}=U$

(9.) $A\cap A^{c}=\emptyset$

Infinitary Set Operations

If we have any finite collection of sets, $A_{1},A_{2},\dots ,A_{n}$ then we can union all of them together with a finite number of pairwise unions.

A_{1}\cup A_{2}\cup \cdots \cup A_{n}

However, it can be more compact and convenient to use "big union" notation instead.

\bigcup _{i=1}^{n}A_{i}

What this means is "Start with $i=1$ and the corresponding set $A_{i}$ . Then take $i=2$ and the set $A_{2}$ , and then $i=3$ , and so on, up to $i=n$ with each of the corresponding sets. Take the union of all of these."

Definition: union from 1 to n

Let $A_{1},A_{2},A_{3},\dots ,A_{n}$ be any "indexed sequence of sets", where the indices are written in the subscripts, from index 1 to n. Then we define the union of $A_{i}$ for index i from 1 to n as

\bigcup _{i=1}^{n}A_{i}=A_{1}\cup A_{2}\cup \cdots \cup A_{n}

Equivalently,

\bigcup _{i=1}^{n}A_{i}=\{z:z\in A_{i}{\text{ for some }}i,{\text{ where }}1\leq i\leq n\}

Exercise

Let $A_{1}$ be the set of natural numbers divisible by 2, and $A_{2}$ the set of natural numbers divisible by 3, and $A_{3}$ the natural numbers divisible by 4.

Write the first five elements of $\bigcup _{i=1}^{3}A_{i}$ .

This is a notational convenience, especially valuable when the number of sets is large.

However, we can even generalize the notation to permit so-to-speak "infinite unions".

Definition: union from 1 to $\infty$

Let $A_{1},A_{2},\dots$ be any infinite indexed sequence of sets, from 1 to infinity. Then we define the union of $A_{i}$ for i from one to $\infty$ as

\bigcup _{i=1}^{\infty }A_{i}=\{z:z\in A_{i},{\text{ for some }}i,{\text{ where }}1\leq i\}

Exercise

For each i, define $L_{i}$ as the set of all strings of length i. What, then, is the set

\bigcup _{i=2}^{\infty }L_{i}

Note that the index begins at 2, and therefore we have not technically defined exactly what this means.

Of course, we just mean the same basic idea as $\bigcup _{i=1}^{\infty }L_{i}$ except that we do not include $L_{1}$ .

Of course we may naturally also extend the notion of intersection to an infinitary intersection.

Definition: big intersection

Let $A_{1},A_{2},\dots ,A_{n}$ be any indexed sequence of sets, from index 1 to n. We define the union of $A_{i}$ for index i from 1 to n as

\bigcap _{i=1}^{n}A_{i}=A_{1}\cap \cdots \cap A_{n}

If $A_{1},A_{2},\dots$ be any indexed sequence of sets, from 1 to infinity. We define the union of $A_{i}$ for i from 1 to infinity as

\bigcap _{i=1}^{\infty }A_{i}=\{z:z\in A_{i},{\text{ for all }}1\leq i\}

Exercise

Show that the following identities hold for the infinitary operations, for any sequence of sets $A_{1},A_{2},\dots$ , and set B, with universe U.

(1.) $\left(\bigcup _{i=1}^{\infty }A_{i}\right)^{c}=\bigcap _{i=1}^{\infty }A_{i}^{c}$

(2.) $\left(\bigcap _{i=1}^{\infty }A_{i}\right)^{c}=\bigcup _{i=1}^{\infty }A_{i}^{c}$

(3.) $B\cap \left(\bigcup _{i=1}^{\infty }A_{i}\right)=\bigcap _{i=1}^{\infty }(B\cap A_{i})$

(4.) $B\cup \left(\bigcap _{i=1}^{\infty }A_{i}\right)=\bigcap _{i=1}^{\infty }(B\cup A_{i})$

The Set Product

A construction that we will use very often is to construct the set of all pairs, from two given sets.

First we need to be clear about what a pair is.

The "pair" of 1 and 'a' is written as (1,'a'). Mathematically, a pair is very similar to a list of length two. In this example, 1 is the left "coordinate" and 'a' is the right coordinate.

Unlike sets, for pairs order will matter. That is to say, $(1,'a')\neq ('a',1)$ .

Pairs allow for each coordinate to be equal. That is to say, (1,1) is a legitimate pair.

Now consider the sets $A=\{1,2,3\}$ and B = {'a','b'}. The set of all pairs, with left coordinates in A and right coordinates in B, is

{\begin{aligned}A\times B=\{(1,{\text{‘a'}}),(2,{\text{‘a'}}),(3,{\text{‘a'}}),\\(1,{\text{‘b'}}),(2,{\text{‘b'}}),(3,{\text{‘b'}})\}\end{aligned}}

Notice that, for every choice of element $x\in A$ and every choice of element $y\in B$ , the pair $(x,y)$ is present in $A\times B$ .

Also notice that if A has m elements and if B has n elements, then $A\times B$ has $mn$ elements. This is surely from whence the name "set product" derives.

Suppose that the set C is $\{\Box ,\Delta \}$ . If we then write the product of all three sets $(A\times B)\times C$ then this is

{\begin{aligned}\{((1,{\text{‘a'}}),\Box ),((2,{\text{‘a'}}),\Box ),((3,{\text{‘a'}}),\Box ),\\((1,{\text{‘b'}}),\Box ),((2,{\text{‘b'}}),\Box ),((3,{\text{‘b'}}),\Box ),\\((1,{\text{‘a'}}),\Delta ),((2,{\text{‘a'}}),\Delta ),((3,{\text{‘a'}}),\Delta ),\\((1,{\text{‘b'}}),\Delta ),((2,{\text{‘b'}}),\Delta ),((3,{\text{‘b'}}),\Delta )\}\end{aligned}}

Notice that this is made of pairs, for which the left coordinate is itself pairs from A and B; the right coordinate is from C.

Notice that this is not exactly the same thing as $A\times (B\times C)$ . This would result in pairs, which would have left coordinates in A and right coordinates would be pairs from B and C.

Although these are technically different, we will never be interested in this difference.

We will often write $A\times B\times C$ as a short-hand for $(A\times B)\times C$ , although you are also free to think of $A\times B\times C$ as the set of triples. For instance, you are free to write

{\begin{aligned}A\times B\times C=\{(1,{\text{‘a'}},\Box ),(2,{\text{‘a'}},\Box ),(3,{\text{‘a'}},\Box ),\\(1,{\text{‘b'}},\Box ),(2,{\text{‘b'}},\Box ),(3,{\text{‘b'}},\Box ),\\(1,{\text{‘a'}},\Delta ),(2,{\text{‘a'}},\Delta ),(3,{\text{‘a'}},\Delta ),\\(1,{\text{‘b'}},\Delta ),(2,{\text{‘b'}},\Delta ),(3,{\text{‘b'}},\Delta )\}\end{aligned}}

Definition: set product

Let A and B be two sets. We define the set product of A and B by

A\times B=\{(x,y):x\in A,\ y\in B\}

For an indexed sequence of sets $A_{1},A_{2},\dots ,A_{n}$ for index 1 to n, if we write $A_{1}\times A_{2}\times \cdots \times A_{n}$ then we mean to take the products "from left to right". We use the notation $A^{2}$ to represent $A\times A$ .

More generally, $A^{n}$ represents $\overbrace {A\times A\times \cdots \times A} ^{n}$ .

Exercise

List three elements from the set product $A\times B$ if A is the set of all strings and B is the set of negative rational numbers.

Exercise

Let $A=\{0,1\}$ . Find $A^{2}$ and $A^{3}$ .

Hint: The former should have 4 elements, the latter 8 elements.

The Powerset

Continuing the theme of constructing new sets from given sets, we next consider forming the set of all subsets.

For example, let $A=\{1,2,3\}$ . We have seen earlier that $\emptyset$ is a subset of every set, and hence $\emptyset \subseteq A$ .

Next, here are all of the subsets of A which have size 1.

\{1\},\{2\},\{3\}

Quick side-note: a set of size 1 is called a "singleton".

Next, here are all of the subsets of size 2.

\{1,2\},\{1,3\},\{2,3\}

And finally the subset of size 3 is $\{1,2,3\}$ .

Therefore the set of all subsets is

{\mathcal {P}}(A)=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}

Definition: power set

For any set A, the power set of A is

{\mathcal {P}}(A)=\{z:z\subseteq A\}

Notice that because $\emptyset \subseteq \emptyset$ (again, the empty set is a subset of every set, including being a subset of itself) then

{\mathcal {P}}(\emptyset )=\{\emptyset \}

I'll remind anyone who needs reminding: $\emptyset$ is not the same as $\{\emptyset \}$ ! The former has no elements, the later has one which is $\emptyset$ .

Exercise

Find ${\mathcal {P}}({\mathcal {P}}(\{1\}))$ .

Hint: the result should have $2^{2^{1}}=4$ elements. (In general, if set A has n elements, then ${\mathcal {P}}(A)$ has $2^{n}$ elements.)