Discrete Mathematics/Set theory/Page 2

Power Sets

The power set of a set A is the set of all its subsets (including, of course, itself and the empty set). It is denoted by P(A).

Using set comprehension notation, P(A) can be defined as

P(A) = { Q | Q ⊆ A }

Example 4

Write down the power sets of A if:

(a) A = {1, 2, 3}

(b) A = {1, 2}

(c) A = {1}

(d) A = ø

Solution

(a) P(A) = { {1, 2, 3}, {2, 3}, {1, 3}, {1, 2}, {1}, {2}, {3}, ø }

(b) P(A) = { {1, 2}, {1}, {2}, ø }

(c) P(A) = { {1}, ø }

(d) P(A) = { ø }

Cardinality of a Power Set

Look at the cardinality of the four sets in Example 4, and the cardinality of their corresponding power sets. They are:

	| A |	| P(A) |
(a)	3	8
(b)	2	4
(c)	1	2
(d)	0	1

Clearly, there's a simple rule at work here: expressed as powers of 2, the cardinalities of the power sets are 2³, 2², 2¹ and 2⁰.

It looks as though we have found a rule that if | A | = k, then | P(A) | = 2^k. But can we see why?

Well, the elements of the power set of A are all the possible subsets of A. Any one of these subsets can be formed in the following way:

• Choose any element of A. We may decide to include this in our subset, or we may omit it. There are therefore 2 ways of dealing with this first element of A.

• Now choose a second element of A. As before, we may include it, or omit it from our subset: again a choice of 2 ways of dealing with this element.

• ...and so on through all k elements of A.

Now the fundamental principle of combinatorics tells us that if we can do each of k things in 2 ways, then the total number of ways of doing them all, one after the other, is 2^k.

Each one of these 2^k combinations of decisions - including elements or omitting them - gives us a different subset of A. There are therefore 2^k different subsets altogether.

So if | A | = k, then | P(A) | = 2^k.

The Foundational Rules of Set Theory

The laws listed below can be described as the Foundational Rules of Set Theory. We derive them by going back to the definitions of intersection, union, universal set and empty set, and by considering whether a given element is in, or not in, one or more sets.

The Idempotent Laws

As an example, we'll consider the ′I heard you the first time′ Laws – more correctly called the Idempotent Laws - which say that:

A ∩ A = A and A ∪ A = A

This law might be familiar to you if you've studied logic. The above relationship is comparable to the tautology.

These look pretty obvious, don't they? A simple explanation for the intersection part of these laws goes something like this:

The intersection of two sets A and B is defined as just those elements that are in A and in B. If we replace B by A in this definition we get that the intersection of A and A is the set comprising just those elements that are in A and in A. Obviously, we don't need to say this twice (I heard you the first time), so we can simply say that the intersection of A and A is the set of elements in A. In other words:

A ∩ A = A

We can derive the explanation for A ∪ A = A in a similar way.

De Morgan's Laws

There are two laws, called De Morgan's Laws, which tell us how to remove brackets, when there's a complement symbol - ′ - outside. One of these laws looks like this:

(A ∪ B) ′ = A ′ ∩ B ′

