For reflexive, symmetric and transitive relations. Use it with the tag (relations).

learn more… | top users | synonyms

1
vote
3answers
50 views

Proving equivalence relation for 7 | (3a + 4b)

I know this might be quite trivial, but I just can't seem to figure out how to prove $$R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : 3a + 4b \text{ is divisible by } 7\}$$ is a symmetric relation, ...
1
vote
0answers
52 views

Equivalence of Group Actions, Transitivity, and Conjugate Subgroups

Some Preliminary Definitions and Properties: Actions of a group $G$ on sets $X$ and $Y$ are equivalent if the corresponding action of $G$ on maps from $X$ to $Y$ fixes some bijection. In this case, ...
-2
votes
1answer
62 views

Find the distinct equivalence classes

Let $B = \{0,1,2,3,4\}$ and let $\{0\},\{1,3,4\},\{2\}$ be a partition of $B$ that induces a relation $Q$. Find the distinct equivalence classes of $Q$.
0
votes
1answer
17 views

proof or deproof linear equivalence of X, X is an amount.

Again I am stuck at some proof. I need to proof or deproof that for all linear equivalences: R:(X,X) is R = So far I think it is correct because we get symmetry and linearity, but I have ...
0
votes
0answers
125 views

Equivalence relation for strings

Let R be the relation consisting of all pairs (x,y) such that x and y are strings of uppercase and lowercase English letters with the property that for every positive integer n, the nth characters in ...
-1
votes
1answer
36 views

Connections between Posets and WQO's

Here is the question that I posted on the Mathematics Chat Room that I was unable to find an answer to: Question: Under what conditions/properties is a poset ever a wqo (well-quasi-order)? Can we ...
2
votes
1answer
24 views

Proof: Sum / Intersection of family of equiuvalence relations is equivalence relation

I have to check if sum and intersection of family of equivalence relations is equivalence relation. Here is the exercise: Let $\mathcal{R}$ be a family of equivalence relations defined on some set ...
3
votes
1answer
54 views

Is $xRy \iff x+y = 0$ an equivalence relation?

$R$ is a relation on real numbers. $xRy \iff x+y = 0 $. Is it an equivalence relation? My answer is no proof: -(Reflexive) let $x = a$ , $aRa \iff 2a=0$. Since $2a = 0$ doesn't hold for every real ...
1
vote
1answer
36 views

How to prove an equivalence relation with more than 2 variables?

Let $R$ be a relation of positive integers $$((a,b),(c,d)) \in R \iff ac = bd.$$ Prove that $R$ is an equivalence relation. So I need to prove that this relation is reflexive , transitive and ...
0
votes
3answers
17 views

Show that $(H, \circ)$ is a subgroup of the group $G$

Question: Let $G$ be a group and $H$ be a nonempty subset of $G$. A relation $\rho$ defined on $G$ by ``$a\rho b$ if and only if $a\circ b^{-1}\in H$" for $a,b\in G$, is an equivalence relation on ...
1
vote
0answers
69 views

Symmetric closure of the reflexive closure of the transitive closure of a relation

Give an example to show that when the symmetric closure of the reflexive closure of the transitive closure of a relation is formed, the result is not necessarily an equivalence relation. My attempt ...
1
vote
1answer
68 views

How to proof that nested intervals are an equivalent relation?

I want to show that a relation on the space of all sequences of nested intervals is an equivalence relation. Definition: Let $[a_n,b_n]_{n\in\mathbb{N}}$ and $[c_n,d_n]_{n\in\mathbb{N}}$ be two ...
1
vote
2answers
32 views

Equivalence relations on metric spaces

Let $d:X\times X \rightarrow \mathbb{R} \cup \{\infty\}$ be a metric on the set X. I should prove that $d(x,y)\neq \infty$ is an equivalence relation but I'm not sure what this expression means. ...
1
vote
1answer
25 views

What is the empty relation?

I was reading the Wikipedia article on equivalence relations and one section says that "the empty relation R on a non-empty set X is vacuosly symmetric and transitive but not reflexive." What is the ...
0
votes
1answer
93 views

Show that a relation is equivalent if it is both reflexive and cyclic.

A relation $R$ on set $X$ is called cyclic if whenever both $xRy$ and $yRz$ then $zRx$ where $x,y,z\in X$. Show that a relation on $X$ is an equivalence relation if and only if it is both reflexive ...
2
votes
1answer
44 views

Describing Distinct Equivalence Classes of a Relation

Suppose that $R$ is a relation on the set of complex numbers $\mathbb{C}$. The relation $R$ is defined as follows: For any two complex numbers $w,z \in \mathbb{C}$, $$w R z \Leftrightarrow ...
-1
votes
2answers
70 views

Is the set $\Bbb Q$ a quotient set of $\Bbb Q^*$?

