Ch. 2. Cartesian Product of Sets and Relations - Concepts Review

Contents

2.1 Cartesian product of sets
2.2 Relations
2.3 Types of relations
2.4 Some results on relations
2.5 Composition of relations



2.1 Cartesian product of sets

Cartesian product is an operation on sets.


Ordered pair: An Ordered pair consists of two objects or elements in a given fixed order.

Cartesian product: Let A and B be any two non empty sets. The set of all ordered pairs (a,b) such that a ЄA and b ЄB is called the Cartesian product of the sets A and B and is denoted by A×B

Theorems

Theorem 1; For any three sets

(i) A×(B U C) = (A×B) U (A×C)
(ii) A×(B∩C) = (A×B) ∩(A×C)

Theorem 2: For any three sets

A×(B – C) = (A×B) – (A×C)

Theorem 3: If and A and B are any two non-empty sets, then

A×B = B×A => A = B

Theorem 4: If A is a subset of B, A×A is a sub set of (A×B) ∩(B×A)


2.2 Relation

Let A and B be two sets. Then a relation R from A to B is a subset of A×B.

R is a relation from A to B => R is a subset of A×B.

Total number of relations: If A and B are two non empty sets with m and n elements respectively, A×B consists of mn ordered pairs.
Since each subset defines a relation from A to B, so total number of relations from A to B is 2^mn.


2.3 Types of relations


Void relation
Universal relation
Identity relation
Reflexive relation
Symmetric relation
Transitive relation
Antisymmetric relation
Equivalence relation

Cartesian Products of Sets and Relations - Part 2



2.4 Some more properties and results on relations

1. If R and S are two equivalence relations on a set A, then R∩S is also an equivalence relation on A.
2. The union of two equivalence relations on a set is not necessarily an equivalence relation on the set.
3. If R is an equivalence relation on a set A, the R^-1 is also an equivalence relation on A.


2.5 Composition of Relations

When r and S are two relations from set A to B and B to C respectively, we can define a relation SoR from A to C such that

(a.c) Є SoR imples for all b Є B subject to the relations (a,b) ЄR and (b.c) ЄS.

SoR is called the composition of R and S.

Properties of SoR

In general RoS is not equal to SoR.

(SoR) ^- = R^-oS^-