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

learn more… | top users | synonyms

8
votes
4answers
4k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
1
vote
5answers
2k views

prove that $a \equiv b \mod m$ is an equivalence relation on the integers

prove that $a \equiv b \mod m$ is an equivalence relation on the integers I believe there are 3 properties that it must meet to prove and equivalence relationship. Any reference material would be ...
2
votes
1answer
173 views

Equivalence relation question with cardinality and countability $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $

Let $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $ What is the cardinality of $[\pi]_S$ ? Prove that the quotient group $\mathbb R/S$ is uncountable. Well I think that cardinality is ...
2
votes
3answers
601 views

Equivalence Relation problem [duplicate]

Let $S$ be the relation on $\mathbb{N} \times \mathbb{N}$ defined by $(a,b)S(c,d)$ if and only if $ad=bc$. Prove this is an equivalence relation on $\mathbb{N} \times \mathbb{N}$. I think I've found ...
1
vote
1answer
119 views

Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to apb

the question: a) Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to $apb$ b) If p is both an equivalence relation ...
3
votes
2answers
636 views

Distinguishing equality and isomorphism as relations

Is this relational characterization of equality in Wikipedia accepted? The identity relation is the archetype of the more general concept of an equivalence relation on a set: those binary ...
0
votes
2answers
139 views

How to calculate equivalence relations

How can I calculate how many equivalence relations can be defined on a given set? For example: How many possible equivalence relations can be defined on S = {a,b,c,d}?
0
votes
2answers
370 views

How do you show that $R$ is an equivalence relation and enumerate one bit string from each of the different equivalence classes of $R$?

If $A$ is the set of all bit strings of length $12$. Let $R$ be the relation define on $A$ where two bit strings are related if the first $2$ bits, the $4^{\text{th}}$ bit and the $7^{\text{th}}$ bit ...
9
votes
1answer
412 views

Is the quotient map a homotopy equivalence?