(If you've done Exercise 3, question 4, you may have spotted this law already from the Venn Diagrams.)

Look closely at how this Law works. The complement symbol after the bracket affects all three symbols inside the bracket when the brackets are removed:

A becomes A ′

B becomes B ′

and ∪ becomes ∩.

To prove this law, note first of all that when we defined a subset we said that if

A ⊆ B and B ⊆ A, then A = B

So we prove:

(i) (A ∪ B) ′ ⊆ A ′ ∩ B ′

and then the other way round:

(ii) A ′ ∩ B ′ ⊆ (A ∪ B) ′

The proof of (i) goes like this:

Let's pick an element at random x ∈ (A ∪ B) ′. We don't know anything about x; it could be a number, a function, or indeed an elephant. All we do know about x, is that

x ∈ (A ∪ B) ′

So

x ∉ (A ∪ B)

because that's what complement means.

This means that x answers No to both questions Are you in A? and Are you in B? (otherwise it would be in the union of A and B). Therefore

x ∉ A and x ∉ B

Applying complements again we get

x ∈ A ′ and x ∈ B ′

Finally, if something is in two sets, it must be in their intersection, so

x ∈ A ′ ∩ B ′

So, any element we pick at random from (A ∪ B) ′ is definitely in A ′ ∩ B ′. So by definition

(A ∪ B) ′ ⊆ A ′ ∩ B ′

The proof of (ii) is similar:

First, we pick an element at random from the first set, x ∈ A ′ ∩ B ′

Using what we know about intersections, that means

x ∈ A ′ and x ∈ B ′

So, using what we know about complements,

x ∉ A and x ∉ B

And if something is in neither A nor B, it can't be in their union, so

x ∉ A ∪ B

So, finally:

x ∈ (A ∪ B) ′

So:

A ′ ∩ B ′ ⊆ (A ∪ B) ′

We've now proved (i) and (ii), and therefore:

(A ∪ B) ′ = A ′ ∩ B ′

This gives you a taste for what's behind these laws. So here they all are.

The Laws of Sets

Commutative Laws

A ∩ B = B ∩ A

A ∪ B = B ∪ A

Associative Laws

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

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

Distributive Laws

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Idempotent Laws

A ∩ A = A

A ∪ A = A

Identity Laws

A ∪ ø = A

A ∩ U = A

A ∪ U = U

A ∩ ø = ø

Involution Law (A ′) ′ = A

Complement Laws

A ∪ A' = U

A ∩ A' = ø

U ′ = ø

ø ′ = U

De Morgan’s Laws

(A ∩ B) ′ = A ′ ∪ B ′

(A ∪ B) ′ = A ′ ∩ B ′

Duality and Boolean Algebra

You may notice that the above Laws of Sets occur in pairs: if in any given law, you exchange ∪ for ∩ and vice versa (and, if necessary, swap U and ø) you get another of the laws. The 'partner laws' in each pair are called duals, each law being the dual of the other.

• For example, each of De Morgan's Laws is the dual of the other.

• The first complement law, A ∪ A ′ = U, is the dual of the second: A ∩ A ′ = ø.

• ... and so on.

This is called the Principle of Duality. In practical terms, it means that you only need to remember half of this table!

This set of laws constitutes the axioms of a Boolean Algebra. See Boolean Algebra for more.

Proofs using the Laws of Sets

We may use these laws - and only these laws - to determine whether other statements about the relationships between sets are true or false. Venn diagrams may be helpful in suggesting such relationships, but only a proof based on these laws will be accepted by mathematicians as rigorous.

Example 5

Using the Laws of Sets, prove that the set (A ∪ B) ∩ (A ′ ∩ B) ′ is simply the same as the set A itself. State carefully which Law you are using at each stage.

Before we begin the proof, a few do's and don't’s:

Do start with the single expression (A ∪ B) ∩ (A ′ ∩ B) ′, and aim to change it into simply A.	Don’t begin by writing down the whole equation (A ∪ B) ∩ (A ′ ∩ B) ′ = A – that’s what we must end up with.
Do change just one part of the expression at a time, using just one of the set laws at a time.	Don't miss steps out, and change two things at once.
Do keep the equals signs underneath one another.	Don't allow your work to become untidy and poorly laid out.
Do state which law you have used at each stage.	Don't take even the simplest step for granted.

Solution

		Law Used
(A ∪ B) ∩ (A ′ ∩ B) ′	= (A ∪ B) ∩ ((A ′) ′ ∪ B ′)	De Morgan’s
	= (A ∪ B) ∩ (A ∪ B ′)	Involution
	= A ∪ (B ∩ B ′)	Distributive
	= A ∪ ø	Complement
	= A	Identity

We have now proved that (A ∪ B) ∩ (A ′ ∩ B) ′ = A whatever the sets A and B contain. A statement like this – one that is true for all values of A and B – is sometimes called an identity.

Hints on Proofs

There are no foolproof methods with these proofs – practice is the best guide. But here are a few general hints.

• Start with the more complicated side of the equation, aiming to simplify it into the other side.

• Look for places where the Distributive Law will result in a simplification (like factorising in 'ordinary' algebra - see the third line in Example 5 above).

• You’ll probably use De Morgan’s Law to get rid of a ' symbol from outside a bracket.

• Sometimes you may need to 'complicate' an expression before you can simplify it, as the next example shows.

Example 6

Use the Laws of Sets to prove that A ∪ (A ∩ B) = A.

Looks easy, doesn’t it? But you can go round in circles with this one. (Try it first before reading the solution below, if you like.) The key is to 'complicate' it a bit first, by writing the first A as A ∩ U (using one of the Identity Laws).

Solution

		Law Used
A ∪ (A ∩ B)	= (A ∩ U) ∪ (A ∩ B)	Identity
	= A ∩ (U ∪ B)	Distributive
	= A ∩ (B ∪ U)	Commutative
	= A ∩ U	Identity
	= A	Identity

Set Theory Exercise 4

Click link for Set Theory Exercise 4.

Cartesian Products

Ordered pair

To introduce this topic, we look first at a couple of examples that use the principle of combinatorics that we noted earlier (see Cardinality); namely, that if an event R can occur in r ways and a second event S can then occur in s ways, then the total number of ways that the two events, R followed by S, can occur is r × s. This is sometimes called the r-s Principle.

Example 7

MENU

Main Course

Poached Halibut

Roast Lamb

Vegetable Curry

Lasagne

Dessert

Fresh Fruit Salad

Apple Pie

Gateau

How many different meals – Main Course followed by Dessert - can be chosen from the above menu?

Solution

Since we may choose the main course in four ways, and then the dessert in three ways to form a different combination each time, the answer, using the r-s Principle, is that there are 4 × 3 = 12 different meals.

Example 8

You're getting ready to go out. You have 5 different (clean!) pairs of underpants and two pairs of jeans to choose from. In how many ways can you choose to put on a pair of pants and some jeans?

Solution

Using the r-s Principle, there are 5 × 2 = 10 ways in which the two can be chosen, one after the other.

In each of the two situations above, we have examples of ordered pairs. As the name says, an ordered pair is simply a pair of 'things' arranged in a certain order. Often the order in which the things are chosen is arbitrary – we simply have to decide on a convention, and then stick to it; sometimes the order really only works one way round.

In the case of the meals, most people choose to eat their main course first, and then dessert. In the clothes we wear, we put on our underpants before our jeans. You are perfectly free to fly in the face of convention and have your dessert before the main course - or to wear your underwear on top of your trousers - but you'll end up with different sets of ordered pairs if you do. And, of course, you'll usually have a lot of explaining to do!

The two 'things' that make up an ordered pair are written in round brackets, and separated by a comma; like this:

(Lasagne, Gateau)

You will have met ordered pairs before if you've done coordinate geometry. For example, (2, 3) represents the point 2 units along the x-axis and 3 units up the y-axis. Here again, there's a convention at work in the order of the numbers: we use alphabetical order and put the x-coordinate before the y-coordinate. (Again, you could choose to do your coordinate geometry the other way round, and put y before x, but once again, you'd have a lot of explaining to do!)

Using set notation, then, we could describe the situation in Example 7 like this:

M = {main courses}, D = {desserts}, C = {complete meals}.

Then C could be written as:

C = { (m, d) | m ∈ M and d ∈ D }.

C is called the set product or Cartesian product of M and D, and we write:

C = M × D

(read 'C equals M cross D')

Suppose that the menu in Example 7 is expanded to include a starter, which is either soup or fruit juice. How many complete meals can be chosen now?

Well, we can extend the r-s Principle to include this third choice, and get 2 × 4 × 3 = 24 possible meals.

If S = {soup, fruit juice}, then we can write:

C = S × M × D

An element of this set is an ordered triple: (starter, main course, dessert). Notice, then, that the order in which the individual items occur in the triple is the same as the order of the sets from which they are chosen: S × M × D does not give us the same set of ordered triples as M × D × S.

Ordered n-tuples

In general, if we have n sets: A₁, A₂, ..., A_n, then their Cartesian product is defined by:

A₁ × A₂ × ... × A_n = { (a₁, a₂, ..., a_n) | a₁ ∈ A₁, a₂ ∈ A₂, ..., a_n ∈ A_n) }

and (a₁, a₂, ..., a_n) is called an ordered n-tuple.

Notation

A₁ × A₂ × ... × A_n is sometimes written:

$\times _{i=1}^{n}$ A_i

The Cartesian Plane

The Cartesian Plane: Fig. 8

You probably know already the way in which a point in a plane may be represented by an ordered pair. The diagram in Fig. 8 illustrates a Cartesian Plane, showing the point represented by the ordered pair (5, 2).

The lines are called axes: the x-axis and the y-axis. The point where they meet is called the origin. The point (5, 2) is then located as follows: start at the origin; move 5 units in the direction of the x-axis, and then 2 units in the direction of the y-axis.

Using set notation:

If X = {numbers on the x-axis} and Y = {numbers on the y-axis}, then:

(5, 2) ∈ X × Y

and, indeed, if X = {all real numbers}, and Y = {all real numbers} then X × Y as a whole represents all the points in the x-y plane.

(This is why you will sometimes see the x-y plane referred to as R², where R = {real numbers}.)
Example 9

It is believed that, if A, B, P and Q are sets where B ⊂ A and Q ⊂ P, then:

B × Q ⊂ A × P

Use a carefully shaded and labelled Cartesian diagram to investigate this proposition.

Solution

Bearing in mind what we said above about the ordered pairs in X × Y corresponding to points in the x-y plane, if we want to represent a Cartesian product like A × P on a diagram, we shall need to represent the individual sets A and P as sets of points on the x- and y- axes respectively.

The region representing the Cartesian product A × P is then represented by the points whose x- and y-coordinates lie within these sets A and P. Like this:

The Cartesian Plane: Fig. 9a

The same can also be said about B and Q: B must lie on the x-axis, and Q on the y-axis.

In addition, since B ⊂ A, then we must represent B as a set chosen from within the elements of A. Similarly, since Q ⊂ P, the elements of Q must lie within the elements of P.

When we add these components on to the diagram it looks like this:

The Cartesian Plane: Fig. 9b

Finally, when we represent the set B × Q as a rectangle whose limits are determined by the limits of B and Q, it is clear that this rectangle will lie within the rectangle representing A × P:

The Cartesian Plane: Fig. 9c

So, the proposition B × Q ⊂ A × P appears to be true.

Set Theory Exercise 5

Click link for Set Theory Exercise 5.