Relations | Studytution

New Sets From Old

• As we saw a set is a collection of items and we can construct new sets from old sets.
• So, we can take unions combine two sets into one.
• We can take intersections, take the common elements.
• We can take the difference that is take the elements of X which are not in Y and if we define the universe with respect to which we are working, we can define the complement those elements that are not in X.

Define subsets using set comprehension

• Odd integers
  {z | z ∈ Z, z mod 2 = 1}
  Rationals not in reduced form
  {p/q | p, q ∈ Z, gcd(p, q) > 1}
  Reals in [3, 17)
  {r | r ∈ R, 3 ≤ r < 17}
• Now, in general we are interested in carving out subsets of a set and so, we use the set comprehension notation.
• So, what this does is it takes a base set and takes elements of that set, then it applies some condition those elements we are interested in and then it collects
  them all together.
• So, we can take all the integers which are divisible by 2 or not divisible by 2 in this case, so we get the odd one; so, those where the remainder is 1.
• Or we can take all fractions in which the numerator and the denominator have no common divisor or we can take for instance the real numbers which lie in an interval with [3,17).

Cartesian Product

• in the Cartesian product basically what we do is we take two sets and we take one element from each and form a pair.
• So, A × B as it is called is the set of all pairs which we write with this normal bracket notation (a,b) such that the first element a comes from the big the set A and the second element comes from the set B.
• A × B = {(a, b) | a ∈ A, b ∈ B}
• Pair up elements from A and B
  A = {0, 1}, B = {2, 3}
  A × B = {(0, 2),(0, 3),(1, 2),(1, 3)}
• So, for instance, if A is the set {0, 1} and B is a set {2, 3} then all possible pairs we can form in the Cartesian product a 0 combined with 2.
• So, (0, 2), (0 ,3) and then 1 combined with 2, (1 , 2) and (1,3). So, we have four possible pairs.
• in sets we said that the order of the element is not important, but of course, when we  are doing this kind of a pairing, then we know that the left set comes from the left part of the product and the right element comes from the right part of the product.
• So, for example, (0 ,1) is not equal to (1 , 0). So, here we have to respect the order when we talk about a pair.
• Now, if we have sets of numbers right, then we normally visualize the product as a space which we draw familiarly as a graph.
• So, for instance if we take N× N then we draw N × N
  as this grid, where on the x-axis you have one copy of N, on the y-axis you have another copy of N.
• So, you can take the first coordinate plot it on the x-axis; take the second coordinate plot it on the y-axis and where those two points meet in the grid is the point that we are interested in.
• So, this is one way of visualizing a binary relation on numbers.
• And, we can do the same thing if you are using say the reals, in which case the grid points that we are going to plot will have real coordinates and not just natural number coordinates.

Binary Function

• Cartesian product which consists of all possible pairs of the two sets and as we did with set comprehension we might want to pick out some of these sets some of these pairs and this is what we call a relation.
• So, we combine this Cartesian product operation with set comprehension.
• {(m, n) | (m, n) ∈ N × N, n = m + 1}
  {(0, 1),(1, 2),(2, 3), . . . ,(17, 18), . . .}
• So, for instance, we can take all pairs of numbers which are natural numbers (m ,n), but we want to insist that
  the second number is 1 plus the first number.
• So, we get for instance (0, 1) because the second number one is 0 + 1; (2, 3) because 3 is 2 + 1, (17, 18) and so on.
• And, if we plot these points alone on the right then we get these so, we get a subset of the overall points and this these points satisfied this set comprehension
  condition.
• Pairs (d, n) where d is a factor of n
  {(d, n) | (d, n) ∈ N × N, d|n}
  {(1, 1), . . . ,(2, 82), . . . ,(14, 56), . . .}
• example would be pairs again of natural numbers (d,n), where d is a factor of n.
• Remember, d is a factor of n means that if I divide n by d, I get remainder 0.
• So, for instance 2 is a factor of 82, 14 is a factor of 56. So, these will be points in our relation.
• So, this is what is called a binary relation.
• Binary relation R ⊆ A × B
• So, formally it is a subset of the product.
• So, we take the Cartesian product all possible pairs and then we apply some kind of a condition which filters out the pairs of interest to us and it gives us therefore, a subset of pairs and this is what we call a relation.
• Notation: (a, b) ∈ R, a R b
• Now, to denote the pairs that belonged to the relation either we can give the name of the relation as a set and say that (a,b) ∈R or sometimes to say that a is related to b, we use R as a kind of operator.
• We say a is related by R to b and so, we write a R b.
• So, these are two notations which you might see in different books and they mean exactly the same thing.

More Relations

• supposing you have a school in which there are some teachers and some courses to be taught.
• So, T is the set of teachers; C is the set of courses that are being offered in this term, then you need to describe which teachers are teaching which courses.
• So, we would have an allocation relation A which is a subset of all possible pairs T × C.
• A ⊆ T × C describes the allocation of teachers to courses
  A = {(t, c) | (t, c) ∈ T × C,t teaches c}
