Partial Order Relation

DEFINITION1: Let  X be a set and  R\subset{X\times{X}}. If the relation  R is reflexive, antisymmetric and transitive, then the relation  R is called a "partial order relation" and denoted by  R=\le in general. If " \le" is a partial order relation over a set  X, then  (X,\le) is called "partially ordered set" or shortly "poset".

DEFINITION2: Let  x and  y are elements of a partially ordered set  X. If it holds “ x\le{y}\lor{y\le{x}}”, then  x and  y are called “comparable”. Otherwise they are called “incomparable”.

DEFINITION3: If  x and  y are comparable for all  x,y in a partially ordered set  (X,\le), then the relation  \le is called a “total order” and the set  X is called a “totally ordered set” or “linearly ordered set”.

DEFINITION4: Let  (X,\le) be a partially ordered set and  A\subset{X}. If  (A,\le) is a totally ordered set, then  A is called a “chain” in  X.

DEFINITION5: Let  (X,\le) be a partially ordered set and  A\subset{X}. If there exists an element  a^{*}\in{A} satisfying  a\le{a^{*}} for all  a\in{A}, then  a^{*} is called the maximum of  A, and if there exists an element  a_{*}\in{A} satisfying  a_{*}\le{a} for all  a\in{A}, then  a_{*} is called the minimum of  A. The minimum and the maximum of  A are denoted by  \min{A} and  \max{A} respectively.

» Read more

Relation

DEFINITION1: Let  X and  Y be two sets. Any subset of the cartesian product  X\times{Y} is called a relation with domain  X and codomain  Y. While some sources are giving the definition of relation, they assume  X,Y\ne{\varnothing} and it’s said the emptyset being a subset of  X\times{Y} isn’t a relation. However, the assumption “the emptyset is a relation” is not a problem for any branch of the mathematics. On the contrary, the assumption “the emptyset is a relation” plays an important role in some branch of the mathematics.

If  X and  Y are two sets with  n and  m elements respectively, then the cartesian product  X\times{Y} has  n.m elements. Since a relation with domain  X and codomain  Y is an element of the power set  \mathbf{P}(X\times Y) and the number of the elements of the power set of a set with  k elements is  2^{k}, then the number of all the relations with domain  X and codomain  Y is  2^{n.m}. If  X,Y\ne{\varnothing} and at least one of  X and  Y is infinite set, then the number of all the relations with domain  X and codomain  Y is also infinity.

Let  R\subset{X\times{Y}} be a relation not being the emptyset. The statement  (x,y)\in{R} is read “x is R-related to y” and is denoted by  xRy or  R(x)=y.

EXAMPLE1: Let  X=\{a,b,c\} and  Y=\{1,2\}. Since  X has 3 elements and  Y has 2 elements, the number of all the relations with domain  X and codomain  Y is  2^{2.3}=2^{6}=64. We can give some of these  64 relations:

 R_1=\varnothing,

» Read more