Discrete math for programmers, Part 1: Set algebra

If I said, these Discrete math posts were going to be somehow greater, better than the others out there, I would lie. I treat these math posts as my flashcards. To have a place where I can glance and just know some definition. I’m gonna make it simplified for me (and for the other programmers hopefully -_^). I’m learning discrete math right now, on my own, mostly with the Discrete Math (Wright, Ross) book, just to be a better programmer and I want to have some place to keep my notes.

1. What is a Set in math?

A set is just a collection of unique elements. The keyword here is unique. There are no duplicates allowed.

In your daily tech stack, a set is:

• Set in TypeScript
• MapSet in Elixir
• A database table where you enforce unique keys

Let’s look at how the core operations look in theory versus actual practice.

2. Base set operations

2.1. Union (A ∪ B)

The Theory: You combine everything from both sets. If an item is in both, it only appears once in the result. In logic, this is just your OR operator.

Real-world example: You have a list of emails subscribed to a tech newsletter ($Set A$) and a list subscribed to a business newsletter ($Set B$). You want to send a general holiday email to everyone.

2.1.1. Mathematical context

In formal mathematics, the union of two sets is defined using set-builder notation. It explicitly states that an element belongs to the new set if it satisfies the predicate of belonging to either of the source sets:

2.1.2. Code examples

const tech = new Set(["adam", "eva"]);
const biz = new Set(["eva", "jan"]);
const everyone = new Set([...tech, ...biz]);
// Result: Set { 'adam', 'eva', 'jan' }

tech = MapSet.new(["adam", "eva"])
biz = MapSet.new(["eva", "jan"])
everyone = MapSet.union(tech, biz)
# Result: #MapSet<["adam", "eva", "jan"]>

tech := map[string]struct{}{
    "adam": {},
    "eva":  {},
}

biz := map[string]struct{}{
    "eva": {},
    "jan": {},
}

everyone := make(map[string]struct{})

2.2. Intersection (A ∩ B)

The Theory: You pull only the elements that exist in both $Set A$ and $Set B$ at the same time. In logic, this is your AND operator.

Real-world example: You want to give a special discount to users who are subscribed to your newsletter AND have already bought a product from you.

2.2.1. Mathematical context

It explicitly states that an element belongs to the new set if and only if it satisfies the predicate of belonging to both source sets simultaneously. Here, the flipped wedge symbol ($\land$) represents the logical AND operator:

2.2.2. Code examples

const newsletter = new Set(['adam', 'eva', 'jan']);
const customers = new Set(['eva', 'marek']);
const discount = new Set([...newsletter].filter(x => customers.has(x)));
// Result: Set { 'eva' }

newsletter = MapSet.new(["adam", "eva", "jan"])
customers = MapSet.new(["eva", "marek"])
discount = MapSet.intersection(newsletter, customers)
# Result: #MapSet<["eva"]>

newsletter := map[string]struct{}{
    "adam": {},
    "eva":  {},
    "jan":  {},
}

customers := map[string]struct{}{
    "eva":   {},
    "marek": {},
}

discount := make(map[string]struct{})

for person := range newsletter {
    if _, exists := customers[person]; exists {
        discount[person] = struct{}{}
    }
}
// Result: map[eva:{}]

2.3. Difference (A \ B)

The Theory: You take everything from $Set A$, but throw away any elements that also show up in $Set B$. Basically: “show me A, but minus B”.

Real-world example: You have a list of all registered users ($Set A$) and a list of users who have paid for a premium subscription ($Set B$). You want to send a payment reminder email only to the free users.

2.3.1. Mathematical context

It explicitly states that an element belongs to the new set if it satisfies the predicate of belonging to the first set, while simultaneously not belonging to the second set:

const allUsers = new Set(['adam', 'eva', 'jan']);
const premiumUsers = new Set(['eva']);
const freeUsers = new Set([...allUsers].filter(x => !premiumUsers.has(x)));
// Result: Set { 'adam', 'jan' }

all_users = MapSet.new(["adam", "eva", "jan"])
premium_users = MapSet.new(["eva"])
free_users = MapSet.difference(all_users, premium_users)
# Result: #MapSet<["adam", "jan"]>

func difference[T comparable](a, b map[T]struct{}) map[T]struct{} {
    r := map[T]struct{}{}

    for x := range a {
        if _, ok := b[x]; !ok {
            r[x] = struct{}{}
        }
    }

    return r
}

freeUsers := difference(allUsers, premiumUsers)

2.4. Symmetric Difference

The Theory: You pull elements that exist in one of the sets, but not in both.

Real-world example: You are syncing data between two microservices (Service A and Service B). You want to find a list of records that are out of sync - meaning they exist only in Service A or only in Service B, but haven’t been successfully mirrored between them.

2.4.1. Mathematical context

It can be defined in two equivalent ways using our base set operations: either as the union of two distinct relative complements, or as the total union minus the intersection.

2.4.2. Code examples

const serviceA = new Set(['adam', 'eva', 'jan']);
const serviceB = new Set(['eva', 'jan', 'max']);

const symmetricDiff = new Set([
...[...serviceA].filter(x => !serviceB.has(x)),
...[...serviceB].filter(x => !serviceA.has(x))
]);

// Result: Set { 'adam', 'max' }

service_a = MapSet.new(["adam", "eva", "jan"])
service_b = MapSet.new(["eva", "jan", "max"])

