Set Theory Ordered Pairs and Cartesian Product with R

July 6, 2017
By

(This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers)

Part 5 of 5 in the series Set Theory
Ordered and Unordered Pairs

A pair set is a set with two members, for example, \{2, 3\}, which can also be thought of as an unordered pair, in that \{2, 3\} = \{3, 2\}. However, we seek a more a strict and rich object that tells us more about two sets and how their elements are ordered. Call this object \langle2, 3\rangle, which specifies that 2 is the first component and 3 is the second component. We also make the requirement that \langle2, 3\rangle \neq \langle3, 2\rangle. We can also represent this object, generalized as \langle x, y\rangle, as:
 \large{\langle x, y\rangle = \langle u, v \rangle}

Therefore x = u and y = v. This property is useful in the formal definition of an ordered pair, which is stated here but not explored in-depth. The currently accepted definition of an ordered pair was given by Kuratowski in 1921 (Enderton, 1977, pp. 36), though there exist several other definitions.

 \large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}}

The pair \langle x, y \rangle can be represented as a point on a Cartesian coordinate plane.

Cartesian Product

The Cartesian product A \times B of two sets A and B is the collection of all ordered pairs \langle x, y \rangle with x \in A and y \in B. Therefore, the Cartesian product of two sets is a set itself consisting of ordered pair members. A set of ordered pairs is defined as a ‘relation.’

For example, consider the sets A = \{1, 2, 3\} and B = \{2, 4, 6\}. The Cartesian product A \times B is then:

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

Whereas the Cartesian product B \times A is:

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

The following function implements computing the Cartesian product of two sets A and B.

cartesian <- function(a, b) {
  axb <- list()
  k <- 1
  for (i in a) {
    for (j in b) {
      axb[[k]] <- c(i,j)
      k <- k + 1
    }
  }
  return(axb)
}

Let’s use the function to calculate the Cartesian product A \times B and B \times A to see if it aligns with our results above.

a <- c(1,2,3)
b <- c(2,4,6)

as.data.frame(cartesian(a, b))
##   c.1..2. c.1..4. c.1..6. c.2..2. c.2..4. c.2..6. c.3..2. c.3..4. c.3..6.
## 1       1       1       1       2       2       2       3       3       3
## 2       2       4       6       2       4       6       2       4       6
as.data.frame(cartesian(b, a))
##   c.2..1. c.2..2. c.2..3. c.4..1. c.4..2. c.4..3. c.6..1. c.6..2. c.6..3.
## 1       2       2       2       4       4       4       6       6       6
## 2       1       2       3       1       2       3       1       2       3

Both outputs agree to our previous results.

Some Cartesian Product Theorems

We can state some theorems related to the Cartesian product of two sets. The first theorem states:

If A is a set, then A \times \varnothing = \varnothing and \varnothing \times A = \varnothing.

We can demonstrate this theorem with our cartesian() function.

cartesian(a, c()) # c() represents the empty set.
## list()
cartesian(c(), a)
## list()

The outputs are an empty list which is equivalent to the empty set \varnothing for our purposes of demonstration.

The next theorem involves three sets A, B, C.

  • A \times (B \cap C) = (A \times B) \cap (A \times C)
  • A \times (B \cup C) = (A \times B) \cup (A \times C)
  • (A \cap B) \times C = (A \times C) \cap (B \times C)
  • (A \cup B) \times C = (A \times C) \cup (B \times C)

We can demonstrate each in turn with a combination of our cartesian() from above, and the set.union() and set.intersection() functions from a previous post on set unions and intersections. The base R functions union() and intersect() can be used instead of the functions we defined previously.

a <- c(1,2,3)
b <- c(2,4,6)
c <- c(1,4,7)

The first identity A \times (B \cap C) = (A \times B) \cap (A \times C).

ident1.rhs <- cartesian(a, set.intersection(b, c)) # Right-hand Side
ident1.lhs <- set.intersection(cartesian(a, b), cartesian(a, c)) # Left-hand Side

isequalset(ident1.rhs, ident1.lhs)
## [1] TRUE
as.data.frame(ident1.rhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4
as.data.frame(ident1.lhs)
##   c.1..4. c.2..4. c.3..4.
## 1       1       2       3
## 2       4       4       4

The second identity A \times (B \cup C) = (A \times B) \cup (A \times C).

ident2.rhs <- cartesian(a, set.union(b, c))
ident2.lhs <- set.union(cartesian(a, b), cartesian(a, c))

isequalset(ident2.rhs, ident2.lhs)
## [1] TRUE
as.data.frame(ident2.rhs)
##   c.1..2. c.1..4. c.1..6. c.1..1. c.1..7. c.2..2. c.2..4. c.2..6. c.2..1.
## 1       1       1       1       1       1       2       2       2       2
## 2       2       4       6       1       7       2       4       6       1
##   c.2..7. c.3..2. c.3..4. c.3..6. c.3..1. c.3..7.
## 1       2       3       3       3       3       3
## 2       7       2       4       6       1       7
as.data.frame(ident2.lhs)
##   c.1..2. c.1..4. c.1..6. c.2..2. c.2..4. c.2..6. c.3..2. c.3..4. c.3..6.
## 1       1       1       1       2       2       2       3       3       3
## 2       2       4       6       2       4       6       2       4       6
##   c.1..1. c.1..7. c.2..1. c.2..7. c.3..1. c.3..7.
## 1       1       1       2       2       3       3
## 2       1       7       1       7       1       7

The third identity (A \cap B) \times C = (A \times C) \cap (B \times C).

ident3.rhs <- cartesian(set.intersection(a, b), c)
ident3.lhs <- set.intersection(cartesian(a, c), cartesian(b, c))

isequalset(ident3.rhs, ident3.lhs)
## [1] TRUE
as.data.frame(ident3.rhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7
as.data.frame(ident3.lhs)
##   c.2..1. c.2..4. c.2..7.
## 1       2       2       2
## 2       1       4       7

We finish the post with the fourth identity (A \cup B) \times C = (A \times C) \cup (B \times C).

ident4.rhs <- cartesian(set.union(a,b), c)
ident4.lhs <- set.union(cartesian(a,c), cartesian(b,c))

isequalset(ident4.rhs, ident4.lhs)
## [1] TRUE
as.data.frame(ident4.rhs)
##   c.1..1. c.1..4. c.1..7. c.2..1. c.2..4. c.2..7. c.3..1. c.3..4. c.3..7.
## 1       1       1       1       2       2       2       3       3       3
## 2       1       4       7       1       4       7       1       4       7
##   c.4..1. c.4..4. c.4..7. c.6..1. c.6..4. c.6..7.
## 1       4       4       4       6       6       6
## 2       1       4       7       1       4       7
as.data.frame(ident4.lhs)
##   c.1..1. c.1..4. c.1..7. c.2..1. c.2..4. c.2..7. c.3..1. c.3..4. c.3..7.
## 1       1       1       1       2       2       2       3       3       3
## 2       1       4       7       1       4       7       1       4       7
##   c.4..1. c.4..4. c.4..7. c.6..1. c.6..4. c.6..7.
## 1       4       4       4       6       6       6
## 2       1       4       7       1       4       7
References

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

MacGillivray, G. Cartesian Products and Relations. Victoria, BC. Retrieved from http://www.math.uvic.ca/faculty/gmacgill/guide/RF.pdf

Stacho, Juraj (n.d.). Cartesian Product [PowerPoint slides]. Retrieved from http://www.cs.toronto.edu/~stacho/macm101.pdf

The post Set Theory Ordered Pairs and Cartesian Product with 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...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)