This lesson covers basics of set theory, operations on sets and application of sets in computer-science/data-science. 

Sets and Set Operations: Lesson

#### Intersection 
The *intersection* of two sets A and B is the set containing all the elements that A and B have in common. It is represented as A ⋂ B. If the two sets have nothing in common, then the answer is the empty set.

Let us try to find the intersection of the set of all prime numbers and even numbers. A prime number has only two factors: 1 and itself. The set of prime numbers, P, is {2, 3, 5, 7, 11, 13, …}.   

To find P ⋂ E (the set of even numbers), or all even primes, list the elements present in both E and P. The number 2 is the only even prime number, so E ⋂ P = {2}.  

Let us look at another example. A set of band students, B = {Sam, Chen, Halona, Paul} and a set of chorus students, C = {Halona, Hope, Leena, Paul, Tony, Zach} have a performance tomorrow. Which band students are part of the chorus too? 	

We need to look for students in the band who are part of both band *and* chorus (set intersection). 

B ⋂ C = {Halona, Paul} 

#### Union
The *union* of two sets A and B is the set of all their elements together (without repeating any elements that they share). It is represented as A ∪ B. Let us try to find the list of all students who are participating in the concert, as part of band *or* chorus (set union).

B ∪ C = {Sam, Chen, Halona, Paul, Hope, Leena, Tony, Zach}

#### Difference
The *difference* between two sets A, B is represented as A - B and is the set of all elements of A that are *not* present in B. An ice cream website held a poll asking users which flavor they liked the best. Here are the results from North Dakota and South Dakota:

N =  {Chocolate, Vanilla, Strawberry, Banana-Chocolate-Chip}   

S = {Chocolate, Vanilla, Butter-Pecan, Cappuccino, Cherry-Almond}

We can use the difference operator to find the flavors that are popular in North Dakota, but not in South Dakota. 

N - S = {Strawberry, Banana-Chocolate-Chip}

The `.union()` method of Python can be used to find the union of one set with another.
The `.intersection()` method returns the intersection of one set with another.  



Set operations on multiple sets

Venn diagrams are visual representations of sets. A rectangle represents the Universal set, U. Each set is represented by a circle or ellipse inside this rectangle. The circles can show the relationships among sets. 

Venn diagram 1 is a three-circle Venn diagram. 

* The blue circle is set A, the red circle is set C and the yellow circle is set B. 
* The region outside a circle shows the complement of that set.
* Two circles together represent the union of the two sets.
* The overlapping part of two circles represents the intersection of the two sets.

The diagram allows us to depict A ⋂ B, B ⋂ C, C ⋂ A, and even A ⋂ B ⋂ C ! 


Venn Diagram

Set theory is used as a foundation for many subfields of mathematics and computer science. Let us explore two areas. 

#### Sets in Data science

A *dataset* is a collection of numbers or values that relate to a particular subject. A public health authority may maintain a dataset of community health records.  

Your local public health authority has decided to support people with cardiac risk by offering healthy lifestyle programs. They wish to make a list of vulnerable community members based on the following criteria: people with hypertension, people aged over 60, and obese people who also have a family history of cardiac issues. Can you help them extract data to make a contact list?  

Let H be the set of people with hypertension, A the set of people aged over 60, O the set of obese people, and F the set of people with family history of cardiac issues.

The set of people who are vulnerable =  H ∪ A ∪ (O ⋂ F)

#### Sets in Databases

In databases, records within a table can be treated as objects in a set - i.e. the table becomes a *set* of records.

SQL (Structured Query Language) is used to communicate with a database. SQL statements are used to perform tasks such as update data on a database, or retrieve data from a database. 
 
Amazon maintains a database of customers and orders. To contact all customers who have placed orders, we need to find the *intersection* of the customers and orders table. The SQL `Inner Join` is just the *intersection* of two sets.


Applications of sets 

Here’s a summary of what we’ve learned: 

* A set is denoted by a capital letter and is represented by listing all its unique elements inside curly braces.    

* A subset is formed by taking parts of the original set.    

* Basic set operations:   

  * The complement of a set A is the set of all elements in the universal set U that are not in A.    

  * The cardinality of a set is the number of elements in the set.    

* More set operations:   

  * The intersection of two sets A and B, written A ⋂ B, is the set containing all elements of A that also belong to B.    

  * The union of two sets, written A ∪ B, is the set of all the elements contained in either set (or both sets).     

  * The difference of two sets, written A – B, is the set of all elements of A that are not elements of B.    

* A Venn diagram uses overlapping circles to illustrate the logical relationships between two or more sets of items.    

* The Identity Property for Union says that the union of a set and the empty set is the set itself. For a set A, A ∪ ∅ = A.  
  
* The intersection of a set with the Universal set is the set itself. For a set A, A ⋂ U = A.  

* Any set intersected with an empty set gives the empty set. A ⋂ ∅ = ∅.  

* The union of any set with the Universal set is the Universal set. A ∪ U = U.  

* Set operations can be used to gain insights into data from datasets/databases. 


Venn Diagram with three circles A, B and C

Review

Let us start with the simplest examples of sets. 

* The empty set (or the *null* set), is what it sounds like, the set with no elements. We usually denote it by  ∅  or by  { }. 

* The number of elements in a set may be inﬁnite. For example, N is the set of all natural numbers. We do not need to list all the elements. This set can be represented as N = {1, 2, 3, ...}. 

