Questions tagged [equivalence-relations]

For questions about relations that are reflexive, symmetric, and transitive. These are relations that model a sense of "equality" between elements of a set. Consider also using the (relation) tag.

Filter by
Sorted by
Tagged with
1
vote
1answer
18 views

How many equivalence classes does the following equivalence relation (over permutations) have?

Let $n\in\mathbb{N}$. Consider the set of all permutations over $n$. Two permutations $\pi_1 = i_1..i_n$ and $\pi_2 = j_1..j_n$ are not equivalent if either $i_n i_1$ appears in $\pi_2$ (that is, $\...
0
votes
1answer
22 views

Equivalence classes for a relation between integers

I have the following relation in $\mathbb Z$: $x \sim y$ iff $x-y$ is a multiple of $4$. How do I approach this?
1
vote
1answer
29 views

Suppose $[a], [b] \in \mathbb{Z}_n$ and $[a]\cdot[b] = [0]$. Is it necessarily true that either $[a] = [0]$ or $[b] = [0]$?

Let $n \in \mathbb{N}$. Let $R$ be the equivalence relation $\equiv \pmod{n}$. Suppose $[a], [b] \in \mathbb{Z}_n$ and $[a]\cdot[b] = [0]$. Is it necessarily true that either $[a] = [0]$ or $[b] = [0]$...
0
votes
0answers
22 views

How to find the equivalance class of an equivalance statement?

im fairly new to math and im trying to find all elements of equivalance class [-1] and [4/5] for the following equivalance relation For a, b, c, d ∈ Z with b, d ≠ 0: a/b R c/d ⇔ ad = bc. Ive ...
1
vote
2answers
14 views

Showing that a relation is neither an equivalence relation nor a partial order

Say we have a relation $R$ on $\mathbb{Z} \times \mathbb{Z}$ such that $(a, b) R (c, d)$ if $a^2 + b^2 \leq c^2 + d^2$ So to prove that $R$ is not an equivalence relation we need to show that $R$ ...
1
vote
0answers
16 views

Equivalence relation in a simple directed graph $D$

I have written my proof, but I'm still not sure if it's rigth: Determine if for all directed graphs $D$ the following relation $R$ defined in $V(D)$ is an equivalence relation: $xRy$ if and only if $...
1
vote
1answer
25 views

Show that $P$ is a partition of the corresponding set $A$ and define the equivalence relation induced by partition $P$.

$A = \mathbb N$ and $ P = \{ \{ m \in \mathbb N: m \ \ \text{is a multiple of} \ \ 3\}, \{ m \in \mathbb N: m \ \ \text{is not a multiple of 3}\} \} $. How can I define the equivalence relation ...
0
votes
1answer
17 views

Union of equivalence relation, problem If R ∪ S is an equivalence relation on A, then R and S are equivalence relations on A.

Let A be a non-empty set and let R and S be relations defined on A. If R ∪ S is an equivalence relation on A, then R and S are equivalence relations on A. how can i prove it? i think it is not ...
1
vote
1answer
33 views

Equivalence relation proof, problem $x∼y \iff x^2 − 2x + 1 = y^2 + 4y + 4$

Determine if the following relationships are equivalent. If they are, determine the equivalence classes, give a set of indices and the quotient set. Sketch out the graph of each relationship (whether ...
0
votes
1answer
26 views

Is $G=\{(x,y)\in \mathbb{Z}\times\mathbb{Z}:x+y<4\}$ irreflexive?

Let $G=\{(x,y)\in \mathbb{Z}\times\mathbb{Z}:x+y<4\}$ Is $G$ irreflexive? I know $<$ is an irreflexive relation. But how to show it? How do I do this? The Reflexive and Irreflexive property ...
0
votes
2answers
18 views

List one of three properties of an equivalence relations

I have the following question and answers: Let $A = \{1,2,3,4\}$. Write down $R \subseteq A x A$ which has one of the three properties of an equivalence relation (3 cases). The official answers for ...
0
votes
1answer
11 views

Definition of the equality refered by the definition of a partial order

A partial order $≤$ on a set $P$ must satisfy the following properties: Reflexivity: For all $a \in P$, $a ≤ a$ Anti-symmetry: For all $a,b \in P$, $a ≤ b \land b ≤ a → a = b$ Transitivity: For all $...
1
vote
0answers
36 views

The sets of all equivalence relations and of all partitions does not exist

Statement The sets of all equivalence relations and of all partitions does not exist. Proof. First of all we observe that the idetity relations $\text{Id}$ is an equivalence relations for ...
0
votes
1answer
35 views

Prove an equivalent norm

Consider $g\in C[0,1]$ a strictly positive function and bounded away from zero, prove $\|f\|_g=(\int_0^1g(x)|f(x)|^2dx)^{\frac{1}{2}}$ is equivalent to $\|f\|=(\int_0^1f^2(x)dx)^{\frac{1}{2}}$. I ...
6
votes
1answer
59 views

What do you call a relation that isn't finer than any equivalence, besides the full relation?

In other words, this is a relation whose "equivalence closure" is the full relation. The term "weakly connected" comes to mind naturally, since if you draw a directed graph, with a vertex coming from $...
2
votes
2answers
39 views

Equivalence Relations: Understanding Compatibility

Synopsis My textbook, near the end of the section on equivalence relations, mentions the problem of "defining functions on a quotient set". Specifically, assume that $R$ is an equivalence relation on ...
1
vote
1answer
86 views

Could a limiting result (in terms of convergence) imply an equivalence relation?

Let $(X_n)$ be a martingale and a uniformly integrable collection of random variables. Given a filtration $(\mathcal{F}_n)$, given that $\Phi\in\mathcal{F}_m$ and $X_n\rightarrow X_{\infty}$ in $\...
0
votes
1answer
25 views

Why the homegeneous relation $\mathcal{R}$ over a set $E$ below, isn't transitive? I concluded that it was a transitive property.

Why the homegeneous relation $\mathcal{R}$ over a set $E$ below, isn't transitive? I concluded that it was a transitive property. A couple has 5 children: Andrew, Billy, Carl, Dariel and Elizabeth: ...
0
votes
0answers
25 views

Determine if for all directed graphs $D$ the following relation R defined in $V (D)$ is an equivalence relation

Determine if for all directed graphs D the following relation R defined in $V (D)$ is an equivalence relation: $xRy$ if and only if $x = y$ or there is an $xy$-path directed. I don't seem to ...
-1
votes
2answers
14 views

Equivalence relation and clases [closed]

Let R ⊆ Z × Z be the equivalence relation on Z defined by R = {(a, b) : a = b + kn for some k ∈ Z}. For a ∈ Z we have [a] = {b ∈ Z : (a, b) ∈ R}. How to show that if [a] ∩ [b] ≠ ∅ then [a] = [b]?
1
vote
1answer
44 views

Question re the equivalence relation used to solve the „infinite hat puzzle“

The infinite hat puzzle starts with an infinite sequence of prisoners wearing either black (0) and white (1) hats. One introduces an equivalence relation on sequences of hats $x, y$ as follows: ...
1
vote
1answer
26 views

Determine the equivalence classes on the relation a - b is in H where H = {4k : k is in Z}

Let H = {4k : k ∈ Z}. A relation R is defined on Z by aRb if a − b ∈ H. (a) Show that R is an equivalence relation. (b) Determine the distinct equivalence classes. A) aRa if a - a is in H. Thus a ...
1
vote
2answers
36 views

Prove or disprove that R is an equivalence relation

A relation R is defined on Z by xRy if x · y ≥ 0. Prove or disprove the following: (a) R is reflexive (b) R is symmetric (c) R is transitive (a) If xRx then x*x >= 0 for all x in Z. This is true ...
2
votes
1answer
30 views

A doubt on a passage from the proof of Doob's First Martingale Inequality in Jacod-Protter

I quote Jacod-Protter THEOREM Let $M=(M_n)_{n\geq0}$ be a martingale or a positive submartingale and $M_n^*=\sup_{j\leq n}|M_j|$. Then \begin{equation} \mathbb{P}(M_n^* \geq \alpha) \leq \frac{\...
1
vote
2answers
20 views

Listing the equivalence classes of a specific relation on a set

Say we have the set $S=\{1, 2, 3, ..., 20\}$ and we define our relation (R) as For every $x, y \in S$, $xRy$ iff for every prime $p, p | x \iff p | y$ This relation is an equivalence relation (as ...
0
votes
1answer
65 views

Cardinality of a quotient set of [0,1]

Let $[0,1] \subset \mathbb{R}$. Let $x,y \in [0,1]$ and $q \in \mathbb{Z}$, $k \in \mathbb{N}$. Define the equivalence relation $$x \sim y \iff x-y = \frac{q}{2^k}$$ for some $q,k$. How do I find ...
0
votes
3answers
43 views

Find the cardinality of the quotient of $\mathbb R$ in respect to R

R is an equivalence relation defined as $xRy \Leftrightarrow a - b$ is an integer. What is the cardinality of the quotient of $\mathbb R$ in respect to R? How would you prove it? I thought about a ...
1
vote
3answers
51 views

Show that $a\sim b \iff 5a+5b\equiv 0\bmod10$ is an equivalence relation

Let $R$ be the relation on $\mathbb Z$ defined by $$ a\sim b\text{ if and only if } 5a+5b\equiv 0\bmod10 $$ Show this is an equivalence relation. Using that $10\mid 5(a+b)$ if and only if $2\mid ...
2
votes
1answer
32 views

Equivalence between spin-1/2 and fundamental representation of SU(2)

$V_j=$ polynomials functions on $\mathbb{C}^2$, that are homogeneous of degree $2j$. Could any one tell me how $U_{\frac{1}{2}}$ is equivalente to $\Gamma$? What I know about a representation of $SU(...
0
votes
2answers
41 views

Prove that $\{(x,y)\in \mathbb{Z}\times\mathbb{Z}: x^2\equiv y^2 \!\!\!\mod \!\!4\}$ is an equivalence relation [duplicate]

I'm trying to prove that the relation R on $\mathbb{Z}$ is an equivalence relation, where R is defined by: $$\{(x,y)\in \mathbb{Z}\times\mathbb{Z}: x^2\equiv y^2 \!\!\!\mod \!\!4\}$$ I know I need ...
-1
votes
0answers
23 views

Equivalence between representations in U(1)

How to proof that any complex 1-dimensional representation of U(1), that is, a homomorphism $\Gamma: U(1) \rightarrow GL(\mathbb{C})$; is equivalent to one of the representations $\rho_{n}$, given by: ...
4
votes
1answer
29 views

Another Hadamard matrix of order 4?

Wikipedia states that there is, up to equivalence, a unique Hadamard matrix of order 4, namely $$ \def\p{\phantom+} \begin{pmatrix} \p1&\p1&\p1&\p1 \\ \p1&-1&\p1&-1 \\ \p1&...
1
vote
0answers
43 views

Equivalance relation for a mapping

I have an assignment to solve which is related to Equivalence relation of a mapping. The following picture will show you the content of the question. Actually, for the question a, it can be easily ...
0
votes
1answer
24 views

Let $\sim$ be a relation on set $\mathbb{N}\times\mathbb{N}$ defined by $(x,y)\sim(z,w)$ if $xw=yz$. Prove that $\sim$ is an equivalence relation.

I start by saying, let $(x,y)\in\mathbb{N}\times\mathbb{N}$. Since $xy=xy$ we have $(x,y)\sim (x,y)$ and $\sim$ is reflexive. Let $(x,y),(z,w)\in\mathbb{N}\times\mathbb{N}$ and assume $(x,y)\sim(z,w)...
0
votes
0answers
24 views

$\lim_{n \to \infty} \frac{\lg(1 + n)}{n} = \lim_{n \to \infty} \frac{1}{1 + n}$

I have found this in part of a proof from https://walkccc.github.io/CLRS/Chap03/3.2/, question 3.2-5: $\lim_{n \to \infty} \frac{\lg(1 + n)}{n} = \lim_{n \to \infty} \frac{1}{1 + n}$ I'm not able ...
0
votes
1answer
39 views

Define $a \sim b$ if $a - b$ is an integer in $\Bbb R$. Show that ${}\sim{} $ is an equivalence relation. Show the classes of equivalence as well.

Define $a \sim b$ if $a - b$ is an integer in $\Bbb R$. Show that ${}\sim{} $ is an equivalence relation. Show the classes of equivalence as well. Here's my work. Am I correct? I also do not ...
0
votes
3answers
46 views

Let A = {a, b, c} and R = {(a, a), (b, b), (c, c)}. Why is this statement considered equivalence relations? [closed]

Why is the above statement considered equivalence relations? I understand that (a,a) in that set has met the conditions to be considered Reflexive and Symmetric. However, I couldn't see the relations ...
1
vote
2answers
22 views

Prove that given a partition $\mathcal{P}$ of a set $A$ nonempty, there exists a unique equivalence relation on $A$ from which it is derived

Prove that given a partition $\mathcal{P}$ of a set $A$ nonempty, there exists a unique equivalence relation on $A$ from which it is derived sol: Let $\mathcal{P} $ be the partition $\{ A_{\...
-1
votes
1answer
20 views

Define a relation $\sim$ on $\mathbb{R}$ by the rule $x \sim y$ if $x - y \in \mathbb{Q}$. List 5 elements of the equivalence class $[\pi]$

Part(a):List 5 elements of the equivalence class $[\pi]$ I have that $[\pi]=\{x\in \mathbb{R}\mid xR\pi\}=\{x\in \mathbb{R}\mid x-\pi\in\mathbb{Q}\}=\{\pi\}$. Not sure this is correct because there ...
2
votes
2answers
136 views

Let $\sim$ be an equivalence relation on a set $A$ and let $a, b, c \in A$. Prove that if $a \in [ b ]$ and $c \notin [ a ]$, then $c \notin [b]$.

Let $a,b\in A$, and assume $a \sim b$. Let $c\in [a]$. This means $c\sim a$. Since $c\sim a$ and $a\sim b$, so therefore $c\sim b$, which means $c\in [b]$. Would this be the correct way to show a ...
0
votes
0answers
21 views

Define $R$ on the set $\mathbb{Q}^+$ by $p\ R\ q$ if $\dfrac{p}{q} = 2^m$ for some integer $m$. Find 3 elements of the equivalence class $[ 7 ]$

Part (a): Find 3 elements of the equivalence class $[ 7 ]$. Justify your answer. I have so far $[7]=\{p\in\mathbb{Q} \mid pR7\}$=$\{p\in\mathbb{Q}\mid\frac{p}{7}=2^m\}$. Part (b): Find 3 element of ...
0
votes
0answers
20 views

Showing that a function of sets is bijective

Let $x\sim _{0=1} y \iff x=y \text{ or } x,y\in \{0,1\}$ be a relation in $[0,1]$ and $x\sim _{\mathbb{Z}} y \iff \exists n \in \mathbb{Z} : x=y+n$ a relation in $\mathbb{R}$. I proved that both ...
1
vote
1answer
26 views

Let $n \in \mathbb{Z}$ with $n > 1$. Prove that $a \equiv b \pmod{n}$ is an equivalence relation on $\mathbb{Z}$.

For reflexive: Let $a\in\mathbb{Z}$. This means $a \equiv a(mod n)$, which can be written as $n\mid a-a$. There is an integer $k$ such that $a-a=nk$. I know we need to find if there is a $k \in \...
0
votes
1answer
26 views

How can i show that $b-a = d-c$ is transitive?

Let R be a binary relation on the set of ordered pairs of integers such that $R={(a,b),(c,d))| b-a=d-c} $. Show that R is an equivalent relation. What I got so far is this, i'm not sure if its right,...
0
votes
1answer
17 views

Biconditional in equivalence relation proof?

Not too sure how to approach this. Say I am given this: All $x, y \in\mathbb{Z}, xRy \iff y = x + 6$ or $y = x - 6$ Question is to check whether this is an equivalence relation. To approach this ...
0
votes
1answer
26 views

Showing that $x \sim _{0=1} y$ is an equivalence relation

Let $x \sim _{0=1} y \iff x=y \text{ or } x,y\in \{0,1\}$ be a relation on $[0,1]$. I have to show that this is indeed an equivalence relation. I think that's not really hard If my argumentation is ...
0
votes
2answers
24 views

How to prove the uniform equivalence is indeed an equivalence relation on the class of metrics on X

May I ask a homework question? I'm just wandering the equivalence relation is defined on two sets while the uniformly equivalent is defined on two metrics. How can they be equal? And how to prove that?...
0
votes
1answer
31 views

Prove the cardinalities of the equivalence classes are the same.

I have proof/idea but just wanted to get any extra advice. Prove that given any $k \in \mathbb{N}$, the equivalence relation defined by $a \sim b \iff a \equiv b$(mod k) yields equivalence classes ...
2
votes
2answers
26 views

Quotient Topology, equivalence relation. I need help to prove if X is homeomorphic to X/~

Let $X = [0,3] \subset\mathbb{R}$ and consider the following equivalence relation: $$ x\sim y \Leftrightarrow x=y \vee x,y \in [1,2]$$ and call $Y = X/\sim$. (1). Establish if $Y$ is ...
0
votes
1answer
40 views

Define a relation R on R by xRy if and only if y − x ∈ Z.

Define a relation $R$ on $\mathbb R$ by $xRy$ if and only if $y − x \in \mathbb Z$. (a) Show that $R$ is an equivalence relation on $\mathbb R$. (b) Describe the set of all $x \in \mathbb R$ which ...

1
2 3 4 5
48