• So, every teacher and principle could be teaching every course, but of course, this is not normally the case.
• We do not have all teachers teaching all courses, we have some teachers teaching some courses.
• So, we would specifically say take every pair of possible teacher course pairs, then we take out those were precisely the teacher T is actually teaching the
  course C and we collect those together to form this allocation relation.
• So, here is a different graphical way of describing a relation not in terms of the grid and the graph that we have learned when we do graphs in school.
• Another example of a similar type of a relation is that between a parent and a child specifically let us look at mothers and children.
• So, if we have a set of people in a country, then we can take the set of all pairs of people and then isolate from that pairs in which the first element of the pair is the mother of the second element.
• So, we want (m,c) which belongs to P × P such that m is the mother ofc
• So, supposing we want to plot all points which are in R × R which are at a distance 5 from (0, 0) which is normally called the origin.
• So, one thing you need to know for this we probably you should have learned this at some point is that if I take a point (a ,b) and calculate its difference from (0 , 0).
• So, this is calculated using the Pythagoras theorem and it comes out to be √a 2 +b 2 .
• So, in other words, the relation we are looking for in this case is all (a,b) whose distance from (0 , 0) is 5. So, all (a, b) and R cross R such that √a 2 +b 2 is equal to 5.
• So, here are some of the points (0,5) for instance you can see (0, 5) is there because the sum is 0 plus 25 and the square root of that is 5.
• (3 ,4) is there because 3 squared is 9, 4 squared is 16, 9 plus 16 is 25, square root to 25 is again 5.
• if we plot every such point in R × R which satisfies this actually defines a circle of radius 5 with center at (0 , 0).
• So, relations can define interesting geometric shapes and very often we do deal with geometric shapes in this relational form because it is easier to manipulate than looking at pictures.
• A subset of Q
  {p/q | (p, q) ∈ Z × Z, gcd(p, q) = 1}
  . . . but also a relation on Z × Z
  {(p, q) | (p, q) ∈ Z × Z, gcd(p, q) = 1}
• a rational in reduced form has p / q such that p and q are integers and the gcd is 1 right; that means, that
  they do not have a greatest common divisor other than 1.
• But, we can also think of this as a relation on integers itself.
• We want all pairs of integers.
• So, every rational is really a pair of integers, the numerator and the denominator and we want every pair of integers where the gcd is 1, that is, there is no common divisor.

Beyond Binary Relations

•  The Cartesian product notation extends to multiple sets.
• Pythagoras theorem which says that the square on the hypotenuse is the sum of the squares on the opposite sides.
• So, what values of a, b and c could be the sides of a right triangle are determined by Pythagoras’s theorem.
• So, we would say that a, b and c is a valid triple in the Pythagoras sense if (a, b, c) belongs to N × N × N.
• So, here we now have three copies of N and a, b, c must all be nonzero.
• They must all be positive length we do not want to have triangles in which one line one side is collapsed to a point and we want the constraint that a2 +b 2=c 2

Back To The Binary Relations

 identity relation

•  the identity relation maps every element to itself.
• So, if I take A × A, so, first of all the identity relation is defined on two copies of the same set because identity means equality.
• So, I take A × A.
• So, this has all kinds of pairs (a , b), where both a and b belong to A and now, I want the condition that a = b.
  So, in other words, I want things of the form (a , a).
• So, if I plot this for instance on the natural numbers and N × N, then I get (0, 0); (1, 1) and so on, and these are the points which are drawn on the right in this grid.
• I ⊆ A × A
  I = {(a, b) | (a, b) ∈ A × A, a = b}
  I = {(a, a) | (a, a) ∈ A × A}
  I = {(a, a) | a ∈ A}
• Now, point of notation we sometimes it is tedious to write this notation as it is says us (a,b) time in n. So, we do not want to you know have to write out this long thing.
• So, sometimes we simplify this by saying I want all pairs such that a comma a belongs to A × A.
• So, what we are really saying is that the second day and the first day must be the same.
• So, we are collapsing the equality and this.
• Now, this is not technically correct, but this is often used in order to simplify the notation.
• sometimes we might drop the product altogether.
• We might just say we want all pairs (a ,a)where a comes from the set A.
• So, in other words we are pulling out one copy of the element from the set and then we are constructing a pair by taking two copies of it.
• these are equivalent ways of writing this although only the first one technically follows the notation that we are using to introduce relations.

properties of relations

1.REflexive

• reflexivity refers to the fact that an element is related to itself.
• R ⊆ A × A, I ⊆ R
  {(a, b) | (a, b) ∈ N × N, a, b > 0, a|b}
  a|a for all a > 0
•  a reflexive relation is one in which for every element a; (a,a) belongs to R.
• So, in other words based on what we just wrote above, it means that the identity relation is included in R. So, it does not mean that is the only thing.
• The identity relation has only the reflexive elements.
• A relation that is reflexive will have the identity pairs and it will have other pairs, but it must have all the
  identity pairs to be called reflexive.

symmetric relation

