4 min read
This post is the first of a series adapted from my conference talk, Fun, Friendly Computer Science. Links to other posts in the series can be found at the end of this post.
Venn diagrams are a great way to think about set theory. A set is a data structure similar to arrays or lists but the difference is that it is an unordered collection of objects with no duplicates. So we can’t assume that sets are sorted in any way or that they maintain order and each element in a set is unique. That in itself is pretty uninteresting, but these constraints mean we can do very interesting things with sets. These operations form the basis of set theory.
We’ll be using the following Venn diagram for our examples. These are all very cute Instagram accounts that I encourage to you follow if you love cute animals in your feed. 🐶🐱 The circle on the left is a set containing Instagram handles of accounts with cute dogs. The circle on the right is a set containing the handles of accounts with cute cats.
When we’re talking mathematical notation, the dog set will be X and the cat set will be Y.
The union of 2 sets returns all of the elements that exist in set X OR set Y. Mathematically, this is written as X ∪ Y (said “X cup Y” or “X union Y”). Since you are asking for any element that exists in X or Y, all of the elements will be returned.
If you were to curate your Instagram feed to contain the union of the dog accounts and cat accounts, you would be following all of the cute animals!
I like to think of the intersection of 2 sets as the logical inverse of the union. Where the union returns anything in X OR Y, the intersection returns elements in X AND Y. Mathematically, this is written as X ∩ Y (said “X cap Y” or “X intersect Y”). The intersection of 2 sets returns only those elements that exist in both sets.
If you were using the set intersection to curate your Instagram feed, you would only see accounts that featured both cute dogs and cute cats. None of the accounts feature only one or the other would be present in your feed.
The difference of 2 sets returns only the elements that exist in set X and none of the elements that exist in set Y. Mathematically, this is written the same as you write a numeric difference X - Y.
If this was your Instagram curation strategy, you would only follow accounts featuring cute dogs. You would not follow any of the accounts that exist in the intersection of the sets because those accounts also feature cats.
The opposite of the set difference is the relative complement. The relative complement is written mathematically as Y \ X but is the same as Y - X (computer scientists and mathematicians always like to make things more confusing than they need to be). Exactly how the set difference returns elements that exist in only set X, the relative complement returns elements that exist only in set Y.
Your Instagram feed would feature only cute cats with this strategy. Again, you would not see any of the cats that exist in the intersection of the 2 sets, because those accounts also feature cute dogs. You don’t want anything from the intersection when you’re asking for the relative complement.
Finally, the symmetric difference is the opposite of the intersection. It is denoted mathematically X △ Y. The symmetric difference—sometimes called the disjunctive union because again computer scientists and mathematicians like it when things seem complicated—returns the elements that exist in only X and the elements that exist in only Y but none of the elements that exist in the intersection. Which means that it is the union of the difference and the relative complement ( (X - Y) ∪ (Y ∖ X) for those who like to be fancy).
In this case, your Instagram feed would feature cute dogs and cute cats but no adorable interspecies friendships, because you won’t see any of the accounts that feature both dogs and cats.
Set theory uses
Set theory forms the foundation of relational databases. If you’ve ever written SQL or used some kind of relational database, then you have used set theory without needing to think about it. If you are a web developer, you may have needed to develop a feature to let users filter search results. This is also an application of set theory where 2 filters applied within the same category act as a union (a logical OR) and 2 filters applied from different categories act as an intersection (a logical AND).
I find Venn diagrams extremely helpful whenever I’m faced with challenging grouping problems while coding. They can help you visually break down which elements you want in different use cases without requiring that you remember all of the mathematical bits of set theory.
Other posts in this series
- Big O notation and cupcakes
- Set theory and cute Instagram accounts
- Recursion and Russian nesting dolls
- Linked lists and scavenger hunts
- Stacks and PEZ dispensers
- Queues and lunch lines
- Trees and Harry Potter's Triwizard tournament
- Encapsulation and horses
- Abstraction and remote controls - Coming soon
- Inheritance and gardening - Coming soon
- Polymorphism and yarn crafts - Coming soon
Published Oct 19 2019