Sets! Part 1

the things in squiggly braces :)

Attention!

In this article, I’m writing about the applications of sets in mathematics. There is a bit of background necessary to understand the contents of this article including understanding propositional logic. I plan to write articles about more topics in discrete math, so I’ll update this page with other articles I write that can help provide more context and understanding.

With that being said, let’s get onto the rest of the article ❤

The curly braces {}

I started learning pre-calc and taking my first programming class around the same time during high school. In my math class, instead of using the x to denote multiplication, for example 9 x 9, we’d now moved onto better math practices and used the nice round brackets to specify multiplication, so instead (9)(9). In my Python programming class, we used square brackets like [] to denote lists. Then in university when I took an intro to discrete math class, I discovered the beauty of the curly braces {}, otherwise used to denote sets. The following week in my 15–112 programming class at CMU, I was forced to abuse the properties of sets in every possible way for that weeks homework. It’s safe to say that I quickly learned to love the beauty of sets and their operations (they are now my favourite type of squiggly/curvy line).

So what is a set?

A set is a data structure that can store items (which are called elements), and in math we declare a set using {} and insert the elements inside of them.

Here are some things you need to know

1. Sets are not ordered, as seen below both examples are valid sets.

setOne = {1, 2, 3, 4}
setTwo = {4, 3, 2, 1}

