#reflexive symmetric transitive relations

[edusquaremaths]

Q10 Exercise1.1 I Class 12 Maths NCERT Chapter 1 Relations and Functions | NCERT solutions

NCERT Class 12Chapter: Relations and FunctionsExercise 1.1Question 10: Give an example of a relation. Which is(i) Symmetric but neither reflexive nor transitive.(ii) Transitive but neither reflexive nor symmetric.(iii) Reflexive and symmetric but not transitive.(iv) Reflexive and transitive but not symmetric.(v) Symmetric and transitive but not reflexive.

[bubbloquacious]

A partial equivalence relation is a reflexive, symmetric, and transitive binary relation ≡, which allows you to compare some, but not all pairs of elements x, y of the domain. A total equivalence relation is similar, but we also require that for all x, y we have that x ≡ y or y ≡ x.

[noelements-setempty]

Word rhyming is an equivalence relation

Take the definition that two words rhyme if and only if they end with the same sound.

Reflexive: Every word rhymes with itself.

Well, if two words are the same, all their sounds have to match, including the final one, so this point holds.

Symmetric: If A rhymes with B, B rhymes with A.

This one’s really hard to prove, because it’s so obvious. If A rhymes with B, then the final sounds of A and B are the same. They will still be the same if we swap the words around. Please don’t make me explain it more, I’ll cry.

Transitive: If A rhymes with B and B rhymes with C, then A rhymes with C.

Call the sound at the end of word A ‘&’. If A rhymes with B, then B also has to end with ‘&’. If B rhymes with C, and B ends with ‘&’, then C also has to end with ‘&’. This means that both A and C end with ‘&’, and so A rhymes with C.

There we go. The argument no one cares about but me has been made. Rhyme is an equivalence relation. You can all go home.

[lipshits-continuous]

If your relation(ship) is

Reflexive

Symmetric

Transitive

It's not romantic, it's an equivalence

[codeshive]

Homework 3 CSCI 301 solved

Use the method of proof by contradiction. 1. [4 points] Prove that √6 is irrational. 2. [4 points] If �, � �ℤ , then �) − 4� − 2 ≠ 0. 3. [4 points] Suppose Suppose A≠ Ø. Since Ø ⊆A×A, the set R= Ø is a relation on A. Is R reflexive? Symmetric? Transitive? If a property does not hold, say why. 4. [4 points] Define a relation R on Z as xRy if and only if 4 | (x + 3y) Prove R is an equivalence…

[codingprolab]

Homework 3 CSCI 301

Use the method of proof by contradiction. 1. [4 points] Prove that √6 is irrational. 2. [4 points] If �, � �ℤ , then �) − 4� − 2 ≠ 0. 3. [4 points] Suppose Suppose A≠ Ø. Since Ø ⊆A×A, the set R= Ø is a relation on A. Is R reflexive? Symmetric? Transitive? If a property does not hold, say why. 4. [4 points] Define a relation R on Z as xRy if and only if 4 | (x + 3y) Prove R is an equivalence…

[class12maths]

Relations and Functions: Class 12 Maths Video Tutorials — Mathyug

Are you a Class 12 student gearing up for your Maths exams? Do the concepts of relations and functions seem daunting? Fret not! Ashish Sir from MathYug has designed an exceptional self-study course that covers everything you need to master these topics. This comprehensive course includes video tutorials, detailed notes, and assignments that ensure thorough understanding and practice.

What You’ll Learn

Ashish Sir’s course on MathYug is meticulously structured to provide a deep understanding of relations and functions, a crucial component of Class 12 Mathematics. The course is divided into two main parts:

1. Relations

In this segment, you will explore various types of relations. Here’s a brief overview of what you’ll learn:

Empty Relations: Understanding the concept of relations where no element of a set is related to any element of another set.

Universal Relations: Learning about relations where every element of a set is related to every element of another set.

Trivial Relations: Delving into the simplest form of relations that only relate to the identical pairs.

Reflexive Relations: Understanding relations where every element is related to itself.

