Question

Which of the following relations on the set of all people are reflexive? Symmetric? Antisymmetric? Transitive? Explain why your assertions are true. (a) \(R(x, y)\) if \(x\) and \(y\) either both like German food or both dislike German food. (b) \(R(x, y)\) if (i) \(x\) and \(y\) either both like Italian food or both dislike it, or (ii) \(x\) and \(y\) either both like Chinese food or both dislike it. (c) \(R(x, y)\) if \(y\) is at least two feet taller than \(x\).

Short answer

(a) Reflexive, symmetric, transitive; (b) Reflexive, symmetric, transitive; (c) Antisymmetric.

Step-by-step solution

Understanding Reflexivity

A relation is reflexive if every element is related to itself. Hence, for a relation \( R(x, y) \) to be reflexive, for every person \( x \), \( R(x, x) \) must hold true.

Analyzing Relation (a) Reflexivity

In relation (a), \( R(x, x) \) holds because everyone either likes or dislikes German food. Thus, \( x \) relates to themselves in terms of liking or disliking. So, it is reflexive.

Analyzing Relation (b) Reflexivity

Similarly, in relation (b), \( R(x, x) \) holds because everyone either likes or dislikes both Italian and Chinese food. Therefore, it is also reflexive.

Analyzing Relation (c) Reflexivity

In relation (c), \( R(x, x) \) does not hold as no one can be two feet taller than themselves. Thus, it is not reflexive.

Understanding Symmetry

A relation is symmetric if \( R(x, y) \) implies \( R(y, x) \). Thus, if \( x \) relates to \( y \), then \( y \) must relate to \( x \).

Analyzing Relation (a) Symmetry

In relation (a), if \( x \) and \( y \) both like or dislike German food, then \( y \) and \( x \) must also both like or dislike German food. Hence, it is symmetric.

Analyzing Relation (b) Symmetry

In relation (b), if \( x \) and \( y \) both have the same preferences for Italian and Chinese food, then \( y \) and \( x \) mimic the same behavior. Therefore, it is symmetric.

Analyzing Relation (c) Symmetry

In relation (c), if \( y \) is two feet taller than \( x \), then \( x \) cannot possibly be two feet taller than \( y \). Hence, it is not symmetric.

Understanding Antisymmetry

A relation is antisymmetric if whenever \( R(x, y) \) and \( R(y, x) \) both hold, then \( x = y \).

Analyzing Relation (a) Antisymmetry

In relation (a), \( R(x, y) \) allows for \( x eq y \) to have \( R(y, x) \), hence, it is not antisymmetric.

Analyzing Relation (b) Antisymmetry

For relation (b), if both \( x \) and \( y \) agree on both food types, it doesn't imply they are the same individual, so it is not antisymmetric.

Analyzing Relation (c) Antisymmetry

Relation (c) is antisymmetric because if \( x \) is two feet shorter than \( y \), \( y \) cannot also be two feet shorter than \( x \) unless \( x = y \), which is impossible.

Understanding Transitivity

A relation is transitive if whenever \( R(x, y) \) and \( R(y, z) \), it implies \( R(x, z) \).

Analyzing Relation (a) Transitivity

For relation (a), if \( x \), \( y \), and \( z \) agree on liking or disliking German food, then this applies transitively. Thus, it is transitive.

Analyzing Relation (b) Transitivity

For relation (b), the condition holds transitively if all three \( x \), \( y \), and \( z \) agree on both food types. Therefore, it is transitive.

Analyzing Relation (c) Transitivity

For relation (c), if \( x \) is two feet shorter than \( y \) and \( y \) is two feet shorter than \( z \), \( x \) cannot be directly related to \( z \) unless the height condition fails. Hence, it is not transitive.

Key concepts

Relations

In discrete mathematics, relations are a way to describe how elements from one set are connected or related to elements of another set, or even the same set. It's like a bridge linking different elements, highlighting some sort of connection between them. In everyday terms, think of a relation as a way to express if two people are friends, if two numbers are equal, or even if one object is bigger than another.

