Content

Relation

The intuitive approach of set theory used in number theory can only help to get the idea of the properties of numbers in the set. Relation is another fundamental concept used in number theory to study the properties of number in an ordered set.

Ordered Set

In general, an ordered set is a set equipped with relations among elements which are arranged in an order such that the relation between two elements can be well defined. For example, ordered set {a, b}≠ordered set {b, a} in general

n-Tuple

n-tuple is a list or an ordered set of n elements. Sometimes n-tuple is also called ordered n-tuple. For example, (a1,a2,...,an) where a1 is the first element, a2 is the second element, and an is the nth element.

Therefore, two ordered n-tuples are equal if and only if two corresponding elements are equal. For example, (a1,a2,...,an) and (b1,b2,...,bn) are equal if and if ai=bi for i=1, 2,...,n.

Ordered Pair

An ordered pair is a set of a pair of objects equipped with an order between them, for example, {a,b}. In general , an ordered pair is a 2-tuple or a sequence of length 2. 

Cartesian Product

A Cartesian product is a mathematical operation. A Cartesian product of two sets, binary Cartesian product or Cartesian square, is the set of all ordered pairs from the corresponding elements of the two sets. For example, A⨯B={(a,b)|a∈A∧b∈B}.

Simiarly, the n-ary Cartesian product of the sets A1, A2, ..., An, is denoted by

A1⨯A2⨯...⨯An. And the Cartsian product is the set of ordered n-tuples (a1,a2,...,an) from the corresponding elements of the n ordered sets. For example, A1⨯A2⨯...⨯An={(a1,a2,...,an)|ai∈Ai for i=1, 2, ..., n}.

Some other arities are 1-ary for unary, 2-ary for binary, and 3-ary for ternary.

Relation

In general, a relation is a correspondence of an object with the others. A correspondence itself is the process of pairing objects according to some relationship such that any given objects either does or does not correspond. For example, an order pair of a relation or binary relation R between sets A and B is always an element of the Cartesian product AxB. The relation R can also be interpreted as a set of ordered pairs for which the relation is true and is therefore a subset of the Cartesian product AxB. If sets A and B are the same set C, the relation R on set C is also a subset of the Cartesian product CxC. 

Relation may also be of other arities. Similarly, an n-tuple of an n-ary relation R between sets A1, A2,..., and An is an element of the n-ary product A1⨯A2⨯...⨯An. The relation R can also be interpreted as a set of n-tuples for which the relation is true and is therefore a subset of the n-ary product A1⨯A2⨯...⨯An.

Binary Relation

For a binary relation R, an ordered pair can be considered as a point on a plane and the set of all ordered pairs of corresponding elements can then be considered as a graph on the plane. The set of all ordered pairs {a, b} according to relation R can be written as aRb if and only if {a,b}∈R for which a has the relation R to y, or a corresponds to b under R. For example, R={(a,b):(a,b)∈R}. The set of all first elements of the ordered pairs under relation R is called the domain of R. For example, dom R={a:(∃b)(a,b)∈R} The set of all second elements of the ordered pairs under relation R is called the range of R. For example, range R={b:(∃a)(a,b)∈R}.

The inverse, R-1, of a relation R is the set of ordered pairs obtained by reversing tle elements of the ordered pairs under relation R. For example, R-1={(a,b):(b,a)∈R}.

Typical Binary Relation

A relation R betwen set A and B or on C is empty if all ordered pairs under relation R do not correspond or are false. In other words, the set for an empty relation is an empty set ∅.

A relation R betwen set A and B or on C is full if all ordered pairs under relation R do correspond or are true. In other words, the set for a full relation or universal relation is the set AxB or CxC.

A relation R on C is an identity only if the first and second elements of all ordered pairs are identical under relation R do correspond or are true . In other words, the set for an identity relation on set C is the set {(c,c)|c∈C}.

Important Properties of Binary Relation

Some properties of a binary relation R over a set C with x, y, and z are elements of set C

• reflexive: for all x in C, if xRx. For example, =

• irreflexive: for all x and y in C, if xRy implies x≠y. For example, <

• symmetric: for all x and y in C, if xRy implies yRx. For example, =

• antisymmetric: for all x and y in C, if xRy and yRx implies x = y. For example, <