Symmetric Relations: Exploring relations where if one element is related to another, the second element is also related to the first.

Transitive Relations: Learning about relations where if one element is related to a second, and the second to a third, then the first is related to the third.

Equivalence Relations: Discovering relations that are reflexive, symmetric, and transitive.

Equivalence Classes: Understanding the partition of a set into disjoint subsets where each subset is an equivalence class.

To ensure comprehensive understanding, the course provides practice questions from diverse sources such as NCERT Textbook exercises, NCERT Examples, Board’s Question Bank, RD Sharma, and NCERT Exemplar. You can download the PDF of assignments within the course for additional practice.

2. Functions

The second part of the course focuses on functions, including:

One to One and Onto Functions: Understanding functions where each element of one set is paired with a unique element of another set, and functions that map elements from one set onto every element of another set.

Composite Functions: Learning how to combine two functions to form a new function.

Inverse of a Function: Exploring how to find the function that reverses the effect of the original function.

Similar to the relations segment, this part also includes practice questions from various reputable sources. The assignments are designed to reinforce your understanding and are available for download within the course.

Sample Videos

To give you a glimpse of the quality of instruction, Ashish Sir has shared sample videos covering some of these essential topics. Watching these will help you understand his teaching methodology and the depth of content provided.

If you’re aiming to excel in your Class 12 Maths exams, Ashish Sir’s course on MathYug is your go-to resource. With detailed video tutorials, comprehensive notes, and extensive assignments, you will gain a solid understanding of relations and functions. Start your journey towards mastering these crucial topics today!

For more information and to access the course, visit MathYug. Happy learning!

[mathyug]

Unlock a deeper understanding of Reflexive, Symmetric, Transitive, and Equivalence Relations, and master Exercise 1.1 in Relations and Functions Class 12 Maths with expert instructor Ashish Sir on MathYug.Explore additional video lectures on our website: https://mathyug.com/class-12-maths

[quietimtryingtostudy]

9. Let W denote the set of words in the English dictionary. Define the relation R by R= {(x, y) ∈ W x W such that x and y have at least one letter in common}. Show that this relation R is reflexive and symmetric, but not transitive.

