Properties of the Cartesian Product

For every element in A, the Cartesian Product of A and B involves pairing the element in A with every element in B. Thus, if there is nothing in B, we may suspect that we can’t pair up elements in A, and so the result would just be the empty set.

Theorem 4.2.1

For any A ⊆ 𝒰, we have that

A ✕ ∅ = ∅
∅ ✕ A = ∅

Proof

General Strategy: By assuming A ✕ ∅ is actually non-empty, then that would imply that ∅ has at least one element in it, contradicting the definition of ∅. The exact same strategy works for ∅ ✕ A.

Presume – for the purpose of showing a contradiction – that A ✕ ∅ is non-empty. This means that

| A ✕ ∅ | ≥ 1.

Thus, there is at least one ordered pair (a, ?) ∈ A ✕ ∅. By definition of the Cartesian Product of two sets, we then have that

a ∈ A

? ∈ ∅

However, the result ? ∈ ∅ contradicts the fact that | ∅ | = 0.

Hence, our presupposition that A ✕ ∅ is non-empty was false, meaning we have that A ✕ ∅ = ∅ as desired.

Showing that ∅ ✕ A = ∅ involves the exact same logic.

✕ Distributes Over ∪ and ∩

Here, we’ll see some of the distributive properties of the Cartesian Product.

Theorem 4.2.2

For any A, B, C ⊆ 𝒰, we have that

A ✕ (B ∪ C) = (A ✕ B) ∪ (A ✕ C)
(A ∪ B) ✕ C = (A ✕ C) ∪ (B ✕ C)

Proof

General Strategy: We’ll prove that

A ✕ (B ∪ C) = (A ✕ B) ∪ (A ✕ C)

by showing that each side is a subset of the other side. We do this by using element arguments. The exact same logic will apply for showing that

(A ∪ B) ✕ C = (A ✕ C) ∪ (B ✕ C),

so we’ll omit that particular proof for the sake of brevity.

Step 1: Show that A ✕ (B ∪ C) ⊆ (A ✕ B) ∪ (A ✕ C)

	(a, x) ∈ A ✕ (B ∪ C)	Reason
⟹	(a ∈ A) ∧ (x ∈ B ∪ C)	Definition of Cartesian Product
⟹	(a ∈ A) ∧ [(x ∈ B) ∨ (x ∈ C)]	Definition of Union
=	[(a ∈ A) ∧ (x ∈ B)] ∨ [(a ∈ A) ∧ (x ∈ C)]	Distribution of ∧ over ∨
⟹	[(a, x) ∈ A ✕ B] ∨ [(a, x) ∈ A ✕ C]	Definition of Cartesian Product
⟹	(a, x) ∈ (A ✕ B) ∪ (A ✕ C)	Definition of Union

Thus, we’ve just shown that whenever (a, x) ∈ A ✕ (B ∪ C), we also have that (a, x) ∈ (A ✕ B) ∪ (A ✕ C). This means that we have by definition that

A ✕ (B ∪ C) ⊆ (A ✕ B) ∪ (A ✕ C).

Step 2: Show that (A ✕ B) ∪ (A ✕ C) ⊆ A ✕ (B ∪ C)

	(a, x) ∈ (A ✕ B) ∪ (A ✕ C)	Reason
⟹	[(a, x) ∈ A ✕ B] ∨ [(a, x) ∈ A ✕ C]	Definition of Union
⟹	[(a ∈ A) ∧ (x ∈ B)] ∨ [(a ∈ A) ∧ (x ∈ C)]	Definition of Cartesian Product
=	(a ∈ A) ∧ [(x ∈ B) ∨ (x ∈ C)]	Distribution of ∧ over ∨
⟹	(a ∈ A) ∧ (x ∈ B ∪ C)	Definition of Union
⟹	(a, x) ∈ A ✕ (B ∪ C)	Definition of Cartesian Product

Just like in the first step, we’ve shown that (A ✕ B) ∪ (A ✕ C) ⊆ A ✕ (B ∪ C).

Conclusion: A ✕ (B ∪ C) = (A ✕ B) ∪ (A ✕ C)

Because we’ve shown that both

A ✕ (B ∪ C) ⊆ (A ✕ B) ∪ (A ✕ C)

(A ✕ B) ∪ (A ✕ C) ⊆ A ✕ (B ∪ C)

we have by definition of set equality that