It is well known that, if $A \subset X$ is a reasonable contractible subspace, then the quotient map $X \to X/A$ is a homotopy equivalence ("reasonable" means that the pair $(X,A)$ has the homotopy ...
5
votes
2answers
155 views

Why are equivalence classes called “classes” and not “sets”?

Why are equivalence classes called so and not equivalence sets? I am kind of not able to find the difference between a class and a set. What properties that a set have that a class cannot have? It ...
4
votes
2answers
127 views

Equivalence relations on classes instead of sets

Can someone please explain to me how to deal with equivalence relations on classes instead of sets? Is there some sort of generalisation of relations? Thank you
6
votes
1answer
491 views

Is “have the same cardinality” a equivalence relation?

A relation is a subset of the Cartesian product of two sets, if "have the same cardinality", denoted as $R$, is a relation, then there must exist set $A, B$, such that $R \subset A \times B$. What are ...
5
votes
1answer
290 views

Is this alternative definition of 'equivalence relation' well-known? useful? used?

I discovered that $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ The nice thing about ...
4
votes
1answer
155 views

The class of equivalence.

Let $Q$ be the following set of $\mathbb{Z}\times \mathbb{Z}$ \begin{align*} Q=\{(a,b)\in \mathbb{Z}\times \mathbb{Z} | b\neq 0\} \end{align*} Define the relation $\sim$ on $Q$ as ...
4
votes
2answers
141 views

Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$.

For $a,b \in \mathbb{R}$ define $a \sim b$ if $a - b \in \mathbb{Z}$ I don't understand how I'm suppose to prove this: Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$ Also can you ...
4
votes
3answers
5k views

Prove that the intersection of two equivalence relations is an equivalence relation.

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R ...
4
votes
2answers
384 views

The fibres of a map form a partition of the domain.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post. This problem is from ...
4
votes
3answers
186 views

What's the name for the equivalence induced by a function on its domain?

Any function $f$ with domain $X$ induces an equivalence relation on $X$, with classes $$\{f^{-1}(\{y\})\,:\, y \in \operatorname{im}f\;\} .$$ Is there a name for this equivalence? Thanks!
4
votes
5answers
3k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
3
votes
1answer
114 views

Surjections and equivalence relations

(a) Let $f: A \to B$ be a surjective function. We define $a_1 \sim a_2$ if $f(a_1)=f(a_2)$. Prove that $\sim$ is an equivalence relation. Reflexivity: This comes for free. If $a_1 \sim a_1$, ...
2
votes
1answer
77 views

If $X,Y$ are equivalence relations, so is $X \times Y$

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
2
votes
3answers
108 views

Equivalence class for the relation of having the same set of prime divisors

For an integer $n\in \mathbb{N}$ define $P(n) = \{p : p \mid n \text{, where $p$ is a prime} \}$. For example $P(12)=\{2,3\} $ and $P(1)=\emptyset$. Question: Consider the relation $R$ on ...
2
votes
4answers
313 views

Showing that $R$ is an equivalence relation on $X \times X$

Let $X = \{1,2,3,..,10\}$ define a relation $R$ on $X \times X$ by $(a,b)R(c,d)$ if $ad=bc$. Show that R is an equivalence relation on $X \times X$. I know that the $R$ have to be reflexive (because ...
1
vote
2answers
70 views

Transitive, symmetric $R$ such that for all $x$, there is $y$ such that $xRy$, is an equivalence relation

I'm stuck at one particular task I'm working on. Here is the task: Let R be a transitive and symmetrical relation on $S$. Assume that for all $x \in S$ there is a $y \in S$ so that $xRy$. ...
1
vote
2answers
232 views

Is this alternative definition of 'equivalence relation' correct?

I was puzzling over another question: Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$. And this made me discover that $$(0) \; \langle \forall a,b :: aRb ...
1
vote
2answers
989 views

Congruence Class $[n]_5$ (Equivalence class of n wrt congruence mod 5) when n = $-3$, 2, 3, 6

The question is, "What is the congruence class$[n]_5$ (that is, the equivalence class of $n$ with respect to congruence modulo 5) when n is a) 2? b)3? c) 6? d)−3?" I know this is more work ...
0
votes
2answers
80 views

Proofs on equivalence relations rational numbers

The relation R = {(x, y)|x − y is an integer} is an equivalence relation on the set of rational numbers. I'm kind of confused with this question and what it is asking me to do. In order to solve ...
0
votes
1answer
47 views

Equivalence relation for set given as matrix

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I ...
0
votes
1answer
59 views

Double check $G\sim H$ iff $G≈H$

Let $S$ be the collection of all groups. Define a relation on $S$ by $G \sim H$ iff $G ≈ H$. Prove that this is an equivalence relation. So $S$ is partitioned into isomorphism classes. Proof: Let ...
0
votes
2answers
67 views

For all $x,y∈\Bbb{R}$ define that $ x\equiv y$ if$ x^2=y^2$

For all $x,y\in\Bbb{R}$ define that $x\equiv y$ if $x^2=y^2$ . Then $\equiv$ is an equivalence relation on $\Bbb{R}$ , there are infinitely many equivalence classes, one of them consists of one ...
0
votes
0answers
63 views

For all $x,y\in\mathbb{R}$ define that $x\equiv y$ if $x^{2}=y^{2} $; prove $\equiv$ is an equivalence relation. [duplicate]

For all $x,y\in\mathbb{R}$ define that $x\equiv y$ if $x^{2}=y^{2}$ . Then $\equiv$ is an equivalence relation on $\mathbb{R}$ , there are infinitely many equivalence classes, one of them ...
0
votes
1answer
78 views

Equivalence relations and power sets.

Let $\mathcal{A}$ be the class of all sets and define the relation $R$ on $\mathcal{A}$ as: $A\space R\space B$ iff there is a bijective function $f:A \to B$. Prove that $R$ is an equivalence relation ...
0
votes
1answer
107 views

Equivalence relations on S given no relation?

On my assignment, one of the questions ask to list all equivalence relations on S and count how many are of partial orders. Let S = {u, v, w}. List all equivalence relations on S. How many of these ...
0
votes
2answers
113 views

Revisted$_2$: Are doubling and squaring well-defined on $\mathbb{R}/\mathbb{Z}$?

Define a relation $\sim$ on $\mathbb{R}$ as follows: for any $a,b \in \mathbb{R}$, $$a\sim b \iff a-b\in \mathbb{Z}.$$ Let $S=\mathbb{R}/{\sim}$. That is, $S$ is the set of equivalence classes of ...
0
votes
1answer
215 views

Rational Numbers and Equivalence Classes

Describe the rational numbers as the equivalence classes for an equivalence relation on certain pairs of integers.
0
votes
1answer
133 views

Proving $\;x-y \in2\pi \mathbb Z\;$ defines an Equivalence Relation

Prove that $\;x-y \in2\pi \mathbb Z\;$ defines an equivalence relation on $\;\mathbb R.$
0
votes
1answer
207 views

Equivalence Relation? Column-equivalence on the set of all $m\times n$ matrices.

How do I show that column equivalence on the set of all $m\times n$ matrices is an equivalence relation? I know that to show it is an equivalence relation, I need to show that column equivalence is ...
-1
votes
2answers
56 views

Is this relation reflexive?

Suppose $R$ is a relation on $N_4=\{1,2,3,4\}$ such that $R\circ R = R$. How would I prove that $R$ is reflexive? Could you give me some tips about how to start off?
-1
votes
2answers
143 views

Cardinality of “$x-y\in\Bbb Q$”-equivalence class of $1/\sqrt2$

For $x,y\in I:=[0,1]$ define the relation on $I$ as $x-y\in \Bbb Q$. How big (using cardinal number) is the cardinality of the equivalence class $[1/\sqrt2]$? I have tried to solve it by ...
-2
votes
1answer
77 views

Cardinality of “x−y∈Q”-equivalence class of 1/2 √ [duplicate]

For x,y∈I:=[0,1] define the relation on I as x−y∈Q. How big (using cardinal number) is the cardinality of the equivalence class [1/√2]? I have tried to solve it by finding the equivalence class but ...
7
votes
2answers
167 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
2
votes
1answer
90 views

Is there a name for this property: If $a\sim b$ and $c\sim b$ then $a\sim c$?

Let $X$ be a set with a binary relation $\sim$, such that for all $a$, $b$, and $c$ in $X$: If $a\sim b$ and $c\sim b$ then $a\sim c$ Is anyone familiar with this property of a binary relation? ...
6
votes
1answer
160 views

Solve for ? - undetermined inequality symbol

So I was solving a problem in Rudin (chapter 3 #16, to be specific) and I realized how convenient it would be to have a symbol that represented an undetermined equivalence relationship. As an example ...
5
votes
2answers
6k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
4
votes
4answers
2k views

Proving an equivalence relation on $\mathbb{Z}\times\mathbb{Z}$

I'm working on some discrete mathematics problems, and have run into an issue involving proving an equivalence relation. The relation I'm tasked with proving is the relation $R$ defined on ...
2
votes
1answer
70 views

Measure spaces s.t. $\mathcal{L}^1 = L^1$

I have two questions: 1, Give an example of a measure space such that $L^{1}(X,\mathcal{A},\mu) = \mathcal{L}^{1}(X,\mathcal{A},\mu)$. 2, State, and prove, a condition on $\mu$ which is equivalent ...
2
votes
0answers
210 views

Attempting to find a specific similarity (equivalence) matrix

Apologies if this has already been asked - I searched but couldn't find. My question is regarding matrix similarity (equivalence): I have a square matrix $A$ that is of permutation form and (square) ...
1
vote
1answer
176 views

I don't understand equivalence relations

I'm trying to show that the left coset with a subgroup is an equivalence relation. So taking some element $g \in G$ and a subgroup $H$, the left coset is defined as $gH = \{gh : h \in H\}$. That means ...
0
votes
1answer
159 views

How to prove the Cone is contractible?

Let $\sim$ be an equivalence relation on a topological space $X$ with a subset $A ⊂ X$ such that the equivalence classes are: $A$ itself and Singletons $\{x\}$ such that $x ∉ A$. Then define $X/A$ ...
0
votes
1answer
108 views

Equivalence relation classifying the slopes of the tangent lines to the curve?

We apply the Mean value theorem to a real analytic function $f$ (defined on $\mathbb R$) in the interval $(u,a)$ such that $f(u)=0$ and $f(a)\neq 0$ to find a $c\in(u,a)$ such that: the expression ...