April 21, 2021
0 strokes bestowed

Set Theory

A Primer

edit

I find Sets and set theory to be a fascinating concept, both in the abstract and in the concrete , and one that I find more and more useful as time goes on. I've wanted to write an introductory post on the topic for a while now and hope it might inspire a similar interest in Sets for you.

What is a Set?

A Set is a collection of unique elements. Those elements can be literally anything. There exists the set of all integers that are factors of 3, the set of all aquatic mammals, the set of all of my siblings.

A Set can be full of many elements, such as the set of all blades of grass in my lawn , or a set can be empty, such as the set of all humans living on planets other than Earth.

Sets, in the abstract, also don't have a sense of "order". If I'm talking about the set of all whole numbers between the values of 1 and 5, they do not necessarily need to come in the order: 1, 2, 3, 4, 5. They can be thought of just as equally in the order: 2, 1, 4, 3, 5 or any other order. In this way, Sets are like bag data structures.

Throughout the rest of this post, I will be using drawings to aid in my explanation, so to get started, here's a Set:

A circle representing a "set", filled in with a color

It is important to note that Sets often exist within a universe:

A circle representing a "set", surrounded by a square representing the "universe" the set lives in

Sets interacting with other Sets

Sets become far more interesting (and useful) when we consider how they interact with one another.

Unions

The union of Set A and Set B is the Set containing all the elements from Set A and all the elements from Set B.

Two slightly overlapping circles, all filled in with color

function union(setA, setB) {
  // Make a copy
  const result = new Set(setA)

  for (let element of setB) {
    result.add(element)
  }

  return result
}

Intersections

The intersection of Set A and Set B is the Set containing the elements in Set A that are also in Set B. You may recognize this as a Venn Diagram.

Two slightly overlapping circles, only the overlap is colored in

function intersection(setA, setB) {
  const result = new Set()

  for (let element of setA) {
    if (setB.has(element)) {
      result.add(element)
    }
  }

  return result
}

Differences

The difference of Set A and Set B is the Set containing all the elements from Set A that are not in Set B.

Two slightly overlapping circles, only the left circle, minus the overlap, is colored in

function difference(setA, setB) {
  const result = new Set()

  for (let element of setA) {
    if (!setB.has(element)) {
      result.add(element)
    }
  }

  return result
}

Note that the difference between two sets is dependent upon the order of the arguments. That is, given that Set A and Set B are not equal sets, then difference(setA, setB) will not be equal to difference(setB, setA)

Symmetric differences

The symmetric difference of Set A and Set B is the Set containing all the elements that are not shared by Set A and Set B.

Two slightly overlapping circles, everything but the overlap is colored in

function symmetricDifference(setA, setB) {
  const result = new Set()

  for (let element of setA) {
    if (!setB.has(element)) {
      result.add(element)
    }
  }

  for (let element of setB) {
    if (!setA.has(element)) {
      result.add(element)
    }
  }

  return result
}

Note, unlike difference, symmetricDifference will achieve the same result regardless of argument order. In this case, symmetricDifference(setA, setB) will result in the same set as symmetricDifference(setB, setA).

Complements

The complement of a Set A is the Set containing all of the elements not in Set A. By default, this would be all the other elements in the universe, but when constrained, complements can be useful.

Two adjacent universe squares with the same circle as a set inside each. In the first, the set is colored in, in the second, everything in the universe except for the set is colored in

For example, the symmetric difference of Set A and Set B is equivalent to the complement of the intersection of Set A and Set B. We can figure this out by first creating the union of Set A and Set B, then their intersection, and then getting the difference of those two results.

const all = union(setA, setB)
const shared = intersection(setA, setB)
const notShared = difference(all, shared)

Subsets and Supersets

Set A is a subset of Set B if every element of Set A is in Set B.

Two concentric circles, one containing the other, colored different colors. Set A is fully inside Set B, and thus A is a subset of B, and B is a superset of A

We can make use of Array.prototype.every to help us with this one.

function subset(setA, setB) {
  return [...setA].every(element => setB.has(element))
}

Set A is a superset of Set B if Set B is a subset of Set A.

function superset(setA, setB) {
  return [...setB].every(element => setA.has(element))
}

Subsets and supersets are useful when categorizing elements. For example, React is a subset of JavaScript. If someone tells me that they know React, I can safely deduce that they know some JavaScript as well. However, if someone tells me they know JavaScript, I cannot deduce that they know some React. They might, they might not.

Disjointed Sets

Set A and Set B are considered disjointed if they share no elements.

Two circles with no overlap

Another way to think about disjointed sets is that their intersection is the empty set, and therefore has a size of 0. We can use that to determine if two sets are disjointed or not.

function disjoint(setA, setB) {
  return intersection(setA, setB).size === 0
}

It is not uncommon to create disjointed unions, as we will soon see.

Where am I using Sets without maybe realizing it?

Type systems!

When you describe a value as the type string, what you're really saying is that this value belongs to the Set of all strings. When you type an array as Array<number>, you're saying that this array belongs to the Set of all arrays containing numbers.

This is why types that use | and & are called union types and intersection types respectively.

If I have a type that is string | number, I'm really saying that this item belongs to the union of the set of all strings and the set of all numbers. This is a disjointed union, since it's impossible for a value to be both shared by the set of strings and the set of numbers.

Are there practical uses?

Quite a few, but you have to get used to looking for them. I have used sets for tag/category systems (I use Sets for my tags on this site). I've used them for making efficient filtering systems, too. It's sometimes easiest to think of filtering items in terms of unions and intersections.

Another place you've probably seen them over and over is in vector drawing tools. Take a look at Figma for instance. If I make two vector shapes, select them both and then look at my options, don't these look strangely familiar? They even use some of the same words to describe the operation.

A menu from Figma that says: Union selection, Subtract selection, Intersect Selection, and Exclude Selection

At its core, manipulating vector graphics is as simple as doing some Set operations. Every shape is a Set of points, and we can use the operations to manipulate those points into complex shapes.

Summary

Sets are a collection of unique elements. Learning the fundamentals of Sets and set theory may open up some new ways of thinking of operating with data for you. Your mileage may vary. At the very least, I hope you find words like "unions" and "intersections" less intimidating (if they ever were at all).

Resources

There's one specific library I like to share with people in regards to Sets that I want to share with you: Zet. It's incredibly simple and excellent. I encourage you to read the source code as well.

Additional Notes

It's worth noting that there are proposals to improve Sets in JavaScript in the works: https://github.com/tc39/proposal-set-methods. The work here will replace the need for libraries like Zet in the future.


Finished reading?

Here are a few options for what to do next.

Like
Liked the post? Click the beard up to 50 times to show it
Share
Sharing this post on Twitter & elsewhere is a great way to help me out
Support
Was this post valuable to you? Make a donation to show it
Make a Donation
Kofi logo

Newer Post: Symbolic Logic
Older Post: What is a Tuple?
Tags
JavaScriptComputer Science

Let's talk some more about JavaScript, React, and software engineering.

I write a newsletter to share my thoughts and the projects I'm working on. I would love for you to join the conversation. You can unsubscribe at any time.

Introduction to State Machines and XState Logo
Introduction to State Machines and XState

Check out my courses!

Liked the post? You might like my video courses, too. Click the button to view this course or go to Courses for more information.
View on egghead.io
Kyle Shevlin's face, which is mostly a beard with eyes
Kyle Shevlin is a software engineer who specializes in JavaScript, React and front end web development.