Mathematically, a relation is a subset of the Cartesian product of two sets. If we have two sets, say A and B, the Cartesian product is all possible ordered pairs ewline (a, b) where \( a \in A \text{ and } b \in B \). The relation, then, is simply a set of these pairs that we are interested in.

• Reflexive Relation
• Symmetric Relation
• Antisymmetric Relation
• Transitive Relation

Each type of relation has unique properties, which we'll explore further in the following sections.

Reflexivity

Reflexivity is a foundational concept in the study of relations. A relation \( R \) on a set is said to be reflexive if every element is related to itself.

Try to picture this as everyone being friends with themselves. If you think about a relation \( R(x, y) \) on a set of people, reflexivity would mean that for every person \( x \), \( R(x, x) \) holds true. It's like saying, "Since I like Italian food, I'm in agreement with myself about my food preference."

In practical terms, reflexivity in our sets of relations implies that the condition is met for all individuals without needing further comparison.

• In relation (a), since everyone either likes or dislikes German food and the same holds when considering themselves, it is reflexive.
• Similarly, in relation (b), preferences for both Italian and Chinese food are considered for the individual themselves, hence reflexive.
• However, in relation (c), a person cannot be two feet taller than themselves, thus not reflexive.

Symmetry

Symmetry in relations means that if one element is related to another, the reverse is also true. In simpler terms, if you say a relationship \( R(x, y) \) is symmetric, then if \( x \) is related to \( y \), \( y \) must also be related to \( x \). It's like saying, if "Alice is a friend of Bob," then "Bob must be a friend of Alice."

When examining relations using this idea:

• For relation (a), where both \( x \) and \( y \) either like or dislike German food, if \( y \, R \, x\) already implies \( x \, R \, y \), achieving symmetry.
• With relation (b), similar logic applies. If there's a mutual agreement between \( x \) and \( y \) for Italian and Chinese food, symmetry is established.
• For relation (c), symmetry breaks because if \( y \) is two feet taller than \( x \), \( x \) can't be two feet taller than \( y \).

Antisymmetry

Antisymmetry is different from symmetry but provides unique insights into relations. For a relation \( R \) to be antisymmetric, if \( R(x, y) \) and \( R(y, x) \) both hold, then \( x \, must \, equal \, y \).

In plain words, it states that if \( x \) relates to \( y \) in a certain way, and \( y \) also relates back to \( x \) in the same way, they must actually be the same entity or thing, otherwise the relation wouldn't hold.

• In relation (a), antisymmetry doesn't apply since different people can share similar preferences.
• The same holds for relation (b); sharing food preferences doesn't force \( x \) and \( y \) to be identical.
• However, for relation (c), antisymmetry is present. If \( x \) is two feet shorter than \( y \), \( y \) can't be two feet shorter than \( x \) unless \( x = y \), a situation that's inherently impossible because one cannot be taller and shorter simultaneously.

Transitivity

Transitivity brings an interesting layer of depth to relations. A relation \( R \) is transitive if whenever \( R(x, y) \) and \( R(y, z) \), it also implies \( R(x, z) \). It's a domino effect of relationships.

Think of it in terms of trust: if "Alice trusts Bob" and "Bob trusts Carol," then, assuming transitivity, "Alice should trust Carol" as well. Let's explore our relations under this perspective:

• For relation (a), when people align either in liking or disliking German food, the condition transfers through people naturally, hence it's transitive.
• Relation (b) also supports transitivity, as agreement on Italian and Chinese food between people creates a chain of acceptance.
• Nevertheless, relation (c) does not exhibit transitivity. If \( x \) is two feet shorter than \( y \) and \( y \) is two feet shorter than \( z \), \( x \) cannot skip directly to being related to \( z \), breaking the transitive possibility.