Discrete Mathematics Relations - Discrete Mathematics

What are Discrete Mathematics Relations?

The relation between the elements of the set is very important topic. The relations might be between the objects of the same set or between the objects of two or more sets.

What is the definition of Relation in Discrete Mathematics?

A binary relation R from set x to y (written as xRy or R(x,y)) is a subset of the Cartesian product x×y. If the ordered pair of G is reversed, the relation also changes.

Generally an n-ary relation R between sets A1,…, and An is a subset of the n-ary product A1×⋯×An. The minimum cardinality of a relation R is Zero and maximum is n2 in this case.

A binary relation R on a single set A is a subset of A×A.

In case of two distinct sets A and B, with cardinalities m and n, the maximum cardinality of the relation R from A to B is mn.

What is Domain and Range?

If there are two sets A and B, and relation R have order pair (x, y), then −

  • The domain of R, Dom(R), is the set {x|(x,y)∈RforsomeyinB}
  • The range of R, Ran(R), is the set {y|(x,y)∈RforsomexinA}

Examples

Let, A={1,2,9} and B={1,3,7}

  • Case 1 − If relation R is 'equal to' then R={(1,1),(3,3)}

Dom(R) = {1,3},Ran(R)={1,3}

  • Case 2 − If relation R is 'less than' then R={(1,3),(1,7),(2,3),(2,7)}

Dom(R) = {1,2},Ran(R)={3,7}

  • Case 3 − If relation R is 'greater than' then R={(2,1),(9,1),(9,3),(9,7)}

Dom(R) = {2,9},Ran(R)={1,3,7}

How the relations are represented using Graphs?

Graphs can be used for representing Relations.

The number of elements of the set is represented by the number of vertices of the graph, defined by the relation. In relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’, for each of the ordered pair (x, y). For the ordered pair (x, x), there will be self- loop on vertex ‘x’.

For instance, there is a relation, R={(1,1),(1,2),(3,2)} on set S={1,2,3}, then it can be represented by the following graph −

Relation

What are the different types of Relations in Discrete Mathematics?

  • The Empty Relation between sets X and Y, or on E, is the empty set ∅
  • The Full Relation between sets X and Y is the set X×Y
  • The Identity Relation on set X is the set {(x,x)|x∈X}
  • The Inverse Relation R' of a relation R is defined as − R′={(b,a)|(a,b)∈R}.

Example − If R={(1,2),(2,3)} then R′R′ will be {(2,1),(3,2)}.

  • A relation R on set A is called Reflexive if ∀a∈A is related to a (aRa holds)

Example − The relation R={(a,a),(b,b)} on set X={a,b} is reflexive.

  • A relation R on set A is called Irreflexive if no a∈A is related to a (aRa does not hold).

Example − The relation R={(a,b),(b,a)} on set X={a,b} is irreflexive.

  • A relation R on set A is called Symmetric if xRy implies yRx, ∀x∈Aand ∀y∈A.

Example − The relation R={(1,2),(2,1),(3,2),(2,3)} on set A={1,2,3} is symmetric.

  • A relation R on set A is called Anti-Symmetric if xRy and yRx implies x=y∀x∈A and ∀y∈A.

Example − The relation R={(x,y)→N|x≤y} is anti-symmetric since x≤y and y≤x implies x=y.

  • A relation R on set A is called Transitive if xRy and yRz implies xRz,∀x,y,z∈A.

Example − The relation R={(1,2),(2,3),(1,3)} on set A={1,2,3} is transitive.

  • A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive.

Example − The relation R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)} on set A={1,2,3}is an equivalence relation since it is reflexive, symmetric, and transitive.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics