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

اخر الاخبار

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

مجلة تسليم تدعو الباحثين والأكاديميين للمشاركة في أعدادها القادمة

المجمع العلمي يواصل إقامة محاضراته الأسبوعية في مقام الإمام المهدي (عجل الله فرجه)

جامعة الكفيل تطلق الدورة التدريبية الصيفية لطلبة كلية الهندسة التقنية

استعدادًا لزيارة الأربعين العتبة العباسية المقدسة تعقد الورشة التنسيقية الرابعة الخاصة بمراكز إرشاد التائهين

المزيد

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

دراسة علمية تكشف مفاجأة حول الأسباب الحقيقية للسمنة

دراسة: الأطباء يتجاهلون "سببا شائعا" لارتفاع ضغط الدم

نظامك الغذائي غني بالبروتين؟.. احذر هذه الآثار الجانبية

لا تتجاهلها.. أعراض تنذرك بأنك مهدد بالإصابة بالسكري

المزيد

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

ISOFIX: معيار الأمان الذهبي لمقاعد الأطفال في السيارات

هل المحرك الأكبر دائمًا الأفضل للسيارة؟

اختبارات ناجحة لمحرك "VK-800" الروسي وتطويره لطائرة بايكال الخفيفة

رئيس إنفيديا: الذكاء الاصطناعي الصيني "محفز للتقدم العالمي"

المزيد

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

Subset

Set Class

Set

Second Category

Proper Subset

Power Set

Matroid

Inductive Set

Independent Vertex Set

Independent Set

Graphoid

G_delta Set