Maths in IT #3: Algebra of sets

Sander Rossel

4.86/5 (6 votes)

16 Nov 2015CPOL6 min read

22.3K

An introduction to algebra and 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.

Maths in IT #1: Basic set theory [CodeProject]
Maths in IT #2: Venn diagrams [CodeProject]
Maths in IT #3: Algebra of sets
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.

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).

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 \cap A = A$
$A \cup A = A$

Absorption:
$A \cap (A \cup B) = A$
$A \cup (A \cap 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$

The post Maths in IT #3: Algebra of sets appeared first on Sander's bits.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)