Let $\Bbb Q^*=\{\frac a b: a\in \Bbb Z, b\in \Bbb N\}$. From this definition we can see $c=\frac 2 3$ and $d=\frac 4 6$ are elements of $\Bbb Q^*$. Claim: $$\frac 2 3\neq \frac 4 6$$ Proof: ...
1
vote
1answer
62 views

Is “to be conjugate” is an equivalence relation?

Let denote $P_x$ the minimal polynomial of $x$ over a field $K$. We say that $x$ and $y$ are conjugate if $P_x(y)=0$. Is "to be conjugate" is an equivalence relation ? The question behind this ...
0
votes
0answers
58 views

How many distinct strict ordinal 2x2x2 games exist?

Consider the same type of strict ordinal games as described in How to simply show that there are "78 'strict ordinal' 2x2 game matrices" and add a third player with two strategies ...
1
vote
1answer
51 views

Equivalent classes of similar/equivalent $n\times n$ matrices

Is there a natural way to find describe all the equivalence classes of $F^{n\times n}$ under equivalence, F an arbitrary field? Here equivalence is just the normal definition: $A$ is equivalent to $B$ ...
0
votes
0answers
45 views

find the Equivalence classes of this equivalence relation

Is this correct? Let R and S be the equivalence relations on Z X Z defined by ((a,b),(c,d)) ∈ R if and only if ab=cd and ((a,b),(c,d)) ∈ S if and only if ad=bc Find the equivalence class ...
0
votes
0answers
44 views

Show that multiplication $[(x, y)] * [(n,m)] = [(xn + ym, xm + yn)]$ is also well- defned.

I'm having a bit of trouble on this proof. It's part of the construction of the integers. $R$ is the relation, $\mathbb{N}$ the natural numbers, $((x,y),(n,m)) \in ...
0
votes
2answers
27 views

Similarity transformation-proof of equivalence

I am getting stuck with following problem: Show that \begin{align} \dot{x} = f(x/t) \end{align} is equivalent to \begin{align} \dot{y} = (f(y) − y)/t \end{align} using the transformation ...
0
votes
1answer
28 views

$a^2 \equiv b^2$ mod 4 equivalence classes.

so we have the relation $a^2 \equiv b^2$ mod 4. And to find equivalence classes we say b or a = 0 so $a^2=4k$ so $a=+-2\sqrt{k} $ so all even numbers. But when we get to a=1 then $a^2=4k+1$ after ...
4
votes
1answer
38 views

Are there any distinct $a, b$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime?

Are there any distinct $a, b \in \mathbb{N}$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime for all $x \in \mathbb{N_0}$? I can show there are no coprime $a,b$ using Dirichlet's theorem: ...
1
vote
2answers
26 views

Describe equivalence classes from equivalence relations

I don't really understand the way to do these. Describe equivalence classes for the following equivalence relations on the given set $S$: (i) $S$ is the set of all points in the plane, and $a\sim b$ ...
1
vote
0answers
24 views

Problem with understanding natural number difference

Proofwiki says the following about difference in natural numbers: In the context of the natural numbers, the difference is defined as: $n−m=p⟺m+p=n$ from which it can be seen that the ...
0
votes
1answer
35 views

Proving bijection is an equivalence relation

If $ M = \{A_n\}_{n=1}^\infty$ is a collection of sets. Consider a relation R on M where $ A_mRA_n$ if there exists a bijection from $A_m$ to $A_n$. Here is my work so far. For symmetry if we assume ...
0
votes
1answer
9 views

Conjecture about a finest equivalence relation

I've thought about finest equivalence relations and came up with a conjecture but I am neither able to prove nor able to disprove it. A hint would be great. Be $M$ a set, be $f$ a bijective function ...
2
votes
2answers
29 views

Prove that $xRy \iff 5 |(x+4y)$ is an equivalence relation

Prove that $xRy \iff 5 |(x+4y)$ is an equivalence relation. Reflexive: $xRx$, since $x+4x = 5x$, which is a multiple of $5$. Transitive: Suppose $xRy$ and $yRz$. Then $$x+4y=5k_1,\quad y+4z = ...
-2
votes
2answers
66 views

Prove or disprove this is an equivalence relation

Let $R$ be a relation defined on the set $\Bbb N$ by $a R b$ if either $a|2b$ or $b|2a$. Prove or disprove: $R$ is an equivalence relation. I able to prove reflexive and symmetric. I understand that ...
0
votes
1answer
22 views

fine the inverse of $[2]$ and $[23]$ in$ \mathbb{Z}_{41}$

I know the inverse of [23] is [23] * [25] = 575 575 congruent to 1 mod 41 [25] is the inverse I have started the other one but I am doing something wrong I got [2] * [41] = [82] = [0] 82 ...
1
vote
2answers
85 views

How many distinct equivalence classes does this equivalence on rationals have?

