Set Theory Ordered Pairs and Cartesian Product with R
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, {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 ⟨2,3⟩, which specifies that 2 is the first component and 3 is the second component. We also make the requirement that ⟨2,3⟩≠⟨3,2⟩. We can also represent this object, generalized as ⟨x,y⟩, as:
⟨x,y⟩=⟨u,v⟩
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.
⟨x,y⟩={{x},{x,y}}The pair ⟨x,y⟩ can be represented as a point on a Cartesian coordinate plane.
Cartesian Product
The Cartesian product A×B of two sets A and B is the collection of all ordered pairs ⟨x,y⟩ with x∈A and y∈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×B is then:
A×B={{1,2},{1,4},{1,6},{2,2},{2,4},{2,6},{3,2},{3,4},{3,6}}Whereas the Cartesian product B×A is:
B×A={{2,1},{2,2},{2,3},{4,1},{4,2},{4,3},{6,1},{6,2},{6,3}}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×B and B×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×∅=∅ and ∅×A=∅.
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 ∅ for our purposes of demonstration.
The next theorem involves three sets A,B,C.
- A×(B∩C)=(A×B)∩(A×C)
- A×(B∪C)=(A×B)∪(A×C)
- (A∩B)×C=(A×C)∩(B×C)
- (A∪B)×C=(A×C)∪(B×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×(B∩C)=(A×B)∩(A×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×(B∪C)=(A×B)∪(A×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∩B)×C=(A×C)∩(B×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∪B)×C=(A×C)∪(B×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.
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.