• transitive: for all x, y and z in C, if xRy and yRz implies xRz. For example, =

Equivalence Relation

An equivalence relation ~ on C is a binary relation which is reflexive (x ~ x for every x∈C), symmetric (x~y ⇒ y~x), and transitive (x ~ y and y ~ z ⇒ x ~ z). For example, =. The refexive, symmetric, and transitive properties of an equivalence relation can be used to partition a set C into disjoint equivalence classes. Let X be the set of elements c equivalent to x in C, X={c:c~x}. Let Y be the set of elements c equivalent to y in C, Y={c:c~y}. Let Z be the set of elements c equivalent to z in C, Z={c:c~z}. If x~y, then y~x. Since x∈X and y∈Y, therefore x∈Y and implies y∈X. If x~y and y~z, then x~z. Since z∈Z, therefore x∈Y and y∈Z and implies x∈Z. In other words, if y∈Z, then x∈Y⇒x∈Z, where x is a common element of sets Y and Z. Besides, if y∈Z, then Y⊂Z can be assumed. However by symmetry, if y∈Z, then z∈Y implies Z⊂Y can be assumed also. Thererfore if y∈Z, then Y=Z when there is a common element x in Y and Z. In other words, for any equivalence classes Y, Z, if there is a common element x, the two equivalence classes must be equal, otherwise sets Y and Z are disjoint. That is

• Each equivalence class contains a set of elements of set C. Since all elements are equivalent to each other, all elements in set C that equivalent to any element of the equivalence class are members of the equivalence class.

• Any element of an equivalence class may be used as a representative to stand for all the members of the equivalence class.

• The equivalence classes of a set C are disjoint. No element x∈C such that x is in more than one equivalence class.

• The equivalence classes exhaust E. No element x∈C such that x is in no equivalence class.

Order Relation

In general, an order relation is a relation that ranks the order of elements against one another. Two elements x and y are incomparable under the order relation R on set C where x, y∈C if neither xRy nor yRx. That is x||y or x#y. The order relation is a partial order if there is a pair of elements x,y in a set C for which neither xRy nor yRx is true. However if for every pair of element x,y in a set C for which either xRy or yRx is true,  the order is a total order. In other words, there is at least two elements are incomparable for a partial order relation while there is no two element are incomparable in a total order relation.

An order or partial order is a binary relation R on a set C which satisfies the reflexive, antisymmetric and transitive properties. This is a non-strict order. However, in everyday usage, orders are usually with the irreflexive property. When an order is irreflexive and transitive, the order is also antisymetric trivally because xRy and yRx is always false. This order is call a strict order.

Relation Operation

A relation can also be produced by relation operation. Let R be a relation from X to Y and S be a relation from Y to Z.

• Composition or Join:  The composition of two relations R and S, R∘ S is the relation T={(x,z)∈XxZ|xRy and ySz for some y∈Y}. Transitivity is a property of a single relation related to a common element, while composition set is an operation on two relations related to a common element for producing a new relation of a new set of pairs which may or may not be transitive.

• Product: The product of two relations R and S is the relation T={(w,x,y,z)|wRx∧yRz}.

• Converse or Transpose: The converse of a relation R, R-1 is the relation T={(y,x)|xRy}. Symmetry is a propety of a single relation related to the same two elements while converse set is an operation on a relation by swapping the order of pairs for producing  a new relation of a new set of pairs which may or may not be symmetric. In other words, the union of a relation with its converse is a symmetric relation.

• Closure: The closure of a relation R is the relation that {(x,z)|(x,y)∈R∧(y,z)∈R}

• Transitive Closure: The transitive closure of R is the

• Intersection: The intersection of two relations R and S, RS is the relation T={x(RS)y|xRy and xSy}.

• Union: The union of two relations R and S, R∪S is the relation T={x(R∪S)y|xRy or xSy}.

• Difference: The difference of two relations R and S, R−S or R \ S, is the relation T={x(R−S)y|xRy but not xSy}.

Relation on Relations

Let C be a set, and relations R and S be relations on C. Since relations are sets, the relations on relations can be.

• two sets of relastions R and S are equal if for every x,y∈E, xRy iff xSy.

• The set of relation R is a subset of the set of relation S if for every x,y∈E, xRy implies xSy.