Sets

Relation

Keywords: relations, reflexivity, symmetry, transitivity, anti-symmetry, equivalence, partial order:, dichotomy, order

Definition

A2=A×A=a,b:aA, bA
ρA2

The relation ρ is a set of ordered pairs, a subset of an Cartesian squere AxA.

Example:

A=1,3,6
AxA=1,1,1,3,1,6,3,1,3,3,3,6,6,1,6,3,6,6
ρ={1,1,1,3,1,6,3,3,3,6,6,6} | ρA2,


The relation ρ in this case means (less or equal): (1≤1), (1≤3), (1≤6), (3≤3), (3≤6), (6≤6).

Properties of Relations

Reflexivity

(aA): aρa

IN CASE OF ORDERED GRAPH: every vertex of graph hase loop.

Example:ρ is reflexiv, because for every element of  A is true: 11,33,66

Symmetry

(a, bA): aρbbρa

IN CASE OF ORDERED GRAPH: every edge of the graph is two sided.

Example:ρ is not symmetric, because if 3 ≤ 6 [or (3, 6) ∈ ρ], does not follow that 6 ≤ 3 [or (6, 3) ∈ ρ].

Transitivity

(a, b,cA): aρbbρcaρc

IN CASE OF ORDERED GRAPH: if there is a path between two vertices, there is a longer path too between them.

Example:ρ is transitiv, because if 1 ≤ 3 and 3 ≤ 6 means 1 ≤ 6.

Anti-symmetry

(a, bA): aρbbρa

IN CASE OF ORDERED GRAPH: there is 0 or 1 edge between any of two different vertecies.

Example:ρ is ant-symmetric, because each number is less than or equal to itself.

Types of Relations

  • Equivalence Relations: reflexive, symmetric and transitivev
  • Partial order: reflexive, anti-symmetric and transitivevv
  • Dichotomy: for every a, b ∈ A,  (a, b) ∈ ρ or (b, a) ∈ ρ
    IN CASE OF ORDERED GRAPH: there is a path between any two points of the graph.
  • Order:, partial order and dichotomy