(i vaguely remember my teacher saying that we don't have word problems from this chapter or smtg. but just in case, ya know?)

Took help from one of my friends for this one- but I understood the entire procedure by the end!

(Yeah, I understand. Thanks for sending it though!!)

[futurebird]

If lines could be parallel to themselves we could call parallelism in the Euclidean plane an equivalence relation.

Why not do this?

What is a name for a relation that is only transitive and symmetric, but not reflexive?

Aren’t sets of parallels equivalence classes?

[edusquaremaths]

Q9 Exercise1.1 I Class 12 Maths NCERT Chapter 1 Relations and Functions | NCERT solutions

NCERT Class 12Chapter: Relations and FunctionsExercise 1.1Question 9: Show that each of the relation R in the set A = {x ∈ Z : 0 ≤ x ≤ 12}, given by(i) R = {(a, b) : |a – b| is a multiple of 4}(ii) R = {(a, b) : a = b}is an equivalence relation. Find the set of all elements related to 1 in each case.

[bhargaw1]

Equivalence relation

#equivalencerelations Definition 🙂 An equivalence relation on a set A, is a relation “R” in A which is #reflexive, #symmetric, and #transitive.

Definition 🙂 An equivalence relation on a set A, is a relation “R” in A which is reflexive, symmetric, and transitive. Reflexive relation ARB is a relation in set A, then R is called Reflexive relation R is reflexive, i.e., for all a belongs to R (a, a) also belongs to R a=1 & b=a then (1,1) also belongs to R ⭐⭐⭐⭐ Rating: 4 out of 5. Symmetric relation (mirror) Let R be a relation in set…

[wuggen]

An innocuous little math thing that I find really neat for some reason: a partial equality relation (symmetric and transitive) almost implies a full equality relation (symmetric, transitive, and reflexive). If a=b, then by symmetry b=a, and by transitivity a=a, and then you've got reflexivity. The only way to have a partial equality relation that is not a full equality relation is if there exists some element that just doesn't appear in the relation at all

[model-theory]

Found out that symmetric, reflexive relations are called Fuzzys. This is an adorable name and very clever since it's just an equivalence relation w/o transitivity so instead of equivalence classes [x] you get vague classes. Arguably ≈ is a fuzzy:

x≈x, x≈y→y≈x, but ≈ isn't transitive

[dronaacadmey]

What is an anti-symmetric relation?

What is Antisymmetric Relation?

Relation and its types proves to be one of the essential aspects of the set theory. There are different   sets, relations, and functions that are interdependent topics. The sets indicate the collection of ordered elements, in case of functions and relations and they will denote the operations that are performed on sets. The Relations will always show the connection between two sets and they are basically simple ways through which we can understand and regulate the different relations. Antisymmetric relation is a concept that is based on symmetric and asymmetric relation in terms of discrete math. In a simple sentence, the antisymmetric relation of a set as a one that have no ordered pair and is reverse in the relation.   

Basics of Antisymmetric Relation

A relation becomes an antisymmetric relation that is for a binary relation R on a set A. in this there will be no pair of distinct elements of A, that will get related by R to the other. Expect for the antisymmetric, there are different relations like the ones as reflexive, irreflexive, symmetric, asymmetric, and transitive.   

The relation R is antisymmetric, more specific for all a and b in A; so, if R (x, y) with the equation x ≠ y, then R (y, x) must not hold. On the similar manner if we have  R(x, y) and R(y, x), then x = y. so, when we have  (XXY) that is in  relation to R, then (y, x) is not.  In the equation therefore, x and y are nothing, but they are called the elements of set A.

Rules of Antisymmetric Relation

Typically, relations can follow any rules. Consider the relation ‘is divisible by,’ it’s a relation for ordered pairs in the set of integers. For a relation R, an ordered pair (x, y) can get found where x and y are whole numbers or integers, and x is divisible by y. However, it’s not necessary for antisymmetric relation to hold R (x, x) for any value of x. That’s a property of reflexive relation. 

Antisymmetric Relation

In regards to the set theory, the relation R can be  considered as antisymmetric on set A, if x R y and y R x holds, as the values given as  x = y. in this case we can even say that  relation R is antisymmetric with (x, y) ∉ R or (y, x) ∉ R when x ≠ y.

On the other hand the relation R is not antisymmetric when  x, y ∈ A holds, in   such a way that (x, y) ∈ R and (y, a) ∈ R but x ≠ y. the one important thing that need to be kept in mind is that  if a relationship is not symmetric, it also does not mean that   it’s antisymmetric. 

In case of antisymmetric relation, this is like a thing in one set has a relation with a different thing in another set. In the similar manner the different thing has relation back to the thing that is in the first set. To simplify this, there must be a relation with b by some function and b has a relation with a by the same in case of the same function. This thing can only become applicable and true when the two things are equal.

Symmetric, Asymmetric, and Antisymmetric Relations

In most of the cases the students get confused with symmetric, asymmetric and antisymmetric relations so this is so very important that we can understand all the three types clearly so that we are able to distinguish between them. It will indeed help us to quickly solve any antisymmetric relation example in a better manner.

Symmetric: Relation R of a set X will become a  symmetric if (b, a) ∈ R     and (a, b) ∈ R. just for the records here R ‘is equal to’ is a symmetric relation like, 5 = 3 + 2 and 3 + 2 = 5. The relation should always be a two-way street in all ways.

Asymmetric: Relation R of a set X will become asymmetric if (a, b) ∈ R,  but (b, a) ∉ R. in this case, the relation  R ‘is less than’ is an asymmetric    relation such as  a manner that 5 < 11 but 11 is not less than 5.

Antisymmetric: Relation R of a set X will become antisymmetric if (a, b) ∈ R and (b, a) ∈ R, this will also mean that a = b. But, if a ≠ b, then (b, a) ∉ R, in simple words it can also be said as a one side street.

There concepts can be better learnt on the website doubtnut.com It provides video tutorials to help the students learn. There are also good number of practice examples that are provided that will help the student to understand the application part of it.

[lawsofemotion]

Properties of Relations

In this chapter, the study of relations will now be emphasized on a set A that is a subset of A X A.

Binary Relations Recall that for the sets A,B, any subset of A X B is called a binary relation from A to B. Any subset of A X A is called a binary relation on A.

Example Let the relation ℛ on the set ℤ be defined by a ℛ b, or (a,b) ∈ ℛ, if a ≤ b. This subset of ℤ X ℤ is the ordinary "less than or equal to" relation on the set ℤ, which can be also defined on ℝ or ℚ, but not ℂ.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7.

Example Let the universe 𝓤 = {1,2,3,4,5,6,7}. Consider the fixed set C ⊆ 𝓤, where C = {1,2,3,6}. Let the relation ℝ on ℘(𝓤) be defined by A ℛ B if A ⋂ C = B ⋂ C. Then the sets {1,2,4,5} and {1,2,5,7} are related, since {1,2,4,5} ⋂ C = {1,2} = {1,2,5,7} ⋂ C = {1,2}. Additionally, the sets X = {4,5} and Y = {7} are related, because X ⋂ C = ∅ = Y ⋂ C. However, the sets S = {1,2,3,4,5} and T = {1,2,3,6,7} are not related, since S ⋂ C = {1,2,3} ≠ {1,2,3,6} = T ⋂ C.

Example Let Σ be the American alphabet and the relation ℛ is defined as finite strings of letters from Σ by a₁a₂...am ℛ b₁b₂...bn iff m ≤ n and ∀i = 1, 2, ..., m, aᵢ = bᵢ. Then this relation describes the prefix relation of two strings, where the first string's letters must be equal to the second strings letters in the same order for enough letters to satisfy every m letter. Then (xxy,xxydefy) ∈ ℛ but (xx,xyd) ∉ ℛ.

Reflexive Relations A relation ℛ on a set A is called reflexive if for all a ∈ A, (a,a) ∈ ℛ.

Therefore, a relation ℛ is reflexive if each element in A is related to itself.

The above examples were examples of reflexive relations.

Example Let A = {1,2,3,4}. Then a relation ℛ ⊆ A X A will be reflexive if and only if {(1,1), (2,2), (3,3), (4,4)} ⊆ ℛ. Then ℛ₁ = {(1,1), (2,2), (3,3)} is not a reflexive relation on A, but ℛ₂ = {(x,y) | x,y ∈ A, x ≤ y} is reflexive on A.

Number of Reflexive Relations Given a finite set A, where |A| = n, then |A X A| = |A||A| = n2. Then the number of relations on A is 2n2.

A relation ℛ on A = {a₁,a₂,...,an} is reflexive if and only if {(aᵢ,aᵢ) | 1 ≤ i ≤ n} ⊆ ℛ.

Since a relation ℛ is reflexive if and only if every element in A X A of the form {aᵢ,aᵢ} is in the relation, every other element in A X A, a total of |A X A – A| elements, can be in this relation while not affecting the reflexivity.

Therefore, the number of possible reflexive relations on A is the number of subsets of A X A such that the elements in A X A of the form {aᵢ,aᵢ) are already inside the relation, and so the only options left are for the remaining |A X A – A| = n2 - n elements to be either included or excluded in the relation, making a total of 2n2-n possible reflexive relations on A.

Symmetric Relations A relation ℛ on set A is called symmetric if (x,y) ∈ ℛ => (y,x) ∈ ℛ for all x,y ∈ A, where x ≠ y.

Example Let A = {1,2,3}. ℛ₁ = {(1,2), (2,1), (1,3), (3,1)} is a symmetric but not reflexive relation on A. ℛ₂ = {(1,1), (2,2), (3,3), (2,3)} is a reflexive but not symmetric relation on A. ℛ₃ = {(1,1), (2,2), (3,3)} is both reflexive and symmetric. ℛ₄ = {(1,1), (2,2), (3,3), (2,3), (3,2)} is both reflexive and symmetric, since (2,3) ∈ ℛ => (3,2) ∈ ℛ, unlike ℛ₂. ℛ₅ = {(1,1), (2,3), (3,3)} is neither reflexive nor symmetric, because (2,2) is not contained in the set, and there doesn't exist an element (3,2) to be symmetric.

Remember: Any element in A X A of the form (a,a) does not imply symmetry. The elements of A X A must be of the form (a,b) to require symmetric properties.

Number of Symmetric Relations Let A = {a₁,a₂,...,an}. Then A X A can be written as A₁ ⋃ A₂, where A₁ = diagonal entries of A X A = {(aᵢ,a₁) | 1 ≤ i ≤ n} and A₂ = every other element in A X A that is not diagonal = {(aᵢ,aj) | 1 ≤ i,j ≤ n}. Then every ordered pair in A X A is exactly in either A₁ or A₂.

For A₁, |A₁| = the number of diagonal elements in A X A = n. For A₂, |A₂| = the number of elements in A X A of the form {(aᵢ,aj), (aj,aᵢ)}, i ≠ j = (|A X A| - |A|)/2 = (n2 – n)/2.

The cardinality of A₂ is divided by 2, since each element in A X A of the form {(aᵢ,aj), (aj,aᵢ)} has two elements in each subset. It cannot be where only one of the two elements is taken, since that does not define symmetry.

Then for each ordered pair in A₁, there are two choices: inclusion or exclusion. This is the same for A₂'s ordered pairs.

Therefore, by the rule of product, there are a total of (2ⁿ)(21/2(n2-n)) = 21/2(n2+n) symmetric relations on A.

Number of Reflexive and Symmetric Relations For the number of relations ℛ on set A such that the relations are both reflexive and symmetric, it is the number of subsets of A₂, since all of the diagonal entries are already inside the relation. Symmetry is not affected if only a few symmetric pairs are inside the relation, but having only a few reflexive pairs in the relation does affect the reflexivity.

Therefore, the number of relations on set A that are both symmetric and reflexive is 21/2(n2-n).

Transitive Relations For a set A, a relation ℛ on A is called transitive if for all x,y,z ∈ A, (x,y), (y,z) ∈ ℛ => (x,z) ∈ ℛ.

Therefore, if x is related to y and y is related to z, then the relation ℛ is transitive if x is related to z. Then y is called an intermediary.

Note that elements of the form (a,a) ∈ A X A that are in ℛ do not relate to transitivity. Transitivity is only concerned when there are elements (a,b) and (b,c) in ℛ.

Example Let the relation ℛ on the set ℤ⁺ be defined by a ℛ b if a exactly divides b, where there exists some c ∈ ℤ⁺ such that b = ca. If x ℛ y and y ℛ z, does x ℛ z? x ℛ y => y = sx, s ∈ ℤ⁺ y ℛ z => z = ty, t ∈ ℤ⁺ z = ty = t(sx) = (ts)x, ts ∈ ℤ⁺ => x ℛ z Therefore, ℛ is transitive. Additionally, ℛ is reflexive, because of the property a | a, but ℛ is not symmetric, since (2,6) ∈ ℛ but (6,2) ∉ ℛ.

Example Consider the relation ℛ on the set ℤ defined by a ℛ b when ab ≥ 0. Then for all integers x, xx = x² ≥ 0, and so x ℛ x and ℛ is reflexive. If x,y ∈ ℤ and x ℛ y, then xy ≥ 0 => yx ≥ 0 => y ℛ x, and so ℛ is also symmetric. However, for (3,0), (0,-7) ∈ ℛ, since (3)(0) ≥ 0, and (0)(-7) ≥ 0, it is not true that (3)(-7) ≥ and so (3,-7) ∉ ℛ and ℛ is not transitive.

Example Let A = {1,2,3,4} and ℛ₁ = {(1,1), (2,3), (3,4), (2,4)} and ℛ₂ = {(1,3), (3,2)}. Then ℛ₁ is transitive on A. ℛ₂ is not transitive, because (1,3), (3,2) ∈ ℛ₂, but (1,2) ∉ ℛ₂.

Number of Transitive Relations In regards to transitive relations, there is no known general formula for the total number of transitive relations ℛ on the set A.

Antisymmetric Relations A relation ℛ on a set A is antisymmetric if for all a,b ∈ A, (a,b), (b,a) ∈ ℛ => a = b.

Therefore, a relation ℛ on a set A is antisymmetric if the only way a is related to b and b is related to a is that a and b are the same element from A.

Example For a given universe 𝓤, let the relation ℛ on ℘(𝓤) be defined by (A,B) ∈ ℛ if A ⊆ B for A,B ⊆ 𝓤. Therefore, ℛ is a subset relation. If A ℛ B and B ℛ A, then A = B, which is the definition of antisymmetric. Therefore, the relation is antisymmetric, reflexive, and transitive.

The terms "antisymmetric" and "not symmetric" are not the same, which is demonstrated in the following example:

Example Let A = {1,2,3}, and let the relation ℛ on A be defined by ℛ = {(1,2), (2,1), (2,3)}. Then ℛ is not symmetric, because although (1,2), (2,1) ∈ ℛ, (3,2) ∉ ℛ. It is not antisymmetric either, because although (1,2), (2,1) ∈ ℛ, 1 ≠ 2. The relation ℛ₁ = {(1,1), (2,2)} is both symmetric (1 ℛ 1 => 1 ℛ 1) and antisymmetric (1,1) ∈ ℛ => 1 = 1.

The difference between antisymmetric and not symmetric is that to be antisymmetric, it must be required that all elements in ℛ related to each other interchangeably is due to each component being equal to each other, while being not symmetric requires that not all elements in ℛ are symmetric.

Number of Antisymmetric Relations Given x,y ∈ A, an element of the form (x,y) ∈ A X A, x ≠ y, has three options instead of two for making the relation antisymmetric:

1. Place (x,y) inside ℛ. 2. Place (y,x) inside ℛ. 3. Place neither (x,y) nor (y,x) inside ℛ.

Then, for each subset of A X A of the form {(x,y), (y,x)}, x ≠ y, a total of |A X A – A| subsets of this form, there are three options.

Additionally, for the diagonal elements of A X A of the form (x,x), there are only two options for each of these elements.

Therefore, by the rule of product, there is a total of (2ⁿ)(31/2(n2-n)) possible antisymmetric relations on A.

Irreflexive Relations A relation ℛ on a set A is irreflexive if for all a ∈ A, (a,a) ∉ ℛ.

The difference between irreflexive and not reflexive is being not reflexive requires that not all of the diagonal elements of the form (a,a), a ∈ A, to be in ℛ, while being irreflexive require that all of the diagonal elements of the form (a,a), a ∈ A, to not be in ℛ.

Number of Irreflexive Relations The number of reflexive relations already assumed the diagonal elements of A X A were in the relation and only counted the number of ordered pairs that were not of the form (aᵢ,aᵢ) ∈ A X A.

Similarly with irreflexive relations, assume that any elements in A X A of the form (aᵢ,aᵢ) are not in ℛ. Then only the elements in A X A of the form (aᵢ,aj), i ≠ j, are counted, and each have two options of inclusion inside ℛ or exclusion.

Therefore, the number of irreflexive relations is the same as the number of reflexive relations, which is 2n2-n.

Partial Ordering Relations A relation ℛ on a set A is called a partial ordering relation, or partial order, denoted as ≤, if ℛ is reflexive, antisymmetric, and transitive.

Example Let the relation ℛ on the set ℤ be defined by a ℛ b, or (a,b) ∈ ℛ, if a ≤ b. This subset of ℤ X ℤ is the ordinary "less than or equal to" relation on the set ℤ, which can be also defined on ℝ or ℚ, but not ℂ. This relation is a partial order.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7. This relation is not a partial order, because this relation is not antisymmetric, since it can never be where for n = 7, x = y.

Example Let Σ be the American alphabet and the relation ℛ is defined as a finite strings of letters from Σ by a₁a₂...am ℛ b₁b₂...bn iff m ≤ n and ∀i = 1, 2, ..., m, aᵢ = bᵢ. Then this relation describes the prefix relation of two strings, where the first string's letters must be equal to the second strings letters in the same order for enough letters to satisfy every m letter. Then (xxy,xxydefy) ∈ ℛ but (xx,xyd) ∉ ℛ. This relation is a partial order, because it is antisymmetric. Any prefix that relates to each other interchangeably is assumed to be equal in letters.

Example For a given universe 𝓤, let the relation ℛ on ℘(𝓤) be defined by (A,B) ∈ ℛ if A ⊆ B for A,B ⊆ 𝓤. Therefore, ℛ is a subset relation. If A ℛ B and B ℛ A, then A = B, which is the definition of antisymmetric. Therefore, the relation is antisymmetric, reflexive, and transitive. This relation is also a partial order. Additionally, it is not symmetric, because there can never be two different sets A,B such that A ⊆ B and B ⊆ A unless A = B, which is the definition of antisymmetric.

Partially Ordered Sets A set together with a partial order is called a partially ordered set, or poset, denoted as (P, ≤).

Example The relation ℛ on a set ℤ⁺ where a ℛ b if a | b is a poset, which is denoted as (ℤ⁺, ≤).

Equivalence Relations An equivalence relation ℛ on a set A is a relation that is reflexive, symmetric, and transitive.

Example Let n ∈ ℤ⁺. For x,y ∈ ℤ, the modulo n relation ℝ is defined by x ℛ y, if x – y is a multiple of n, or that n | x – y. With n = 7, then 9 ℛ 2, -3 ℛ 11, (14,0) ∈ ℛ, but (3,7) ∉ ℛ, because 3 is not related to 7. This relation is an equivalence relation.

Example Let A = {1,2,3}. The following are examples of equivalence relations on A: ℛ₁ = {(1,1), (2,2), (3,3)}. It includes all elements of the form (a,a), each element is symmetric to itself, each element is transitive to each other (the intermediaries are omitted). ℛ₂ = {(1,1), (2,2), (2,3), (3,2), (3,3)}. It includes all elements of the form (a,a), each element is symmetric to itself or includes an element that demonstrates this property. (3,2) ∈ ℛ => (2,3) ∈ ℛ. ℛ₃ = A X A is also an equivalence relation.

Smallest and Largest Equivalence Relations For a given set A = {a₁,a₂,...,an}, A X A is the largest equivalence relation on A.

The smallest equivalence relation on A is then the equality relation ℛ = {(aᵢ,aᵢ) | 1 ≤ i ≤ n}.

Equality Relations A relation ℛ on a set A is an equality relation if for all elements of the form (a,a) ∈ A X A are inside ℛ and no other element is present, where ℛ = {(aᵢ,aᵢ) | 1 ≤ i ≤ n}

If ℛ is an equality relation, then ℛ is both a partial order and an equivalence relation.

PDF reference: 364/927

a)

