4.1 Relations and Their Properties
6 min read•august 13, 2024
Relations are like rules that connect elements in a set. They're the building blocks for understanding how things relate to each other. We use them to model real-world connections and solve complex problems.
In this part, we'll learn about different types of relations and their key properties. We'll see how to represent them visually and mathematically, which helps us analyze and work with them more easily.
Relations on Sets
Definition and Representation
Top images from around the web for Definition and Representation
Strengths and limitations of each representation of function View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
Strengths and limitations of each representation of function View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
1 of 3
Top images from around the web for Definition and Representation
Strengths and limitations of each representation of function View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
Strengths and limitations of each representation of function View original
Is this image relevant?
OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Relations, Graphs, and Functions View original
Is this image relevant?
1 of 3
- Define a on a set A as a subset of the A × A, where each element of the relation is an (a, b) with a, b ∈ A
- Represent a relation using various methods such as a set of ordered pairs (e.g., R = {(1, 1), (1, 2), (2, 1)}), a directed graph (with vertices representing elements and edges representing ordered pairs), or a matrix (where entries indicate the presence or absence of ordered pairs)
- Identify the domain of a relation R on a set A as the set of all first components (a values) of the ordered pairs in R, while the range is the set of all second components (b values)
Properties of Relations
- Determine the properties of a relation, which include reflexivity (every element is related to itself), symmetry (if a is related to b, then b is also related to a), and transitivity (if a is related to b and b is related to c, then a is also related to c)
- Classify a relation as an equivalence relation if it is reflexive, symmetric, and transitive (e.g., equality relation on integers: a = b), or as a if it is reflexive, antisymmetric (if a is related to b and b is related to a, then a = b), and transitive (e.g., "less than or equal to" relation on real numbers: a ≤ b)
Properties of Relations
Determining Reflexivity, Symmetry, and Transitivity
- Check if a relation is reflexive by verifying the presence of (a, a) for all a ∈ A (e.g., for A = {1, 2, 3} and R = {(1, 1), (2, 2), (3, 3)}, R is reflexive)
- Check if a relation is symmetric by examining the ordered pairs in the relation and ensuring that (a, b) ∈ R implies (b, a) ∈ R for all a, b ∈ A (e.g., for A = {1, 2, 3} and R = {(1, 2), (2, 1), (2, 3), (3, 2)}, R is symmetric)
- Check if a relation is transitive by examining the ordered pairs in the relation and ensuring that (a, b) ∈ R and (b, c) ∈ R imply (a, c) ∈ R for all a, b, c ∈ A (e.g., for A = {1, 2, 3} and R = {(1, 2), (2, 3), (1, 3)}, R is transitive)
Examples of Relations and Their Properties
- Consider the relation "is a subset of" on the power set of a set A (e.g., for A = {1, 2}, the power set is {{}, {1}, {2}, {1, 2}}); this relation is reflexive (every set is a subset of itself), antisymmetric (if A ⊆ B and B ⊆ A, then A = B), and transitive (if A ⊆ B and B ⊆ C, then A ⊆ C)
- Consider the relation "is a sibling of" on a set of people; this relation is symmetric (if person A is a sibling of person B, then person B is also a sibling of person A) and reflexive (a person is not a sibling of themselves), but not transitive (if person A is a sibling of person B, and person B is a sibling of person C, person A is not necessarily a sibling of person C)
Visualizing Relations
Directed Graphs (Digraphs)
- Represent a relation using a directed graph, where each element of the set is represented by a vertex (node), and each ordered pair (a, b) in the relation is represented by a directed edge (arrow) from vertex a to vertex b
- Construct a directed graph from a given relation by creating a vertex for each element in the set and drawing a directed edge from a to b if (a, b) is in the relation (e.g., for A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 3)}, the digraph would have vertices 1, 2, and 3, with edges from 1 to 2, 2 to 1, and 1 to 3)
- Interpret a directed graph by identifying the elements of the set as vertices and the ordered pairs as directed edges
Matrix Representations
- Represent a relation R on a set A = {a1, a2, ..., an} using an n × n matrix M, where M[i, j] = 1 if (ai, aj) ∈ R and M[i, j] = 0 if (ai, aj) ∉ R
- Construct a matrix representation from a given relation by creating an n × n matrix (where n is the number of elements in the set) and filling in the entries with 1s and 0s based on the presence or absence of ordered pairs in the relation (e.g., for A = {1, 2, 3} and R = {(1, 1), (1, 2), (2, 3)}, the matrix would be [[1, 1, 0], [0, 0, 1], [0, 0, 0]])
- Interpret a matrix representation by identifying the elements of the set as row and column labels and the presence of ordered pairs as 1s in the corresponding entries
Composition of Relations
Definition and Properties
- Define the composition of two relations R and S on a set A, denoted by R ∘ S, as a new relation on A where (a, c) ∈ R ∘ S if and only if there exists an element b ∈ A such that (a, b) ∈ R and (b, c) ∈ S
- Find the composition of two relations by identifying all possible pairs (a, c) such that (a, b) is in the first relation and (b, c) is in the second relation for some element b, and including (a, c) in the resulting composition (e.g., for A = {1, 2, 3}, R = {(1, 2), (2, 3)}, and S = {(2, 1), (3, 2)}, R ∘ S = {(1, 1), (2, 2)})
- Recognize that the properties of the composition of two relations depend on the properties of the individual relations and may not always be easily predictable
Preservation of Properties under Composition
- Understand that reflexivity is not always preserved under composition, meaning that even if R and S are reflexive, R ∘ S may not be reflexive (e.g., for A = {1, 2}, R = {(1, 1), (1, 2)}, and S = {(1, 1), (2, 2)}, both R and S are reflexive, but R ∘ S = {(1, 1), (1, 2)} is not reflexive)
- Recognize that symmetry is not always preserved under composition, meaning that even if R and S are symmetric, R ∘ S may not be symmetric (e.g., for A = {1, 2}, R = {(1, 2), (2, 1)}, and S = {(1, 2), (2, 1)}, both R and S are symmetric, but R ∘ S = {(1, 1), (2, 2)} is not symmetric)
- Understand that transitivity is preserved under composition, meaning that if R and S are transitive, then R ∘ S is also transitive (e.g., for A = {1, 2, 3}, R = {(1, 2), (2, 3)}, and S = {(1, 2), (2, 3), (1, 3)}, both R and S are transitive, and R ∘ S = {(1, 3)} is also transitive)
Key Terms to Review (17)
Antisymmetric property: The antisymmetric property is a characteristic of a binary relation that states if an element A is related to an element B, and B is related to A, then A must be equal to B. This property is significant when analyzing the structure of relations, especially in the context of order relations and equivalence classes.
Cantor-Bernstein-Schröder Theorem: The Cantor-Bernstein-Schröder Theorem states that if there are injections (one-to-one functions) between two sets, then there exists a bijection (a one-to-one correspondence) between those sets. This theorem is crucial for understanding the concept of cardinality and helps determine when two sets can be considered to have the same size, especially when dealing with infinite sets. It connects closely with concepts such as relations and functions, as it relies on the properties of injective mappings to establish equivalence between different sets.
Cartesian Product: The Cartesian product is a mathematical operation that returns all possible ordered pairs from two sets. It connects to various aspects of relations, as it forms the foundational basis for defining relations between elements of different sets, allowing for the exploration of their interactions and properties.
Domain and Range: Domain and range are fundamental concepts in mathematics that describe the set of possible inputs and outputs of a function. The domain refers to all the values that can be input into a function, while the range refers to all the values that can be output from that function. Understanding these concepts is crucial for analyzing relationships and their properties, as well as for exploring inverse functions, which essentially swap the roles of inputs and outputs.
Fermat's Little Theorem: Fermat's Little Theorem states that if 'p' is a prime number and 'a' is an integer not divisible by 'p', then $$a^{p-1} \equiv 1 \pmod{p}$$. This theorem is significant in number theory and helps establish properties of modular arithmetic, particularly in relation to prime numbers and their behavior with respect to certain integers.
Function: A function is a specific type of relation that assigns exactly one output for every input from a given set, often described as a mapping from one set to another. Functions are essential in mathematics as they provide a systematic way to express relationships between quantities and allow for the abstraction of processes and operations. Understanding functions involves recognizing how they operate within sets, relate to other types of relations, and take on various forms and types based on their properties and behaviors.
Injective Function: An injective function, or one-to-one function, is a type of function where every element in the domain maps to a unique element in the codomain. This means that no two different inputs can produce the same output, ensuring that each output is associated with only one input. Understanding injective functions helps to analyze relationships between sets and contributes to the larger concepts of functions such as surjectivity and bijectivity.
Non-reflexive Example: A non-reflexive example refers to a type of relation in which at least one element does not relate to itself. In the context of relations and their properties, understanding non-reflexivity helps in distinguishing between different kinds of relations, particularly when analyzing whether a relation possesses reflexive characteristics. Non-reflexivity plays a crucial role in various mathematical concepts, such as equivalence relations and orderings, where reflexivity is one of the key properties that may or may not be present.
Non-symmetric example: A non-symmetric example is a relation where, if one element is related to another, the reverse is not necessarily true. This highlights the lack of symmetry in certain relations, allowing for a clearer understanding of how relationships can be unidirectional and how they differ from symmetric relations. Understanding non-symmetry helps in distinguishing various properties of relations, particularly in evaluating their behavior and implications in mathematical contexts.
Ordered Pair: An ordered pair is a pair of elements combined in a specific sequence, typically represented as (a, b), where 'a' is the first element and 'b' is the second. The order in which these elements are arranged is crucial because it determines the relationship between them, especially in contexts like Cartesian coordinates and relations. Understanding ordered pairs is foundational to exploring properties of relations and functions.
Partial Order: A partial order is a binary relation defined on a set that is reflexive, antisymmetric, and transitive. This means that for any elements in the set, the relation can establish a comparison between them, but it does not require every pair of elements to be comparable. This characteristic allows for the organization of elements into a structure where some elements can be compared while others cannot, reflecting a hierarchy or arrangement.
Reflexive Relation: A reflexive relation is a type of binary relation on a set where every element is related to itself. This means that for any element 'a' in the set, the pair (a, a) is included in the relation. Reflexive relations are crucial in understanding the properties of relations, as they help to define more complex relationships like equivalence relations and orderings.
Relation: A relation is a connection or association between elements of two sets, often represented as a set of ordered pairs. It describes how elements from one set correspond to elements in another, highlighting the concept of pairing and interaction between different entities. Relations can be classified based on their properties, such as reflexivity, symmetry, and transitivity, which help us understand the structure and behavior of these connections in mathematics.
Relation Composition: Relation composition is an operation that takes two relations and produces a new relation that connects elements of the first relation to those of the second through a shared intermediate element. This concept is key to understanding how different relations interact and combine, revealing deeper connections between sets and helping analyze the properties and structure of these relations.
Surjective Function: A surjective function, also known as an onto function, is a type of function where every element in the codomain has at least one corresponding element in the domain. This means that the function covers the entire codomain, ensuring that no elements are left out. In terms of relationships between sets, a surjective function emphasizes the idea of mapping all outputs while still allowing for multiple inputs to produce the same output.
Symmetric relation: A symmetric relation is a type of binary relation where if one element is related to another, then the second element is also related to the first. This property ensures that for any elements a and b, if a is related to b, then b is necessarily related to a. Understanding symmetric relations is crucial in exploring other properties of relations, such as reflexivity and transitivity, which can help to characterize more complex structures within mathematics.
Transitive Property: The transitive property states that if one element is related to a second element, and that second element is related to a third element, then the first element is also related to the third element. This property is fundamental in understanding how relationships work within sets, particularly in the context of equivalence relations and orderings.