Stack Exchange Network

Stack Exchange network consists of 174 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
2answers
21 views

Isomorphic equivalence relations and partitions

Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic if there exists a bijection f : X → X such that the following holds: For all y, z ∈ X : (y, z) ∈ $R_1$ ...
1
vote
0answers
32 views

Prove there is a bijection φ : R(X) → P(X)

For a set $X$, let $R(X)$ be the set of equivalence relations on $X$ and let $P(X)$ be the set of partitions of $X$. Prove there is a bijection $\varphi : R(X) \to P(X)$. Stuck on how to proceed with ...
1
vote
1answer
32 views

What are the equivalence classes of this relation?

Let $f \colon X → X$ be an injective function. For $y, z ∈ X$, define $y \sim z$ to mean there exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ ...
3
votes
1answer
57 views

Generalization of topologies with equivalence classes of sets

Is there a generalization of topological spaces which works on equivalence classes of subsets? To be a little bit more precise, I would think of something like the following: Let $X$ be a set and $P(...
0
votes
1answer
30 views

Arrange people at round table so that everyone knows the two people next to them

Each of the guests know: a) more than half of the guests b) at least half of the guests. Prove that in both of these cases it is possible to arrange them to sit around a round table so that everyone ...
1
vote
2answers
35 views

Finding the equivalence class and quotient set of relation

I have the relation: $ \forall x \in \mathbb{R}: xRy \Leftrightarrow |x - 3| = |y - 3| $ I need to find the equivalence class and quotient set of the relation. I think the equivalence class is: $ \...
0
votes
2answers
27 views

What does this relation represents ?

so i have a hard time understanding what would this relation looks like, we aren't given any precise function so it's hard to know what this would look like. We have to establish the relation and then ...
0
votes
0answers
11 views

Showing that left and right group actions of group $G $ on set $A$ induce the same equivalence relation on A?

Let $g.a$ denote the left action of group $G$ on a set $A \; \forall g\in G , a\in A$. Let $a.g$ denote the corresponding right action of $G$ on $A$. Then show that both induce the same equivalence ...
0
votes
1answer
20 views

Subtraction in Building a Set from Nonnegative Reals

When defining equivalence classes using elements contained by the nonnegative reals, may I use subtraction in the function that defines equivalence between those classes? My thinking is that if ...
0
votes
0answers
50 views

An equation involving Non-Trivial Zeros of the Riemann Zeta function

$\rho$ is a Non-Trivial Zero of the Riemann Zeta function if and only if $$\displaystyle\int_1^{+\infty} \lfloor x\rfloor x^{-2-\rho} dx =\int_1^{+\infty} \lfloor x\rfloor \{ x \}x^{-2-\rho} dx $$ ...
0
votes
0answers
16 views

Quotient Set of a Quotient Set

Can anyone help me with this problem? Given: $A = \{a,b,c\}$ $G=I_A \cup\{(a,b), (b,a),(b,c),(c,b)\}$ $H=I_A \cup\{(b,c), (c,b)\}$ (Note: H is a refinement of G) Then: $A|G = \{G_a, G_b,G_c\}$ ...
0
votes
1answer
29 views

building a DFA from equivalence classes of $R_L$(tricky)

i've encoutered an interesting question from an old exam with no solution and i was wondering: how do you build a dfa(deterministic finite automata) from given equivalence classes? this is the ...
0
votes
1answer
18 views

Counting equivalence classes

Given any $n$ integers $m_1,m_2,\ldots m_n\in \mathbb{N}$ if we define an equivalence relation $\sim$ on $\mathbb{N}^n$ as follows: $$(a_1,a_2,\ldots a_n)\sim (b_1,b_2,\ldots b_n)\iff \text{For every ...
0
votes
0answers
15 views

Is Geometric Median Affine Equivariance?

Does the geometric median have the natural property - Affine Equivariance? That is the depth of the geometric median and its relative location to other data points do not change under affine ...
0
votes
0answers
22 views

finding equivalence classes of $R_L$ in automata(Nerode)

i am having trouble understanding this concept. would really appreciate your corrections so i could learn and improve. 1)$L=\left\{w\:\in \Sigma^* |\:w\:begins\:and\:ends\:with\:aa\right\}$ 2)$L=\...
0
votes
1answer
23 views

Show that it is a partial order and not an equivalence reaction [closed]

I've been given the question below and I'm not sure how to show that it is a partial order. Show that the relation $R =\{(a,b) \mid a \text{ divides } b\}$ over the set $\mathbb{Z}^+$ is a partial ...
-1
votes
0answers
19 views

How many there are different equivalent relations on natural numbers? [duplicate]

How many there are different equivalent relations on natural numbers? Please, have a look at my try: What is relation? It is a subset of Cartesian product. In Cartesian product there are $|\mathbb{N}\...
0
votes
1answer
18 views

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$.

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$. $T$ is an equivalence relation on $\mathbb{R}\...
1
vote
2answers
57 views