One example could be ℛ = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (3,2)}.

Since all of the elements from A X A of the form (aᵢ,aᵢ) are inside ℛ, the relation is reflexive. Since (1,2), (2,3) ∈ ℛ and (2,1), (3,2) ∈ ℛ, the relation is symmetric. However, for, say, (1,2), (2,3) ∈ ℛ but (1,3) ∉ ℛ, the relation is not transitive.

b)

One example could be ℛ = {(1,1), (2,2), (3,3), (4,4), (2,3)}.

Since all of the elements from A X A of the form (a,a) are inside ℛ, the relation is reflexive. Since any elements of the form (x,y), (y,z) (x,z) are inside ℛ, the relation is transitive. However, since (2,3) ∈ ℛ but (3,2) ∉ ℛ,  the relation is not symmetric.

c)

One example could be ℛ = {(1,1), (1,2), (2,1)}. Since any elements of the form (x,y), (y,z) (x,z) are inside ℛ, the relation is transitive. Since (1,2), (2,1) ∈ ℛ, the relation is symmetric. However, since not all of the elements in A X A of the form (a,a) are inside ℛ, the relation is not reflexive.

**not completed

a)

The relation is reflexive, since the integer property a | a holds for some a ∈ ℤ⁺. The relation is antisymmetric, since the only way a | b and b | a is if a = b. The relation is transitive, since the integer property a | b, b | c => a | c holds for some a,b,c ∈ ℤ⁺.

