Tag Archives: set algebra

Maths in IT #3: Algebra of sets

Hey everyone and welcome back! I’ve already announced this posts subject in my previous post, algebra of sets.¬†So algebra is difficult and scary. At least that’s what people say (hmm hmm), so let’s shake that off. I’m sorry if you got the reference ūüôā

If you haven’t read my previous posts I really suggest you do so as this post will continue where the previous one left off.

  1. Maths in IT #1: Basic set theory
  2. Maths in IT #2: Venn diagrams
  3. Maths in IT #3: Algebra of sets
  4. Coming soon…

Here’s a quick cheat sheet of symbols introduced in the previous post:
Intersection: A \cap B = \{x | x \in A \land x \in B\}
Union: A \cup B = \{x | x \in A \lor x \in B\}
Universe U: The collection of all elements we consider for our scenario.
Absolute complement (or simply complement): A^c = \{x | x \in U \land x \notin A\}
Relative complement of A in B: B \cap A^c = A \setminus B

Algebra

What exactly is algebra? It’s about the study of symbols, or operations, and laws for manipulating these operations.¬†Elementary algebra, for example, is a set of laws for operations (+, -, /, *) on numbers. Just like that \cap, \cup and¬†A^c¬†are operations on sets and the laws used to manipulating them is called the algebra of sets.

These laws can help us to simplify formulas. So let’s get started.

Commutative property

Consider the following addition: 2 + 3. I’m pretty sure we all know the answer is 5 and the answer doesn’t change if we switch the¬†numbers to 3 + 2. More abstract we can say that for every two numbers x and y goes that x + y = y + x.
When the order of operands¬†(that is the objects on which an operation is performed) in an operation doesn’t matter for the outcome of that operation we call that operation commutative.

Multiplication (on real numbers) is commutative too, because 2 \cdot 3 = 3 \cdot 2¬†(you may be used to seeing x or * as multiplication symbol, but you should remember \cdot from high school). Minus isn’t commutative, because 3 - 2 \neq 2 - 3 and neither is division, 2/3 \neq 3/2.

When working with sets we can say that A \cap B = B \cap A and A \cup B = B \cup A. That means both \cap and \cup are commutative.

Associative property

When the order in which the same operation is performed in a single formula¬†is unimportant for the outcome of that formula we say that the operation is associative. For example (1 + 2) + 3 = 1 + (2 + 3). It doesn’t matter if we first evaluate 1 + 2 and then add 3 or first evaluate 2 + 3 and add it to 1, the outcome is always 6.
The same holds true for multiplication, because (2 \cdot 3) \cdot 4 = 2 \cdot (3 \cdot 4) but not for subtraction, (10 - 8) - 2 \neq 10 - (8 - 2) and division, (16/4)/2 \neq 16/(4/2).

When looking at sets we find that both \cap and \cup are associative, because (A \cap B) \cap C = A \cap (B \cap C) and (A \cup B) \cup C = A \cup (B \cup C).

That means parenthesis can be omitted, removing any confusion on operator precedence.

And with the commutative and associative properties of both intersection and union we can now simplify
C \cap (D \cap A) \cap B
to A \cap B \cap C \cap D
or C \cup (D \cup A) \cup B
to A \cup B \cup C \cup D.
And when we combine intersection and union we can simplify as well. D \cap (C \cup (B \cup A)) can be simplified to (A \cup B \cup C) \cap D. Notice that we still need parenthesis to define the order of the \cap and \cup operations.

We can now also take the intersection or union of any number of sets because we don’t have to worry about the order of operands or operators. A_1 \cap A_2 \cap A_3... gets tiresome really quick though. So suppose we have A_1 to A_{100}. The intersection or union of all those sets can now be expressed as follows:
\displaystyle\bigcup_{i=1}^{100} A_i     or     \displaystyle\bigcap_{i=1}^{100} A_i
And inline this look like \cup_{i=1}^{100} A_i and \cap_{i=1}^{100} A_i.

