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˘.

اخر الاخبار

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

قسم الشؤون الفكرية يطلق باقة من النشاطات الرقمية الخاصة بشهر المحرم

العتبة العباسية المقدسة تختتم السلسلة الأولى لمشروع المحاضرات القرآنية العاشورائية في بابل

العتبة العباسية المقدسة تسلّم راية العزاء إلى تجمّع مواكب محافظة الديوانية

قسم الشؤون الفكرية يواصل إقامة المجالس الحسينية ضمن سلسلة (بيوت النعيم)

المزيد

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

لكبح الجوع وخسارة الوزن.. "سر بسيط" في نظام جوكوفيتش ؟

هل يساعد الرجيم في علاج الأمراض العقلية؟

لحماية أسنان طفلك.. هذا الفيتامين يقلل خطر التسوس

أكل الطعام بسرعة.. طريق سريع إلى أمراض خطيرة

المزيد

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

ما هي أفضل درجة حرارة لتكييف الهواء في السيارة؟

ذوبان الأنهار الجليدية يوقظ "عمالقة نائمة"!

9 يوليو يشهد أقصر يوم في التاريخ المسجل ؟!!

راتبه عشرات ملايين الدولارات.. زوكربرغ يخطف "عقل أبل"

المزيد

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

Subset

Set Class

Set

Second Category

Proper Subset

Power Set

Matroid

Inductive Set

Independent Vertex Set

Independent Set

Graphoid

G_delta Set