Relations and Equivalent Relations

Posted By on October 16, 2014


Download PDF
Importance of Algorithm Analysis
Linear Inequalitites and Linear Equations

Relation

A relation is any subset of a Cartesian product. For instance, a subset of A×B, called a “binary relation from A to B,” is a collection of ordered pairs (a,b) with first components from A and second components from B, and, in particular, a subset of A×A is called a “relation on A.” For a binary relation R, one often writes aRb to mean that (a,b) is in R×R

Equivalence Relation

An equivalence relation on a set X is a subset of X×X, i.e., a collection R of ordered pairs of elements of X, satisfying certain properties. Write “xRy” to mean (x,y) is an element of R, and we say “x is related to y,” then the properties are

1. Reflexive: aRa for all a in X,

2. Symmetric: aRb implies bRa for all a,b in X

3. Transitive: aRb and bRc imply aRc for all a,b,c in X,

where these three properties are completely independent. Other notations are often used to indicate a relation, e.g., a=b or a∼b

Importance of Algorithm Analysis
Linear Inequalitites and Linear Equations

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com