What is Discrete Mathematics?
Discrete mathematics is a branch of mathematics that deals with mathematical structures and objects that are fundamentally discrete rather than continuous. It focuses on countable sets and finite structures, such as integers, graphs, and logical statements.
Understanding Binary Relations
In discrete mathematics, binary relations are an important concept. A binary relation is a mathematical relation that is defined between two sets. It establishes a relationship between elements of the first set and elements of the second set. Binary relations are commonly represented using ordered pairs.
Examples of Binary Relations
Let’s explore some examples of binary relations to gain a better understanding:
Example 1: Parent-Child Relationship
Consider the set of all people and the relation “is the parent of.” In this case, the first set consists of all individuals, and the second set also consists of all individuals. The binary relation “is the parent of” establishes a relationship between a person and their child.
For example, if we have the ordered pair (John, Mary), it means that John is the parent of Mary. Similarly, the ordered pair (Mary, John) would mean that Mary is the parent of John.
Example 2: Greater Than Relation
Another common example of a binary relation is the “greater than” relation. Consider the set of all real numbers. The binary relation “is greater than” establishes a relationship between two real numbers.
For example, if we have the ordered pair (5, 3), it means that 5 is greater than 3. Similarly, the ordered pair (3, 5) would mean that 3 is not greater than 5.
Example 3: Divisibility Relation
The divisibility relation is another binary relation. Consider the set of all positive integers. The binary relation “is divisible by” establishes a relationship between two positive integers.
For example, if we have the ordered pair (12, 6), it means that 12 is divisible by 6. Similarly, the ordered pair (6, 12) would mean that 6 is not divisible by 12.
Properties of Binary Relations
Binary relations can have various properties that describe their behavior. Some common properties include:
Reflexive
A binary relation is reflexive if every element in the first set is related to itself. In other words, for every element a in the set, the ordered pair (a, a) is in the relation.
Symmetric
A binary relation is symmetric if for every ordered pair (a, b) in the relation, the ordered pair (b, a) is also in the relation.
Transitive
A binary relation is transitive if for every ordered pair (a, b) and (b, c) in the relation, the ordered pair (a, c) is also in the relation.
Example of Reflexive, Symmetric, and Transitive Relations
Let’s consider the following binary relation on the set of all integers:
R = {(a, b) | a – b is an even number}
This relation is reflexive because for every integer a, (a, a) is in the relation since a – a = 0, which is an even number.
This relation is symmetric because for every ordered pair (a, b) in the relation, (b, a) is also in the relation. This is because if a – b is an even number, then b – a is also an even number.
This relation is transitive because for every ordered pair (a, b) and (b, c) in the relation, (a, c) is also in the relation. This is because if a – b and b – c are both even numbers, then a – c is also an even number.
Conclusion
Binary relations are a fundamental concept in discrete mathematics. They allow us to establish relationships between elements of different sets. Understanding binary relations and their properties is essential in various areas of mathematics and computer science.