Does there exist $a \in \mathbb Z$ such that $a^2 = 5,158, 232,468,953,153$?

Does there exist $a \in \mathbb Z$ such that $a^2 = 5,158, 232,468,953,153$? Use the work from part a to justify the answer. So in part a, I had to prove: For each $[a] \in \mathbb Z_5 ,$ if $[a]...
0
votes
1answer
21 views

Let $a \in A \ and\ U \in C \ such\ that\ a \in U\ $. Prove that $[a] = U\ $.

If you refer to this link and the question, it's this same question, this is the last part of the 4 part question . The equivalence relation $\sim$ is defined as: $$\textsf{For }x,y\in A,x\sim y\...
0
votes
1answer
39 views

Prove that $\sim$ is an equivalence relation on the set $A$

Let $A$ be a nonempty set and $C$ is a partition of $A$. A relation $\sim$ is defined as: $$For \ x, y \in A, x\sim y\ \ if \ and \ only \ if \ there \ exists \ U \in C \ such \ that\ x \in U and\ y \...
0
votes
1answer
30 views

Equivalence relation with complex numbers.

In $ \mathbb{C} $ we define the binary relations $ R_{j} $ , $ j=1,2,3,4. $ $ z_{1} R_{1} z_{2} \Leftrightarrow |z_{1}| = |z_{2}| $ $ z_{1} R_{2} z_{2} \Leftrightarrow arg(z_{1}) = arg(z_{2}) $ ...
0
votes
1answer
36 views

Find classes of relation equivalence