• (a, b) ∈ R if and only if (b, a) ∈ R
• {(a, b) | (a, b) ∈ N × N, gcd(a, b) = 1}
• A symmetric relation for instance is one where if (a, b) is there, then (b, a) must be there.
• So, for instance looking at reflexive relations, one example is the division relation.
• So, if we provided we make sure that the numbers are not 0, then we know it is reflexive because every number divides itself.
• So, if we take the reflect division relation as the relation that we introduced in the first part of this lecture that would be reflexive because a divides a for every a which is not 0.
• Similarly, symmetric relations if we look at pairs where the greatest common divisor is 1, in other words they have no common divisors.
• This is what happens for example, in reduced fractions, then it does not matter whether we write it as (a , b) or (b, a). So, if (a, b) has greatest common divisor 1, so does (b , a). So, (a, b) and (b, a) must both either be there in the relation or neither will be there.
• {(a, b) | (a, b) ∈ N × N, |a − b| = 2}
• Similarly, if we look at this which is asking about the absolute value so, it is saying give me all numbers a and b such that a – b is either 2 or -2.
• So, the absolute value takes the difference and removes the negative sign.

2.Transitive Relations

• transitivity says that if we have two pairs which are related such that they share an elements.
• So, a is related to b and b is related to c, then a must be related to c.
• So, again our divisibility is a relation. So, supposing we say that 2 | 6 and we say that 6 | 36, then from this we can conclude that 2 | 36 as well, right.
• Similarly, if we take less than if we say that 3 < 10 and 10 < 28, then we know from this that 3 < 28.

3.AntiSymmetry Relations

•  symmetry says that if (a, b) is in R, then (b, a) must also be in R.
• Anti-symmetry says something different it says if (a, b) is in R, then (b, a) should not be in R.
• So, less than for example, which was transitive above is also anti-symmetric.
• If you take strictly less than, if a is strictly less than b; then it cannot be that be strictly less than a.
• So, this is an anti symmetric relation, but anti symmetry does not require that one of the two must be there.
• It only says that if one pair is there the opposite pair should not be there ok.
• Similarly, if we look at our mother and children example; obviously, if p is the mother of c then c cannot be the mother of p ok.
• Now, there may be p and c such that neither p is the mother of c nor is c is the mother of p.
• So, that is allowed.
• We do not insist that every pair (p, c) must be related one way or another, but if it is related one way it should not be related the other way is what anti-symmetry says.

Equivalence Relations

•  equivalence relation is something that is reflexive, symmetric and transitive.
• So, as an example supposing we connect together all numbers which have the same  remainder modulo 5.
• So, for instance 7 has a remainder 2 with respect to 5 and so does 22.
• So, 7 and 5 would be related in this way if we define the relationship as having the same remainder modulo 5.
• Now, notice that if two numbers have the same remainder modulo 5; that means, that going
  from one number to the other you are going in multiples of 5.
• So, for instance 22 -7 is 15 right.
• So, this is this modulo arithmetic. So, if you add the number that you are dividing by, then you get the same remainder and so, in set notation we can say that the integers modulo 5 are all pairs a, b such that b – a mod 5 is 0.
• In other words, we are not asking what is the actual remainder of b and a, we are just saying that b and a are separated by a multiple of 5 therefore, they must have the same remainder modulo 5.
• Now, this divides the integers into five groups if I based on the remainder.
• So, there are the group of numbers which are divisible by 5, they have remainder 0.
• Those like 6, 11 and all which have remainder 1; 7, 12 and all which one remainder 2 and so on. So, we have five possible remainders 0, 1, 2, 3, 4 and therefore, this divides the set of integers into five disjoint classes.
• So, he main thing to note about an equivalence relation is that it partitions a set.
• It partitions a set into disjoint groups, all of the elements within a group are equivalent and all of the elements outside across groups are not equivalent to each other.
• So, the groups of equivalent elements that we formed through an equivalence relation are called equivalence classes.
• So, this might look a little abstract now, but equivalence classes really represent a kind of equality and sometimes we are happy to work with this equality in terms of equivalence relations rather than actual equality and it has very much the same properties as equality does.

Summary

So, to summarize as we have seen a Cartesian product can generate n-tuples of elements from n sets. So, if we haveX1
, X2 , up to Xn , n sets these can be different or the same, then we can take one element from each set and form an n-tuple x1
, x2 , up to x n . And, when we now pick out some particular subset of these n-tuples, we get a relation. So, for instance, if we take pairs from N × R and we want the second element of the pair the real number to be the square root of the first element, then we get N × R such that r = √m. So, here on the right we have seen we show one picture of this. So, there are some elements like (2, √2 ), (4 , 2) , (7, √7) and so on. Now, just notice that in this picture the y-axis is elongated compared to the x-axis. So, this is not in some sense to scale in both dimensions because the square root function behaves like this. So, we have seen that there are some properties that we would like to record of binary relations – reflexivity, symmetry, transitivity and sometimes anti-symmetry. And, using reflexivity, symmetry and transitivity together we get what is called an equivalence relation,an equivalence relations partition sets into equivalence classes which behave like equality.