#!/usr/bin/env python
# coding: utf-8

# # Set algebra with Python scripts

# Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics. The language of set theory can be used in the definitions of nearly all mathematical objects.
# 
# **Set theory is commonly employed as a foundational system for modern mathematics**, particularly in the form of [**Zermelo–Fraenkel set theory**](https://en.wikipedia.org/wiki/Zermelo-Fraenkel_set_theory) with the [axiom of choice](https://en.wikipedia.org/wiki/Axiom_of_choice).
# 
# Python offers a native data structure called set, which can be used as a proxy for a mathematical set for almost all purposes.

# In[8]:


import IPython.display as disp


# ## Various ways to create a 'set' object in Python

# In[4]:


# Directly with curly braces
Set1 = {1,2}
print (Set1)


# In[5]:


type(Set1)


# In[6]:


# By calling the 'set' function i.e. typecasting
Set2 = set({2,3})
print(Set2)


# In[7]:


my_list=[1,2,3,4]
my_set_from_list = set(my_list)
print(my_set_from_list)


# ** Empty (Null) set is a special set **
# $$ \forall x, x \notin \varnothing $$ 
# #### Do not try to create the empty set by declaring an empty {}. That denotes an empty dictionary object 

# In[8]:


my_set = {}
print(type(my_set))


# #### Instead, use the set() function to create the empty (null) set from any empty data type e.g. dictionary or list

# In[9]:


my_set = set({})
print(type(my_set))
my_set_2 = set([])
print(type(my_set_2))


# ## Membership and size testing

# ### Membership testing by '*in*' and '*not in*' keywords

# In[10]:


my_set = set([1,3,5])
print("Here is my set:",my_set)
print("1 is in the set:",1 in my_set)
print("2 is in the set:",2 in my_set)
print("4 is NOT in the set:",4 not in my_set)


# ### Size checking by '*len*' or '*not*'

# In[11]:


S = {1,2}
not S


# In[12]:


T = set()
not T


# In[13]:


print("Size of S:", len(S))
print("Size of T:", len(T))


# ## Venn diagrams

# In[14]:


import matplotlib.pyplot as plt
import matplotlib_venn as venn
S = {1, 2, 3}
T = {0, 2, -1, 5}
venn.venn2([S, T], set_labels=('S','T'))
plt.show()


# In[15]:


venn.venn3(subsets = (1, 1, 1, 2, 1, 2, 2), set_labels = ('Set1', 'Set2', 'Set3'))
plt.show()


# ## Set relations
# * **Subset**
# * **Superset**
# * **Disjoint**
# * **Universal set**
# * **Null set**

# In[16]:


Univ = set([x for x in range(11)])
Super = set([x for x in range(11) if x%2==0])
disj = set([x for x in range(11) if x%2==1])
Sub = set([4,6])
Null = set([x for x in range(11) if x>10])


# In[17]:


print("Universal set (all the positive integers up to 10):",Univ)
print("All the even positive integers up to 10:",Super)
print("All the odd positive integers up to 10:",disj)
print("Set of 2 elements, 4 and 6:",Sub)
print("A null set:", Null)


# In[18]:


Super.issuperset(Sub)


# In[19]:


Super.issubset(Univ)


# In[20]:


Sub.issubset(Super)


# In[21]:


Sub.issuperset(Super)


# In[22]:


Super.isdisjoint(disj)


# **Alternatively, operators like '<=' or '>' can be used to check relations**

# In[23]:


Super > Sub


# In[24]:


Sub <= Super


# ### Algebra of inclusion

# If A, B and C are sets then the following hold:
# 
# **Reflexivity:**
# 
# $$ {\displaystyle A\subseteq A} $$
# 
# **Antisymmetry:**
# 
# $$ A\subseteq B\ \ and\ B\subseteq A\ \text if\ and\ only\ if\ A=B $$
# 
# **Transitivity:**
# 
# $$If\ {\displaystyle A\subseteq B}\ and \ {\displaystyle B\subseteq C}, then\ A ⊆ C $$

# ## Set algebra/Operations
# * **Equality**
# * **Intersection**
# * **Union**
# * **Complement**
# * **Difference**
# * **Cartesian product**

# ### Equality/Non-equality of sets

# In[25]:


S1 = {1,2}
S2 = {2,2,1,1,2}
print ("S1 and S2 are equal because order or repetition of elements do not matter for sets\nS1==S2:", S1==S2)


# In[26]:


S1 = {1,2,3,4,5,6}
S2 = {1,2,3,4,0,6}
print ("S1 and S2 are NOT equal because at least one element is different\nS1==S2:", S1==S2)


# ### Intersection between sets

# In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. Formally,
# 
# $$  {\displaystyle A\cap B=\{x:x\in A{\text{ and }}x\in B\}.} $$
# 
# ![Set intersection](https://upload.wikimedia.org/wikipedia/commons/5/5a/PolygonsSetIntersection.svg)

# In[27]:


# Define a set using list comprehension
S1 = set([x for x in range(1,11) if x%3==0])
print("S1:", S1)


# In[28]:


S2 = set([x for x in range(1,5)])
print("S2:", S2)


# In[29]:


# Both intersection method or & can be used
S_intersection = S1.intersection(S2)
print("Intersection of S1 and S2:", S_intersection)

S_intersection = S1 & S2
print("Intersection of S1 and S2:", S_intersection)


# ** One can chain the methods to get intersection with more than 2 sets **

# In[30]:


S3 = set([x for x in range(4,10)])
print("S3:", S3)


# In[31]:


S1_S2_S3 = S1.intersection(S2).intersection(S3)
print("Intersection of S1, S2, and S3:", S1_S2_S3)


# ** Now change the S3 to contain 3**

# In[32]:


S3 = set([x for x in range(3,10)])
print("S3:", S3)
S1_S2_S3 = S1.intersection(S2).intersection(S3)
print("Intersection of S1, S2, and S3:", S1_S2_S3)


# #### The symbol '&' can be used for intersection

# In[1]:


A = {1, 2, 3}
B = {5,3,1}
print("Intersection of {} and {} is: {} with size {}".format(A,B,A&B,len(A&B)))


# ![3 sets intersection](https://upload.wikimedia.org/wikipedia/commons/3/3e/Venn_0000_0001.svg)

# **Commutative law:** 
# $$ {\displaystyle A\cap B=B\cap A} $$
# 
# **Associative law:**
# $$ {\displaystyle (A\cap B)\cap C=A\cap (B\cap C)} $$
# 
# ** Distributive law:**
# $$ {\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)} $$
# 
# 
# 
# 

# ### Union of sets

# In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. Formally,
# 
# $$ {\displaystyle A\cup B=\{x:x\in A{\text{ or }}x\in B\}}$$

# In[33]:


# Both union method or | can be used
S1 = set([x for x in range(1,11) if x%3==0])
print("S1:", S1)
S2 = set([x for x in range(1,5)])
print("S2:", S2)

S_union = S1.union(S2)
print("Union of S1 and S2:", S_union)
S_union = S1 | S2
print("Union of S1 and S2:", S_union)


# In[34]:


S3 = set([5*x for x in range(1,3)])
print("S3:", S3)
S4 = set ([7,8])
print("S4:", S4)
S1_S2_S3_S4 = S1.union(S2).union(S3).union(S4)
print("Union of S1, S2, S3, and S4:", S1_S2_S3_S4)


# #### The symbol '|' can be used for union

# In[12]:


A = {1, 2, 3}
B = {5,3,4}
print("Union of {} and {} is: {} with size {}".format(A,B,A|B,len(A|B)))


# ![Union of sets](https://upload.wikimedia.org/wikipedia/commons/e/ee/Venn_0111_1111.svg)

# ** We can prove the following identities (associative and distributive properties) **
# 
# $$ {\displaystyle A\cup (B\cup C)=(A\cup B)\cup C} $$
# $$ {\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)} $$
# $$ {\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)} $$ 

# ### More algebra of inclusion involving union and intersection

# If A, B and C are subsets of a set S then the following hold:
# 
# **Existence of a least element and a greatest element:**
# 
# $$ {\displaystyle \varnothing \subseteq A\subseteq S} $$
# 
# **Existence of joins:**
# 
# $$ {\displaystyle A\subseteq A\cup B} $$
#             
# $$ If\ {\displaystyle A\subseteq C}\ and\ {\displaystyle B\subseteq C,}\ then\ {\displaystyle A\cup B\subseteq C} $$
# 
# **Existence of meets:**
# $$ {\displaystyle A\cap B\subseteq A} $$
# 
# $$ If\ {\displaystyle C\subseteq A}\ and\ {\displaystyle C\subseteq B,}\ then\ {\displaystyle C\subseteq A\cap B} $$
# 

# ### Complement of set

