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

learn more… | top users | synonyms

42
votes
4answers
6k views

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
11
votes
4answers
5k 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
1answer
70 views

Define a relation and find its equivalence classes.

Define a relation $\sim$ on $\Bbb{N}$ as follows. For any $a,b∈\Bbb N$, $a\sim b$ if and only if $ab$ is a perfect square. Show that $\sim$ is an equivalence relation. What are the equivalence classes?...
3
votes
7answers
257 views

The map $f:\mathbb{Z}_3 \to \mathbb{Z}_6$ given by $f(x + 3\mathbb{Z}) = x + 6\mathbb{Z}$ is not well-defined

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is not a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ ...
1
vote
1answer
193 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
814 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 ...
1
vote
5answers
6k 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 ...
0
votes
2answers
192 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}?
9
votes
1answer
675 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 ...
6
votes
3answers
4k views

Definition of “quotient set”

I searched and searched about quotient set and cannot figure out what it is. At the beginning, I thought it was the same as partitions, but now I'm confused. Can someone show some examples and explain?...
3
votes
0answers
87 views

Unitary Farey Sequence Matrices

Take the Farey sequence $\mathcal{F}_n$ with values $a_m\in \mathcal{F}_n$ and put them into a vector $$ \vec v_k=\frac1{\sqrt{|\mathcal{F}_n|}}\biggr(\exp(2\pi i k a_m)\biggr)_m $$ The dimension of ...
7
votes
1answer
861 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
3answers
8k 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
132 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
1
vote
1answer
223 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 ...
5
votes
1answer
81 views

Cardinality of equivalence relations in $\mathbb{N}$

I came across this long proof on this site: Cardinality of relations set But I would like to know whether my direction can work. Say we want to find the cardinality of all equivalence relations in $...
5
votes
1answer
297 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
2answers
504 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
188 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
2answers
155 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
5answers
4k 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 ...
4
votes
1answer
189 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 \begin{align*} ...
3
votes
4answers
369 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 ...
3
votes
1answer
84 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 equivalence ...
3
votes
1answer
41 views

Show that $X$ can be represented as a union of disjoint equivalence classes

Let $X$ be a set. Let $\sim$ be an equivalence relation on $X$. Show that $X$ is the union of disjoint equivalence classes $\{x\}$ for $x \in X$. What I have tried: claim: $X = \bigcup_{x\in X} \{ x ...
3
votes
1answer
187 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
3answers
883 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
2answers
239 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
1answer
627 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
2answers
2k 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
1answer
115 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
114 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
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
213 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
2answers
68 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
1answer
60 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 $S$ ...
-1
votes
2answers
66 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?
9
votes
3answers
7k views

why is frobenius norm of a matrix greater than or equal to the 2 norm?

How can you prove that: $$\|A\|_2 \le \|A\|_F$$ I cannot use: $$\|A\|_2^2 = \lambda_{max}(A^TA)$$ It makes sense that the 2-norm would be less than or equal to the frobenius norm but I dont know how ...
7
votes
2answers
182 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 ...
5
votes
3answers
14k 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: {$(a,a)(a,b)(a,c)(a,d)(b,a)(b,...
3
votes
2answers
57 views

We Quotient an algebraic structure to generate equivalence classes?

Till now I visualized Quotient groups as a technique to generate equivalence classes whenever needed, as in $\mathbb{Z}/n\mathbb{Z}$. But now I have a feeling of doubt since I haven't seen a book that ...
2
votes
1answer
96 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
211 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 ...
6
votes
1answer
292 views

How to simply show that there are “78 'strict ordinal' 2x2 game matrices”

In "Theory of Moves", Steven J. Brams analyses two-player games with two strategies per player, where each player can totally rank his payoffs, although payoffs need not be comparable among players. ...
4
votes
4answers
3k 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 $\mathbb{...
3
votes
4answers
787 views

connected components equivalence relation

Prove that the relation $x \sim y$ iff $y$ is an element of the connected component of $x$ is an equivalence relation. This question is confusing me, do I simply go about showing the relation is ...
2
votes
1answer
79 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
222 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
328 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$ ...
-1
votes
3answers
222 views

When can we modify $a \propto \ b$ adding $\delta $?

This is a general, theoretical question about formalization of concepts, it is difficult for me to explain it adequately, please, if I fail, tell me in a comment what is not clear or feel free to edit ...