# Set Theory Ordered Pairs and Cartesian Product with R

**R – Aaron Schlegel**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

###### Ordered and Unordered Pairs

A pair set is a set with two members, for example, [latex]\{2, 3\}[/latex], which can also be thought of as an unordered pair, in that [latex]\{2, 3\} = \{3, 2\}[/latex]. 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 [latex]\langle2, 3\rangle[/latex], which specifies that [latex]2[/latex] is the first component and [latex]3[/latex] is the second component. We also make the requirement that [latex]\langle2, 3\rangle \neq \langle3, 2\rangle[/latex]. We can also represent this object, generalized as [latex]\langle x, y\rangle[/latex], as:

[latex display=”true”] \large{\langle x, y\rangle = \langle u, v \rangle} [/latex]

Therefore [latex]x = u[/latex] and [latex]y = v[/latex]. 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.

[latex display=”true”] \large{\langle x, y \rangle = \big\{\{x\}, \{x, y\} \big\}} [/latex]

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

###### Cartesian Product

The Cartesian product [latex]A \times B[/latex] of two sets [latex]A[/latex] and [latex]B[/latex] is the collection of all ordered pairs [latex]\langle x, y \rangle[/latex] with [latex]x \in A[/latex] and [latex]y \in B[/latex]. 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 [latex]A = \{1, 2, 3\}[/latex] and [latex]B = \{2, 4, 6\}[/latex]. The Cartesian product [latex]A \times B[/latex] is then:

[latex display=”true”] A \times B = \big\{\{1,2\}, \{1,4\}, \{1,6\}, \{2,2\}, \{2,4\},\{2,6\},\{3,2\},\{3,4\},\{3,6\}\big\}[/latex]

Whereas the Cartesian product [latex]B \times A[/latex] is:

[latex display=”true”] B \times A = \big\{\{2,1\}, \{2,2\}, \{2,3\}, \{4,1\}, \{4,2\},\{4,3\},\{6,1\},\{6,2\},\{6,3\}\big\}[/latex]

The following function implements computing the Cartesian product of two sets [latex]A[/latex] and [latex]B[/latex].

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 [latex]A \times B[/latex] and [latex]B \times A[/latex] 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 [latex]A[/latex] is a set, then [latex]A \times \varnothing = \varnothing[/latex] and [latex]\varnothing \times A = \varnothing[/latex].

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 [latex]\varnothing[/latex] for our purposes of demonstration.

The next theorem involves three sets [latex]A, B, C[/latex].

- [latex]A \times (B \cap C) = (A \times B) \cap (A \times C)[/latex]
- [latex]A \times (B \cup C) = (A \times B) \cup (A \times C)[/latex]
- [latex](A \cap B) \times C = (A \times C) \cap (B \times C)[/latex]
- [latex](A \cup B) \times C = (A \times C) \cup (B \times C)[/latex]

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 [latex]A \times (B \cap C) = (A \times B) \cap (A \times C)[/latex].

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 [latex]A \times (B \cup C) = (A \times B) \cup (A \times C)[/latex].

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 [latex](A \cap B) \times C = (A \times C) \cap (B \times C)[/latex].

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 [latex](A \cup B) \times C = (A \times C) \cup (B \times C)[/latex].

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.

**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 about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.