Skip to content

Introduction ​

Definition

Let A and B be sets. A binary relation from A to B is a subset of A×B

INFO

We use the notation aRb to denote that (a,b)∈R and aR̸b to denote that (a,b)∉R. Moreover, when (a, b) belongs to R, a is said to be related to b by R.

  • Relations are a generalization of graphs of functions

Relations on a Set ​

Definition
  • A relation on a set A is a relation from A to A.
  • In other words, a relation on a set A is a subset of A×A.

Properties of Relations ​

Reflexive ​

Definition

A relation R on a set A is called reflexive if (a,a)∈R for every element a∈A.

Remark

Using Quantifier, we see that the relation R on the set A is reflexive if

∀a((a,a)∈R)

where the universe of discourse is the set of all elements in A.

  • Example:
    • Relation R on set A={1,2,3,4}
    • R={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)} is reflexive, but
    • R={(1,1),(1,2),(1,4)} isn't relexive

Symmetric ​

Definition

A relation R on a set A is called symmetric if (b,a)∈R whenever (a,b)∈R, for all a, b∈A.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

∀a∀b((a,b)∈R→(b,a)∈R).
  • Example:
    • Relation R on set A={1,2}
    • R={(1,2),(2,1)} is symmetric,

Antisymmetric ​

Definition

A relation R on a set A is called antisymmetric if (a,b)∈R and (b,a)∈R, then a=b, for all a, b∈A.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

∀a∀b((a,b)∈R∧(b,a)∈R→(a=b)
  • Example:
    • Relation R on set A={1,2}
    • R={(1,1),(1,2)} is antisymmetric

Transitive ​

Definition

A relation R on a set A is called transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c)∈R, for all a,b,c∈A.

Remark

Using Quantifier, we see that the relation R on the set A is symmetric if

∀a∀b∀c((a,b)∈R∧(b,c)∈R→(a,c)∈R)
  • Example:
    • Relation R on set A={1,2,3}
    • R={(1,3),(3,2),(1,2)} is transitive

Combining Relations ​

TIP

Two relations from A to B can be combined in any way two sets can be combined

Composite definition

  • Given two relations R and S from A to B:

    • R: relation from A→B
    • S: relation from B→C
  • Composite S∘R is relation from A→C including (a,c) that there exists an element b∈B such that:

(a,b)∈R and (b,c)∈S
  • Example: image.png

The powers of a relation R ​

INFO

Let R be a relation on the set A. The powers Rn, n = 1, 2, 3, ..., are recursively defined by

BASIS STEP:

R1=R

RECURSIVE STEP:

Rn+1=Rn∘R

Theorem 1 ​

INFO

The relation R on a set A is transitive if and only if Rn⊆R for n = 1, 2, 3, ...

Inverse relation of R ​

INFO

Let R−1 be a reverse of relation R:

R−1={(b,a)|(a,b)∈R}

Complementary relation of R ​

INFO

Let R― be a complement of relation R:

R―={(a,b)|(a,b)∉R}

Representing relations ​

Using Matrices ​

  • The relation R can be represented by the matrix MR=[mij], where

INFO

mij={1if (ai,bj)∈R0if (ai,bj)∉R

Relfexive relations ​

  • The relation R is self-reflexive if mii=1 for all i∈R.

TIP

[11...1]

Off diagonal elements can be 0 or 1

Symmetric relations ​

  • The relation R is symmetric if mij=mji for all i,j∈R.

TIP

MR=(MR)t

image.png

Antisymmetric relations ​

  • The relation R is antisymmetric if mij=0∨mji=0 when i≠j.

image.png

Using Digraphs ​

Built with ❤️ and curiosity