Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [equivalence-relations]

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

1
vote
0answers
9 views

Quotients by commuting equivalence relations

Let $U,V$ be equivalence relations on a set $A$. There's a canonical function $$A/(U \wedge V) \to A/U \times_{A/(U \vee V)} A/V$$ given by $[a]_{U\wedge V}\mapsto ([a]_U,[a]_V)$. Here $U\wedge V$ ...
3
votes
1answer
46 views

What uniquely characterizes equivalence classes of eventually equal binary sequences?

Let $X$ be the set of all infinite binary sequences. (Or we can think of them as subsets of $\mathbb{N}$ or real numbers between $0$ and $1$.) Let us define an equivalence relation $\sim$ on $X$ by ...
0
votes
1answer
21 views

What does “collect all mutually $R$-equivalnent elements in $A$” mean?

I am reading "Sets, Numbers and Topology" by Masahiko Saito. Let $R$ be an equivalence relation on a set $A$. If we collect all mutually $R$-equivalnent elements in $A$, we get a subset of $A$. ...
0
votes
0answers
11 views

What are sufficient conditions for finitely many equivalence classes of slice contours of surfaces?

Apologies in advance for imprecision of the question. Thanks for improving it. Let M be a compact, connected, orientable surface in three dimensional Euclidean space without boundary and without self-...
-2
votes
0answers
22 views

Check failure that $(a, b) \simeq (c, d) \iff ad = bc$ really is an equivalence relation [on hold]

What happens if a check-proof system fails (or not proof) that this a really equivalence relation $$(a, b) \simeq (c, d) \iff ad = bc$$ related to set $S = \{(x, y) ∈ \Bbb Z × \Bbb Z : y \neq 0\}$ ...
1
vote
3answers
33 views

Classes of an equivalence relation

Let $R$ be the equivalence relation on the real numbers given by $$R = \{(x, y) \in \Bbb R^2: (x−y)(x+y) = 0 \} $$ What are the equivalence classes of $R$? So I wrote that, for every $x \in \Bbb ...
3
votes
0answers
39 views

How to compute the number of equivalence classes under the relation $a\sim b\iff a=x^m b x^n$?

Let $G$ be a finite group. Fix an element $x\in G$, and denote by $\sim$ the equivalence relation on $G$ given by $a\sim b \iff \exists m,n\text{ such that }a=x^m b x^n$. Example: Let $G=\langle(123),...
0
votes
0answers
20 views

Show that $K∩L$ is homeomorphic to $A$, where $K ∩ L = \{\{(a,0),(a,1)\} : a \in A\}$ is a subset of equivalence classes in $[0,1] \times \{0,1\}$.

I'm trying to solve the following question: Let $X$ be a topological space and $A$ a subset of $X$. On $X\times\{0,1\}$ define the partition composed of the pairs $\{(a,0),(a,1)\}$ for $a\in A$, ...
0
votes
1answer
15 views

First Order Stochastic Dominance relation of conditional distributions

Suppose there are two CDF's $F$ and $G$ over the same support, $[0,1]$, and assume that one first order stochastically dominates the other: $$\tag{FOSD 1}F\succsim_{FOSD}G$$ meaning that $F(x)\leq G(x)...
0
votes
3answers
66 views

Is “30 times more likely” equivalent to a “3000% greater probability”?

I am trying to make a persuasive point based on facts and would like to be most accurate / clear in my point. Would "30 times more likely" be equivalent to a 3000% greater probability"
0
votes
1answer
21 views

How to prove an equivalence relation on the unit square?

I saw the following example of an equivalence relation in a topology textbook: Let $X$ be the unit square. Define $\sim$ as follows: $(0,y)\sim(1,y)$ for all $y\in [0,1]$, and for any point $(...
1
vote
1answer
102 views

Countability of arbitrary classes $\mathcal{A}$ of subsets of $\Omega$ and the partitions of $\Omega$ induced by $\mathcal{A}$

Partitions of $\Omega$ I denote a partiton of $\Omega$ to be $\Omega_{\tau}$ which satisfies $\Omega=\cup_{\beta} B_{\beta}$ for $B_{\beta}\in\Omega_{\tau}$ and $B_{\beta}\cap B_{\beta'}=\emptyset$ ...
0
votes
1answer
36 views

About two sets of the equivalence classes on the same set $A$.

I am reading "Introduction to Algorithms 3rd Edition" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. I am reading section 16.4 "Matroids and greedy methods" now. ...
-3
votes
1answer
47 views

Let $≺$ be a relation on a set $P$, reflexive and transitive. Def. $∼$ on $P$ by $p ∼ q \iff p ≺ q ∧ q ≺ p$. Show $∼$ is an equiv. relation.

Can I get some help on this one? Any solutions? Let $≺$ be a relation on a set $P$ that is reflexive and transitive. Define the relation $∼$ on $P$ by $p ∼ q$ iff $p ≺ q ∧ q ≺ p$. (a) Show $∼$ is ...
-1
votes
1answer
29 views

confused about quotient set

For $a,b\in \mathbb Z$, let $a \sim b \iff (ab>0) \lor (a=b)$. Is $\sim$ an equivalence relation on $\mathbb Z$? If so, find the quotient set. I've already found that $\sim$ is an equivalence ...
3
votes
2answers
51 views

Commensurability of Subgroups

Let $G$ be some group, and let $S_1$ and $S_2$ be some subgroups. Then $S_1$ and $S_2$ are said to be commensurable iff $|S_1 : S_1 \cap S_2|$ and $|S_2 : S_1 \cap S_2|$ are finite. I am trying to ...
0
votes
4answers
38 views

Symmetry, transitivity and reflexivity

I need some help on how to approach this problem. I can't seem to find any examples that help me understand this, so if anyone has an approach example to post I would be very grateful: "Consider a ...
0
votes
1answer
34 views

Given an equivalence relation on B, construct a partition on B

By definiton We know that an equivalence relation has to be: reflexive, symmetric and transitive. But, how can I construct a partition of B (set)?
1
vote
1answer
37 views

showing a relation on $\mathbb Z$ \ $0$ is an equivalence relation

We define a relation on $\mathbb Z \setminus {0}$ where a ~ b iff $0< ab$. How would you show this is an equivalence relation and describe the equivalence classes?
0
votes
3answers
25 views

Equivalence relation involving finiteness of symmetric difference of sets

I'm posting this message so as to know if it would possible to get a hint so as to solve the following problem: A subset $A$ of $\mathbb N$ is related to a subset $B$ of $\mathbb N$ (A%B) if the ...
2
votes
2answers
23 views

Germs: Why is it sensible to define a function on a collection of equivalence classes by its action on each element?

I am following Loring W. Tu in his second edition of 'An introduction to manifolds'. Here is a pdf-copy of the book. On page 87 he defines $C^\infty_p(M)$ as the set of germs of $C^\infty$-functions ...
0
votes
1answer
29 views

Find all equivalence classes?

a) Let S be : S={3,4,5,6,7,8} and the relation ~ defined as m~n if m^2 ≡ n^2 (mod 5). b) Let S be : S={1,2,3,4,5,6,7,8} and the relation ~ defined as m~n if m ≡ n (mod 4). Can someone help me with ...
0
votes
1answer
15 views

Finding how many distinct equivalence classes there are.

Define a relation R on the set of all integers Z by xRy (x related to y) if and only if x-y=3k for some integer k. I have already verified that this is in fact an equivalence relation. But now I ...
0
votes
1answer
15 views

Proving symmetry and transitivity of a relation

