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
0 answers
30 views

Are $\phi^{'}_i,\tau_i$ the coresponding compatible functions for equivalence relations constructed in the directed limit of groups/rings.

Background: The following is taken from: A Graduate Course In Algebra - Volume 1 by: Ioannis Farmakis and Martin Moskowitz, How to Prove it by: Dan Velleman, and An Invitation to Abstract Algebra by ...
Seth's user avatar
  • 3,429
1 vote
0 answers
25 views

Constructing compatible functions $\phi'_i,\phi'_j$ for equivalence relation $\sim$ for directed limit of directed systems of groups.

Background: The following is taken from: A Graduate Course In Algebra - Volume 1 by: Ioannis Farmakis and Martin Moskowitz, and How to Prove it by: Dan Velleman. Definition 1: Let $(G_i)_{i\in I}$ be ...
Seth's user avatar
  • 3,429
0 votes
0 answers
25 views

Set of equivalence classes as the image of a map

In the book I am reading it states that any map of sets $f\colon S \to T$ gives us an equivalence relation $\bar{S}$ defined by $a\sim b$ if and only if $f(a)=f(b)$. This all makes sense to me, but ...
baslerbuenzli's user avatar
1 vote
1 answer
80 views

Is this correct notation for set of equivalence class and quotient sets for directed limit of directed system of groups.

Background: The following is taken from: A Graduate Course In Algebra - Volume 1 by: Ioannis Farmakis and Martin Moskowitz, and How to Prove it by: Dan Velleman. Definition 1: Let $(G_i)_{i\in I}$ be ...
Seth's user avatar
  • 3,429
4 votes
2 answers
236 views

Are we assuming a relation to be transitive untill proven otherwise?

I do not know if the title would be correct title for the question but I think I am asking a valid question. While studying set theory and relations we were often asked about whether a relation $R$ is ...
madhurkant's user avatar
0 votes
0 answers
22 views

How to describe the transitive closure of a relation in terms of the ground relation

Let $X$ be a non-empty set and $\equiv$ a relation on $X$, which is symmetric and reflexive but is not transitive. I know that there exists a transitive closure of $\equiv$, saying, $\equiv_{cl}$. But ...
Kaique Roberto's user avatar
-2 votes
0 answers
14 views

My question even if any data set in integer doesn't satisfy the transitive we can genralize thats its not going to be transitive [closed]

Let R be a relation on ZZ defined by (a, b) * R(c, d) if and only if ad – bc is divisible by 5. Then R is
Sundram Kumar's user avatar
1 vote
1 answer
58 views

Which of these 4 statements about sets A and B are equivalent?

Which of these 4 statements about sets A and B are equivalent?: (1) A $\cap$ C $\subseteq$ B $\cap$ C for all C (2) A $\subseteq$ B (3) A $\cup$ C $\subseteq$ B $\cup$ C for all C (4) A \ B = $\...
Thao Mai's user avatar
1 vote
3 answers
90 views

Find an equivalence relation over all of $\mathbb{Z}$ which has infinitely many equivalence classes with infinitely many elements in each

I want to find an equivalence relation defined on all integers (that is, all of $\mathbb{Z}$) where The equivalence relation partitions $\mathbb{Z}$ into infinitely many equivalence classes; and ...
Christopher Miller's user avatar
2 votes
0 answers
40 views

Closedness of the Relation given by an Involution of $[0,1]$

If $I=[0,1]$, let $f:I\to I$ be an involution. Then $\sim_f:=\Delta_I\cup \text{Gr}(f)\subseteq I^2$ defines an equivalence relation on $I$ where $\Delta_I=\{(t,t):t\in I\}$ is the diagonal of $I$ and ...
tripaloski's user avatar
1 vote
1 answer
22 views

Show that the relation R defined on $\mathscr{P} \left( A \right)$ by $a R b, \forall x (x \in A \Leftrightarrow x \in B)$

Let $\mathscr{P} \left( A \right)$ denote the set of all subsets of a set $A$. Show that the relation $R$ defined on $\mathscr{P} \left( A \right)$ by $a R b, \forall x (x \in A \Leftrightarrow x \in ...
Linhao231035's user avatar
1 vote
1 answer
34 views

Coequalizer in the category of modules

I am trying to prove that the category of modules is cocomplete. It suffices to show that it has all coequalizers and coproducts. It's relatively easy to show that all coproducts exist, and I am left ...
Squirrel-Power's user avatar
1 vote
1 answer
37 views

Question regarding Transitivity of a Relation

Suppose we define a relation $R$ in the natural set $\mathbb N$ which says: $$(x,y)\in R\iff x^2-4xy+3y^2=0$$ and we would like to find which of the following properties does $R$ satisfy. My book ...
20DPCO190 Amanul Haque's user avatar
2 votes
1 answer
70 views

How much choice is needed to prove that $|G| \nless |G/ \sim|$ for any equivalence relation $\sim$ on set $G$?

$G/ \sim$ is the set of $\sim$-equivalence classes in $G$ and $|G/ \sim|$ is the cardinality of $G/ \sim$. $|A| \leq |B|$ means that there is an injective function from $A$ to $B$. $|A| < |B|$ ...
Hussein Aiman's user avatar
0 votes
0 answers
53 views

number of "equivalence relations" on a set with "n-elements"

I am trying to find a formula for number of equivalence relations on a set with n-elements however I am confused. I have already encountered the idea of "bell's number" and "Stirling ...
Sepehr GH's user avatar
0 votes
0 answers
26 views

Relabel According to the Order of First Occurrence

Let $a\in\mathbb R^n$ be a tuple of length $n\in\mathbb Z_{>0}$. Let $X=\{a_i:1\le i\le n\}$ be the set of elements of $a$ for $x\in X$ let $$i(x)=\min\{j:a_j=x\}$$ be the first occurence of $x$ in ...
Matija's user avatar
  • 3,558
2 votes
1 answer
60 views

How change an non-equivalency relation to equivalency relation?

I am an engineer, so maybe this question is naive. I study equivalence relations and equivalence classes. An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. ...
ALIN's user avatar
  • 123
3 votes
0 answers
56 views

Defining a measure on a group from a measure on the equivalence classes

Let $G$ be a group, and a $H$ a subgroup, and for $a,b \in G$ let $a\sim b$ if $aH = bH$. Suppose I have a measure $\mu$ on $G/\sim$, the left cosets of $H$, and suppose that $G$ is equipped with a ...
Ryan's user avatar
  • 169
0 votes
1 answer
47 views

Let $B^2 :=\{(x,y,z) \in \mathbb{R}^3 : x^2 + y^2 + z^2 = 1\}$. Show $B^2$ is equinumerous to $\mathbb{R}$

Let $B^2 :=\{(x,y,x) \in \mathbb{R}^3 : x^2 + y^2 + z^2 = 1\}$. Show $B^2$ is equinumerous to $\mathbb{R}$. I think there are a few ways to do this, probably some are easier, but I've committed to ...
user avatar
4 votes
0 answers
76 views

Equivalence Relation Textbook Mistake

I found a question in my textbook but I think the answer provided is wrong. The question says: Let $S$ be a relation defined over $\mathbb R$ such that $(a,b) \in S \iff ab≥0$. Is $S$ equivalence? ...
20DPCO190 Amanul Haque's user avatar
2 votes
1 answer
49 views

If there is a bijection $F : A \mapsto A / R$, then $R = \{(x, y) \in A^2 : x = y\}$?

Assume $R$ is an equivalence relation over $A$ and there is a bijection between $A$ and $A / R$. Does this entail $R = \left\{ (x, y ) \in A^2 : x = y \right\} $? What I thought is the following. ...
lafinur's user avatar
  • 3,322
1 vote
1 answer
37 views

Is the following proof of equality complete?

Say we have only defined the rational numbers. If we have two rational numbers, s and r, and we can show that $|s-r|<\epsilon$, for all positive rational $\epsilon$, is that enough to show that $s =...
Vector's user avatar
  • 357
0 votes
0 answers
67 views

Generalization of Pólya Enumeration Theorem by de Bruijn

I need help with this question. Suppose that G is a group acting on a set of objects S, and that C is the set of colorings of elements of S using the colors in a set R. Let $\overline c$ denote the ...
ssd500's user avatar
  • 1
2 votes
1 answer
97 views

Free Commutative Monoid Quotient by Relations?

Say I have a commutative monoid $M$ that is generated by three elements $A,B,C$, where I have that $A+C=2B$. I want to write this a free (does that even mean anything?) monoid $\mathbb N^3$ with ...
Chris's user avatar
  • 2,946
3 votes
0 answers
55 views

Use of quotient space to turn differentiation into a bijective operator

Not sure if this has been asked before. Recently, I've been thinking about differentiation and integration as linear operators acting on functional spaces. I know that integration cannot be properly ...
interspazia's user avatar
1 vote
0 answers
50 views

Bijection Between Equivalence Classes and Non-Negative Reals

Consider the following equivalence relation: $ (x_1, x_2) \sim (y_1 ,y_2)$ iff $ x_1^2 + x_2^2 = y_1^2 + y_2^2 $ Now, find a bijection $ f: R^2/ \sim \rightarrow [0, \infty) $. From my ...
Anon's user avatar
  • 443
2 votes
1 answer
281 views

Let $∼$ be a relation on $\mathbb{R}$ and $x ∼ y \iff x=y$ or $x+y=6$. [closed]

Let $∼$ be a relation on $\mathbb{R}$ and $x ∼ y \iff x=y$ or $x+y=6$. I proved that $∼$ is an equivalence relation. Now I have to find a complete set of representatives. I know that $[a]_∼ := \{b \in ...
Mr. Sir's user avatar
  • 79
0 votes
0 answers
70 views

equivalence classes vs partitions in imperfect-information games

I am reading Multiagent Systems by Yoav Shoham, and in chapter 5 about extensive games, the definition of imperfect-information games extends the perfect-information games definition with equivalence ...
VishalVignesh's user avatar
1 vote
1 answer
63 views

What is the smallest equivalence relation containing two equivalence relations

I'm struggling with the following problem: Given two equivalence relations $q,s$ on set $X$. Prove that there exists the smallest (in a sense of inclusion) equivalence relation $r$ such that $g \cup s ...
user avatar
4 votes
2 answers
98 views

Two definitions of mapping being equivalent, which one is correct and why?

The following are two definitions of the concept that two mappings $ f:A\mapsto B $ and $ g:A^\prime\mapsto B^\prime $ are equivalent. Def1 : Both the domains and codomains are the same, i.e., $A=A^\...
Qi Tianluo's user avatar
0 votes
2 answers
83 views

Proving $A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \iff nk\in B$ is equivalence relation.

In an exercise I'm asked to prove that (not whether, the prompt assumes it is true) $$For \ A,B \subseteq \mathbb{N}\ \ A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \...
4-4's user avatar
  • 13
0 votes
0 answers
89 views

Axiomatic justification of the quotient set being a set rather than a class

Suppose we have an underlying set $S$ and an equivalence relation $\sim$ defined on $S$ inducing the partition $S\backslash\sim=\{[s]_{\sim}:s\in S\}$ of $S$ known as the quotient set where $[s]_{\sim}...
dandar's user avatar
  • 980
0 votes
1 answer
76 views

Why does the proof of the disjointedness of equivalence classes not account for when an equivalence class is just a subset of another?

I saw a proof of the disjointedness of two equivalence classes. The proof was as follows: Suppose we have two equivalence classes $[a]\not=[b]$. We'll show they are disjoint. Suppose $x\in[a]\cap[b]$. ...
Vector's user avatar
  • 357
0 votes
1 answer
89 views

Finding bijection between set of equivalence classes and integers

Let $X = \Bbb N \times \Bbb N$ be the set of pairs of positive integers. Consider the equivalence relation $(a, b) \sim (c, d)$, if $a + d = c + b$. Prove that there is a bijection $F: X{/} \to \Bbb Z$...
Anon's user avatar
  • 443
1 vote
1 answer
85 views

Struggle with equivalence relation definition in graph theory paper regarding clique-width

I'm trying to get more involved in graph theory and understanding harder concepts. I stumbled upon a paper that proves the clique-width of split graphs to be unbounded. They define a split graph as ...
Noob's user avatar
  • 13
1 vote
1 answer
56 views

What can we say about Green's relations on a semilattice?

Note: This is a soft-question in the flavour of, say, "what does $X$ look like?" and "Is there a description of $Y$?" - so, hopefully, it is not too broad. Let's focus on the ...
Shaun's user avatar
  • 45.1k
0 votes
0 answers
19 views

What is this equivalence class like set-theoretic construct called?

I have a relation $R$ defined on a set $X$. For any $a\in X$, I have the following sets: $$[a] = \{x: R(a,x)\}$$ $R$ is symmetric and reflexive, but not necessarily transitive, hence not an ...
SagarM's user avatar
  • 1,789
1 vote
1 answer
77 views

Is the empty set in this quotient set

Let $S$ be a non-empty set and $\mathcal{A}$ a class of subsets of $S$ and define the following equivalence relation $\sim_{\mathcal{A}}$ on $S$; $$s\sim_{\mathcal{A}}t\Longleftrightarrow 1_{A}(s)=1_{...
dandar's user avatar
  • 980
0 votes
0 answers
34 views

Inverse images of sets versus inverse functions - should we use different notation?

I am reading the following paper Beloso-Herves, C. and Monteiro, P.K. Information and s-algebras. Economic Theory, 54(2): 405-418, 2013. and have a question of a technical nature which the authors ...
dandar's user avatar
  • 980
6 votes
1 answer
71 views

Equivalence relations, formal languages, and hypercube walks - what did I unleash on my students?

I teach a class in discrete mathematics and formal language theory. On my most recent final exam, I asked a question that involved a crossover between equivalence relations and formal languages. Here'...
templatetypedef's user avatar
1 vote
1 answer
62 views

Equivalence classes of $\mathbb{R}/\mathbb{Z}$.

I am trying to write down and prove a precise characterization of the equivalence classes of the relation on $\mathbb{R}$ defined by $x \sim y$ if and only if $x - y \in \mathbb{Z}$. What I've done so ...
Brad G.'s user avatar
  • 2,238
1 vote
0 answers
63 views

Intuition on equivalence classes from group action on $a$ and index of the stabilizer of $a$ [duplicate]

I am currently reading Abstract Algebra by Dummit and Foote Chapter 4. I was trying to grasp the idea behind proposition 2, I could prove it but could not construct a geometric understanding of the ...
khanh's user avatar
  • 212
3 votes
0 answers
59 views

Is there any way to have a geometric, visual intuition of what this manifold could be?

Let's consider $H$ the space of $3\times3$ matrices with real coefficients of the form $$A =\begin{bmatrix} 1 & 0 & 0 \\ x & 1 & 0 \\ z & y & 1 \end{bmatrix}$$ with the ...
ccnptr's user avatar
  • 45
2 votes
3 answers
105 views

Trigonometric proof of the equivalence $ \arctan [\frac {1} {2}] - \arccos [{\frac {1+3 \sqrt{3}}{2 \sqrt{10}}}] = \frac {\pi} {12} $

Solving this problem Two identical circles passing through each other's centres. Three parallel lines and two diagonal lines drawn as below. What is the value of the marked angle? I found that the ...
user967210's user avatar
1 vote
1 answer
49 views

The equivalence relation is defined on a set of 9 elements and is negatively transitive relation. How many equivalence classes can be there?

I looked for answers a lot but mostly used the Bell number, which we haven't studied. And I have no idea how to do it with negatively transitive relations.. (Edit) Negatively transitive relation, ...
Dal's user avatar
  • 11
1 vote
0 answers
34 views

Proving that we can define a paradoxical set in terms of equidecomposability.

I'm doing an undergrad project on the Banach-Tarski paradox and I'm not convinced by the proof I have come up with for this, everything to do with the Banach-Tarski Paradox is new maths to me and so I ...
spooleey's user avatar
  • 436
1 vote
1 answer
56 views

Is an identity relation unique or can there be multiple?

My question is that suppose a set $A = \{1,2,3,4\}$ so, the identity relation can be $R_1 = \{(1,1), (2,2), (3,3), (4,4)\}$ but can it be $R_2 = \{(1,1), (2,2)\}$?
Aditya Lal's user avatar
3 votes
1 answer
79 views

Magical relationship between Exponential distribution and Poisson process

Consider i.i.d. random variables $X_1,X_2,\ldots,X_n$ satisfying exponential distribution $\operatorname{Exp}(1)$. Let $Y=X_1+X_2+\ldots+X_n$. We know that the p.d.f. of $Y$ is the Gamma distribution $...
andy's user avatar
  • 121
0 votes
0 answers
98 views

Definition of first order infinitesimal number using equivalence classes

I read about model construction in infinitesimal differential geometry (http://www.iam.fmph.uniba.sk/amuc/_vol-73/_no_2/_giordano/giordano.pdf , page 3-6) I can't understand how equivalence class ...
Mike_bb's user avatar
  • 731
0 votes
1 answer
80 views

Is equivalence sufficient for the equivalence relation proportion?

In Euclid Elements Book 5 Definition 5 it defines an equivalence relation for proportions. $A:B = C:D$ if when $mA<=>nB \Rightarrow mC<=>nD$ where $m,n \in \mathbb{N}$ and $<=>$ are ...
crubow's user avatar
  • 56

1
2 3 4 5
63