2. Sets do’nt have duplicates, setOne would be a valid set, and setTwoDuplicates would be an invalid set (in the sense where we wouldn’t write a set as {1, 2, 2, 3, 4, 4, 4} but instead would turn it into a version without the duplicates, so {1, 2, 3, 4}.

setOne = {1, 2, 3, 4}
setTwoDuplicates = {1, 2, 2, 3, 4, 4, 4} 

Something important to take away from points 1 and 2 is that sets don’t have multiplicity. This means that:

#these sets equal each other!
{1, 2, 3, 4} = {4, 3, 2, 1}

{1, 2, 3, 4} = {1, 2, 2, 3, 4, 4, 4}

As you can see despite the order and the duplicates these sets are still equal to each other. This is because sets don’t care about order and don’t consider duplicates when comparing equality.

3. ∈ is a very important symbol. It means belongs to, so this describes if an element is a member of a particular set. For example, if we have a set defined below:

fruits = {apple, orange, strawberry, blueberry, pineapple}

we could say apple∈fruits, which reads as apple belongs to the set of fruits.

We can also state that an element does not belong to a set, for instance:

carrot∉fruits, which reads as carrot does not belong to the set of fruits.

4. ⊆ is a symbol that means contains (or something is a subset) and it refers to if we are checking if a collection of elements belong to a set.

The general format is: check if a collection of elements ⊆ (is contained as a member) in a set.

{1, 3, 4}⊆{1, 2, 3, 4, 5} is true

What reads above is the following: check to see if the elements 1, 3, 4 exist in the set {1, 2, 3, 4, 5}.

The brackets for the collections matter a lot. For instance, the following do not check for the same things.

{1, 3, 4}⊆{1, 2, 3, 4, 5}
{{1, 3, 4}}⊆{1, 2, 3, 4, 5}

{1, 3, 4}⊆{1, 2, 3, 4, 5} checks for if the elements 1, 3, 4 are members of the set {1, 2, 3, 4, 5} (which is true).

HOWEVER

{{1, 3, 4}}⊆{1, 2, 3, 4, 5} checks for if {1, 3, 4} is a member of the set {1, 2, 3, 4, 5} (which is FALSE!).

This would be true if {1, 2, 3, 4, 5} was instead {1, 2, 3, 4, 5, {1, 3, 4}}.

TLDR be careful when checking containment.

I like to think of checking containment by removing the outer brackets of the collection we are checking to see is contained and then looking for if the specific element/s are contained in the set.

5. {} or Ø is called the empty set, which means that there are no elements in the set.

The empty set is a subset of any other set, but this doesn’t mean that the empty set belongs to every set.

Sometimes this concept can be a little confusing to wrap your head around, but it’s not as complicated as you might make it out to be.

Recall that an empty set looks like this {}

There are NO elements inside of it.

Now recall that a subset is when a collection of elements exists in a list. A collection is NOT a subset if an element within it is not contained in the list we are seeing if it’s a subset of.

Let’s define set A as {1, 2, 3, 4}

We want to show that the empty set is not a subset of set A. In other words, we want to prove that there is an element in the empty set that DOESN’T belong in set A.

However, the empty set → {} has no elements, which means that there is nothing in the empty set that doesn’t belong to set A.

Thus, the empty set is a subset of EVERY SET.

6. Universal Set

U represents the universal set, which is just a set that contains all the sets you want to talk about in the context of a problem.

So we can say that the universal set contains everything, every single set is a subset of the universal set.

Set Operations

When we look at sets, we can also perform operations between multiple sets (in my examples I’ll just compare between two sets).

Union

A union is denoted by the symbol ∪ (U for union!).

The formal definition of a union is:

A ∪ B = {x∈u|(x∈A)∨(x∈B)}

This reads as the x values that belong to the universal set such that x belongs to set A OR x belongs to set B.

Simply put, a union contains a set of all the elements that belong to both sets (remember no duplicates!).

We can demonstrate what this looks like with a shaded Venn diagram:

An example of the union of two sets would be:

A = {1, 2, 3}
B = {4, 5, 6}
A ∪ B = {1, 2, 3, 4, 5, 6}

The union of the two sets include all the unique values from both sets regardless of if they appear in only one set or both.

Intersection

An intersection is denoted by the symbol ∩.

The formal definition of an intersection is:

A ∩ B = {x∈u|(x∈A)∧(x∈B)}

This reads as the x values that belong to the universal set such that x belongs to set A AND x belongs to set B.

Simply put, an intersection contains a set of elements that belong to both set A AND set B.

We can demonstrate what this looks like with a shaded Venn diagram:

An example of the intersection of two sets would be:

A = {1, 2, 3}
B = {1, 3, 4}
A ∩ B = {1, 3}

As you can see, the union of the two sets include all the elements that exist in both set A AND set B.

Difference

A set difference is denoted by the symbol \.

The formal definition of union is:

A \ B = {x∈u|(x∈A)∧(x∉B)}

This reads as the x values that belong to the universal set such that x belongs to set A AND x does not belong to set B.

We can demonstrate what this looks like with a shaded Venn diagram:

An example of a set difference between two sets would be:

A = {1, 2, 3, 5, 6}
B = {1, 3, 4}
A \ B = {5, 6}

In the set difference of A \ B, we can see that our list only contains 5 and 6 since these are the elements not belonging to set B, however they belong to set A.

Complement

The complement of a set is denoted with a superscript c, so if we have set A, the complement would be A^c (or A’).

The formal definition of the complement of a set is:

A^c = {x∈u|x∉A}

or 

¬(x∈A)

This reads as the x values that belong to the universal set such that x does not belong to set A.

Essentially the complement of a set is any element that exists which doesn’t currently belong to the set.

We can demonstrate what this looks like with a shaded diagram:

Cartesian Product

If we have set and set B, the cartesian product between both sets is shown by the X symbol, so A X B.

The formal definition is:

A X B = {(a, b)∈ UXU | (a∈A)∧(b∈B)}

The reads as, the ordered pair (a, b) belongs to the cartesian product of the Universal set such that a belongs to set A and b belongs to set B.

We can demonstrate what a cartesian product looks like by showing the result of R X R. As you can see, this operation will give us a pair of coordinates on a graph. So when we take the cartesian product, we are essentially finding all the coordinates that contain both “a” and “b” members from two respective sets.

So when you take the cartesian product of something, you are trying to find all the possible ordered pairs between two sets.

I’m going to draw an example of this to colour code the distributions which will allow you to take the cartesian product and find all possible ordered pairs.

I like to think of this process sort of like distributing polynomials.

Cardinality: Cartesian Products

When finding the cartesian product of sets, we can also focus on the size of these outcomes.

If we have two arbitrary sets defined, set A and Set B, when finding the size or cardinality of a set or cartesian product we denote this by using these bars → | |

for instance, set A’s cardinality is shown as|A|.

The cardinality of the cartesian product of A X B is shown as|A X B|.

Taking a look at each set individually, we know the cardinality of set A would be how many n elements belong to the set. The same goes for set B, we look at how many m elements belong to the set.

We can now say that |A X B| has a cardinality of n times m.

As seen above set A has 3 members and set B has 2 members. Both A X B and B X A have in total 6 ordered pairs in the cartesian product.

Power Set

If we have an arbitrary set A, the power set of a set is denoted by a P(set), so P(A).

The formal definition would be as following:

P(A) = {x | x⊆A}

This reads as, P(A) is x such that x is a subset of set A.

Essentially the power set contains all the possible subsets of a given set.

Remember that the empty set is a subset of ANY given set.

Here is an example of a power set:

let A = {a, b, c}

P(A) = {Ø, {a}, {b}, {c}, {a, b}, {b,c}, 
{a, c}, {a, b, c}}

Remember, sets don’t care about order or duplicates!

Cardinality: Power Sets

Just like a cartesian product can have a cardinality, so can the power set of a set.

However, finding the cardinality of a power set that is large will take a VERY long time, so we can use a trick.

To find the cardinality of a power set, we can use the formula:

P(A) = 2^n

Recall that n represents the number of elements in the defined set.

If we use this formula to check the cardinality of the power set we found earlier, we can see that:

P(A) = 2³ = 8

There are 8 elements above in the power set.

Let’s try some other examples.

Supposed A, B, C are sets.

|A| = 2, |B| = 4, |C| = 6

If we took the power set of B, the cardinality would be |P(B)| = 2^n and n = 4 so |P(B)| = 2⁴.

Recall that the cardinality of a cartesian product is found by multiplying the number of elements in set A (n) by the amount of elements in set B (m).

|AXC| = (2)(6) = 12

Now what if we wanted to find the power set of A X C ? This would look like:

P(|AXC|) = P(12)

To find the cardinality of a power set of n amount of elements, we would use the 2^n, so this would be:

P(|AXC|) = P(12)
P(12) = 2^12

So the power set of |A X C| would have a cardinality of 2¹².

Furthermore we can take the cardinality of the cartesian product of two power sets, for example |P(A) x P(B)|:

|P(A) x P(B)| = (2^2)(2^6) = 2^8

First we find the cardinality of P(A) and P(B). For the cardinality of a cartesian product, we need to multiple the amount of elements in each power set to get our final answer.

Part 2~

So far, we’ve gone over the basics of sets :) There are some more components that I plan to write about, specifically set identities and set containment. When I write about these topics, I’ll link the article(s) below. Stay tuned!

A quick note✨

Hi, I’m Ashley! I’m a freshman (18 years old!!) at Carnegie Mellon University studying computer science and I LOVE writing about things that interest me.

My email is ashleycinquires@gmail.com. I just checked it recently and have come back to many messages. If you have any questions about anything, I’ll try to answer them. I do appreciate all the positive messages I’ve been sent and I’ll now definitely be more active via email. I love talking to people and I also appreciate feedback and suggestions about what to write.

I also plan to attach my newsletter link to my articles towards the end of January. I know it’s a little nerdy to have one, but I enjoy reflecting on my life, keeping a little diary for myself, and sharing updates with others.

I’ll see you soon :)

Ashley ❤

If you liked this article, you may like:

✨ what is a function