Part (a): Symmetric and Transitive Relations
Enroll to start learning
You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.
Interactive Audio Lesson
Listen to a student-teacher conversation explaining the topic in a relatable way.
Understanding Symmetric Relations
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
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: **S**ymmetric means both ways.
Exploring Transitive Relations
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
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.
Counterexamples
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
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.
Functions and Surjectivity
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
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.
Introduction & Overview
Read summaries of the section's main ideas at different levels of detail.
Quick Overview
Standard
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
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.
Youtube Videos
Audio Book
Dive deep into the subject with an immersive audiobook experience.
Introduction to Relations
Chapter 1 of 2
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
In 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.
Counterexample of Symmetric and Transitive Relations
Chapter 2 of 2
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
Well, 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
-
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 & Applications
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
Interactive tools to help you remember key concepts
Rhymes
Symmetry’s a dance we share, trust goes two ways, like a love affair.
Stories
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!
Memory Tools
S.T.R.F - Symmetric, Transitive, Reflexive: Such True Relations Fight for fairness.
Acronyms
S is for symmetric, T for transitive, R for reflexive! Remember, not all play nice!
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.
Reference links
Supplementary resources to enhance your learning experience.