Sometimes we don’t know if a set has 100 sets. Especially when a set is an infinite set of sets the above notation is not feasible. We can now¬†use index notation to intersect or union all sets within the set.
\displaystyle\bigcap_{i \in I} A_i     or     \displaystyle\bigcup_{i \in I} A_i
\cap_{i \in I} A_i and \cup_{i \in I} A_i basically means “intersect/union for every set i in set I” (think of a foreach loop on a¬†List of Lists in C#).

Distributive property

The distributive property is difficult to describe in words. Just remember that multiplication is distributive over addition, meaning that 3 \cdot (4 + 5) = (3 \cdot 4) + (3 \cdot 5). More generally x(y + z) = xy + xz (the multiplication symbol is often omitted between letters).

\cap is distributive over \cup, meaning that
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

Likewise \cup is distributive over \cap, so
A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

We can now show that (A \cap B) \cap (A \cup B) = A \cap B. When we apply the distributive property on (A \cap B) \cap (A \cup B) we get ((A \cap B) \cap A) \cup ((A \cap B) \cap B).
Here it is again, but with colors (and non-mathematical notation) so you can follow where everything went:
(A n B) n (A u B) = ((A n B) n A) u ((A n B) n B).
Applying commutativity and associativity we can now simplify further:
((A \cap B) \cap A) \cup ((A \cap B) \cap B) = (A \cap A \cap B) \cup (A \cap B \cap B).
In the previous article, Maths in IT #2: Venn diagrams, we have seen that A \cap A = A and A \cup A = A. This is called idempotence and can be applied here (twice) to simplify further:
(A \cap A \cap B) \cup (A \cap B \cap B) = (A \cap B) \cup (A \cap B) = A \cap B

Let’s repeat that:

(A \cap B) \cap (A \cup B)

Distributivity

((A \cap B) \cap A) \cup ((A \cap B) \cap B)

Associativity

(A \cap B \cap A) \cup (A \cap B \cap B)

Commutativity

(A \cap A \cap B) \cup (A \cap B \cap B)

Idempotence

(A \cap B) \cup (A \cap B)

Idempotence

A \cap B

So we could¬†make use of distributivity, associativity,¬†commutativity, and idempotence to make a rather difficult formula pretty easy! Unfortunately it was a lot less easy to do…

Other properties

Unfortunately we’re not done yet. There are a few more properties, some of which we’ve already encountered, that I’d like to go over.

First we have the absorption law, which states that A \cap (A \cup B) = A and A \cup (A \cap B) = A.

We’ve seen the so called null element, or empty set, \emptyset. Just like with numbers (x + 0 = x, x - 0 = x and x \cdot 0 = 0) there are some rules for working with \emptyset. Luckily they’re not that hard.
A \cap \emptyset = \emptyset and A \cup \emptyset = A.

When a universe U is defined we can say the following:
A \cap U = A and A \cup U = U.

I’ve shown you that a double complement returns the original:¬†(A^c)^c = A.
Also, A \cap A^c = \emptyset and A \cup A^c = U.

De Morgan’s Law

Finally we’ll look at the law of De Morgan, named after its inventor, the British mathematician Augustus De Morgan.
Suppose my blog can¬†only be read by people who have not studied maths or¬†IT. Let A = \{x | \text{x has studied maths}\} and let B = \{x | \text{x has studied IT}\}. So now the people who may read my blog are people who haven’t studied maths or IT: (A \cup B)^c. I could also say people who haven’t studied maths and people who haven’t studied IT may read my blog: A^c \cap B^c. But that’s the same set of people!
In the following Venn diagram this is represented by the white part.

A Venn diagram of De Morgan's Law
A Venn diagram of De Morgan’s Law

So in short (A \cup B)^c = A^c \cap B^c.

Now suppose my blog may be read only by people who haven’t studied both maths and IT. So that’s (A \cap B)^c. Or we could say people who haven’t studied maths and¬†who haven’t studied IT, A^c \cup B^c. And again this is the same set of people. In the Venn diagram it’s the part where A and B don’t overlap¬†(so almost everything).

A Venn diagram of De Morgan's Law
A Venn diagram of De Morgan’s Law

And so that means (A \cap B)^c = A^c \cup B^c.

Now let’s take another example of how to simplify a formula. Suppose we have B \cap (A \cap B)^c. So let’s first apply De Morgan’s law: B \cap (A \cap B)^c = B \cap (A^c \cup B^c). And now you may recognize a nice pattern for distributivity! So let’s apply distributivity, B \cap (A^c \cup B^c) = (B \cap A^c) \cup (B \cap B^c).¬†That’s nice, because we know that B \cap B^c = \emptyset. And now we know that (B \cap A^c) \cup \emptyset = B \cap A^c. And maybe you’ll remember this from my previous post, this is B \setminus A. And there you have it!

Again, let’s repeat:

B \cap (A \cap B)^c

De Morgan’s law

B \cap (A^c \cup B^c)

Distributivity

(B \cap A^c) \cup (B \cap B^c)

Complement rule

(B \cap A^c) \cup \emptyset

Null element

B \cap A^c

Relative complement

B \setminus A

And there you go! You algebra master, you!

So how will this help you in your day to day programming tasks? For most of us very little I’m afraid, except that you can work out some difficult set operations¬†on paper and possibly simplify requirements. I’m no database developer, but I can imagine you’d need this when developing databases (and to a lesser extent when working with databases).

We did venture into the world of algebra though, and if you’re still with me I say congratulations! Algebra is a bit too abstract and difficult for many people.

I’m leaving you with a little cheat sheet of today’s lessons and I hope to see you again next time (no algebra, I promise)!

Commutativity:
A \cap B = B \cap A
A \cup B = B \cup A

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

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

Idempotence:
A \cup A = A
A \cap A = A

Absorption:
A \cup (A \cap B) = A
A \cap (A \cup B) = A

Null element:
A \cap \emptyset = \emptyset
A \cup \emptyset = A

Universe:
A \cap U = A
A \cup U = U

Complement:
A \cap A^c = \emptyset
A \cup A^c = U

Double complement:
(A^c)^c = A

Relative complement:
A \cap B^c = A \setminus B

De Morgan’s Law:
(A \cap B)^c = A^c \cup B^c
(A \cup B)^c = A^c \cap B^c