A ✕ (B ∪ C) = (A ✕ B) ∪ (A ✕ C)

as desired!

Notice that even though mathematical definitions use ⟺, we instead only considered one direction ⟹ at a time. This is why we had to break this proof up into two steps along with a concluding step.

Of course, we can see some concrete examples of Theorem 4.2.2 by considering a few sets.

Example 4.2.1

Consider the sets

A = { 1, 2, 3 }

B = { a, b }

C = { α, β }

According to Theorem 4.2.2, the two sets

{ 1, 2, 3 } ✕ ( { a, b } ∪ { α, β } )

( { 1, 2, 3 } ✕ { a, b } ) ∪ ( { 1, 2, 3 } ✕ { α, β } )

should be equal to each other. Let’s check.

Step 1: Compute A ✕ (B ∪ C)

First we compute B ∪ C:

B ∪ C	=	{ a, b } ∪ { α, β }
	=	{ a, b, α, β }

Now we can compute A ✕ (B ∪ C):

A ✕ (B ∪ C)	=	{ 1, 2, 3 } ✕ { a, b, α, β }
	=	{ (1, a), (1, b), (1, α), (1, β), (2, a), (2, b), (2, α), (2, β), (3, a), (3, b), (3, α), (3, β) }

So we have that A ✕ (B ∪ C) is the following set:

{	(1, a), (1, b), (1, α), (1, β),
	(2, a), (2, b), (2, α), (2, β),
	(3, a), (3, b), (3, α), (3, β)	}

Step 2: Compute (A ✕ B) ∪ (A ✕ C)

First, we compute A ✕ B:

A ✕ B	=	{ 1, 2, 3 } ✕ { a, b }
	=	{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

Next, we compute A ✕ C:

A ✕ C	=	{ 1, 2, 3 } ✕ { α, β }
	=	{ (1, α), (1, β), (2, α), (2, β), (3, α), (3, β) }

Finally, we compute (A ✕ B) ∪ (A ✕ C):

(A ✕ B) ∪ (A ✕ C)	=	{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) } ∪ { (1, α), (1, β), (2, α), (2, β), (3, α), (3, β) }
	=	{ (1, a), (1, b), (1, α), (1, β), (2, a), (2, b), (2, α), (2, β), (3, a), (3, b), (3, α), (3, β) } }

This tells us that (A ✕ B) ∪ (A ✕ C) is the set

{	(1, a), (1, b), (1, α), (1, β),
	(2, a), (2, b), (2, α), (2, β),
	(3, a), (3, b), (3, α), (3, β)	}

which is exactly the same set we got computing A ✕ (B ∪ C).

In Theorem 4.2.2, we considered any sets A, B, and C from some universal set 𝒰, Nothing in Theorem 4.2.2 prevents us from throwing the empty set into the mix.

Example 4.2.2

Consider the sets

A = { 1, 2, 3 }

B = { }

C = { α, β }

where we set B equal to the empty set ∅.

Let’s compute A ✕ (B ∪ C) first:

A ✕ (B ∪ C)	=	A ✕ (∅ ∪ C)
	=	A ✕ C
	=	{ 1, 2, 3 } ✕ { α, β }
	=	{ (1, α), (1, β), (2, α), (2, β), (3, α), (3, β) }

Now, according to Theorem 4.2.1, we have that A ✕ ∅ = ∅. This makes computing (A ✕ B) ∪ (A ✕ C) a little bit easier:

(A ✕ B) ∪ (A ✕ C)	=	(A ✕ ∅) ∪ (A ✕ C)
	=	∅ ∪ (A ✕ C)
	=	A ✕ C
	=	{ (1, α), (1, β), (2, α), (2, β), (3, α), (3, β) }

We got the exact same set again. Of course, we could short-cut through all of this computation by doing the following:

A ✕ (B ∪ C)	=	A ✕ (∅ ∪ C)
	=	A ✕ C
	=	∅ ∪ (A ✕ C)
	=	(A ✕ ∅) ∪ (A ✕ C)
	=	(A ✕ B) ∪ (A ✕ C)

Of course, we have similar results for the intersection of sets.

Theorem 4.2.3

For any A, B, C ⊆ 𝒰, we have that

A ✕ (B ∩ C) = (A ✕ B) ∩ (A ✕ C)
(A ∩ B) ✕ C = (A ✕ C) ∩ (B ✕ C)