b)

The relation is not reflexive, since the integer property a | a does not hold for a = 0. The relation is not symmetric, since for only some elements in ℛ, such as a = -x and b = x for some x ∈ ℤ, a | b and b | a holds. The relation is transitive, since the integer property a | b, b | c => a | c holds for some a,b,c ∈ ℤ.

c)

The relation is reflexive, since A ⋂ C = A ⋂ C. The relation is symmetric, since A ⋂ C = B ⋂ C => B ⋂ C = A ⋂ C. The relation is transitive, since if A ⋂ C = B ⋂ C and B ⋂ C = D ⋂ C, then A ⋂ C = B ⋂ C = D ⋂ C.

e)

The relation is irreflexive, since x + x = 2x, which is even. The relation is symmetric, since x + y = y + x. The relation is not transitive. Let x = 2, y = 3, z = 4. x + y = 5 (odd), y + z = 7 (odd), but x + z = 6 (even).

f)

The relation is reflexive, since x – x = 0, and 0 is even. The relation is symmetric, since x – y = y – x = ±z, where z is even. The relation is transitive. x – y = 2k, for some k ∈ ℤ. y = x – 2k y – z = 2k', for some k' ∈ ℤ. x – 2k – z = 2k' x – z = 2k' + 2k = 2(k' + k), which is even.

**h)

