Math Concepts for Programming - Sets
Tags: javascript, datastructures, node, math
Published: 2020-09-13 16:48:17

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](https://books.google.com.br/books?id=yZ68h97pnAkC&pg=PA1&redir_esc=y#v=onepage&q&f=false) 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:

```typescript
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**.

```typescript
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**.

```typescript
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. 

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

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

```typescript
usersFromLastWeek = {12938, 89032, 55866}
```

* The empty set.
```typescript
S = {}
```

Sets can also represent more complex cases.
* The set of natural numbers (infinite).

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

* The set of sets mentioned above.

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

* Self-containing sets.

```typescript
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.

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

* **Add** one or more elements to the Set.

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

* **Remove** one or more elements from the Set.

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

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

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

* **Iterate** to loop over elements in the Set.
```typescript
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.
```typescript
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.
```typescript
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`.
```typescript
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`

```typescript
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.

```typescript
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.

```typescript
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

```typescript
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.

```typescript
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.

```typescript
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.

```typescript
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.

```typescript
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.

```typescript
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.
```typescript
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.

```typescript
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.

```typescript
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
```typescript
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](https://www.youtube.com/watch?v=8JDgNL5HsPo)