Binary Relations in Discrete Mathematics: Defining Relationships Between Sets

Explore binary relations in discrete mathematics, defining relationships between elements of sets. This guide explains how to represent relations using ordered pairs, discusses properties of relations (reflexive, symmetric, transitive), and provides examples.

Binary Relations in Discrete Mathematics

What is a Binary Relation?

A binary relation R between two non-empty sets P and Q is simply a set of ordered pairs (a, b), where a is from P and b is from Q. If the pair (a, b) is in R, we say that 'a' is related to 'b' under the relation R, written aRb. If P and Q are the same set, then R is a relation on P.

Examples of Binary Relations

Let A = {a, b, c} and B = {r, s, t}. Then R = {(a, r), (b, r), (b, t), (c, s)} is a relation from A to B.

Let A = {1, 2, 3}. Then R = {(1, 1), (2, 2), (3, 3)} is a relation on A (because P = Q = A).

Counting Relations

The number of possible relations between two sets depends on the size of the sets.

  • Example 1 (Relations on a Set): If set A has n elements, then there are 2n² possible relations from A to A (because A x A has n² elements, and each pair can either be in the relation or not).
  • Example 2 (Relations Between Sets): If set A has m elements and set B has n elements, then there are 2mn possible relations from A to B.

Example: All Possible Relations on a Set

Let A = {1, 2}. Let's list some of the possible relations on A (there are 22*2 = 16 total):

  • {(1, 1), (1, 2), (2, 1), (2, 2)}
  • {(1, 2), (2, 1)}
  • {(1, 1)}
  • ∅ (the empty relation)

Domain and Range of a Relation

  • Domain (DOM(R)): The set of all first elements in the ordered pairs of relation R.
  • Range (RAN(R)): The set of all second elements in the ordered pairs of relation R.

Example: Domain and Range

Let A = {1, 2, 3, 4} and B = {a, b, c, d}. If R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}, then:

  • DOM(R) = {1, 2}
  • RAN(R) = {a, b, c, d}

Complement of a Relation

The complement of a relation R (denoted R') consists of all the ordered pairs that are in the Cartesian product of the sets but are not in R.

Example: Complement of a Relation

Let X = {1, 2, 3} and Y = {8, 9}. If R = {(1, 8), (2, 8), (1, 9), (3, 9)}, then the complement R' = {(2, 9), (3, 8)}.

Conclusion

Binary relations provide a fundamental way to describe relationships between elements of sets. Understanding their properties, such as domain, range, and complement, is essential in various areas of discrete mathematics.