Definition 1.1. Any subset of A × B is called a relation between A and B.

Any subset of A × A is called a relation on A.

In other words, if A is a set, any set of ordered pairs with components in A is a relation on A. Since a relation R on A is a subset of A × A, it is an element of the powerset of A × A, i.e. R ⊆ P(A × A). If R is a relation on A and 〈x,y〉 ∈ R,  then we also write xRy, read as “x is in R-relation to y”, or simply, x is in relation to y, if R is understood.

Example 1.1 Let A = {2, 4, 6, 8}, and define the relation R on A by hx,yi ∈ R iff x divides y. Then,

Observe that each number is a divisor of itself.

2. Let A = N, and define R ⊆ A × A by

                  xRy iff x and y have the same remainder when divided by 3.

Since A is infinite, we cannot explicitly list all elements of R; but, for example

Observe, that xRx for x ∈ N and, whenever xRy then also yRx.

3. Let A = R, and define the relation R on R by xRy iff y = x² . Then R consists of all points on the parabola y = x².

4. Let A = R, and define R on R by xRy iff x · y = 1. Then R consists of all pairs 〈x, 1/x〉, where x is non-zero real number.

5. Let A = {1, 2, 3}, and define R on A by xRy iff x + y = 7. Since the sum of two elements of A is at most 6, we see that xRy for no two elements of A; hence, R = ∅.

For small sets we can use a pictorial representation of a relation R on A: Sketch two copies of A and, if xRy then draw an arrow from the x in the left sketch to the y in the right sketch.

Let A = {a, b,c, d,e}, and consider the relation

(1.1)

An arrow representation of R is given in Fig. 1.1

We observe that e does not appear at all in the elements of R, and that, for example,  b is not the first component of any pair in R. In order to give names to the sets of those elements of A which are involved in R, we make the following

Definition 1.2. Let R be a relation on A. Then,

                        dom R = {x ∈ A : There exists some y ∈ A such that 〈x,y〉 ∈ R}.

dom R is called the domain of R.

                  ran R = {y ∈ A : There exists some x ∈ A such that 〈x,y〉 ∈ R}

is called the range of R.

Finally, fld R = dom R ∪ ran R is called the field of R. Observe that dom R,  ran R, and fld R are all subsets of A.

Example 1.2. Let A and R be as in (1.1); then

               dom R = {a,c, d}, ran R = {a, b,c, d}, fld R = {a,b, c, d}.

2. Let A = R, and define R by xRy iff y = x² ; then,

                   dom R = R, ran R = {y ∈ R : y > 0}, fld R = R.

3. Let A = {1, 2, 3, 4, 5, 6}, and define R by xRy iff and x divides y;

R = {(1, 2),(1, 3), .. . ,(1, 6),(2, 4),(2, 6),(3, 6)},

and

dom R = {1, 2, 3}, ran R = {2, 3, 4, 5, 6}, fld R = A.

4. Let A = R, and R be defined as 〈x,y〉 ∈ R iff x²+y² = 1. Then 〈x,y〉 ∈ R iff hx,yi is on the unit circle with centre at the origin. So, dom R = ran R =

Definition 1.3. Let R be a relation on A; then R˘ = {〈y, x 〉: 〈x,y〉 ∈ R} is called the converse of R.

We obtain the converse R˘ of R if we turn around all the ordered pairs of R;  if we have a pictorial representation of R, this means that all existing arrows are reversed.

In our next definition we combine two relations to form a third one:

Definition 1.4. Let R and S be relations on A; then R ◦ S = {〈x,z〉: there is a y ∈ A such that xRy and ySz}. The operation ◦ is called the composition or the relative product of R and S.

Example 1.3.

1. Suppose that we have a pictorial representation of the relations R and S. The relation R ◦ S is the set of all pairs 〈x,z〉  such that x is in the left copy of A,z is in the right copy, and there is an arrow from x to z via an element in the centre copy of A.

2. Let A = N and R defined by xRy iff x + 1 = y, S defined by ySz iff z = 2y. Then 〈x,z〉: ∈ R ◦ S iff z = 2(x + 1):  

   〈x,z〉: ∈ R ◦ S ⇐⇒ There is some y ∈ A with xRySz

   ⇐⇒ y = x + 1 and z = 2y,

       ⇐⇒ z = 2(x + 1).

3. Let R be any relation on A; then

R◦R˘ = {〈x,z〉:: x,z ∈ dom R and there is some y ∈ ran R with xRy and zRy} :

Note that on both sides of = we have a set, so, we have to show that two sets are equal.

Proof. “⊆”: Let hx,zi ∈ R ◦ R˘; then there exists some y ∈ A such that xRyR˘z, i.e. 〈x,y〉 ∈ R and 〈 y, z 〉 ∈ R˘. Since 〈x,y〉, we have

x ∈ dom R, and since 〈 y, z 〉 ∈ R˘, we have (z, y) ∈ R; hence z ∈ dom R.

Furthermore, y ∈ ran R, as well as xRy and zRy.

“⊇”: Let 〈x,y〉 ∈ R and (z,y) ∈ R; then, 〈 y, z 〉 ∈ R˘, and thus, xRyR˘z,  i.e. 〈x,y〉 ∈ R and 〈 y, z 〉 ∈ R˘.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم التطوير يقيم دورة عن أخلاقيات المهنة للمنتسبين الجدد

تتضمن زيارة المراقد المقدسة في كربلاء.. معهد القرآن الكريم النسوي ينظم سفرة دينية لطالباته

المجمع العلمي يحتفي بذكرى ولادة الإمامين الباقر والهادي (عليهما السلام)

قسم الشؤون الفكرية يطلق فعاليات الأسبوع الثالث من برنامج البذرة الصالحة

المزيد

الآخبار الصحية

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

الآخبار التكنلوجية

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

مواضيع ذات صلة

Subset

Set Class

Set

Second Category

Proper Subset

Power Set

Matroid

Inductive Set

Independent Vertex Set

Independent Set

Graphoid

G_delta Set