Proof

General Strategy: We’ll adopt a similar strategy used to prove Theorem 4.2.2 except we’ll use logical equivalencies ⟺ instead of logical implications ⟹. This will make the proof much more compact since we won’t have to use two element arguments. We’ll only need one. Again, we’ll only prove that

A ✕ (B ∩ C) = (A ✕ B) ∩ (A ✕ C)

and omit the proof for

(A ∩ B) ✕ C = (A ✕ C) ∩ (B ✕ C)

for the sake of brevity.

We begin by considering an arbitrary ordered pair (a, x) in the Cartesian Product A ✕ (B ∩ C):

	(a, x) ∈ A ✕ (B ∩ C)	Reason
⟺	(a ∈ A) ∧ (x ∈ B ∩ C)	Definition of Cartesian Product
⟺	(a ∈ A) ∧ (x ∈ B) ∧ (x ∈ C)	Definition of Intersection
⟺	(a ∈ A) ∧ (a ∈ A) ∧ (x ∈ B) ∧ (x ∈ C)	Idempotent Law of ∧ (see Section 1.4)
⟺	(a ∈ A) ∧ (x ∈ B) ∧ (a ∈ A) ∧ (x ∈ C)	Commutative Law of ∧
⟺	[(a ∈ A) ∧ (x ∈ B)] ∧ [(a ∈ A) ∧ (x ∈ C)]	Associative Law of ∧
⟺	[(a, x) ∈ A ✕ B] ∧ [(a, x) ∈ A ✕ C]	Definition of Cartesian Product
⟺	(a, x) ∈ (A ✕ B) ∩ (A ✕ C)	Definition of Intersection

We’ve just shown that

(a, x) ∈ A ✕ (B ∩ C) ⟺ (a, x) ∈ (A ✕ B) ∩ (A ✕ C)

which is logically equivalent to showing that both

(a, x) ∈ A ✕ (B ∩ C) ⟹ (a, x) ∈ (A ✕ B) ∩ (A ✕ C)

(a, x) ∈ (A ✕ B) ∩ (A ✕ C) ⟹ (a, x) ∈ A ✕ (B ∩ C)

meaning that we have

A ✕ (B ∩ C) ⊆ (A ✕ B) ∩ (A ✕ C)

(A ✕ B) ∩ (A ✕ C) ⊆ A ✕ (B ∩ C)

and so we have that

A ✕ (B ∩ C) = (A ✕ B) ∩ (A ✕ C)

as desired.

Let’s see some examples using the intersection.

Example 4.2.3

Consider the sets

A = { 1, 2, 3 }

B = { a, b }

C = { b, c }

We’ll proceed much the same way we did as in Example 4.2.1:

Step 1: Compute A ✕ (B ∩ C)

Computing B ∩ C yields

B ∩ C	=	{ a, b } ∩ { b, c }
	=	{ b }

Now we compute A ✕ (B ∩ C):

A ✕ (B ∩ C)	=	{ 1, 2, 3 } ✕ { b }
	=	{ (1, b), (2, b), (3, b) }

Step 2: Compute (A ✕ B) ∩ (A ✕ C)

Computing A ✕ B yields the following:

A ✕ B	=	{ 1, 2, 3 } ✕ { a, b }
	=	{ (1, a), (2, a), (3, a), (1, b), (2, b), (3, b) }

Computing A ✕ C yields the following set instead:

A ✕ C	=	{ 1, 2, 3 } ✕ { b, c }
	=	{ (1, b), (2, b), (3, b), (1, c), (2, c), (3, c) }

Computing the intersection of A ✕ B and A ✕ C gives the following set:

(A ✕ B) ∩ (A ✕ C)	=	{ (1, a), (2, a), (3, a), (1, b), (2, b), (3, b) } ∩ { (1, b), (2, b), (3, b), (1, c), (2, c), (3, c) }
	=	{ (1, b), (2, b), (3, b) }

Again, we got the exact same set as we did in Step 1.

Example 4.2.4

Consider the sets

A = { 1, 2, 3 }

B = { a, b }

C = { α, β }

Since

B ∩ C = { a, b } ∩ { α, β } = ∅

Theorem 4.2.1 tells us that

A ✕ (B ∩ C) = A ✕ ∅ = ∅.

Now, when computing (A ✕ B) ∩ (A ✕ C), we start by computing A ✕ B and A ✕ C:

A ✕ B = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
A ✕ C = { (1, α), (1, β), (2, α), (2, β), (3, α), (3, β) }

A ✕ B and A ✕ C don’t share any elements, and so we have that

(A ✕ B) ∩ (A ✕ C) = ∅.

Once again, we’ve seen that

A ✕ (B ∩ C) = (A ✕ B) ∩ (A ✕ C).

Cartesian Products of Subsets

There is an interplay between Cartesian Products and subsets.

Theorem 4.2.4

For any non-empty sets A, B, C, D ⊆ 𝒰,

(A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

Proof

General Strategy: Since we’re trying to prove a logical equivalency, we’ll break this proof up into two steps. In both steps, we’ll use element arguments by picking arbitrary ordered pairs of the form (x, y).

Step 1: (A ✕ B) ⊆ (C ✕ D) ⟹ A ⊆ C ∧ B ⊆ D

In this step, we’ll assume that (A ✕ B) ⊆ (C ✕ D) is true.

Because we know that (A ✕ B) ⊆ (C ✕ D), we know that for any arbitrarily picked ordered pair (x, y) from A ✕ B will also be present in C ✕ D, meaning we have that

(x, y) ∈ A ✕ B ⟹ (x, y) ∈ C ✕ D.

Since (x, y) ∈ A ✕ B, we know (by the definition of Cartesian Product) that

x ∈ A ∧ y ∈ B.

Since we also know that (x, y) ∈ C ✕ D, we similarly have that

x ∈ C ∧ y ∈ D.

Thus, whenever x ∈ A, we also know that x ∈ C, meaning we have that

A ⊆ C

by the definition of subset. Furthermore, we also have that

B ⊆ D.

This establishes that

(A ✕ B) ⊆ (C ✕ D) ⟹ A ⊆ C ∧ B ⊆ D,

completing Step 1.

Step 2: A ⊆ C ∧ B ⊆ D ⟹ (A ✕ B) ⊆ (C ✕ D)

In this step, we assume that both A ⊆ C and B ⊆ D are true, and will use those two facts when needed.

Consider an arbitrarily picked ordered pair (x, y) from A ✕ B. By definition of Cartesian product, this tells us that

x ∈ A

y ∈ B

Now, since x ∈ A and A ⊆ C, we also have that

x ∈ C.

Likewise, we also know that

y ∈ D.

Therefore, by the definition of Cartesian Product, we have that

(x, y) ∈ C ✕ D.

Thus, we’ve just shown that whenever (x, y) ∈ A ✕ B, we automatically know that (x, y) ∈ C ✕ D as well. This means that

(x, y) ∈ A ✕ B ⟹ (x, y) ∈ C ✕ D

thus establishing that

A ✕ B ⊆ C ✕ D

by definition of subset.

This completes Step 2.

Conclusion: (A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

From Steps 1 and 2, we’ve shown that

(A ✕ B) ⊆ (C ✕ D) ⟹ A ⊆ C ∧ B ⊆ D

A ⊆ C ∧ B ⊆ D ⟹ (A ✕ B) ⊆ (C ✕ D)

and as such, we have that

(A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

as desired.

A couple of examples are in order.

Example 4.2.5

Consider the sets

A = { 1, 2, 3 }

B = { a, b }

C = { 8, 9 }

D = { x, y, z }

Notice that A is not a subset of C, and B is not a subset of D. Thus we expect that since

[A ⊆ C ∧ B ⊆ D] = 0

and

(A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

by Theorem 4.2.4, we would also have that

[(A ✕ B) ⊆ (C ✕ D)] = 0

meaning A ✕ B is not a subset C ✕ D (as a reminder, [(A ✕ B) ⊆ (C ✕ D)] is a proposition saying that A ✕ B is a subset C ✕ D, and thus takes on a truth value of either 0 or 1.)

We can avoid computing both A ✕ B and C ✕ D by noting that since 1 ∈ A, the set A ✕ B will have ordered pairs where the first element is a 1. However, since 1 ∉ C, none of the ordered pairs in C ✕ D will have 1 as the first element. This means that A ✕ B has at least one element that is not in C ✕ D, and so we have that

(A ✕ B) ⊈ (C ✕ D)

as expected.

One could compute A ✕ B and C ✕ D, but sometimes, stopping and thinking can prevent a lot of unnecessary work from being done.

Example 4.2.6

Consider the sets

A = { 1, 2 }

B = { a, b }

C = { 1, 2, 3 }

D = { a, b }

Unlike in Example 4.2.5, we do have that A ⊆ C and B ⊆ D, as such we expect that (A ✕ B) ⊆ (C ✕ D) as a consequence of Theorem 4.2.4.

Start by computing A ✕ B:

A ✕ B	=	{ 1, 2 } ✕ { a, b }
	=	{ (1, a), (1, b), (2, a), (2, b) }

Now we compute C ✕ D:

C ✕ D	=	{ 1, 2, 3 } ✕ { a, b }
	=	{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

Of course we see that all four elements within A ✕ B is also in C ✕ D:

(1, a) ∈ { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }	(1, b) ∈ { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }
(2, a) ∈ { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }	(2, b) ∈ { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

Thus, we have that A ✕ B ⊆ C ✕ D as expected.

There is another way we could prove Theorem 4.2.4, so for the sake of showing that there are sometimes multiple ways to prove a statement, we’ll provide another proof of Theorem 4.2.4 that shows how mastery of logical equivalence and logical implications can make quick work of some problems.

Theorem 4.2.4 (Revisited)

For any non-empty sets A, B, C, D ⊆ 𝒰,

(A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

Proof

General Strategy: We’ll make heavy use of previous theorems, definitions, and logical equivalencies.

	(A ✕ B) ⊆ (C ✕ D)	Reason
⟺	(x, y) ∈ A ✕ B ⟹ (x, y) ∈ C ✕ D	Definition of Subset
⟺	(x ∈ A) ∧ (y ∈ B) ⟹ (x ∈ C) ∧ (y ∈ D)	Definition of Cartesian Product
⟺	[(x ∈ A) ∧ (y ∈ B) ⟹ (x ∈ C)] ∧ [(x ∈ A) ∧ (y ∈ D) ⟹ (y ∈ D)]	Logically Equivalent Arguments
⟺	[(x ∈ A) ⟹ (x ∈ C)] ∧ [(y ∈ D) ⟹ (y ∈ D)]	Conjunctive Simplification
⟺	A ⊆ C ∧ B ⊆ D	Definition of Subset

Thus, by making use of logically equivalent arguments (Section 2.4), definitions, and the laws of logic (Section 1.4), we have shown that

(A ✕ B) ⊆ (C ✕ D) ⟺ A ⊆ C ∧ B ⊆ D

as desired.

The second proof of Theorem 4.2.4 was much more compact than the first proof, however it may be somewhat harder to read just because of all the symbology used. Either way, both methods are valid.

Notice that Theorem 4.2.4 required that A, B, C, and D all be non-empty. Indeed, in both proofs, we relied on being able to pick arbitrary elements from A and B, as well as showing that they were also in C and D respectively. What happens if one or more of the sets is the empty set?

Example 4.2.7

Consider the sets

A = ∅

B = { a, b }

C = { 1, 2, 3 }

D = { a, b }

Here we have that

A ⊆ C = 1

B ⊆ D = 1

and so

A ⊆ C ∧ B ⊆ D = 1 ∧ 1 = 1.

Theorem 4.2.1 tells us that A ✕ B = ∅ because A = ∅.

Computing C ✕ D yields

{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }.

Since ∅ is a subset of every set, we also have that

∅ ⊆ { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

meaning that (A ✕ B) ⊆ (C ✕ D) = 1. In this case, we have that

[(A ✕ B) ⊆ (C ✕ D)] ↔ [A ⊆ C ∧ B ⊆ D] = 1 ↔ 1 = 1.

Example 4.2.8

Consider the sets

A = { 1, 2 }

B = { a, b }

C = { 1, 2, 3 }

D = ∅

This time, we have that

A ⊆ C = 1

B ⊆ D = 0

and so this time we get that

A ⊆ C ∧ B ⊆ D = 1 ∧ 0 = 0.

Computing A ✕ B yields { (1, a), (1, b), (2, a), (2, b) }.

Theorem 4.2.1 tells us that since D = ∅, we have that C ✕ D = ∅.

Now, since A ✕ B ≠ ∅ and C ✕ D = ∅, we know that

(A ✕ B) ⊆ (C ✕ D) = 0.

Thus, we have that

[(A ✕ B) ⊆ (C ✕ D)] ↔ [A ⊆ C ∧ B ⊆ D] = 0 ↔ 0 = 1.

Example 4.2.9

Consider the sets

A = { 1, 2 }

B = ∅

C = ∅

D = { a, b }

Here, we see that

A ⊆ C = 0

B ⊆ D = 1

meaning that

A ⊆ C ∧ B ⊆ D = 0 ∧ 1 = 0.

Again, Theorem 4.2.1 tells us that A ✕ B = ∅ because B = ∅.

Similarly, Theorem 4.2.1 tells us that C ✕ D = ∅ since C = ∅.

Thus, we have that

(A ✕ B) ⊆ (C ✕ D) = ∅ ⊆ ∅ = 1.

Now we have that

[(A ✕ B) ⊆ (C ✕ D)] ↔ [A ⊆ C ∧ B ⊆ D] = 1 ↔ 0 = 0.

Example 4.2.9 shows us why one of the premises of Theorem 4.2.4 is that A, B, C, and D need to be non-empty. Having some combination of empty sets can disrupt any logical equivalencies we hope to achieve.

Experiment with Theorem Premises

Always pay careful attention to the premises of any theorem. If any one of the premises fails to be true, then the theorem no longer applies. The stated conclusion may be true, but not as a result of the theorem. Instead, other theorems, definitions, or axioms must be used to establish the conclusion’s truth.

It’s good practice to experiment and come up with example scenarios where not all premises of a theorem are true. Trying to “break” a theorem is a great way to gain insight into why the theorem is true.

✕ Distributes Over – and △

There are two more operators to discuss. We’ll first look at how ✕ interacts with -.

Theorem 4.2.5

For any A, B, C ⊆ 𝒰,

A ✕ (B – C) = (A ✕ B) – (A ✕ C)

Proof

General Strategy: This will be a standard proof using multiple logical equivalencies and definitions of operations, all contained within a larger element argument.

Let (a, x) be an arbitrarily picked element in A ✕ (B – C).

	(a, x) ∈ A ✕ (B – C)	Reason
⟺	(a ∈ A) ∧ (x ∈ B – C)	Definition of Cartesian Product
⟺	(a ∈ A) ∧ (x ∈ B) ∧ (x ∉ C)	Definition of Set Difference
⟺	[(a, x) ∈ A ✕ B] ∧ [(a, x) ∉ A ✕ C]	Definition of Cartesian Product
⟺	(a, x) ∈ (A ✕ B) – (A ✕ C)	Definition of Set Difference

Since we have shown that

(a, x) ∈ A ✕ (B – C) ⟺ (a, x) ∈ (A ✕ B) – (A ✕ C)

we know that

A ✕ (B – C) = (A ✕ B) – (A ✕ C)

as desired.

Now that we know that ✕ distributes over -, we can use that fact to prove our next theorem.

Theorem 4.2.6

For any A, B, C ⊆ 𝒰,

A ✕ (B △ C) = (A ✕ B) △ (A ✕ C)

Proof

General Strategy: We’ll proceed in much the same way as we did in the proof for Theorem 4.2.5, except here, we’ll use Theorem 4.2.5 in addition to the definitions and logical equivalencies previously used.

	(a, x) ∈ A ✕ (B △ C)	Reason
⟺	(a, x) ∈ A ✕ [(B – C) ∪ (C – B)]	Definition of Symmetric Difference
⟺	(a, x) ∈ [A ✕ (B – C)] ∪ [A ✕ (C – B)]	Theorem 4.2.2
⟺	(a, x) ∈ [(A ✕ B) – (A ✕ C)] ∪ [(A ✕ C) – (A ✕ B)]	Theorem 4.2.5
⟺	(a, x) ∈ (A ✕ B) △ (A ✕ C)	Definition of Symmetric Difference

Since we’ve shown that

(a, x) ∈ A ✕ (B △ C) ⟺ (a, x) ∈ (A ✕ B) △ (A ✕ C)

we have also shown (by definition) that

A ✕ (B △ C) = (A ✕ B) △ (A ✕ C)

as desired.

Example 4.2.10

Consider the sets

A = { x, y, z }

B = { 1, 2, 3 }

C = { 4, 5 }

According to Theorem 4.2.5, we expect to find that

A ✕ (B – C) = (A ✕ B) – (A ✕ C).

We see that

A ✕ (B – C)	=	{ x, y, z } ✕ ({ 1, 2, 3 } – { 4, 5 })
	=	{ x, y, z } ✕ { 1, 2, 3 }
	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }

A ✕ B	=	{ x, y, z } ✕ { 1, 2, 3 }
	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }

A ✕ C	=	{ x, y, z } ✕ { 4, 5 }
	=	{ (x, 4), (x, 5), (y, 4), (y, 5), (z, 4), (z, 5) }

Now we see that

(A ✕ B) – (A ✕ C)	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }
	=	A ✕ (B – C)

Of course, the power in Theorem 4.2.5 is that it can save us a lot of work if we are ever in a situation where we have to compute (A ✕ B) – (A ✕ C) because that theorem says we could just compute A ✕ (B – C) instead. As demonstrated above, there is much less work involved in calculating A ✕ (B – C) compared to (A ✕ B) – (A ✕ C).

Turning our attention to Theorem 4.2.6, we also expect that

A ✕ (B △ C) = (A ✕ B) △ (A ✕ C).

Calculating A ✕ (B △ C) yields

A ✕ (B △ C)	=	{ x, y, z } ✕ ({ 1, 2, 3 } △ { 4, 5 })
	=	{ x, y, z } ✕ { 1, 2, 3, 4, 5 }
	=	{ (x, 1), (x, 2), (x, 3), (x, 4), (x, 5), (y, 1), (y, 2), (y, 3), (y, 4), (y, 5), (z, 1), (z, 2), (z, 3), (z, 4), (z, 5) }

Now we compute both A ✕ B and A ✕ C:

A ✕ B	=	{ x, y, z } ✕ { 1, 2, 3 }
	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }

A ✕ C	=	{ x, y, z } ✕ { 4, 5 }
	=	{ (x, 4), (x, 5), (y, 4), (y, 5), (z, 4), (z, 5) }

Since A ✕ B and A ✕ C are disjoint, calculating (A ✕ B) △ (A ✕ C) simply involves taking their union

(A ✕ B) △ (A ✕ C)	=	{ (x, 1), (x, 2), (x, 3), (x, 4), (x, 5), (y, 1), (y, 2), (y, 3), (y, 4), (y, 5), (z, 1), (z, 2), (z, 3), (z, 4), (z, 5) }
	=	A ✕ (B △ C)

which is exactly what we expected to happen.

Example 4.2.11

Consider the sets

A = { x, y, z }

B = { 1, 2, 3 }

C = { 1, 4 }

A ✕ (B – C)	=	{ x, y, z } ✕ ({ 1, 2, 3 } – { 1, 4 })
	=	{ x, y, z } ✕ { 2, 3 }
	=	{ (x, 2), (x, 3), (y, 2), (y, 3), (z, 2), (z, 3) }

A ✕ B	=	{ x, y, z } ✕ { 1, 2, 3 }
	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }

A ✕ C	=	{ x, y, z } ✕ { 1, 4 }
	=	{ (x, 1), (x, 4), (y, 1), (y, 4), (z, 1), (z, 4) }

Finally, computing (A ✕ B) – (A ✕ C) yields

(A ✕ B) – (A ✕ C)	=	{ (x, 2), (x, 3), (y, 2), (y, 3), (z, 2), (z, 3) }
	=	A ✕ (B – C)

Once again, we turn our attention to Theorem 4.2.6:

A ✕ (B △ C)	=	{ x, y, z } ✕ ({ 1, 2, 3 } △ { 1, 4 })
	=	{ x, y, z } ✕ { 2, 3, 4 }
	=	{ (x, 2), (x, 3), (x, 4), (y, 2), (y, 3), (y, 4), (z, 2), (z, 3), (z, 4) }

A ✕ B	=	{ x, y, z } ✕ { 1, 2, 3 }
	=	{ (x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3), (z, 1), (z, 2), (z, 3) }

A ✕ C	=	{ x, y, z } ✕ { 1, 4 }
	=	{ (x, 1), (x, 4), (y, 1), (y, 4), (z, 1), (z, 4) }

Last, we compute (A ✕ B) △ (A ✕ C):

(A ✕ B) △ (A ✕ C)	=	{ (x, 2), (x, 3), (x, 4), (y, 2), (y, 3), (y, 4), (z, 2), (z, 3), (z, 4) }
	=	A ✕ (B △ C)

The Book ofFoundational Mathematics

Quick Links