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).

0
votes
0answers
24 views

Showing addition and multiplication are well defined under the rational numbers

I'm having a lot of trouble with this homework question Here is the question: Recall that we have the relation "mod n" on the integers where a ≡ b mod n if b-a|n. We call the set of equivalence ...
0
votes
1answer
15 views

Proving that the equivalence of paths is an equivalence relation.

The definition of equivalent paths is as follows : Two paths $f: [a,b] \rightarrow \mathbb{R^n} $ and $g: [c,d] \rightarrow \mathbb{R^n} $ are equivalent if there exist a $C^{1}$ bijection $\phi: [...
1
vote
0answers
20 views

Tangent vectors as equivalence classes of triples and ordinary vectors

I am using this document as a reference on tangent spaces etc. In the section on tangent spaces, the author provides three equivalent definitions of a tangent vector, the first being the intuitive ...
1
vote
0answers
30 views

Showing that the solutions of two problems are equivalent

I have a question regarding the equivalence between the solutions of two mathematical problems. Problem 1 Let $A\equiv \{1,...,N\}$ and let $P: A\rightarrow [0,1]$ such that $P(i)\geq 0$ $\forall i ...
0
votes
2answers
106 views

If R is an equivalence relation, and S is only symmetric and transitive, what is R ∪ S?

I have a question that asks the following: Let R and S be binary relations on a set A. Suppose that R is reflexive, symmetric, and transitive and that S is symmetric, and transitive but is not ...
1
vote
1answer
21 views

Please Explain the Importance of Equivalence Classes in Classifying Groups of Order $2p$

I'm trying to go through the solutions at this link and I'm not exactly understanding the solution for part (d). The question is: Suppose that $G$ does not contain an element of order $2p$. Show ...
0
votes
1answer
43 views

Identification of a Subset to a Point

If $A$ is a subspace of a topological space $S$, we can define a relation $∼$ on S by declaring $$x ∼ x\quad\text{for all}\quad x\in S$$ (so the relation is reflexive) and $$x ∼ y\quad\text{for all}\...
2
votes
1answer
26 views

Showing equivalence relations a=b/a=-b

I have this equivalence relation where $S=\mathbb{R}$ and $a\sim b$ $ \iff a=b$ or $a=-b$ I know this is an equivalence relation and that it is also very simple but I am just confused about how to ...
3
votes
1answer
56 views

Find $H<G$ so that $\{(x, y) | xx^{−1} y^{−1} \in H\}$ is not an equivalence relation on $G$.

The question is as follows: Find an example of a group $G$ with a subgroup $H$ so that $$\{(x, y) | xx^{−1} y^{−1} \in H\}$$ is not an equivalence relation on $G$. I've just been working on this ...
0
votes
1answer
9 views

An equivalence relation that implies another.

I have two equivalence relations $A$ and $B$. If $xAy \implies xBy$, how can I show that $A$ has no fewer equivalence classes than $B$? I'm imagining partitioning a plane with boundaries, and how $A$ ...
-1
votes
3answers
42 views

How to show that the relation $xRy$ if $\sin(x-y)=0$ is transitive? [closed]

"Logically" it seems transitive as if $x-y=k(𝜋)$ and $y-z=k(\pi)$ then $x-z=k'(\pi)$ but how to put it into a good proof? also what would we be its equivalence classes since if it is transitive then ...
0
votes
0answers
19 views

Checking for equivalence relations

Let a relation $R$ be defined on $\mathbb{N}^2$, such that $(a,b)R (c,d)$ if $ad(b+c)=bc(a+d)$. I am able to prove reflexivity and symmetry but I'm not able to prove transivity. The answer is ...
-1
votes
1answer
22 views

Getting the elements of an equivalence class, and total number of equivalence classes

$$\text{Let } A = \{1,2,3,4,...,271\}. \text{Define the relation $R$ on $A \times A$ by:}$$ $$ \text{for any $(a,b)$, $(c,d) \in A \times A$, $(a,b)R(c,d)$ iff $a + b = c+ d$.}$$ $\text{(a) List ...
0
votes
0answers
13 views

Question on congruence modulo m and partitions

I do not really understand what to do with the following problem and would appreciate any help. Let $\Bbb{Z}=\{[0]_6,[1]_6,[2]_6,[3]_6,[4]_6,[5]_6\}. $Consider the purported function $f:\Bbb{Z}_6\...
1
vote
1answer
14 views

Can two utility representations always be connected by a strictly monotonic function?

The Microeconomics Lecture notes by Rubinstein has the following question in Problem set two. Let $U, V: X \to \mathbb{R}$ be two utility representations of the preference relation $P$ (preference ...
2
votes
1answer
23 views

Equivalence relation of group members.

A group of $n\geq 6$ members decide to split up and travel in $n-3$ parties. How many equivalence relations exist on the set of members such that the members in each travel party form an equivalence ...
0
votes
3answers
57 views

Prove that $\sim$ is an equivalence relation

Let $A = \{1, 2, 3,...,9\}$ and let $\sim$ be the relation on $A\times A$ defined by $(a,b) \sim(c,d)$ if $a+d = b+c$. Prove that $\sim$ is an equivalence relation. Really stuck on this question, ...
6
votes
3answers
145 views

What is $\mathbb{Q}$?

When we say set of rationals $\mathbb{Q}$, which of the following does it refer to? $$\left\{\frac{p}{q}~|~p,q\in\mathbb{Z},q\neq 0\right\}$$ or $$\left\{\left[\frac{p}{q}\right]~|~p,q\in\mathbb{Z},...
2
votes
0answers
20 views

$g$-equivalent subspaces

The following definition is from the book Lectures in Abstract Algebra, by Jacobson. Chapter "Witt's theorem". Definition Let $\Re$ be a vector space, let $\mathfrak{S}_1$ and $\mathfrak{S}_2$ be ...
0
votes
1answer
36 views

Equivalence relation on N .(proof)

Let $n,m \in \mathbb N$. Let further $k \in \mathbb N_0$ be such that $km \leq n <(k+ 1)m$. We define the modulo operation $n \pmod{m}$ to be $n \pmod{m}:=n−km$. Now define for a fixed $m \in \...
10
votes
2answers
655 views

How is the relation “the smallest element is the same” reflexive?

Let $\mathcal{X}$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $\mathcal{R}$ on $\mathcal{X}$ by: $\forall A, B \in \mathcal{X}, A \mathcal{R} B$ iff the ...
0
votes
1answer
14 views

Understanding transitive relations on set $\{0,1,2,3\}$

I'm having a hard time understanding the transitive property for the following relation. I believed it to be transitive and I can't determine why it is not: Example 1: $$\{(0,0),(1,1),(1,3),(2,2),(2,...
0
votes
4answers
26 views

Equivalence relation for $X \sim Y \iff X \cap T = Y \cap T$

For the question Let $T$ be a fixed subset of a nonempty set $S$. Define the relation $\sim$ on power set of S by $$X \sim Y \iff X \cap T = Y \cap T$$ Show that $\sim$ is an equivalent relation. ...
0
votes
0answers
35 views

Distribute m=17 cards to n=7 entities

Every entity must receive at least 2 cards and all cards have to be distributed. Only the cards and not the entities are distinguishable. My approach was as follows: Since every entity has to receive ...
2
votes
1answer
34 views

If $a \mid c$ and $b \mid c$ where $a, b, c \in \mathbb{N}$, under what conditions does it follow that $a \mid b$?

The following question is pretty basic, and the underlying idea was used in the "proof" of a statement in this hyperlinked answer to another MSE question. The question is as follows: If $a \mid c$ ...
0
votes
1answer
24 views

How do i approach finding the number of equivalence classes of a relation?

(Question too long to post as title) The question is, Let S = {1,2,3,4,5,6,7,8,9} and let T = {2,4,6,8}. Let R be the relation on P(S) defined by for all X, Y ∈ P (S), (X, Y ) ∈ R if and only if |X − ...
0
votes
1answer
18 views

About equivalence relation

How can I Give an example of an equivalence relation on $\mathbb{R}$ with only 2 equivalence classes .
0
votes
1answer
54 views

Show that the product of nonzero elements of $\mathbb Z_p$ ($p$ prime) is nonzero.

This is the second part of an assignment in which the first part was the following: Show, if $n \in \mathbb{N}$ is not prime, then there exists $[a],[b] \in \mathbb{Z}_n$ such that $[a] \neq [0] \neq ...
1
vote
1answer
19 views

Find equivalence classes: On the power set of $X$ by $A R B \iff A \cup Y = B \cup Y$.

For the question Let $X = \{1, 2, 3, 4, 5\}$ , $Y = \{3, 4\}$. Define a relation $R$ on the power set of $X$ by $A R B \iff A \cup Y = B \cup Y$. How many equivalence classes are there? I am ...
0
votes
0answers
30 views

How single elements belong to partition though they can't satisfy equivalence relation?

Let $A = \{2, 3, 5, 15\}$ and $G$ is the equivalence relation of elements divisible by 3 and $H$ is the equivalence relation divisible by 5. Now the quotient set $A/G = \{\{3, 15\}, \{5\}, \{2\}\},$ ...
0
votes
0answers
44 views

How to think intuitively quotient of quotient set in equivalence relations

If $G$ and $H$ are arbitrary equivalence relations in $A$, prove that $$A/(G\circ H) ≈ (A/G)/(G\circ H/G).$$ How to think $(G\circ H)/G$ intuitively, especially if $(G\circ H)$ is empty set, and ...
1
vote
2answers
20 views

Find Equivalence Classes for the relation $S$ on the set $\mathbb{R}^*$ is definied as $aSb \iff ab > 0$

I am trying to understand how to determine the equivalence classes. I have this question in the book The relation $S$ on the set $\mathbb{R}^*$ is definied as $aSb \iff ab > 0$ The answer in ...
0
votes
1answer
33 views

Form relation inside set $ A = \{1,2,3\} $ so that $\text{R}:\text{A}\leftrightarrow \text{A}$

Problem Form relation inside set $ A = \{1,2,3\} $ so that $\text{R}:\text{A}\leftrightarrow \text{A}$ Attempt to solve I know that $\text{R}:\text{A}\leftrightarrow \text{A}$ is true when ...
1
vote
1answer
56 views

Equivalence Relation Requiring Set of all Sets

I'm trying to formalize the concept os equivalence between optimization problems. Here are the definitions I'm working with: 1) An optimization problem is a pair $(S,f)$ where $S$ is a set and $f\...
0
votes
1answer
18 views

Rigorous Proof of Infinite Number of Equivalence Classes

Let X $=\mathbb{R}$ Let $x \sim y \leftrightarrow x - y \in \mathbb{Z}$. It is intuitively obvious why this would have an inifinite number of equivalence classes. Is there a rigorous way of proving ...
2
votes
2answers
49 views

Problem about components in a compact Hausdorff space

I have the following problem of general topology: In a compact Hausdorff space, define $x\sim y$ if for every continuous function $f:X\rightarrow\mathbb{R}$ with $f(x)=0$ and $f(y)=1$, there exists $w\...
0
votes
1answer
30 views

Prove $R$ is an equivalence relation

Problem: Let $A = \lbrace1,2,3,4,5,6\rbrace$ and $B = \lbrace2,4,6\rbrace$. The relation $R$ on $\mathcal{P}(A)$ defined by $\forall x,y \in \mathcal{P}(A), xRy \Longleftrightarrow x-B = y-B$ Prove ...
0
votes
1answer
37 views

Finding the equivalence classes of a seemingly infinite set

I've encountered this question: $A = \mathbb Z$ and $R = \{\, (x,y) \mid x + x^2 = y + y^2 \,\}$ is an equivalence relation on $A$. What are its equivalence classes? The relation is an equivalence ...
-1
votes
3answers
114 views

Help to prove that: if m ≡ n (mod a) then mb ≡ nb (mod ab)

Question asks to use mathematical language to prove that: if m ≡ n (mod a) then mb ≡ nb (mod ab). Question also says if proving an equivalence, each direction should be clear.
0
votes
1answer
14 views

Equivalence/(Partial order) relation or any other suitable known relations?

Let $G$ be an indirected graph, let $V(G)$ and $E(G)$ be the set of vertices and edges of $G$, respectively. Define a relation $R$ on $G$ as: for all $v\in V(G)$ and $e\in E(G)$, $vRe$ if and only if ...
0
votes
2answers
46 views

How many equivalence relations on S have exactly 3 equivalence classes?

Let S = {1,2,3,4,5,6,7,8}. How many equivalence relations on S have exactly 3 equivalence classes? The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like ...
0
votes
2answers
19 views

Show that the values of F are the equivalence classes of the equivalence relation

I have the relation $aRb \iff f(a)=f(b)$ where $f: X \to Y$ which I know is an equivalence relation. For $y \in f(X)$, define $F(y)=f^{-1}(\{y\})$. How can I show that the values of F are the ...
0
votes
0answers
55 views

How to represent equivalence relation as a function in set theory?

While writing a proof for below statement, I stuck at representing equivalence relation as a function. Let $f : A → B $ be a function and let G be an equivalence relation in B. Prove that the ...
0
votes
0answers
20 views

Name for a poset where incomparability is an equivalence relation

Say I have a partial order $\leq$ on a set $S$. Let me write $a \sim b$ if $a$ and $b$ are incomparable under this order. Is there a name for the following restriction on the partial order? $\sim$ ...
2
votes
2answers
45 views

Proving the difference of two matrices is PSD

Claim: For $x\in \mathbb{R}^n$, we have $\operatorname{Diag}(x) - xx^T \succeq 0$ if and only if $x_i \geq 0 \ \forall i\in [n]$ and $\sum_{i} x_i \leq 1$. Where $\operatorname{Diag}$ denotes the ...
2
votes
1answer
21 views

Equivalence of codes defines a symmetric relation

Two codes $C_1, C_2 \subseteq A^n$ are called equivalent (notation: $\sim$) if there are permutations $\pi \in Sym(A)$ and $\sigma_1, \dots, \sigma_n \in S_n$ such that $$C_2 = \{(\sigma_1(a_{\pi(1)}...
1
vote
1answer
27 views

Ordered Set example. Why is partially ordered?

I am studying these concepts of order for the first time, and I am having a certain difficulty: I define an Order relation in $A=\mathbb{R_{+}^{2}}$ as : $x,y \in A$, $x\geq y \iff x_{1} \geq y_{1}$ ...
-1
votes
1answer
25 views

Error in proving a relation transitive

In the homework solution in the image the professor represents s as a ratio of integers, despite s itself being defined as an integer. Is this allowed? I proved the relation transitive without using ...
0
votes
0answers
22 views

Use of the expression “for some element $x$ $\in$ a subgroup $H$”

This is a question asking for clarification in use of the terms such as "for some element..." and "let $x$ be an arbitrary element in a set...." in abstract algebra. Let's say I have a group $M$ and ...
0
votes
1answer
29 views

Equivalence Relation saturating a subset

Following this question, can someone help me understand (even better with some basic visualization) the meaning of "saturation" when it comes to partition and its counterpart (equivalence relation)? ...