Algebra of Sets in R

By Aaron Schlegel

Venn diagram of relative complement of two sets

(This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers)
Part 4 of 4 in the series Set Theory

The set operations, union and intersection, the relative complement and the inclusion relation (subsets) subseteq are known as the algebra of sets. The algebra of sets can be used to find many identities related to set relations that will be discussed later. We turn now to introducing the relative complement.

Relative Complement

The relative complement of two sets A and B is defined as the members of A not in B and is denoted A - B (or A / B). More formally, the relative complement of two sets is defined as:

 large{A - B = {x in A space | space x notin B }}

Just like the set operations union and intersection, the relative complement can be visualized using Venn diagrams.

The shaded area represents the relative complement A - B.

For example, consider the following three sets A, B, C.

  • Let A be the set of all Calico cats
  • Let B be the set of all Manx cats
  • Let C be the set of all male cats

What are the elements of the set A cup (B - C)? Start with the relative complement in parentheses, which is the set of all nonmale Manx cats. It wouldn’t be as correct to state B - C is the set of all female Manx cats as it hasn’t been explicitly defined that the cats not in the set C are female. Then the union of A and this set is, therefore, the set of all cats who are either Calico or Manx nonmales (or both).

Determining the elements of the set (A cup B) - C proceeds in the same way. The union of A and B represents the set of all cats who are Calico or Manx or both. Thus the relative complement of this set C is then the set of all nonmale cats who are either or both Calico or Manx.

The set (A - C) cup (B - C) simplifies to one of the sets discussed above. The relative complement A - C is the set of all nonmale Calico cats while B - C is the set of all nonmale Manx cats. The union of these two sets thus results in the set of all nonmale cats who are either Calico or Manx, which is the same as the set (A cup B) - C.

We can define an R function to find the relative complement of two sets.

relcomp 

Find the relative complements of the sets A = {1,2,3,4,5} and B = {1,3,5,7}

a 
print(relcomp(b, a))
## [1] 7
Set Identities

Many identities can be formed using the set operations we have explored.

Commutative Laws

 large{A cup B = B cup A}
 large{A cap B = B cap A}

We can show this identity using the isequalset() and set.union() functions we created in the previous post on union and intersections.

a 
isequalset(set.union(a, b), set.union(b, a))
## [1] TRUE
isequalset(set.intersection(a, b), set.intersection(b, a))
## [1] TRUE

Associative Laws

 large{A cup (B cup C) = (A cup B) cup C}
 large{A cap (B cap C) = (A cap B) cap C}

Create a third set c.

c 

Starting with the first associative law A cup (B cup C) = (A cup B) cup C

assoc.rhs 

Showing the second associative law, A cap (B cap C) = (A cap B) cap C

assoc2.rhs 

Distributive Laws

 large{A cap (B cup C) = (A cap B) cup (A cap C)}
 large{A cup (B cap C) = (A cup B) cap (A cup C)}

starting with the first distributive law, A cap (B cup C) = (A cap B) cup (A cap C).

dist.rhs 

Which are equal sets as member order does not matter when determining the equality of two sets. The second distributive law, A cup (B cap C) = (A cup B) cap (A cup C) can be demonstrated likewise.

dist2.rhs 

De Morgan's Laws

 large{C - (A cup B) = (C - A) cap (C - B)}
 large{C - (A cap B) = (C - A) cup (C - B)}

We can use the function to find the relative complement of two sets we wrote earlier to show De Morgan's laws. Starting with the first law, C - (A cup B) = (C - A) cap (C - B)

morgan.rhs 

The second De Morgan's law, C - (A cap B) = (C - A) cup (C - B) can be shown similarly.

morgan2.rhs 

De Morgan's laws are often stated without C, being understood as a fixed set. All sets are a subset of some larger set, which can be called a ‘space,' or S. If one considers the space to be the set of all real numbers mathbb{R}, and A and B to be two subsets of S (mathbb{R}), then De Morgan's laws can be abbreviated as:

 large{-(A cup B) = - A cap - B}
 large{-(A cap B) = - A cup - B}

We will close the post by stating some identities with the assumption A subseteq S

 large{A cup S = S qquad A cap S = A}
 large{A cup - A = S qquad A cap - A = varnothing}

Though we cannot directly program the set of all real numbers mathbb{R} as it is an uncountable set, we can show these identities by using a subset of mathbb{R} where a set A is a subset of that subset.

Generate the set A as the set of integers from one to ten and S, our simulated set of all real numbers, as the set of integers from one to 100.

a 

Show the first identity: A cup S = S

isequalset(set.union(a, s), s)
## [1] TRUE

Second identity: A cap S = A

isequalset(set.intersection(a, s), a)
## [1] TRUE

Third identity: A cup - A = S

isequalset(set.union(a, relcomp(s, a)), s)
## [1] TRUE

Fourth identity: A cap - A = varnothing

set.intersection(a, relcomp(s, a))
## logical(0)
References

Enderton, H. (1977). Elements of set theory (1st ed.). New York: Academic Press.

The post Algebra of Sets in R appeared first on Aaron Schlegel.

To leave a comment for the author, please follow the link and comment on their blog: R – Aaron Schlegel.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more…

Source:: R News

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.