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

learn more… | top users | synonyms

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
67 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?...
1
vote
1answer
186 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
794 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
185 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
662 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
4k views

Definition of “quotient set”

I search and search 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
86 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
856 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
221 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
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 ...
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 $...
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
2answers
502 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
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*} ...
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!
3
votes
1answer
39 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
4answers
367 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
186 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
873 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
618 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 ...
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 \...
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
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
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$ ...
0
votes
1answer
208 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
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 ...
-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
6k 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
181 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
13k 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
56 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
210 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
291 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
775 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
221 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
326 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
221 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 ...
11
votes
5answers
1k views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
5
votes
2answers
855 views

Sets, functions and relations problem

Yes this is a homework problem but I have attempted to solve it and my work is below, also this is my first question here so I'm sorry for any mistakes: Question: Context: Let $A$ and $B$ be subsets ...