Definition: “Let A and B be sets. A binary relation from A to B is a subset of A × B.” Discrete Mathematics and its Applications by Rosen.
From the definition above, we can easily see that in a binary relation from A to B, the first element will belong to A and the second one to B.
Also, to identify or list all pairs that belong to a relation, we need to create the cartesian product AxB and check what pairs of elements hold the specific condition (s) imposed by the specific relation.
I suggest you start following the previous steps, so you don’t miss any pair that belongs to the relation. When you get more practice, you will be able to do it without writing the cartesian product.
If A = {0,1,2,3,4} and B = {0,1,2,3}, then
AxB={(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3), (4,0), (4,1), (4,2), (4,3)}
To solve each exercise, we just need to filter the elements from the cartesian product that holds the specific condition.
Table of Contents
a) a=b
In this case, we choose only the pairs where the first element equals the second element in all the ordered pairs that belong to the cartesian product AxB. Notice that the pairs have the form (a,b) where a∈A and b∈B.
Answer:
{(0, 0), (1, 1), (2, 2), (3, 3)}
b) a+b=4
Similarly, to the previous example, let’s filter the pairs whose sum equals 4.
Answer:
{(1, 3), (2, 2), (3,1), (4,0)}
Notice that all the pairs in the answer below add 4. Also notice that there is no other pair in the cartesian product AxB that adds to 4.
c) a>b
Again, let’s choose all pairs from the cartesian product AxB in which the first number is greater than the second one.
Notice that the cartesian product is from A to B and a∈A and b∈B.
Answer:
{(1,0), (2,0), (2,1), (3,0), (3,1), (3,2), (4,0), (4,1), (4,2), (4,3)}
d)a|b
In this case, you just need to understand the notation and apply the same steps as in the previous exercises. You just filter the cartesian product AxB according to the specific condition.
a|b means that a divides b.
Answer:
{(1,0), (1,1), (1,2), (1,3), (2,0), (2,2), (3,0), (3,3), (4,0)}
e) gcd(a,b) = 1
In this case, you need to know what gcd means. gcd(a,b) equals the greatest common divisor between a and b. In this case, it should be 1. Notice that (4,2) does not belong to this relation because gcd(4,2) = 2.
Answer:
{(0,1), (1,0), (1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), (4,1), (4,3)}
f) lcm(a,b) = 2
In this case, the pairs that belong to the relation, are those whose least common multiple is 2.
“In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b” Source.
Answer:
{(1,2), (2,1), (2,2)}
Related exercises:
- Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)∈R if and only if
- Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) ∈ R if and only if
- For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive.
