Cartesian Product:
Definition: The Cartesian product of two sets A and B, denoted A × B, is the set
of all ordered pairs (a, b) where a is an element of A and b is an element of B.
Cartesian product is the product of any two sets, but this product is actually
ordered i.e, the resultant set contains all possible and ordered pairs such that the
first element of the pair belongs to the first set and the second element belongs
to the second set. The cartesian product of two or more sets is the set of all
ordered pairs/n-tuples of the sets. It is most commonly implemented in set
theory. In addition to this, many real-life objects can be represented by using
cartesian products such as a deck of cards, chess boards, computer images, etc.
Most of the digital images displayed by computers are represented as pixels
which are graphical representations of cartesian products.
Example:
Let A = {1, 2} and B = {x, y}
Then, A × B = {(1, x), (1, y), (2, x), (2, y)}
Cartesian Product of Sets
When two sets have items in them, A and B, their Cartesian product is all the
pairs you can make. Onepart of the pair comes from set A. Theother part
comes from set B. Wemake every possiblepair this way. The result is a new set
of all these pairs. We writethis new set as A×B.
A × B = {(a, b) : a ∈ A and b ∈ B}
Example:
Let A = {1, 2} and B = {4, 5, 6}
A × B = {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6)}
Here the first component of every ordered pair is from set A the second
component is from set B.
Cartesian Product of two sets can be easily represented in the form of a matrix
where both sets are on either axis
Symmetric Relation:
A symmetric relation between two or more elements of set-in discrete
mathematics is one in which if the first element is connected to the second
element, the second element is also related to the first element as described by
the relation. The relationship between any two items of the set is symmetric, as
the term ‘symmetric relations’ implies. A binary relation is a symmetric
relation.
Example: Let A = {1, 2, 3, 4} Define relation R on A as "is equal to or differs
by 1"
R = {(1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3), (3,4), (4,3), (4,4)}
This relation is symmetric because:
● If (1,2) is in R, (2,1) is also in R
● If (2,3) is in R, (3,2) is also in R
● If (3,4) is in R, (4,3) is also in R
● All pairs (a,a) are included for symmetry with themselves
Equivalence Relation:
Definition: An equivalence relation is a relationship on a set, generally denoted
by
“∼”, that is reflexive, symmetric, and transitive for everything in the set.
1. (Reflexivity) a ∼ a,
2. (Symmetry) if a ∼ b then b ∼ a,
3. (Transitivity) if a ∼ b and b ∼ c then a ∼ c.
Equivalence relations are often used to group together objects that are similar,
or “equivalent”, in some sense..
Example1: The relation “is equal to”, denoted “=”, is an equivalence relation on
the set of
real numbers since for any x, y, z ∈ R:
1. (Reflexivity) x = x,
2. (Symmetry) if x = y then y = x,
3. (Transitivity) if x = y and y = z then x = z.
All of these are true.
Example2: Let A be the set of all integers. Define relation R on A as "has the
same remainder when divided by 3"
This is an equivalence relation because:
1. Reflexive: Every number has the same remainder as itself when divided
by 3
2. Symmetric: If a has the same remainder as b when divided by 3, then b
has the same remainder as a
3. Transitive: If a and b have the same remainder, and b and c have the same
remainder, then a and c must have the same remainder
This relation partitions the integers into three equivalence classes:
● Numbers with remainder 0: {..., -3, 0, 3, 6, ...}
● Numbers with remainder 1: {..., -2, 1, 4, 7, ...}
● Numbers with remainder 2: {..., -1, 2, 5, 8, ...}
Properties of equivalence relations:
❖ Each equivalence relation partitions the underlying set into disjoint
equivalence classes
❖ Two elements are equivalent if and only if they belong to the same
equivalence class
❖ Every element in A belongs to one and only one equivalence class
❖ An element in an equivalence class can be used to represent that
equivalence class