$S=\{3n+1:n∈N\} = \{1,4,7,10,...\}$ and relation is defined as: $(x,y) ∈ ρ \text{ def }⇔ 4|(x + 3y)$ I need to prove that relation is relation of equivalence (that means that it is reflexive, ...
0
votes
1answer
37 views

Finding an equivalence relation that isn't a congruence.

Let $B=S \times T$ be a rectangular band such that $|S|=|T|=3$. I've got to find an equivalence relation which is not a congruence in order to prove that at least one exists. I've tried many ...
0
votes
0answers
16 views

An example of random functions that are stochastically equivalent but aren't modifications of each other.

I'm trying to show that stochastic equivalence of random functions (in the broad sense) doesn't imply that they are modifications of each other. For this, I'm looking for a counterexample. Perhaps ...
0
votes
0answers
24 views

equivalence relation with binary and decimal numbers

I am learning about relations and I was hoping to find out if my attempt for my question looks right. Let b(n) equal the value of the highest bit set to 1 in the binary representation of the ...
0
votes
0answers
14 views

Prove, that $M=\{(a,b)\mid a,b \in \mathbb{N_0} \land (a-b) \text{ mod } 4 = 0\} $ is a equivalence relation

Prove, that $M=\{(a,b)\mid a,b \in \mathbb{N_0} \land (a-b) \text{ mod } 4 = 0\} $ is an equivalence-relation. Refl.: $a-a=0 \text{ mod } 4 =0$ Sym.: $\forall x,y \in M: (x,y) \implies (y,x)$ (Not ...
0
votes
1answer
39 views

Equivalence relation generated by a relation: concrete characterization

Let $R$ be a relation on a set $X$. The equivalence relation $\sim_R$ generated by $R$ is defined as $\bigcap A$ for $A$ being the set of all equivalence relations containing $R$ ($A$ is not empty as $...
0
votes
1answer
23 views

elements of order 3 the group $R^2/Z^2$

the group acts on addition is defined by the equivalence of all the reals that differ by squared integers. I have $3r^2 = M^2-3n^2$ but don't know how to proceed?
1
vote
1answer
20 views

How to find a DFA for combinations of even and odd occurrences $0,1$?

Let $L$ be a language over $\{0,1\}$ whose Nerode equivalence classes are: $$ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=0\}\\ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=1\}\\ \{w|\#_0(w)\...
2
votes
1answer
37 views

How to find the equivalence classes of a formal language complement?

Let $L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$ be a language over $\sum=\{a,b,c\}$. Find the equivalence classes of relation $R_L$ which is defined as follows: $xR_Ly \iff \forall z\in \...
0
votes
1answer
30 views

How to find equivalence classes for $R_L$ for the language of words that begin and end with $aa$?

Let $R_L$ be a relation such that: $xR_Ly \iff \forall z\in \sum^*:xz\in L \iff yz \in L$. Find the equivalence classes for $R_L$ for this language: $$ L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts ...
0
votes
0answers
13 views

Equivalence relation - reflexity

I need to prove that relation is an equivalence relation. Equivalence relation means it satisfies reflexity, symmetry, and transitivity. If I was given an set of numbers S=(-1,1) and for example for -...
0
votes
0answers
22 views

prove that for the equivalence class : X/(X/E) = E

Let E be an equivalence relation on the set X . prove that: X / (X / E) = E The definition of euivalence class: x/E = { for every y in the X | xEy } The set of all equivalence classes: X/E = { x/E |...
0
votes
1answer
31 views

Determining the equivalence classes of an equivalence relation represented by graph via its adjacent matrix.

Good day, I wanted to write a programme in python which given the inputs n,E , where n is the number of nodes and E a list of edges gives me certain properties about that graph. I'm mainly interested ...
1
vote
1answer
32 views

RoS is a equivalence relation iff RoS = SoR

Let R and S be two equivalence relation on X. I wanna prove that $R\circ S$ is an equivalence relation, but I can't prove that it is reflexive and transitive. For transitivity: There are arbitrary ...
0
votes
0answers
52 views

Prove the following are equivalent

Let $f$ be bounded on $[a,b]$ and integrable on $[c,b]$ for $a<c<b$. I need to prove the following are equivalent: a) $\lim\limits_{x\to a+}\int_{x}^{b}f$ exists in $\mathbb{R}$ b)$\lim\...
1
vote
1answer
29 views

Sizes of Conjugacy Classes of a Group of Known Order

Suppose G is a group of order 48 (centre consisting identity only). Show it has a conjugacy class of order 3. I know that the size of the conjugacy classes are limited to divisors of 48: 1,2,3,4,6,8,...
0
votes
1answer
40 views

Followup on Proof: Equivalence Classes

The original question at hand was: Suppose α and β are equivalence relations on the set S. Suppose further that the relation γ is defined as follows: For x,y∈S, xγy means xαy and xβy. Prove that γ ...
-1
votes
2answers
24 views

Discrete Mathematics Proof through Equivalence Relations [closed]

Suppose $\alpha$ and $\beta$ are equivalence relations on the set $S$. Suppose further that the relation $\gamma$ is defined as follows: For $x,y \in S$, $x\gamma y$ means $x\alpha y$ and $x\beta y$. ...
0
votes
2answers
20 views

Equivalence Relation with dividing integers

Define $x\sim y$ if $4$ divides $(x+3y)$ for $x$ and $y$ integers. Show that is an equivalence relation. Equivalence relation means it satisfies reflexity, symmetry, and transitivity. Can anyone ...
0
votes
1answer
22 views

Relations from X to Y

Let $X$ and $Y$ be sets, and let $R$ be a binary relation from $X$ to $Y$. What does it mean for $R$ to be reflexive and symmetric? Because I know that for a relation over a single set $A$: It is ...
0
votes
1answer
17 views

Existence of infimum on the set of equivalence classes

Let $Q$ be a complete lattice. Let $\sim$ be an equivalence relation on $Q$ conforming to the axiom $$(f_0\sim f_1\wedge g_0\sim g_1\wedge f_0\leq g_0)\Rightarrow f_1\leq g_1.$$ Define the order on ...
0
votes
1answer
26 views

$For \ a, b \in \mathbb Z, a\approx b\ \ if \ and \ only \ if \ 2a+3b\equiv0\pmod5$ Is $\sim$ an equivalence relation on $\mathbb Z$?

Let $\sim$ and $\approx$ be relations on $\mathbb Z$ defined as follows: $$For \ a, b \in \mathbb Z, a\sim b\ \ if \ and \ only \ if \ 2a+3b\equiv0\pmod5$$ $$For \ a, b \in \mathbb Z, a\approx b\ \ ...
2
votes
3answers
51 views

Proving Equivalence Relations, Constructing and Defining Operations on Equivalence Classes

I think I have an intuitive sense of how ordered pairs can function to specify equivalence classes when used in the construction of integers and rationals, for example. I put the cart before the horse,...
2
votes
1answer
43 views

DFA Minimization: Finding all Nerode equivalence classes.

So I read that you can easily read off the Nerode equivalence classes if you have a minimal DFA. So after the minimization process I got this: But how can I read off the equivalence classes? I read ...
0
votes
0answers
14 views

Q/ The representative system of this relation?

Can you help me to know the representative system of this relation? I have this relation: $x, y \in \mathbb{R}$ and $x \sim y \iff x - y\in \mathbb{R}.$ And I know that it is an equivalence ...
0
votes
3answers
27 views

Prove that congruence mod 7 is an equivalence relation.

I know that an equivalence relation (~), by definition, has to hold 3 properties. 1.) Reflexive 2.) Symmetric 3.) Transitive Although actually using this proof technique is very confusing to me. I ...
1
vote
2answers
46 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
3answers
36 views

Determinant matrix projective space?

Let $M_n(\mathbb{R})$ the space of all real square matrices of dimension $n$, with the equivalence relation E, defined as: 2 matrices are equivalent if and only if they have the same determinant. ...