Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
2.6.1. Part (a): Symmetric and Transitive Relations
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's start by defining a symmetric relation. A relation R on a set A is symmetric if, for every a and b in A, if aRb, then bRa. For example, if a and b are people, and R indicates that 'a trusts b', then trust is symmetric.
So, if Alice trusts Bob, it means Bob trusts Alice as well?
Exactly! Now, can anyone think of a relation that is symmetric but not reflexive?
Maybe the relation 'is a sibling of' because not all siblings will consider each other in the same way?
Good example! A symmetric relation can exist without self-relation. Remember: Symmetric means both ways.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now let's discuss transitive relations. A relation R on a set A is transitive if, whenever aRb and bRc, then aRc as well. Can anyone provide an example?
Like 'is a parent of'? If A is a parent of B, and B is a parent of C, then A must be a grandparent of C?
Exactly right! Remember, transitivity is all about chaining relationships together. It’s not the same as symmetry, where the direction of the relationship matters.
Are there situations when a relation can be both symmetric and transitive?
Yes, a good example is equality. It’s symmetric since if a = b, then b = a, and transitive because if a = b and b = c, then a = c.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's prove that symmetric and transitive relations do not necessarily imply reflexivity. Consider the relation R on set X={1, 2} defined as R = {(1, 1), (1, 2), (2, 1)}. Is this relation symmetric?
Yes, it is since it includes (1, 2) and (2, 1).
Good! But is it reflexive?
No, it’s not because (2, 2) isn't included.
Exactly! This shows us that while similarity and transitivity may exist, they do not alone ensure reflexivity.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now let's look at surjective functions. A function f: A → B is surjective if every element b in B has at least one corresponding a in A. Can we assume surjectivity guarantees bijectivity?
Only if the sets A and B are finite, right?
Correct! A surjective function might not be bijective if B is infinite. Let’s analyze this with a simple example.
An infinite set mapping could lead to non-unique inputs for the same output.
Precisely. This counterexample of surjectivity shows how the relation's nature fundamentally changes with the infinite context.
Overview
Short Summary
This section discusses symmetric and transitive relations, highlighting their properties and the conditions under which they apply.
Medium Summary
The section covers key concepts of symmetric and transitive relations, providing examples and counterexamples, particularly pertaining to reflexivity and the implications of these properties on functions. It emphasizes how certain functions can exhibit these relations under specific conditions.
Detailed Summary
Detailed Summary
In this section, we explore the fundamental properties of symmetric and transitive relations, two critical concepts in discrete mathematics. A relation is symmetric if, for any elements a and b, whenever a is related to b, b is also related to a. Transitive relations require that if a is related to b and b is related to c, then a must also be related to c. The importance of these properties becomes clearer through examples, such as showing that a symmetric and transitive relation need not be reflexive. A key point illustrated includes situations where a function can be surjective without being bijective; specifically, it must be finite for bijectivity to hold. We contextualize this with examples of functions mapped within infinite sets and their characteristics, providing a basis for understanding how relations interact in different kinds of sets.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountIn question 10a, you are asked to either prove what is proof that every non-empty symmetric and transitive relation is also reflexive.
Detailed Explanation
In this section, we begin by defining what a relation is in mathematics. A relation is a way to show a connection or relationship between elements in a set. It can have different properties, which include being symmetric, transitive, and reflexive. Here, we specifically look at symmetric and transitive relations. Symmetric means if a is related to b, then b is related to a. Transitive means if a is related to b, and b is related to c, then a is related to c. This part of the question challenges you to consider whether such a relation must also be reflexive, meaning every element is related to itself as well.
Examples & Analogies
Think of friendships among people. If person A is friends with person B (symmetric) and person B is friends with person C (transitive), you might wonder if that guarantees that person A is also a friend of person A (reflexive). Relationships can be complex just like in friendships, and it’s important to analyze the properties of how people relate to each other.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountWell, we can give a very simple counter example to prove that the statement is false. Imagine you are given a relation R over this set X, the relation is clearly symmetric. It is also transitive.
Detailed Explanation
To begin answering the question, one effective method is to create a counterexample—a special case where the statement fails. For example, suppose we define a relation R on the set X that showcases symmetry and transitivity without being reflexive. If we consider R = {(1, 1), (1, 2), (2, 1)}. The relation is symmetric since (1, 2) is present and therefore (2, 1) is also present. The relation is transitive since it contains the necessary sequences. However, (2, 2) is missing, which makes R not reflexive. Thus, it demonstrates that you can have a symmetric and transitive relation without it being reflexive.
Examples & Analogies
Imagine a club where everyone knows each other’s name (symmetric), and if one person knows a second person, and the second person knows a third, the first person can be assumed to know the third (transitive). However, if no one knows the club president, then the relationship is not reflexive. This illustrates that while the members have connections that are symmetrical and transitive, they may lack a direct link to the leader.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Symmetric Relation:
A relation where if aRb, then bRa.
- Transitive Relation:
A relation where if aRb and bRc, then aRc.
- Surjective Function:
A function where every element in the codomain has at least one pre-image.
- Bijective Function:
A function that is both injective and surjective.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
A symmetric relation is 'is a sibling of'. If a is a sibling of b, then b is also a sibling of a.
An example of a transitive relation is 'is a parent of'. If A is a parent of B and B is a parent of C, then A is a grandparent of C.
Memory aids
Imagine friends on a playground. If Jamie swings with Taylor, then Taylor swings with Jamie — that's symmetry! Meanwhile, if Jamie is on a swing and Taylor is at the slide, and if Taylor's friend Jordan plays with them — that's transitivity in action!
Flash Cards
Glossary
Symmetric Relation
A relation R is symmetric if for any a, b in set A, if aRb then bRa.
Transitive Relation
A relation R is transitive if for any a, b, c in set A, if aRb and bRc, then aRc.
Reflexive Relation
A relation R is reflexive if for every element a in set A, aRa holds true.
Surjective Function
A function f: A → B is called surjective if for every b in B, there exists at least one a in A such that f(a) = b.
Bijective Function
A function f: A → B is bijective if it is both surjective and injective.