* A set can also be bidirectional. For example, Z, the set of all integers = {..., -2, -1, 0, 1, 2, ...}.

* A *universal* set is a set that contains all the elements of other sets (and its own elements). It is usually denoted by the symbol 'U'. Suppose set E is the set of all even numbers, or E = {0, 2, 4, 6, ...}, and set O is the set of all odd numbers, or O = {1, 3, 5, ...}. The set of whole numbers, W, is a Universal set that contains both sets E and O.

* A *subset* is a set formed by taking parts of the original set. For example, the set of even  numbers, E, is a subset of the set of whole numbers, W. This is represented as E ⊂ W. However the set {-1, 0, 1} is not a subset of W, so {-1, 0, 1} ⊄ W. 

Let us look at another example - the collection of possible outcomes of an experiment, like a die roll. D is the set of all outcomes when rolling a die, or D = {1, 2, 3, 4, 5, 6}.

These are some subsets of D: {1}, {}, {5}, {1, 3, 5}, {2, 4}.

In Python, you can loop through the set items using a `for` loop.  The `.issubset()` method can be used to check if one set is a subset of another. To create an empty set in Python, use `set()`, not `{}`. The latter creates an empty dictionary.



Special sets

A bibliophile could own a collection of books, and a music lover may own a collection of CDs. Any collection of unique items can form a *set*. The objects that make up a set could be anything: movies, students, numbers, or even other sets.  You can never tell when set notation will show up - it can be in your math class, philosophy class, or data science class. Knowledge of the symbols used in set theory is an asset!

Sets are conventionally denoted by capital letters. They can be defined by describing the contents, or by listing the elements of the set in curly brackets. Here are some examples of sets:

* A = {1, 2, 3}
* B is the set of all books written by Eiichiro Oda
* P is the set given by the rule “prime numbers less than 15” or P = {2, 3, 5, 7, 11, 13}
* G = {c, o, d, e, a, m, y}, the set of letters in the word ‘codecademy’

A set is unordered and unindexed. Unordered means that the elements of a set are stored in a random order. Unindexed means that we cannot access the elements of a set using indexes, unlike arrays and lists.  

An object in a set is called an *element* (or member) of the set. The symbol ∈ is used to denote that an element is a member of a set and ∉ is used to denote that an object is *not* a member of a set. For example, if set A = {1, 3, 5} then 1 ∈ A, but 7 ∉ A.

*Set* is one of the four built-in data types in Python. The Python set is both unordered and unindexed. Here is the code to create a set -
```py
Fruits = {"apple", "blueberry", "peach", "cherry"}
```

You cannot access items in a set by referring to an index or a key, but you can determine if a specified item is present in a set using the `in` keyword. 
```py
if "cherry" in Fruits:
  print("Yes, 'cherry' is in the Fruits set")
```


Introduction 

The *complement* of a set A - denoted A' or Ac - is the set of all elements in the universal set U that are not in A. If the Universal set is W - the set of all whole numbers - and E is the set of all even numbers, then Ec represents all elements of W that are not members of E. That is,

W = {0, 1, 2, 3, 4, 5, …} 

E = {0, 2, 4, …} 

Ec = {1, 3, 5, …} = the set of all odd numbers 

If our universal set is the set of all chess pieces, U = { king, knight, rook, bishop, queen, pawn} and if K = {king, knight}, then Kc = {rook, bishop, queen, pawn}. 

You will find that a set and its complement together form their universal set!

The *cardinality* of a set is the number of elements in the set. For example, if A = {1, 3, 0, 7, 9}, then the cardinality of A is represented as |A| = 5. Going back to the chess pieces example, the number of elements in set U is 6, set K is 2, and set Kc is 4. This satisfies the relation

|U| = |K| + |Kc|

The `len()` function of Python can be used to find the cardinality of a set. The `.difference()` method returns a set that contains the items that only exist in one set and not the other. `U.difference(K)` will return the set Kc.

Set operations on a single set

The operations on sets satisfy many identities. We will look at some important ones. Note the close similarity between these properties and their corresponding properties for addition and multiplication.

#### Identity Property for Union: 

The Identity Property for Union says that the union of a set and the empty set is the set itself. For a set A, 

A ∪ ∅ = A.

Let A = {3, 5, 7, 11} and B = { }. Then A ∪ B = {3, 5, 7, 11} ∪ { } = {3, 5, 7, 11}.

The empty set is the identity element for the union of sets. What would be the identity element for the addition of whole numbers? It is the number 0. 

#### Identity Property for Intersection: 

The intersection of a set with the Universal set is the set itself. For a set A, A ⋂ U = A.

Let A = {3, 5, 7, 11} and N, the set of all natural numbers. Then A ⋂ N = {3, 5, 7, 11}. 

The Universal set is the identity for the intersection of sets. What would be the identity for the multiplication of whole numbers? It is the number 1.

#### Domination Laws: 

1. Any set intersected with an empty set gives the empty set. A ⋂ ∅ = ∅.

2. The union of any set with the Universal set is the Universal set. A ∪ U = U.


Use the laws of set operations to prove that (M ⋂ ∅) ∪ N = N

 Step 1: M ⋂ ∅ = ∅ (by Domination Law for intersection).
 Step 2: (M ⋂ ∅) ∪ N = ∅ ∪ N (replacing the value of (M ⋂ ∅) from Step 1). 
 Step 3: ∅ ∪ N = N (by Identity property of union)

 Therefore, (M ⋂ ∅) ∪ N = N