Math Concepts for Programming - Sets

Today, I'm starting a series of posts about object relationships. In this post, we are going to see a foundational concept in Mathematics called Set. Let's check some use case examples and operations that can be applied to them.

Sets are "The Building Blocks"

A set is a well-defined collection of distinct objects.

The objects that belong to a set are called its elements (or points or members)

Source: Functional Analysis by P. K. Jain, Khalil Ahmad, and Om P. Ahuja

An informal way of defining a Set is a container (box/circle) that has distinct objects inside. We can represent it with the following notation:

S = {1, 2, 'some string'}

• The elements of the Set are written inside the curly braces. S is an identifier to the Set.

The order of the objects does not matter.

S = {1, 2, 3} = {2, 3, 1} = {3, 2, 1}

• The definition of Set does not allow for repetition of the same element, so each element should be represented at most once.

S = {1, 1, 2, 3, 2, 3} = {1, 2, 3}

Uses

We can use Sets to define the world around us.

• The set of states in a country.

States = {'New York', 'California', 'Florida', 'Washington DC', ...} // size = 50

• The set of username ids who have used your website this week.

usersFromLastWeek = {12938, 89032, 55866}

• The empty set.

S = {}

Sets can also represent more complex cases.

• The set of natural numbers (infinite).

S = {1, 2, 3, 4, ...} // Size = Infinity

• The set of sets mentioned above.

S = { 
    {'New York', 'California', 'Florida', 'Washington DC', ...},
    {12938, 89032, 55866},
    {}
} // Size = 3

• Self-containing sets.

S = {1, 2, S} =
{
    1, 2,
    { // S
        1, 2, { // S
            1, 2, {...}
        }
    }
} // Size = 3

💡 Elements contained in nested Sets are not considered direct elements from the Root Set (S).

Properties

• Size = Number of elements present in the Set.

Operations

Operations are ways to read and/or transform the Set into another Set (or another object):

💡 The notation below is pseudo-code

• Is Empty to check if Set size equals zero.

S1 = {}
isEmpty(S1) // = true
S2 = {1, 2, 3}
isEmpty(S2) // = false

• Add one or more elements to the Set.

S1 = {1, 2}; 
S2 = add(S1, 3, 10); // = {1, 2, 3, 10};

• Remove one or more elements from the Set.

S1 = {'a', 'b', 'c', 'd'}; 
S2 = remove(S1, 'c') // = {'a', 'b', 'd'}

• Has to check if an element is contained in the Set.

S1 = {'a', 'b', 'c', 'd'}; 
has(S1, 'e') // False
has(S1, 'a') // True

• Iterate to loop over elements in the Set.

S1 = {'Sandra', 'Mary', 'Louis'};
for (let person of S1) {
    // person = Sandra, Mary and Louis, respectively
    // Order may vary
}

• Equals for comparing if one Set contains the exact same elements as another Set.

S1 = {'first', 'second', 'third'}
S2 = {'second', 'third', 'first'} // Order does not matter
equals(S1, S2) // True
S3 = {'fourth'}
equals(S1, S3) // False

• Union: Creates a resulting Set that contains all elements from both Sets.

S1 = {'first', 'second', 'third'}
S2 = {'fourth'}
union(S1, S2) // = {'first', 'second', 'third', 'fourth'}

• Difference: Creates a resulting Set with elements in Set1 that are not contained in Set2.

S1 = {'first', 'second', 'third'}
S2 = {'second'}
difference(S1, S2) // = {'first', 'third'}

• Intersection: Creates a resulting set that contains only elements both present in Set1 and Set2

S1 = {'first', 'second', 'third'}
S2 = {'second', 'fourth'}
intersection(S1, S2) // = {'second'}

• Disjoint: 2 sets are disjoint if their intersection is equal to the empty set.

S1 = {1, 2, 3}
S2 = {4, 5, 6}
areDisjoint(S1, S2) // = True

S3 = {3, 9, 10}
areDisjoint(S1, S3) // = False, because of "3"
areDisjoint(S2, S3) // = True

• Filter for getting a set of only the elements that satisfy a given condition. The elements that do not satisfy the condition are not part of the result.

S1 = {1, 2, 3, 4, 5, 6}
numberIsEven = (number) => number % 2 === 0;
S2 = filter(S1, numberIsEven) // = {2, 4, 6}

• Map for mapping Set elements into other elements

S1 = {1, 2, 3, 4, 5}
S2 = map(S1, (number) => number * 9)) // = {9, 18, 27, 36, 45}

• Reduce for iterating on the Set and creating a new result. It takes an accumulator and item and returns a new value for the accumulator.

S1 = {1, 2, 3, 4, 5}
reduce (S1, (count, element) => count + element, 0) // Sum all elements, = 15

• Symmetric Difference for obtaining the elements that are in either of the Sets, but not in both of them.

S1 = {1, 2, 3, 4}
S2 = {2, 4, 5, 6}
S3 = symmetricDifference(S1, S2) // = {1, 3, 5, 6}

• Is Superset For checking whether one Set contains all elements of the other Set.

S1 = {1, 2, 3, 4}
S2 = {1}
isSuperset(S1, S2) // = true
S3 = {3, 4}
isSuperset(S1, S3) // = true
S4 = {3, 4, 5}
isSuperset(S1, S4) // = false

• is Subset For checking whether all elements of one Set are contained in another Set.

S1 = {1, 2, 3, 4}
S2 = {1}
isSubset(S2, S1) // = true
S3 = {3, 4}
isSubset(S3, S1) // = true
S4 = {3, 4, 5}
isSubset(S4, S1) // = false

• Find: Used to find one element in the Set that satisfies some constraint.

S1 = {1, 2, 3, 4, 5}
element = find(S1, n => n > 3) // = 4 or 5 (order may vary)

• Every: Check if all elements of the Set satisfy some constraint.

S1 = {1, 2, 3, 4, 5}
element = every(S1, n => n < 10) // = True

S1 = {1, 2, 3, 4, 5}
element = every(S1, n => n < 3) // = False, because of 4 and 5

• Order two or more Sets by their sizes. Returns a tuple with size as the number of Sets provided.

S1 = {1, 2}
S2 = {0}
S3 = {4, 1, 2}

order(S1, S2) // (S2, S1, S3)

• Changes: A way to compare 2 Sets and find which elements must be removed or added from the first set to become equal to the second set.

S1 = {1, 2, 3, 4, 5, 6}
S2 = {4, 5, 6, 7}
Changes(S1, S2) = ({1, 2, 3}, {7}) // Starting from S1, remove 1, 2 and 3, and add 7 to transform it to S2

• Cartesian Product: Multiply two sets in order to create a set of ordered pairs

S1 = {'a', 'b', 'c'}
S2 = {0, 1}
S3 = cartesianProduct(S1, S2) // = { ('a', 0), ('a', 1), ('b', 0), ('b', 1), ('c', 0), ('c', 1) }

In the next post, we are going to take a deeper look at ordered pairs and its uses.

Bonus

Russell's Paradox - a.k.a. The Barber Paradox