Relations
If we have two sets, A and B, we can refer to the 'Cartesian Product' as being A x B. This means that if A = {1, 2, 3} and B = {a, b, c}, then A x B = {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c}. It's the set of all pairs of values where the first is from A and the second is from B.
A relation from A to B is a subset of A x B. A relation can be said to connect values together, in a way, showing a relationship between them.
As an example, lets take two sets. A = {0, 1, 2} and B = {0, 1, 2}. Because the two sets are the same, we can say that this is a relation on A. Now consider the relation that is described by 'is greater than'. We can start by looking at A x B, which is {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)(2,0)(2,1)(2,2)}. Now the relation R has to be a subset of this. One way to work out what the relation is is to look at each value in turn. So we look at the first value - (0,0). The first value is 0 and the second value is 0, so the relation we have is '0 is greater than 0'. This is not true, so (0,0) is not part of the relation.
The same is true of (0,1) which says '0 is greater than 1', and (0,2) which says '0 is greater than 2'. But when we get up to (1,0) we see that yes, '1 is greater than 0', and that value is in the relation.
In the end we find out that the relation is {(1,0),(2,0),(2,1)} which is a subset of A x B. We can show this as a digraph as follows, where we say 'a and b are related by R if there is an arrow going from a to b'.
- Relation Digraph 1
If a is related to b by relation R, we can also say aRb. So in this case, 1R0, 2R1, and 2R0.
Reflexive, Transitive, Symmetric, Antisymmetric
There are a number of different properties that a relation can have. Let R be a subset of A x A.
R can be said to be reflexive if it is true that for every possible value of 'a' where 'a' is in 'A', it is true that aRa. This means that everything maps onto itself. On a digraph, this can be shown by the fact that every node should have a loop attached to it that points it back on itself. An example of a relation of this type could be 'is the same height as' - Everything is the same height as itself, but it can still be the same height as other things. The key feature, though, is that aRa is always true.
R can be said to be transitive if it is true that for every possible value of a, b, and c, where they are all in A, if aRb is true and bRc is true then it must be the case that aRc is true. An example of this kind of relation is 'is smaller than'. If we have an object a that is smaller than b, and an object b that is smaller than c, then obviously object a must be smaller than object c. This is hard to spot on a digraph, but basically whenever there is an arrow from a to b and an arrow from b to c then there is also an arrow from a to c.
R can be said to be symmetric if all relations work backwards. For example if you have two nodes in your relation, a and b, and it's true that aRb, then for the relation to be symmetric then it must also be true that bRa. 'is the same height as' is a good example of a symmetric relation - If a is the same height as b, then obviously b is the same height as a, and this is true for all objects. On a digraph, this can be shown by the fact that wherever there is an arrow between two nodes, there has to be another one going in the opposite direction.
R can be said to be antisymmetric if it is true that for all a and b in A, if aRb and bRa then a must equal b. ie. if the only relations that work in reverse are between two same nodes.
Equivalence
An equivalence relation is a relation which is reflexive, symmetric, and transitive. To show this we look at the three features and show this:
- Reflexive: a is equivalent to a. This is true.
- Symmetric: If a is equivalent to b, then b is equivalent to a. This is true.
- Transitive: If a is equivalent to b and b is equivalent to c, then a must be equivalent to c. This is true.
The idea of an equivalence relation is that if aRb then a and b are in some sense the same. This will usually divide set A into seperate 'parts'. The idea is that each part contains elements that are equivalent to each other, so a and b are only in the same part if aRb.
So lets assume A is the set of all natural numbers, and R is the relation that states that 'a - b is equal to 0 (mod 2)'. 0R0 is true, 0R1 is not, 0R2 is true, 0R3 is not, etc. 1R0 is not, 1R1 is true, 1R2 is not, 1R3 is true, etc. The digraph for this will look like this:
- Relation Digraph 2
So we can see that if we continued, there would be a partition between the odd numbers and the even numbers. The odd numbers are equivalent in this relation, and the even numbers are equivalent in this relation. We say that it is divided into two R-equivalence classes.
We can talk about the R-equivalence class [a], which is the set of all nodes that are equivalent to a. So in this case, [0] = the set {0,2,4,6,8,10,...} and [1] = the set {1,3,5,7,9,11,...}. This way we can see that the set of all natural numbers, N, consists of all of the elements in each partition exactly once. N = [0]
[1].Similarly, we can say that the conjunction, [0]
[1] is always equal to the empty set, because there is no value in [0] that will also appear in [1].In fact, for any equivalence relation, the following is true:
- a belongs to the set [a]
- For all values of b and c in [a], bRc is true.
- For all values of a and b in A, either [a] is equal to [b], or [a]
- For all values of a and b in A, if [a] = [b] then aRb must be true. (ie. for any two values in the same set, aRb is true)
A partition is a set of subsets that make up a set. For example, the set {[0],[1]} is a partition that makes up the set N.
Operations on Relations
There are a number of operations possible on relations, as they are sets. Let R1 and R2 be relations on A:
The union of R1 and R2 is described as R1
R2, and this is the same as it is in set theory - it's every pair of things that is in either R1 or R2. For example, in a family, we can take the union of the relations 'is the mother of' and 'is the father of' to get the relation 'is the parent of'.The intersection of R1 and R2 is described as R1
R2, and this is the same as it is in set theory - it's every pair of things that is in both R1 and R2. For example, the intersections of the relations 'is the mother of' and 'is the father of' is empty, because nobody is both the mother and father of a child.The complement of R1 is described as Rc1, and is basically the set of all pairs that are in A x A but are not in R1. For example, the inverse of 'is the parent of' is 'is not the parent of'
The inverse of R1 is described as R-11, and is every pair backwards. For example, if 0R3 is a relation in R1, then 3R0 is true in R-11. For example, the inverse of 'is parent of' is 'is child of'.
Composition
If we consider the two relations 'is a parent of' and 'is the mother of', then we can define another relation 'is the grandmother of', by combining these by finding some value where a 'is the mother of' b and b 'is the parent of' c. Then a 'is the grandmother of' c.
In general, if we have two relations R1 from A to B and R2 from B to C, the relational composition of R1 and R2 can be described as R2 ∘ R1, which is a relation from A to C where there is some b in B where aR1b and bR2c.
Closure
For any relation, R, and property, P, we can say that the relation S is the P closure of R if S has property P, and if R' is another relation with property P and R is a subset of R' then S is a subset of R' as well.
For example, lets assume that P is the property of transitivity. The P closure of R is the 'transitive closure' of R. When P is reflexivity then it is known as the reflexive closure, and when P is symmetry it is known as the symmetric closure.
The P closure is constructed by adding to R the minimum number of pairs (a,b) which will make a new relation with property P.
For example, let us consider the relation consisting of (0,1), (0,2), (2,0), and (2,2).
The reflexive closure is the relation consisting of (0,0), (0,1), (0,2), (1,1), (2,0), and (2,2). All we've added are the minimum pairs that are required to make it reflexive - that is, (0,0) and (1,1). All the rest has been left alone.
The transitive closure is harder to find. But consider each pair of pairs in turn to see if there is a way to get straight to them.
(0,1), (0,2) - Not needed. 1 is not equal to 0.
(0,1), (2,0) - Not needed. 1 is not equal to 2.
(0,1), (2,2) - Not needed. 1 is not equal to 2.
(0,2), (0,1) - Not needed. 2 is not equal to 0.
(0,2), (2,0) - (0,0) is needed.
(0,2), (2,2) - (0,2) is needed, but is already there.
And so on. The transitive closure of this relation is (0,0), (0,1), (0,2), (2,0), (2,1), (2,2).
The symmetric closure is much easier, it's just the minimum pairs to ensure that every pair works backwards. In this case it is (0,1), (1,0), (0,2), (2,0), (2,2). We added (1,0).
Order Relations
Another common type of relation is the set of relations that share the properties of 'less than or equal to'. Such relations are called order relations.
The simplest kind of order relation is called the 'partial order', as follows:
A partial order is a relation R which is reflexive, antisymmetric, and transitive.
A partially ordered set, or 'poset', has an additional property. Namely that for any integers, x and y, then either x is less than or equal to y, or y is less than or equal to x (or both). We can say this as 'two integers are comparable with the relationship 'is less than or equal to''.
A partial order relation in which any two elements are comparable is called a total order.
Maximal and Minimal
Given an ordering of a set, we can define the maximal and minimal elements.
An element of a poset A with partial order ≪ is said to be a least element if, for all a, the element ≪ a.
An element of a poset A with partial order ≪ is said to be a greatest element if, for all a, a ≪ the element.
A minimal element for a partial order ≪ of a set A is any element a such that if b ≪ a then a = b.
A maximal element for a partial order ≪ of a set A is any element a such that if a ≪ b then a = b.
In more basic terms, a minimal element is one that can't have another element smaller than itself, and a maximal element is an element that can't have another element bigger than itself. That's not to say that the minimal element is the smallest and the maximal element is the biggest, because two elements may not be comparable in a partial order.
A partial order can have lots of minimal and maximal elements.
In general a poset A can be drawn with a partial order by placing 'larger' elements at the top and less 'large' elements further down. Draw the minimum number of lines so that if x is less than y then there is some sequence of lines descending from y to x. This is called a Hasse Diagram.
And that's basically all there is to know about relations. I recommend reading pages 62-66 of the notes on order relations and minimal and maximal elements and partial orders and stuff because they don't make a tiny bit of sense.
No comments:
Post a Comment