The relation is reflexive, since for (a,a), a ≤ a, then (a,a) ℛ (a,a). The relation is antisymmetric (?). The relation is transitive, since for a ≤ c ≤ g, (a,b) ℛ (c,d), (c,d) ℛ (g,h) => (a,b) ℛ (g,h).

For the above question, a) is a partial order, and c) and f) are equivalence relations.

a)

False. Let A = {1,2} and ℛ = {(1,2), (2,1)}. |A| = |ℛ| = 2, yet ℛ is irreflexive.

b)

For reflexivity, true. For ℛ₂ to be a proper set of ℛ₁, and ℛ₁ is reflexive, then ℛ₂ must be reflexive. For symmetry, false. Let ℛ₁ = {(1,2), (2,1)} and ℛ₂ = {(1,2), (2,1), (3,2)}. For antisymmetry, false. Let ℛ₁ = {(1,2), (2,3), (4,5)} and ℛ₂ = {(1,2), (2,1), (2,3), (4,5)}. For transitivity, false. Let ℛ₁ = {(1,2), (2,3), (1,3)} and ℛ₂ = {(1,2), (2,3), (1,3), (2,1)}.

a)

number of reflexive relations on A = number of possible subsets in A X A of the form (aᵢ,aj), i ≠ j, since all elements in A X A of the form (aᵢ,aᵢ) are counted = 2n2-n = 2¹²

b)

number of symmetric relations on A = number of possible subsets in A X A of the form (aᵢ,aᵢ) (diagonal entries in A X A do not affect symmetry) · number of possible subsets of the form {(aᵢ,aj), (aj,aᵢ)}, i ≠ j, (the elements that satisfy the definition of symmetry) = (2ⁿ)(21/2(n2-n)) = 21/2(n2+n) = 2¹⁰

**not completed