# In[11]:


disp.Image("A-complement.PNG")


# If A is a set, then the absolute complement of A (or simply the complement of A) is the set of elements not in A. In other words, if U is the universe that contains all the elements under study, and there is no need to mention it because it is obvious and unique, then the absolute complement of A is the relative complement of A in U. Formally,
# 
# $$ {\displaystyle A^{\complement }=\{x\in U\mid x\notin A\}.} $$

# In[35]:


S=set([x for x in range (101) if x%2==0])
print ("S is the set of even numbers between 0 and 100:", S)


# In[36]:


S_complement = set([x for x in range (101) if x%2!=0])
print ("S_complement is the set of odd numbers between 0 and 100:", S_complement)


# ** You can take the union of two sets and if that is equal to the universal set (in the context of your problem), then you have found the right complement **

# In[37]:


print ("Is the union of S and S_complement equal to all numbers between 0 and 100?", 
       S.union(S_complement)==set([x for x in range (101)]))


# ** De Morgan's laws:**
# 
# $$ {\displaystyle \left(A\cup B\right)^{\complement }=A^{\complement }\cap B^{\complement }.} $$
# $$ {\displaystyle \left(A\cap B\right)^{\complement }=A^{\complement }\cup B^{\complement }.} $$
# 
# ** Complement laws **
# 
# $$ {\displaystyle A\cup A^{\complement }=U.} $$
# $$ {\displaystyle A\cap A^{\complement }=\varnothing .} $$
# $$ {\displaystyle \varnothing ^{\complement }=U.} $$
# $$ {\displaystyle U^{\complement }=\varnothing .} $$
# $$ {\displaystyle {\text{If }}A\subset B{\text{, then }}B^{\complement }\subset A^{\complement }.} $$

# ### Just an example of De Morgan's laws

# In[38]:


A={-6,3,4,5}
B={-6,5,13}
U=A|B|{12,-2,-4}
print("U:",U)


# In[39]:


def complement_of_union(S1,S2,S3):
    Su = S1|S2
    S4 = set()
    for item in S3:
        if item not in Su:
            S4.add(item)
    return S4

def intersection_of_complement(S1,S2,S3):
    S1C = set()
    S2C = set()
    for item in S3:
        if item not in S1:
            S1C.add(item)
    for item in S3:
        if item not in S2:
            S2C.add(item)
    return (S1C & S2C)


# In[40]:


complement_of_union(A,B,U) == intersection_of_complement(A,B,U)


# In[41]:


complement_of_union(A,B,U)


# In[42]:


intersection_of_complement(A,B,U)


# ### Difference between sets

# If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A, is the **set of elements in B but not in A**.
# 
# $$ {\displaystyle B\setminus A=\{x\in B\mid x\notin A\}.} $$
# 
# ![Set difference](https://upload.wikimedia.org/wikipedia/commons/5/5a/Venn0010.svg)

# In[43]:


S1 = set([x for x in range(31) if x%3==0])
print ("Set S1:", S1)


# In[44]:


S2 = set([x for x in range(31) if x%5==0])
print ("Set S2:", S2)


# In[45]:


S_difference = S2-S1
print("Difference of S1 and S2 i.e. S2\S1:", S_difference)

S_difference = S1.difference(S2)
print("Difference of S2 and S1 i.e. S1\S2:", S_difference)


# ** Following identities can be obtained with algebraic manipulation: **
# 
# $$ {\displaystyle C\setminus (A\cap B)=(C\setminus A)\cup (C\setminus B)} $$
# $$ {\displaystyle C\setminus (A\cup B)=(C\setminus A)\cap (C\setminus B)} $$
# $$ {\displaystyle C\setminus (B\setminus A)=(C\cap A)\cup (C\setminus B)} $$
# $$ {\displaystyle C\setminus (C\setminus A)=(C\cap A)} $$
# $$ {\displaystyle (B\setminus A)\cap C=(B\cap C)\setminus A=B\cap (C\setminus A)} $$
# $$ {\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus (A\setminus C)} $$      
# $$ {\displaystyle A\setminus A=\emptyset} $$
# $$ {\displaystyle \emptyset \setminus A=\emptyset } $$
# $$ {\displaystyle A\setminus \emptyset =A} $$
# $$ {\displaystyle A\setminus U=\emptyset } $$

# ### Symmetric difference

