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.
2,998
questions
-1
votes
0
answers
24
views
Describe the distinct equivalence classes resulting from R. [closed]
A relation R is defined on Z by aRb if 5a−b is even.
(a) Prove that R is an equivalence relation. (I've already completed this section)
(b) Describe the distinct equivalence classes resulting from R.
...
- 1
2
votes
3
answers
207
views
I don't understand why this relation is not reflexive
Let $S = \{a, b, c, d\}$
$R_1 : \{(a, a),(d, d)\} $
I don't understand why this relationship is not reflexive. $R_1$ is a subset of $S$x$S$ and every element in $R_1$ is related to itself. the answer ...
- 75
0
votes
1
answer
72
views
Troubles with proving R is an equivalence relation [duplicate]
With $A = \mathbb{Z}$ and $B = \mathbb{Z}-\{0\}$, I'm trying to prove that the relation $R$ defined on $A\times B\,$ by $(a,b)R(c,d)\,$ iff $\,ad=bc$, is an equivalent relations.
While I do see why ...
- 69
0
votes
0
answers
42
views
Faster way to check if two elements belong to the same coset in $\mathbb{Z}_n$?
Q: Let $G=\mathbb{Z}_{25}$ and $H=\langle 13\rangle$ be the subgroup of $G$ generated by $13$.
Yes or No: do $24$ and $23$ belong to the same $H$-coset in $G$?
No; my reasoning:
Know that $2$ ...
- 319
1
vote
1
answer
30
views
Relation and Equivalences: Finding the equivalence classes of a relation given
Here is the problem:
Let R be the relation on N given by aRb if and only if 5 divides a-b.
a. Verify that R is an equivalence relation.
b. List the equivalence classes of R as sets. List at least 5 ...
- 35
1
vote
0
answers
27
views
Nomenclature for reflexive and symmetric relations
What is the common name for binary relations that are reflexive and symmetric (but not necessarily transitive)?
In other words: What is the generalization of an equivalence relation where transitivity ...
- 105
3
votes
2
answers
39
views
proof that $ \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1 $ is an equivalence relation
Define the following relation on $ \{f \in \mathbb{R}^\mathbb{R} \mid 0 \notin Image(f) \} $:
$ f \ $ is equivalent to $ \ g \ $ if and only if $ \displaystyle \lim_{x \to \infty} \frac{f(x)}{g(x)} = ...
- 804
0
votes
0
answers
27
views
Relation Proof. Let $R$ be a relation on $A$. Then for all $n > 0, \Bbb R^n$ is a set.
While doing my textbook, I came across the following question. Attached are both the question and hint. So from my previous knowledge, I know that what we have to do in this scenario is to show that ...
- 49
1
vote
0
answers
45
views
Showing that a morphism is an equivalence relation
Let $\mathscr{C}$ be a category. $X,Y \in ob(\mathscr{C})$, $X$ and $Y$ are said to be equivalent if there is an equivalence $f:X \rightarrow Y$. Show this is an equivalence relation.
For the ...
- 145
2
votes
1
answer
55
views
Reasoning behind intuitive understanding of specific equivalence class $a \sim b \iff f(a) = f(b)$
I was attempting this question the other day:
Let $f:A \rightarrow B$ be a surjective map of sets. Prove the relation $$a \sim b \iff f(a) = f(b)$$ is an equivalence relation whose equivalence classes ...
- 142
0
votes
1
answer
85
views
How do i prove that this is a equivalence relation
Let
$R = \{(x, xe^n) : x \in \Bbb R,n \in \Bbb Z\}$. Prove that $R$ is an equivalence relation on the set of real
numbers.
Edit: Sorry this is my first time. I am aware that in order to prove that it ...
- 1
1
vote
0
answers
19
views
On the equivalence relation induced by an arbitrary map
The book I am reading (Szekeres's A Course in Modern Mathematical Physics) makes the following claim:
More generally, any map $φ : X → Y$ defines an equivalence relation $R$ on $X$ by $aRb$ iff $φ(a) ...
- 629
0
votes
2
answers
101
views
Find a function $f$ with $\ker(f) ={\sim}$ for equivalence relation $\sim$
Find a function $f: \mathbb{R} \setminus \{0\} \rightarrow ??$, which satisfies
$$\ker(f) = ~ \sim$$
for the equivalence relation
$$x \sim y \iff \exists ~ p,q \in \mathbb{Q}: \frac{x}{y} = p+q \...
- 77
0
votes
1
answer
45
views
Investigating number of equivalence classes in the Gaussian integers formed by adding integers.
I'm trying to find how many equivalence classes on the Gaussian integers can be formed just by adding integers (as part of a wider consideration on how many there are altogether).
Let $\gamma \in \...
- 11
0
votes
0
answers
24
views
What are equivalence classes for relation?
Let $A , B \subseteq \mathbb{R} \ A\sim B \iff \exists k \in \mathbb{R} \ \ B=\{x + k: x\in A\}$ be an equivalence relation. What are equivalence classes for an interval $(0;1]$.
I am not sure, but ...
- 39
-1
votes
1
answer
75
views
are two sets of infinity necessarily equal | Automata
we'll define the relation $\equiv_L$ (same one as the one in Myhill-Nerode theorem) as follows:
there exists two string $x,y$ and a language $L$ under the $\Sigma$ alphabet
$x\equiv_Ly$ if there $\...
user956293
0
votes
0
answers
29
views
Provide equivalence classes for a piece $(0;1]$
Let $A , B \subseteq \mathbb{R_+} \ A\sim B \iff \exists p \in \mathbb{R_+} B=\{x * p: x\in A\}$ be an equivalence relation. Provide equivalence classes for an interval $(0;1]$.
As for me, I think it'...
- 39
0
votes
0
answers
40
views
find a partition of Z into 10 infinite sets? For each partition, what is the corresponding equivalence relation?
I need to find a
partition of Z into 10 infinite sets, and for each partition, what is the
corresponding equivalence relation?
so I know there's a theorem that states "let P be a partition of a ...
- 69
0
votes
0
answers
39
views
Suppose $m$ doesn't divide $n$. Show that “congruent modulo $n$” is not a refinement of “congruent modulo $m$”.
Recall that “≈ is a refinement of ∼” means that every equivalence class of ≈ is contained in some equivalance class of ∼.
a) Suppose $m | n$. Show that “congruent modulo $n$” is a refinement of “...
- 491
3
votes
3
answers
114
views
Let $\sim$ be some equivalence relation on $X$. Is there some function with domain $X$ such that $f(x)=f(y)$ exactly when $x\sim y$?
1. Suppose that $X$ is a set.
a) Let $f$ be some function with domain $X$ (and codomain anything you like), and say that $x \sim y$ means $f(x)=f(y)$. Is $\sim$ an equivalence relation? If it is, then ...
- 491
0
votes
1
answer
33
views
Projections in $C^*$-Algebras and Murray-von-Neumann Equivalence
Let $A$ be a unital $C^*$-algebra. Let $u$ be an isometry in $A$. Then we can write $1_A$, which is a projection, as $u^*u$. It is known that then $uu^*$ is also a projection. Can we produce any ...
- 258
-1
votes
2
answers
45
views
Why is it possible to define a partition of integers as prime, composite and {1,-1,0} although divisibility is not an equivalence relationship?
It's a known theorem that if $\mathcal{R}$ is an equivalence relation defined on a set, let's say $A$, then $\mathcal R$-equivalence-classes define a partition of $A$. It is also known that the ...
0
votes
1
answer
51
views
Why can't a set {(1,1)} be an equivalence relation of set A={1,2,3}?
I know that {(1,1),(2,2),(3,3)} is an equivalence relation of the set A. But I am not sure why can't the set{(1,1)} be an equivalence relation? I think it is because the equivalnce relation is ...
1
vote
1
answer
47
views
Equivalence between two ODEs?
I have formulated a function $f(x)$ as the solution to an ordinary differential equation
$$
f'(x) = \phi(f(x),x) \\
f(x_0) = f_0.
$$
and also the function $F(x) = \int_0^x f(s)ds$ as
$$
F'(x) = \Phi(F(...
- 141
0
votes
2
answers
96
views
Showing that equivalence in ring of fractions is well defined [duplicate]
I'm reading this answer, in which, one of the step involves showing that:
$$s_3(r_1s_2-r_2s_1)=0,\quad s_1(r_2s_3-r_3s_2)=0\implies s_2(r_1s_3-r_3s_1)=0$$
I am utterly confused on how this implication ...
- 9,898
4
votes
1
answer
63
views
Equivalence classes of polynomials under function transformations
Consider the sets of degree $n$ polynomials,
$$P_{n} = \big\{ a_n x^n + a_{n-1}x^{n-1} + \cdots a_1 x + a_0\ : a_{n} \neq 0 \big\},$$
and the collection of classical function transformations:
...
- 4,033
2
votes
1
answer
45
views
Is $[\star]$ a limit point of the sequence $\langle [\frac{1}{1}] , [\frac{1}{2}], [\frac{1}{3}], \dots \rangle$?
Suppose $\mathbb{R}$ has the usual topology. Endow $\mathbb{R}$ with an equivalence relation $\sim$ via $x \sim y$ if $x$ and $y$ are irrational or $x \sim y$ if $x = \frac{a}{n}$, $y = \frac{b}{n}$ ...
- 1,619
2
votes
1
answer
72
views
Examples of relations that don't satisfy one of the three properties of an equivalence relation while satisfying the other two?
Just as a question that I have posed to myself: I want to find three relations $(S, \spadesuit)$, $(R, \clubsuit)$ and $(T, \blacksquare)$ for which $(S, \spadesuit)$ doesn't satisfy the reflexive ...
- 1,133
0
votes
0
answers
44
views
Determine the generated equivalence relation
In algebraic topology one often gives generating relations to induce an equivalence relation and I wondered if there is a fast way to determine the equivalence relation. An example is the following. ...
- 357
3
votes
2
answers
245
views
How to show two equivalent projection in a $C^*$ algebra are not homotopic
Show that two equivalent projections need not be homotopic. HINT: Let $P=\begin{pmatrix} 1&0\\0&0\end{pmatrix}$ and $Q=\begin{pmatrix}
t&\sqrt{t(1-t)}\\\sqrt{t(1-t)}&1-t
\...
- 3,663
0
votes
1
answer
45
views
equivalency of distinct ordinals
I've come across this statement:
it is readily checked that distinct ordinals $\alpha\neq\beta$ are not $L_{∞,ω}$-equivalent
Why ?
Does it even hold that as I'd guess they are not $L_{\kappa,\omega}$...
- 3,935
0
votes
0
answers
55
views
Notation clarification needed for an exercise from Arbib and Manes text.
The following question, is taken from Arbib and Manes’ Arrows, structures and functors text:
Definition 1: Given an equivalence relation $E$ on a set $A$, we define the equivalence class of an ...
- 2,119
2
votes
1
answer
55
views
Every equivalence relation $x \equiv y$ compatible with the structure of a module $E$ is of the form $y-x \in M$ for some submodule $M$ of $E$.
On the end of page 196 of Bourbaki’s Algebra I, it says:
Let $E$ be an $A$-module.
Every equivalence relation $x \equiv y$ compatible with the structure of a module $E$ is of the form $y - x \in M$ ...
- 469
0
votes
2
answers
48
views
Show this set of axioms is $\aleph_0$-categorical. [duplicate]
Let $\mathcal{L}=\{\sim\}$ be a FOL and $\Sigma$ the set formed by the following axioms:
$\left(Ref\right) \;\; \forall x_1 \;\; x_1 \backsim x_1$
$\left(Sym\right) \;\; \forall x_1 \forall x_2\;\; \...
- 363
0
votes
0
answers
31
views
Linearisations of a preorder which 'preserve' equivalence classes.
Suppose I have a preorder $\leq$ on a (finite) set $X$ (so $\leq$ is reflexive and transitive). From this, I can construct an equivalence relation by $x\sim y$ if and only if $x\leq y$ and $y\leq x$.
...
-1
votes
1
answer
32
views
Continuous map from A to $D^2$ [closed]
I'm proving something and the only thing I do not have yet is that I have to give a continuous function from $A=[-1,1]^2$ to $D^2$ a disk such that $(x,1)$ is being sent to the northpole of the disk ...
- 7
2
votes
0
answers
21
views
Propositional Equivalence-Discrete Mathematics
$$ p ∧ ((¬p ∨ q) ∧ (¬q ∨ p))$$ is it a contradiction?
I have to prove that the statement is a contradiction.But my answer is $p$. I couldn't find out my mistake.
- 21
2
votes
0
answers
32
views
Finding a set of representatives to an equivalence relation on sequences [closed]
Define an equivalence relation on the set of infinite real sequences by: a~b iff a-b is bounded. For example, the equivalence class of 0 (the constant sequence 0,0,0,...) is the set of all bounded ...
- 81
5
votes
3
answers
317
views
Foundation of mathematical objects modulo isomorphism in ZFC
Suppose we want to define a notion of graph modulo isomorphism. The first thought that comes to mind is to consider the set of all graphs and then quotient it with respect to the equivalence relation ...
- 426
0
votes
1
answer
69
views
The function that takes two quotient sets and merges them
I want to know the definition and the well-definedness
of the function that takes two quotient sets (disjoint-set data structures), merges them
and returns a quotient set.
For example, if the function ...
- 1
5
votes
2
answers
274
views
Does an equivalence relation on a group play well with the group operation, provided that the equivalence class of the identity is a normal subgroup?
Given an equivalence relation $\sim$ on a group $G$, such that
$$
a \sim a' \ \text{ and } \ b \sim b' \ \Longrightarrow \ ab \sim a'b' \ ,
$$
the equivalence class $[e_G]$ of the identity is a normal ...
- 343
0
votes
1
answer
44
views
Proving properties of relations on a power set.
Take $R$ to be the relation defined on $P(\{1, . . . , 100\})$ by $A \sim B$ if and only if $|A \cap B|$ is even.
Firstly, am I right to think that for example, $|\{0\}\cap \{1\}| = |\{1\}| = 1$.
And ...
- 351
0
votes
0
answers
19
views
Equivalence relations, possible typo in textbook answer
9.78. Let $R_1$ and $R_2$ be equivalence relations on a nonempty set A. Prove or disprove the following:
If $R_1$ ∩ $R_2$ is symmetric, then so are $R_1$ and $R_2$.
The statement is false. Let A = {1,...
- 445
6
votes
1
answer
89
views
Can equivalence relations be axiomatized using just one elementary sentence?
Equivalence relations are traditionally axiomatized by the Reflexivity, Symmetry, and Transitivity axioms. However, they can also be axiomatized by Reflexivity and Circularity. (Circularity is this ...
- 16.8k
0
votes
1
answer
78
views
Characterization of simple groups in terms of its conjugacy classes [closed]
Recently I have seen a post whose link is the following.
I am not able to prove the first statement, namely, "A group $G$ is simple if and only if for any $1 \neq x \in G$, the conjugacy class of ...
- 145
-2
votes
1
answer
43
views
Can any subset of $\Bbb{N}$ be an equivalence class? [closed]
I am wondering if for any given $x \in P(\Bbb{N})- \{\emptyset\}$ we can find an equivalence relation such that it will have an equivalence class equal to $x$.
Extend of this question is whether for ...
- 31
4
votes
1
answer
46
views
Reference Request for Axiomatic/Algebraic Big $\mathcal{O}$ and Little $o$
I have seen the formal definitions of big $\mathcal{O}$ and little $o$, and do all right working with them. Still, I have some questions that a good reference might help clear up.
In what level of ...
- 447
1
vote
1
answer
43
views
Finding the unique representative that lies on the unit circle in an equivalence class of a given equivalence relation.
I am doing an exercise from a number theory textbook for practice and not sure how to approach this problem.
Let $S:=(\Bbb R \times \Bbb R)\setminus{(0,0)}$. For $(x,y),(x',y') \in S$ let $(x,y)~\sim ...
3
votes
2
answers
62
views
Conjugacy classes of an element that are the same
Recently I have been studying the transfer homomorphism, and it came to mind that whether conjugacy class of an element with respect to some subgroup is the same as the original group. Namely, if $x \...
- 145
0
votes
0
answers
21
views
Introductory equivalence relations xRY
I have a question about members/subsets.
Let A be a nonempty set and let B be a subset of the power set $\mathcal{P} ({A})$ of A. Define a relation R from A to B by xRY if x ∈ Y. Give an example of ...
- 445