Relations

• Definition 1 from page 355 relation from one set A to another set B is a subset of A X B
  • Functions are special types of relations
  • Various examples of relations
• Definition 2: Relation on a set A is a subset of A X A
• Properties
• reflexive, transitive, symmetric, and antisymmetric
• A relation can be symmetric and antisymmetric at the same time
• Combining relations. Since the relations are sets we can use all the set theoretic operators. Example 17 and 18 covers all the important operators.
• Composites: Definition 6. As a special case A=B=C.
• Definition 7. Power of a relation. Be areful with the order of relations during the operation
• Theorem 1. Two way implication needs proof for both directions of implication.

Representation of Relations

• Matrix representation bottom of page 373 and 374 explain how to represent a relation using a matrix
• You should be able two write down a relation given the matrix rep. and vice versa
• A relation R on A
• If all the diagonal elements are 1, then the relation is reflexive.
• If the transpose of M_R is equal to M_R then R is symmetric
• If M_R has only diagonal elements equal to 1 and all other elements are 0. Then the relation is reflexive, symmetric, antisymmetric, transitive
• Operations: boolean operations on the matrix correspond to the set theoretic operations on the relation
  • intersection = and
  • union = or
  • composition = boolean product
• verified with an example
• Page 156 and 157 describe the boolean operations on the matrices
• Directed graphs can be used to represent relations as well
• Definition of digraphs definition 1 on page 377.
• The set of edges is clearly a relation because E is a subset of VXV
• Digraphs make it easier to study properties of relations

Equivalence Relations

• Definition of an equivalence relation
  • if a relation is reflexive, symmetric and transitive, then it is called an equivalence relation
• Theorem 1: If we prove that (i) implies (ii), (ii) implies (iii) and (iii) implies (i), we would have proven that (i), (ii) and (iii) are equivalent. why? transitivity of the implication relation.
• not (iii) is equivalent to not (ii)
• Union of al equivalence classes is equal to A
• The equivalence classes [a] and [b] are either equal or disjoint (follows from theorem 1)
• An equivalence relation R partitions A into one or more disjoint subsets. Each one of these disjoints subsets is an equivalence class [a] for at least one a in A
• Similarly, given a partition of A, we can construct an equivalence relation R. aRb if and only if a and b are in the same disjoint subset in the partition.
• Researchers have used equivalence classes in data mining.
• Data mining is a field in Artificial Intelligence that tries to discover previously unknown and potentially useful information from a database.
• Let us say we have a set of patients with a wide variety of symptoms and their diagnosis is also known.
• We can create an equivalence relation such that the patient has same symptoms. The resulting partition is used to approximately describe a set of patients with a give disease. That means we can describe each disease approximately in terms of the symptoms.