# Calculate the union and the intersection independently
union = MapSet.union(service_a, service_b)
intersection = MapSet.intersection(service_a, service_b)

# Subtract the intersection from the union
symmetric_diff = MapSet.difference(union, intersection)

# Result: #MapSet<["adam", "max"]>

func symmetricDiff[T comparable](a, b map[T]struct{}) map[T]struct{} {
    r := map[T]struct{}{}

    for x := range a {
        if _, ok := b[x]; !ok {
            r[x] = struct{}{}
        }
    }

    for x := range b {
        if _, ok := a[x]; !ok {
            r[x] = struct{}{}
        }
    }

    return r
}

serviceA := map[string]struct{}{
    "adam": {}, "eva": {}, "jan": {},
}
serviceB := map[string]struct{}{
    "eva": {}, "jan": {}, "max": {},
}

symmetricDiff := symmetricDiff(serviceA, serviceB)

// map[adam:{} max:{}]

3. De Morgan’s aws

3.1. Commutative laws

The order of operands in a union or an intersection does not alter the resulting set.

3.2. Associative laws

When performing consecutive operations of the same type, the grouping of the operands does not affect the final set evaluation.

3.3. Distributive laws

Union distributes over intersection, and intersection distributes over union.

3.4. Idempotent laws

An operation performed on a set with itself results in the original set.

3.5. Identity & domination laws

These laws define behavior when operating against boundary conditions: the Universal set ($U$) and the Empty set ($\emptyset$).

3.6. Double complement law

Inverting the complement of a set restores the original set boundary.

4. Formal Sets

Formal sets are sets used to describe collections of symbols, strings, or elements in a precise mathematical way. In the context of formal languages, we usually work with an alphabet ($\Sigma$), which is a finite set of symbols.

From an alphabet, we can create different sets of strings.

4.1. Alphabet

An alphabet is a finite set of symbols that can be used to build strings.

Example:

4.2. Kleene star

The Kleene star:

represents the set of all possible strings that can be created using symbols from $\Sigma$.

The * means that symbols can be used zero or more times.

Example:

Lambda is included because the Kleene star allows using symbols zero times.

4.3. Empty String

The symbol $\lambda$ represents the empty string - a string that contains no characters.

Example:

4.4. Kleene Plus Closure

The Kleene plus closure $\Sigma^+$ is similar to Kleene star, but it requires at least one symbol.

Example:

5. Cartesian Product (A × B)

The Theory: You pair every single element from the first set with every single element from the second set. The result is a new set containing ordered pairs, where the first element always comes from $Set A$ and the second element always comes from $Set B$. If either set is empty, the result is completely empty.

Real-world example: You are building a clothing e-commerce database. You have a set of available colors ($Set\ A = \{\text{"red"}, \text{"blue"}\}$) and a set of available sizes ($Set\ B = \{\text{"S"}, \text{"M"}, \text{"L"}\}$). The Cartesian product generates every possible product variant stock-keeping unit (SKU) you need to track.

5.1. Mathematical context

In formal mathematics, the Cartesian product is denoted by the multiplication cross symbol ($\times$). It is defined using set-builder notation as a set of ordered pairs $(x, y)$, where $x$ satisfies the predicate of belonging to $A$, and $y$ satisfies the predicate of belonging to $B$:

5.2. Code examples

const colors = new Set(['red', 'blue']);
const sizes = new Set(['S', 'M', 'L']);

const skus = new Set(
[...colors].flatMap(c => [...sizes].map(s => [c, s]))
);
// Result: Set { [ 'red', 'S' ], [ 'red', 'M' ], ... 4 more items }

colors = MapSet.new(["red", "blue"])
sizes = MapSet.new(["S", "M", "L"])

skus = for c <- colors, s <- sizes, into: MapSet.new(), do: {c, s}

# Result: #MapSet<[{"blue", "L"}, {"blue", "M"}, {"blue", "S"}, {"red", "L"}, {"red", "M"}, {"red", "S"}]>

colors := map[string]struct{}{
    "red":  {},
    "blue": {},
}

sizes := map[string]struct{}{
    "S": {}, "M": {}, "L": {},
}

skus := make(map[[2]string]struct{})

for c := range colors {
    for s := range sizes {
        skus[[2]string{c, s}] = struct{}{}
    }
}

6. Exercises

So! Time for the main course… I mean exercises. Often, I do not understand very well pure math definitions and the best way for me to learn math is just to do, or analyze exercises (like code samples). Below, I’m gonna show some of my calculations.

6.1. Write down a few elements of set

1. $\{ n \in N \}$

2. $\{ r \in Q : 0< r < 1 \}$

3. $\{ 2^n : n \in N \}$

6.2. How many elements contain set?

1. $\{ n \in N: n^2 = 2 \}$

2. $\{ n \in Z: 0 \le n \le 73 \}$

3. $\{ n \in Z: 5 <= |n| <= 73 \}$

4. $P(\{ 0,1,2,3 \})$

6.3. Define the following sets

1. $A \cup B$

2. $A \cap C$

3. $(A \cup B) \cap C^c$

4. $A \setminus B$

5. $C \setminus D$

6. $B \oplus D$

6.4. Define the following sets

At first, we should take a look at out universal space:

1. $B^c \cap C^c$

2. $(B \cap C)^c$

3. $(B \cup C)^c$

4. $A^c \cap C$