This unit introduces the notion of sets and is for Week 5. The unit will introduce:
- Basic Sets, Creating Sets
- Set Operations
- Ways To Prove Set Equivalence
- More proofs about sets
Unit Introduction
Recall that in Quantifiers we had this spiffy diagram that explained how you should read quantified statements.
And throughout Unit 1 itself we had slowly introduced more and more common sets that mathematicians use. Here’s a nice table that summarises the ones we have seen so far:
Symbol | Definition | Explanation |
---|---|---|
Set of natural numbers | Set containing the numbers | |
Set of integers | Set containing the numbers | |
Set of rational numbers | Set containing numbers that can be expressed as a fraction of 2 integers, eg: and |
In this unit, we will delve into this a little deeper. Concepts used here, and in the next Unit on relations are useful for concepts like databases, and distributed systems. In a nutshell, Sets and Relations are also part of the lingo (or vocabulary) on how we communicate. Let me show you a few examples to motivate this. At the end of this unit on sets, some of these examples should hopefully be a little more readable.
Motivation 1: Algorithms
For example, let’s say you’re reading a new book that is teaching you algorithms, and it says the following:
An array of elements from is called sorted if
How do we read this? See from the previous unit, we might get some idea. For example.. looking at the , we probably get that this means variable was taken from some set .. but what is set ? Similarly, variable was taken from set . What is set ? That’s one thing this unit will show you.
Motivation 2: Databases
Later on (beyond this module) you might learn about databases. Databases are a tool to help you manage data. Here’s an oversimplification of some of the concepts (you will get to delve deeper when you take the module):
Let’s say we have two tables of data (don’t worry about what a table is, you can pretend they’re like Microsoft Excel spreadsheets):
Table 1:
Name | |
---|---|
Jon Snow | jsnow@gmail.com |
Barry Allen | the_flash@hotmail.com |
Pikachu | pika@pokemail.com |
Table 2:
Name | |
---|---|
Matt Murdock | dared@gmail.com |
Bruce Wayne | batman@waynemail.com |
Barry Allen | the_flash@hotmail.com |
Using these 2 sheets, let’s say we were told to merge them into a single table with all the data from both initial tables. So something like:
Resulting table
Name | |
---|---|
Matt Murdock | dared@gmail.com |
Bruce Wayne | batman@waynemail.com |
Barry Allen | the_flash@hotmail.com |
Jon Snow | jsnow@gmail.com |
Pikachu | pika@pokemail.com |
Notice here Barry Allen was in both tables and is a duplicate, but this table contains a combination of both original tables.
But there are other possible operations we could perform. What if our boss on the other hand wanted us to create a new table, that only has the common rows of the first 2 tables? Then our output table should be:
Resulting table
Name | |
---|---|
Barry Allen | the_flash@hotmail.com |
Because Barry Allen with that email is the only common entry in both tables.
These are examples of operations we can perform on data. And in discrete math, the starting point for learning how to do this is via set operations. This is also another thing we will cover in this chapter.
As we get more and more involved, we will see how we can analyse more complex set operations as well.
Motivation 3: ML and AI
Lastly, coming back to the theme and goal of understanding math text and exposition, it’s very common that high level concepts (especially algorithms) commonly use set notation and concepts. To understand these in the later module, knowing how to read even more symbols is quite useful. For example, later in the semester when we talk about graphs and trees, we will be using sets.
And graphs are useful when talking about stuff like decision trees or neural nets for AI, and so on.
In conclusion:
In conclusion, think of this as yet another part of the vocabulary that will be useful further down the road. Not to say that this isn’t useful by itself. But perhaps the more application-oriented among you might want to look ahead and understand that this topic has uses down the road.
Basic Sets, Creating Sets, Set Operations
Set Roster Notation
Let’s begin by talking about what is a set. A set is just a collection of objects. So for example, let’s say we wanted to represent the collection of someone’s favourite book authors, we could write something like:
Here, we are saying set contains objects, namely: Agatha Christie, Cal Newport, Michael Crichton.
Pay attention to how we are using the "" symbol to start the set, and the "" symbol, to end the set. We also use the "" symbol to separate elements of the set.
So if we want to create sets by listing out the elements one-by-one, that is what we call set roster notation. Here are a few more examples:
Example
Let be the set that contains the first three prime numbers, then:
Example
Let be the set that contains the integers , then:
Set roster notation can be a little boring at times, we really have to hand-write all the elements.
Element Of
Using the same set again:
We say is an element of set . You might remember, we write this as . The "" symbol here means “is an element of”. Similarly, this means we can also say , and also .
Let’s say we had some other author: Stephen King, and notice here he’s not in set . We can write this in one of two ways, they’re both the same:
or,
Subset
What happens if we have two sets, something like and , then we want to be able to say:
Every object in is also an object in .
Or, formally:
Definition
Let be a subset of , then: The symbol for this, is . So we would write .
What about if we had a set . Can we say that everything in is also in ? No we can’t. In particular, but . So in fact, we can say:
which we know can be re-written:
Which confirms . As a shorthand, we can also write this as .
Example
Let , . Then but .
Example
Let , . Then and also .
Empty Sets
What about if we wanted a set that has no elements? There’s two ways we can write this, though uncommon, some people might write it like so:
The more common notation, and one you should get used to, is this:
Another also common way of writing it is like this:
The empty set is so that nothing is ever in the empty set.
One important thing to note is that the empty set is always a subset of any other set. For example, . It’s also a subset of itself! .
Common Sets for Numbers
Let’s start talking about a few well-established symbols for sets. The most common are: , and .
Symbol | Definition | Explanation |
---|---|---|
Set of natural numbers | Set containing the numbers | |
Set of integers | Set containing the numbers | |
Set of rational numbers | Set containing numbers that can be expressed as a fraction of 2 integers, eg: and | |
Set of real numbers | Set containing any number that is not complex. | |
Set of imaginary/complex numbers | For example, something like , or is complex but not real. |
There is one more common notation that we use in computer science. It turns out for some natural number , it’s very convenient for us to think about the set . The notation for this is .
Example
Example
Example
Explanation: There are no numbers that start from and end at ( and ).
Set Builder Notation
Okay, well right now we’ve seen a bunch of sets, not really built or made anything too big. If we wanted some kind of special, custom set, we’ve had to manually list out all the elements. What if we wanted the set of even numbers? We can’t just write everything out one-by-one… that would take forever!
Here’s how we would do it:
Let’s read this back:
is a set that contains any element from , such that, the following statement about holds true:
Let’s see how this works. Consider a number like . Is ? Well, does it satisfy the statement? and . So there exists a such that . So the condition holds! This means that .
What about something like ? Recall from Example 2 Delving a little deeper, we proved that , or in other words, . So that means that does not fulfil the condition. So we can conclude that .
Here are a few more examples:
Example
The set of real numbers between and (inclusive) can be written as:
So for example, , , , and so on. But .
Example
The set of real numbers between and (exclusive) can be written as:
So for example, , . But , and since , .
Example
The set of natural numbers that divides can be written as:
So . Why is ? Because we can find a such that . In particular, and is such that .
A similar reasoning applies for the rest of the elements.
Example
The set of prime numbers can be written as:
where the predicate is defined as .
Again, for example, is ? We know only has 2 divisors: and itself. So let’s check: is greater than or equal to ; take any , if does in fact divide , we know it has to be either or . So we can conclude that is indeed in .
On the other hand, something like , has divisors , , , . is indeed greater than or equal to . But what about the second half of the condition? Let’s see. Consider value . is in , and is . But is neither nor . So is . This means the condition is . So fails the condition, which means that .
Set builder notation is pretty handy, so let’s talk about the general format now:
So again, we go through elements from some set , and if it fulfils the conditions laid out by , we will admit element .
Example
Let’s try one more example: let’s say we want the even integers between and inclusive. We could also write this:
Pay special attention to how this time around we used , instead of as before. There is an alternative way to write this:
Set Operations
Okay, the next thing to do is to talk about the set operations. These are ways that we can build bigger sets from the ones we currently have. These are super handy and are part and parcel of database operations, and also they somewhat correspond to our logical operations, as we will see.
As a summary, these are almost all the set operations:
- Set Union
- Set Intersection
- Set Difference
- Power Set
- Cartesian Product
Set Union
Given two sets , we can create a new set , which is the union of and . The set contains elements that are either in or in . Formally, contains only all the elements where:
Example
Example
For example, we want to make a set that contains both positive odd numbers, and all negative numbers. Then we can do it in the following way:
Example
For example, we want to make a set that contains both non-negative odd numbers, and also non-negative even numbers:
Wait a minute, isn’t this just ?
Yes. Yes it is!
Set Intersection
Given two sets , we can create a new set which is the intersection of and . The set contains elements that are both in and in . Formally, contains all the elements where:
Example
Example
For example, we want to make a set that contains even numbers that are only negative. We could do so in the following way:
Example
, , then:
Set Difference
Given two sets , we can create a new set , which we call minus . The set contains elements that are from in that is not also in . Formally, contains all the elements where:
We can also write this in set builder notation as:
Transclude of set-minus
Example
Let , and .
Notice that elements and is from but also in , so it is not in . On the other hand, elements are in but not in , so they are in .
Also, note that the sets and are not the same sets! In this case, would contain all the elements in that are not in , which is the set . Notice that this is not the same as .
Example
For example, we want to make a set that contains any non-negative number that is not prime. Then we can do the following:
Let where the predicate is defined as .
Then .
Notice here contains any element from that is not in set (which is the set of primes).
Powerset
The powerset operation is a little unorthodox, it does not look like a logical operation like the ones we have seen. Given a set , the powerset of is denoted by is the set that contains all subsets of . Formally:
In other words, if is a subset of , then is in the power set of and if is in the power set of , then is a subset of .
Example
Notice here that: , so .
Similarly, a set like so .
Example
Remember, , so .
Cartesian Product
Given a sets , and . The set is the cartesian product between sets and . This creates pairs. If and , then the pair .
Note: This operation is one of the most important in how we start creating almost other concepts later on. (Relations, Graphs, etc)
Example
Let , and .
Pictorially, you can see how we got the elements.
Notice here the pairs are ordered. So , and . But . Also, .
Formally: A pair is in set if:
Also, a pair is not in set if:
Example
is the set that contains any pair of integers. For example, . But .
Example
is the set that contains any pair where the first element is from and the second is from . For example, , and also .
Ways To Prove Set Equivalence
So up until this point, we have been showing how to manipulate and create all kinds of sets. And you might have noticed, that sometimes there’s more than one way to create a set. Also, knowing when two sets are equivalent is pretty helpful for something like databases (for those who are curious and would like a sneak peek, you might look want to take a peek at the concepts relational algebra, and relational calculus for databases).
We say two sets are equivalent if they have the same elements. Formally speaking, we write this as:
You can think of this as saying “every element in is also in and every element in is also in .”
There’s broadly two categories for how to show two sets are equivalent. We will be showing both ways.
Directly Proving Two Sets are Subsets of Each Other
So here’s an example, let’s say that we had these two sets:
Which is the set of odd natural numbers. But what if we wrote it like this?
Which is the set of natural numbers that are not even. These two are intuitively the same set right? Let’s see a proof of this. We’ll use these 2 lemmas.
Lemma
- .
- .
Where and .
In English, the first statement is saying “Every natural number is such that if it is not even, it is odd.”.
The second statement is saying “Every natural number that is odd is not even.”.
Okay, so we’ve established that lemma, let’s see how to prove the two sets are the same. Our goal is to show the statement . How do we do this? Remember that is defined to be . So we effectively want to prove:
And remember, the definitions of the sets :
Proof:
- Let , arbitrarily chosen.
- [Definition of ]
- [Specialisation of line 2]
- [Specialisation of line 2]
- [Lemma 2]
- [Universal instantiation on lines 3 and 5]
- [Modus ponens on lines 3 and 6]
- [Conjunction on lines 4 and 7]
- [Definition based on set builder]
- [Conjunction on lines 4 and 9]
- [Definition of ]
- [Universal generalisation on lines 1 and 11]
- Let , arbitrarily chosen.
- [Definition of ]
- [Specialisation on line 14]
- [Specialisation on line 14]
- [Definition based on set builder]
- [Logically equivalent to line 17]
- [Modus ponens on lines 15 and 18]
- [Lemma 1]
- [Universal instantiation on lines 15 and 20]
- [Modus ponens on lines 18 and 19]
- [Conjunction on lines 15 and 22]
- [Definition of ]
- [Universal generalisation on lines 13 and 24]
- [Conjunction of lines 12 and 25]
And we’ve proven they’re the same set! So again, the takeaway is the following:
To prove two sets and have the same elements, we should prove . Or in other words:
Example
Let be any 3 sets. Then:
Here’s the proof:
Proof:
- Let , arbitrarily chosen.
- [Definition of set union]
- Case 1:
- [Generalisation on line 3]
- [Definition of set union]
- [Generalisation on line 3]
- [Definition of set union]
- [Conjunction of lines 3.2 and 3.4
- [Definition of set intersection]
- Case 2:
- [Definition of set intersection]
- [Specialisation on line 4.1]
- [Generalisation on line 4.2]
- [Definition of set union]
- [Specialisation on line 4.1]
- [Generalisation on line 4.5]
- [Definition of set union]
- [Conjunction on lines 4.4 and 4.7]
- [Definition of set intersection]
- In all cases, it is shown that [Proof by cases on lines 2, 3.6, 4.9]
- . [Universal generalisation on lines 1 and 5]
- Let , arbitrarily chosen.
- [Definition of set intersection]
- [Specialisation on line 8]
- [Definition of set union]
- [Logically equivalent to line 10]
- [Specialisation on line 8]
- [Definition of set union]
- [Logically equivalent to line 13]
- Assume .
- [Modus ponens on lines 11 and 16]
- [Modus ponens on lines 13 and 16]
- [Conjunction on lines 15.1 and 15.2]
- [Definition of set intersection]
- [Implication introduction on lines 15, 15.4]
- [Logically equivalent to line 16]
- [Definition of set union]
- [Universal generalisation on lines 7, 18]
- [Conjunction of lines 6, 19]
Here’s another small example of two sets you can try to prove are the same.
Example
, , and .
Then:
Based on logical equivalences
You might have noticed that the set operations we are doing bear some similarity to the logical operations. For example, a set intersection () operation really does look a little bit like the logical and () operation. After all, if , then contains all elements such that . Similarly, if , then contains all elements such that .
What about the set difference () operation? If , then contains all elements such that , in other words: .
Set Operation | Logical Operation |
---|---|
You might actually have noticed this based on the previous sub-section, when we proved the following:
You might have noticed it mirrors this fact:
This is actually something we can do in general. So for the narrower use-case of involving only intersections, set minus and union in very specific ways, here are some examples:
Why? They mirror the following how the following pairs of propositions are logically equivalent:
So what happens if someone asked you if something like whether these two sets are equal or not?
Well, it’s the same as asking whether the following is logically equivalent:
You can check that it is, and thus they are indeed the same set.
What about this?
We are basically checking whether this is equivalent:
You might realise, they’re not. In fact, in terms of the proposition, if we set , , , then the left hand side is , but the right hand side is .
But what about the sets? The fact that we found a way to show the propositions were not logically equivalent gives us a hint. Let’s try something like .
Then , but . Try it step by step to check that what we’ve written here is correct!
This method however, is less general, it typically does not work if we involve sets that use set builder notation to make.
More Proofs About Sets
Now that we have seen a few ideas about sets. We will end this unit on a few more commonly proven concepts about sets. Thus far we’ve only talked about set equivalences and talked about set unions and intersections. Let’s explore a few more ideas that have to do with the powerset and cartesian product operation.
Reasoning about subsets
Here are a example few intuitive facts we can prove involving subsets:
- If is a subset of and is a subset of , then is a subset of .
- If are subsets of , then is a subset of .
- is a subset of .
The key takeaway here are not the facts themselves. Rather, notice our approach has a common theme: We start with an element that is from the “smaller” set, and we show it is in the bigger set.
Example
Proof:
- Assume
- [Specialisation on line 1]
- [Definition of subset]
- [Specialisation on line 1]
- [Definition of subset]
- Let , arbitrarily chosen.
- [Universal instantiation on lines 3, 6]
- [Universal instantiation on lines 5, 7]
- [Universal generalisation on lines 6, 8]
- [Definition of subset]
- [Implication introduction on lines 1, 10]
Example
Proof
- Assume
- [Specialisation on line 1]
- [Definition of subset]
- [Specialisation on line 1]
- [Definition of subset]
- Let , arbitrarily chosen.
- [Definition of union]
- Case 1:
- Then [Universal instantiation on lines 3, 8]
- Case 2:
- Then [Universal instantiation on lines 5, 9]
- In all cases, [Proof by cases on lines 7, 8.1, 9.1]
- [Universal generalisation on lines 6, 10]
- [Definition of subset]
- [Implication introduction on lines 1, 12]
Example
You can try this one for yourself, and the answers have been hidden away in a spoiler tab.
Answer
- Let , arbitrarily chosen.
- [Definition of set intersection]
- [Specialisation on line 2]
- [Definition of set union]
Reasoning about power sets
Recall that is a set that contains all the subsets of . This means that if we had to reason about subsets, that might mean we should involve using the power set concept.
Here are a few theorems that involve using the power set concept:
- .
Example
The proof of this is going to use the theorem that we proved in the previous section, namely that:
Proof:
- Assume
- Let , arbitrarily chosen.
- [Definition of powerset]
- [Conjunction of lines 1 and 1.2]
- [Lemma]
- [Universal generalisation on lines 1.1, 1.5]
- [Definition of subset]
- [Implication introduction on lines 1, 1.7]
Example
The proof for this has to work in two parts, we need to show two things:
Lines 1 through 16 will do part 1, and the remaining will do part 2. We’ll also use this lemma that will be left as an exercise for you to try to prove.
Lemma
Proof:
- Let , arbitrarily chosen.
- Then [Definition of power set]
- [Lemma]
- [Lemma]
- [Conjunction of lines 2 and 3]
- [Modus ponens on lines 4 and 5]
- [Lemma]
- [Lemma]
- [Conjunction of lines 2 and 7]
- [Modus ponens on lines 8 and 9]
- [Definition of power set from line 6]
- [Definition of power set from line 10]
- [Conjunction on lines 11 and 12]
- [Definition of set intersection]
- [Universal generalisation on lines 1 and 14]
- [Definition of subset]
- Let , arbitrarily chosen.
- [Definition of set intersection]
- [Specialisation of line 18]
- [Specialisation of line 18]
- [Definition of power set on line 19]
- [Definition of power set on line 20]
- [Conjunction of lines 21 and 22]
- [Lemma]
- [Modus ponens on line 23 and 24]
- [Definition of power set]
- [Universal generalisation on lines 17 and 26]
- [Definition of subset]
- [Conjunction on lines 16 and 28]
- [Definition of set equality]
Bonus: Google Sheets
Let’s see some of the concepts in action. Let’s say that we are some marathon event organiser, and we had an initial Google sheet that kept the data of the participants. For each participant, we keep their name, their gender, the marathon distance they have signed up for, and whether they signed up as a beginner, or are in the open category.
So here’s an example of a sheet:
Let’s say we need to find out how which people are running 21.1KM or more because they need to start earlier compared to the 10KM runners. How should we do this? You’d use something like this formula:
=QUERY(Sheet1!A:D, "SELECT * WHERE C >= 21.1")
And if you did, you’d get this result on a new sheet:
What is the QUERY
syntax doing on the Google sheet? It’s saying: “Go to Sheet1, look at columns A to D. Select any of the rows where the C column is at least 21.1”
In some sense, you could probably see how this somewhat uses the concept of Set Builder Notation.
Okay, what if after the competition, we tracked the participants that actually arrived and competed. We want to find out how many participants registered but did not show up on the day itself. How should we get this information? We probably want something like a Set Difference operation to help us out. Let be the set of registered participants, let be the set of participants we tracked that showed up. Then we can let be the set we want to compute. And if you remember, we can write this in set builder notation as:
Google sheets has something similar:
==FILTER(Sheet1!A:A, NOT(COUNTIF(Sheet2!A:A, Sheet1!A:A)))
Which basically goes through all elements of Sheet1, and the FILTER
formula basically means we are only allowing cells that satisfy the condition NOT(COUNTIF(Sheet2!A:A, Sheet1!A:A))
which is saying “not the case that the name in Sheet1 is also in Sheet2”.
Incidentally, databases like mySQL and Postgres also has similar ideas on how to manipulate data. While we will not go into detail in this module (since we do not cover databases), if you wish to have a sneak peek, you can look at documentation websites here: postgresql, mysql.