# In set theory, the ***symmetric difference***, also known as the ***disjunctive union***, of two sets is the set of elements which are in either of the sets and not in their intersection.
# $$ {\displaystyle A\,\triangle \,B=\{x:(x\in A)\oplus (x\in B)\}}$$ 
# 
# $$ {\displaystyle A\,\triangle \,B=(A\smallsetminus B)\cup (B\smallsetminus A)} $$
# 
# $${\displaystyle A\,\triangle \,B=(A\cup B)\smallsetminus (A\cap B)} $$

# ![Symmetric difference](https://upload.wikimedia.org/wikipedia/commons/4/46/Venn0110.svg)

# **Some properties,**
# 
# $$ {\displaystyle A\,\triangle \,B=B\,\triangle \,A,} $$
# $$ {\displaystyle (A\,\triangle \,B)\,\triangle \,C=A\,\triangle \,(B\,\triangle \,C).} $$
# 
# **The empty set is neutral, and every set is its own inverse:**
# 
# $$ {\displaystyle A\,\triangle \,\varnothing =A,} $$
# $$ {\displaystyle A\,\triangle \,A=\varnothing .} $$

# In[46]:


print("S1",S1)
print("S2",S2)
print("Symmetric difference", S1^S2)
print("Symmetric difference", S2.symmetric_difference(S1))


# ### Cartesian Product

# In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
# 
# $$ {\displaystyle A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.} $$
# 
# More generally, a Cartesian product of n sets, also known as an n-fold Cartesian product, can be represented by an array of n dimensions, where each element is an *n-tuple*. An ordered pair is a *2-tuple* or couple. The Cartesian product is named after [René Descartes](https://en.wikipedia.org/wiki/Ren%C3%A9_Descartes) whose formulation of analytic geometry gave rise to the concept

# In[47]:


A = set(['a','b','c'])
S = {1,2,3}


# In[48]:


def cartesian_product(S1,S2):
    result = set()
    for i in S1:
        for j in S2:
            result.add(tuple([i,j]))
    return (result)

C = cartesian_product(A,S)
print("Cartesian product of A and S\n{} X {}:{}".format(A,S,C))


# In[49]:


print("Length of the Cartesian product set:",len(C))


# ** Note that because these are ordered pairs, same element can be repeated inside the pair i.e. even if two sets contain some identical elements, they can be paired up in the Cartesian product **

# In[50]:


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

print ("Cartesian product of {} and {} is:\n{}".format(A,B,cartesian_product(A,B)))


# ** Instead of writing functions ourselves, we could use the *itertools* library of Python. Remember to turn the resulting product object into a list for viewing and subsequent processing **

# In[14]:


from itertools import product as prod


# In[15]:


A = {1,2,3,4}
B = {2,3,4}
p=list(prod(A,B))
print (p)


# ### Cartesian Power
# 
# The Cartesian square (or binary Cartesian product) of a set X is the Cartesian product $X^2 = X × X$. An example is the 2-dimensional plane $R^2 = R × R$ where _R_ is the set of real numbers: $R^2$ is the set of all points (_x_,_y_) where _x_ and _y_ are real numbers (see the [Cartesian coordinate system](https://en.wikipedia.org/wiki/Cartesian_coordinate_system)).
# 
# The cartesian power of a set X can be defined as:
# 
# ${\displaystyle X^{n}=\underbrace {X\times X\times \cdots \times X} _{n}=\{(x_{1},\ldots ,x_{n})\ |\ x_{i}\in X{\text{ for all }}i=1,\ldots ,n\}.} $
# 
# The [cardinality of a set](https://en.wikipedia.org/wiki/Cardinality) is the number of elements of the set. Cardinality of a Cartesian power set is $|S|^{n}$ where |S| is the cardinality of the set _S_ and _n_ is the power.
# 
# __We can easily use itertools again for calculating Cartesian power__. The _repeat_ parameter is used as power.

# In[16]:


A = {1,2,3} # 3 element set
p2=list(prod(A,repeat=2)) # Power set of power 2
print("Cartesian power 2 with length {}: {}".format(len(p2),p2))
print("\n")
p3=list(prod(A,repeat=3)) # Power set of power 3
print("Cartesian power 3 with length {}: {}".format(len(p3),p3))


# In[18]:


A = {1, 2, 3}
k = 2
cartesian_power = set([i for i in prod(A, repeat = k)])
print("Tuples in %s^%i: " %(A,k))
for i in cartesian_power:
    print(i)
print;
print("Size = ", len(cartesian_power))