Let $$A = \{ r\in \mathbb Q \mid \exists p\in \mathbb Z,\text{ and $q\in \mathbb Z$, with $p$ even and $q$ odd, and $r = p/q$} \}$$ For example, $A$ contains such $2/9, 16/(-34)$, and $4$. $A$ does ...
0
votes
1answer
10 views

Partition inducing equivalence

In NPTEL Lecture 23 on Discrete Mathematics, the professor proves that every partition induces equivalence. But is it necessary that the elements in the partition blocks are necessarily reflexive ...
0
votes
0answers
29 views

Showing relation is transitive $(a,b) \in \mathcal R \Leftrightarrow 2|(a+b)$

Let $\mathcal R$ be the relation on natural numbers defined by $(a,b) \in \mathcal R \Leftrightarrow 2|(a+b)$ Show it is transitive.
0
votes
1answer
45 views

Why does $xRy$, where $R$ is equivalence relation, imply that $[[x]]_R=[[y]]_R$?

We have two objects, $x$ and $y$. Let there be an equivalence relation $R$ between them, such that $xRy$. How does this imply that their equivalence classes, $[[x]]_R$ and $[[y]]_R$, are equal? A ...
0
votes
2answers
43 views

Equal equivalence classes proof

Let there be two sets $A$ and $B$ and let their Cartesian product be $A{\times}B$. Let there be an equivalence relation $R:R\,{\subset}\,A{\times}B$. Let's define an equivalence class now: ...
0
votes
0answers
26 views

How do the equal equivalence classes under the relation defined below imply the following?

First, we have a commutative semigroup $(S,*)$. Now let $(S_1,*_{↾_1})$ and $(S_2,*_{↾_2})$ be its two subsemigroups, with $*_{↾_1}$ and $*_{↾_2}$ being the restrictions of $*$ to $S_1$ and $S_2$. ...
0
votes
2answers
28 views

Equivalence relations and binary operations

Let S be the set of all sequences of real numbers. Define a relation $\sim$ on S by $\{x_n\} \sim \{y_n\}$ if $x_n - y_n \rightarrow 0$. (i) Prove that $\sim$ is an equivalence relation. (ii) Let ...
0
votes
1answer
39 views

How to describe conjugacy classes for elements of $\mathbb{Z}_{2} \times \mathbb{Z}_{2}$? [closed]

I am totally new to mathematical analysis and just learn what group is. In a problem it says to describe conjugacy class for $\mathbb{Z}_{2} \times \mathbb{Z}_{2}$. But what is the conjugate class ...
0
votes
1answer
18 views

Composing equivalence relations

I´ve come across a problem regarding relation composition. The task is to show, whether a composition of two equivalence relations on a set X is again an equivalence on the set X. I´ve tried ...
4
votes
1answer
44 views

Lemmata about equivalence relations

We've defined relations and equivalence relations a few days ago at university. I tried to look at them a bit more abstract and came up with two lemmata. I am going to write them down with my proofs ...
1
vote
2answers
28 views

requirement on proposition

I want to draw a conclusion from an equivalent description of a relation. Let $R$ be a relation on a set $M$ with $R \subseteq M \times M$. First I have 2 examples of what I mean: $x \sim_R y ...
1
vote
3answers
117 views

What exactly does it mean to take something modulo an equivalence relation?

For instance, the complex projective space is defined as $\mathbb{C}{\mathbb{P}^n} = \left( {{\mathbb{C}^{n + 1}}\backslash \left\{ 0 \right\}} \right)/ \sim $ Where the equivalence relation is ...
2
votes
1answer
71 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
0
votes
2answers
18 views

Equivalence relations and classes

Let $S = [10]$ (the set containing the integers 1,...,10). Define an equivalence relation R on S by $xRy$ $iff$ $x^2 \equiv y^2$ (mod 5) is an equivalence relation and determine the equivalence ...
0
votes
0answers
46 views

Example of a relation on a finite set

In one of the exercises, I proved that $R^n+1\subseteq R^n$ for all $n \ge1$ But now I need to give an example of relation on finite set such that $R^3 \subsetneq R^2 $ Here $R^3$ =$R \circ R \circ ...
0
votes
2answers
35 views

Clarification needed, show it is not an equivalence relation: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$.

A question from HW: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$. Show it is not an equivalence relation. My problem - For instance, how can I even check for ...
0
votes
2answers
33 views

Describing the Partition for a given equivalence relation.

In $\mathbb{R}$ let $a\sim b$ iff $a-b$ exists $\in$ $\mathbb{Q}$. I have already proven that $\sim$ is an equivalence relation. However, the second part of the question asks to describe the ...
0
votes
0answers
38 views

finest equivalence relation classes

"$\sim$" is the finest equivalence relation on $M = \mathbb{Z}^2$ with $(a,b) \sim (a,-b)$, $(a,b) \sim (b,a)$ and $(a,b) \sim (a,a+b)$ for all $a,b \in \mathbb{Z}$. My task is to find every ...