Relations and Their Properties

• Relationships between elements of sets are represented using the structure called a relation
• Relation - is just a subset of the Cartesian product of the sets.
• Relation - is the representation of the relationship between the elements of the set
• Binary relation - is a set of ordered pairs. It may exist between the objects in a same set, or between objects in a different set.
• A binary relation from A to B is a subset of A × B.
• Domain(x) – Set of all first members in a relation
• Range(y) – Set of all second members in a relation
• A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A. In this type of relation, the element in a pair is related to itself
• Irreflexive - The opposite of Reflexive. The element is not related to itself.
• Symmetric - A relation R on a set A if ∀a ∀b [(a,b) € R -> (b,a) € R]. It means that if a is related to b, then the a is also related to b. There is a relationship between each other
• Asymmetric - The opposite of symmetric. A relation R on a set A is called asymmetric if ∀a ∀b [(a,b) € R -> (b,a) R].
• Antisymmetric - A relation R on a set A is called antisymmetric if ∀a∀b [((a,b) € R & (b,a) € R) -> (a=b)].
• Transitive - 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.
• Order of Relations - a type of relation that deals with comparison between objects.
• Partial Order - A relation R on a set A is called a partial order relation if it satisfies the following three properties: (1) Reflexive, (2) Antisymmetric, and (3) Transitive
• Poset - The ordered pair (A, R) is called a partially ordered set when R is a partial order
• Maximal element – element that is greater than or equal to every element to which it is comparable. (There may be many elements to which it is not comparable.)
• Greatest element – element that is greater than or equal to every element in the set
• Total Order (or Linear Order) – When all the elements of a partial order relation are Comparable. The “less than or equal to” relation on real numbers is a total order relation.
• A binary relation R on a set A is a total order if and only if it is

  (1) a partial order, and

  (2) for any pair of elements a and b of A, (a,b) R or (b,a) R.