Let R be the relation {(1,1),(1,2),(2,2),(1,3),(3,3)} on the set {1,2,3}. I am having difficulty proving that it is symmetrical and transitive. I know for symmetry we have to prove if xRy then yRx (...
2
votes
1answer
45 views

Partition on $Z_p$

I'm trying to understand what is established in Proofs from the Book (from Eigner and Ziegler) concerning the representation of numbers as a sum of two squares. Consider $\mathbb{Z}_p$, $p$ an odd ...
0
votes
1answer
23 views

How do I prove $B_{q} \neq \emptyset$.

Suppose that $\mathbb P$ is the uniform distribution on $[0,1)$. Partition the interval $[0,1)$ into an equivalence class such that $x\sim y$ ($x$ is equivalent to $y$) if $x-y\in\mathbb Q$, the set ...
1
vote
1answer
27 views

Proof equivalence relation with functions

We define 2 function: $f : X \rightarrow X$ and $g : X\rightarrow X$ and we define $ V(f,g) = \{x \in X | f(x) \neq g(x) \} $. Next we define a relation $R$ on the set Fun($X,X$) of all functions ...
-7
votes
1answer
104 views

Why are these three equivalence relations special? [closed]

Consider the set of all possible bivectors $\mathfrak{B}$ in $\mathbb{R}^3$. Then there are three possible equivalence relations. Equipollence: The equivalence relation $(\mathfrak{B}, \sim)$ such ...
1
vote
2answers
38 views

Algebra Chapter 0, exercise 1.3

My question concerns the answer to exercise 1.3: Given a partition $P$ on a set $S$, show how to define a relation $\sim$ on $S$ such that $P$ is the corresponding partition. My answer is: We ...
0
votes
1answer
54 views

If comparativity and reflexivity imply symmetry and transitivity how can the axioms of equivalence be orthogonal?

According to BBFSK a relation with the properties of comparativity and reflexivity satisfies symmetry and transitivity. Comparativity is defined as $x\sim{z}\land{y\sim{z}}\implies{x\sim{y}}$. ...
0
votes
0answers
17 views

Given a subset of $\mathbb{R}^2$, how to graphically determine that it satisfies transitive property?

Given a subset $A$ of $\mathbb{R}^2$ (or in general, a subset of $X\times X$ for any non-empty set $X$), it is usually easy to check if it satisfies reflexive property (when it is a superset of the ...
0
votes
2answers
38 views

What is the definition of a relation?

Let $S$ be a set. An equivalence relation on $S$ is a subset $R\subseteq S\times S$ satisfying that $(s,s)\in R$ for all $s\in S$, $(s,t)\in R \implies (t,s)\in R$, $(s,t)\in R\; \land\; (t,u)\in R\...
3
votes
1answer
74 views

Is Axiom of Choice necessary with this particular quotient set?

Learning rigorous set theory for the first time as a freshman in UNI here. I am working through some problems regarding equivalence relations, where one of such was to prove an isomorphism $\mathbb{R}^...
1
vote
1answer
19 views

Need help finding the equivalence relation!

"Let A be the set of all people in the world, R a relation on A defined by (a, b) ∈ R, if and only if a is a twin of b. Is this relation an equivalence relation? Explain!" An equivalence relation is ...
0
votes
0answers
43 views

Conditions on Metric Spaces for Equivalence Relations

Let $V \subset \mathbb{R}^n$ be a finite volume, and $S\subset V$. Let $d$ be the usual Euclidean metric on $\mathbb{R}^n$: $$ d(x,y) = \sqrt{\sum_i (x_i-y_i)^2} $$ Let $d_S(x)$ denote the distance ...
2
votes
2answers
46 views

The quotient set $\mathbb{Z}/{\sim}$ where $a\sim b \iff$ $a^3 \equiv b^3 \pmod{7}$

Consider equivalence relation $\sim$ on $\mathbb{Z}$ s.t. $\forall a,b\in \mathbb{Z}$: $$a\sim b \iff a^3 \equiv b^3\!\!\!\! \pmod{7}.$$ There are some questions, but I am struggling with: determine ...
0
votes
1answer
26 views

Proving that exists equivalence relation $r$ in set $A$ such that $ |A \setminus r| = n$

I am trying to show that if $|A| = m$ and $0\neq n \le m $ then exists equivalence relation $r$ in set $A$ such that $ |A \setminus r| = n$. Could someone help me deal with it?
2
votes
0answers
43 views

General colimits and filtered colimits in the category of sets

A category $\mathsf{I}$ is filtered if $\mathsf{Ob(I)} \neq \varnothing$, for any $i,j \in \mathsf{Ob(I)}$ there is $k \in \mathsf{Ob(I)}$ and morphisms $f\colon i\to k$ and $g\colon j\to k$...
-1
votes
2answers
72 views

When extending the natural numbers to the integers when is it legal to set a natural number equal to an integer.

My source BBFSK I need to add that natural numbers in this context are defined as starting with 1. I didn't think that would impact the answer, but apparently it does. $n-0$ provides a "bridge" ...
0
votes
3answers
53 views

Does symmetry and transitivity imply reflexivity for nonempty binary relation?

I've seen a few answers to this, like here and but they are not satisfying to me (possibly too advanced). The definitions in my book are as follows: A binary relation $\mathrel{R}$ on two sets $A$ ...
1
vote
1answer
59 views

Proof that $ 1_A \cup s \cdot s \cdot s $ is equivalence relation

I have problem with this task: Proof that $$ 1_A \cup s \cdot s \cdot s $$ is equivalence relation where $r \subset A \times A$ and $r$ is a relation such that $$ \forall_{x,y,z} r(x,y) \wedge r(...
-1
votes
2answers
77 views

If $K= \mathbb Z /2\mathbb Z$ what is meant by $K^2$

I realize that $K= \mathbb Z /2\mathbb Z$ is simply the set of equivalence classes. But I recently came across $K^{2}$ given $K= \mathbb Z /2\mathbb Z$ It is then stated that $K^{2}=\{\{0,0\},\{1,0\},...
-1
votes
1answer
27 views

Is this relation always an equivalence relation? [closed]

Given a relation $R$, and a relation $S$ that is the inverse of $R,\;$ is $S \circ R$ always an equivalence relation?
0
votes
1answer
18 views

Showing a relation is transitive

Problem: Let $A = \{(a,b)\}$, determine whether the relation $R = \{(b,a)\}$ is transitive. Claim: No, $R$ is not transitive. Proof: Since $a,b\in A$ and $a\in R$ but $b,a\notin R$. I am not ...
2
votes
0answers
38 views

The category of vector spaces over $\mathbb{R}$, Vect$_{\mathbb{R}}$, is equivalent to the category of $T$ algebras for some monad $T:$ Set $\to$ Set.

Prove that the category of vector spaces over $\mathbb{R}$, Vect$_{\mathbb{R}}$, is equivalent to the category of $T$ algebras for some monad $T:$ Set $\to$ Set. My attempt: First I know that ...
3
votes
3answers
48 views

Are equivalence classes of subobjects of some X in Set just equivalence classes of subsets of X with a specific cardinality?

I'm trying to understand what would be the subobjects of $\{0, 1\}$. Would they be $\{\emptyset, \{0\}, \{1\}, \{0, 1\} \}$? Or are $\{0\}$ and $\{1\}$ somehow identified together? Because I can map ...
4
votes
1answer
92 views

How many $g$ in a finite group are such that $b=g^{-1}ag$ for given $a\ne b$ in the group?

Given a group $G$, we know that we can set up an equivalence relation among its elements by defining $a \equiv b \Leftrightarrow \exists g \in G|b=g^{-1}ag$ (conjugacy). Let's define $\mathcal{F}_b^{(...
0
votes
1answer
18 views

Can sets A, B and C be transitive or does transitivity hold just for individual relations. Also does missing relation prove this false?

Can sets A, B and C be transitive or can we describe only individual relations as being transitive. Also does missing a single relation between two sets mean we can't describe the relation as ...
0
votes
1answer
33 views

Proof of equivalence relations

I have just started my math class and I think I might not be completely understanding the 3 properties of a equivalence relation: reflexivity, symmetry, transitivity. I have these 2 examples and I ...
2
votes
2answers
65 views

When is a space homeomorphic to a quotient space?

Is the following theorem true? It seems straightforward but I haven't seen it published anywhere, not even as a corollary, so I'm concerned I've missed something. Discussions that introduce quotient ...