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

learn more… | top users | synonyms

6
votes
4answers
3k 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 ...
2
votes
1answer
97 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
368 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 ...
2
votes
2answers
422 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
85 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
318 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 ...
5
votes
1answer
275 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 ...
3
votes
3answers
3k 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 ...
1
vote
2answers
61 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
223 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
478 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
64 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
61 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
87 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
110 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
138 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
120 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
180 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
111 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
71 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
156 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 ...
4
votes
4answers
1k 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 ...
1
vote
1answer
138 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
99 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 ...
5
votes
0answers
153 views

Colored Picture for Equivalence Classes, Relations, Partitions, .. [closed]

Origin — A Book of Abstract Algebra — Charles Pinter — p120. I'm trying to sketch a colored picture for the ideas from equivalence classes, equivalence relations, partitions, etc... underneath. ...
5
votes
2answers
421 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 ...
4
votes
2answers
109 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
119 views

How do I work with a relation that is a set of 4-tuples?

Define the relation $\sim$ on $\mathbb{Z}\times\mathbb{Z}$ by $(a,b)\sim(c,d)$ if $a-c=b-d$. Show that $\sim$ is an equivalence relation. What is the equivalence class of $(1,2)$? I'm not sure ...
3
votes
3answers
252 views

Equivalence relation question with functions

We'll define on the set: $A=\Bbb R^{[0,1]}$ the relation $R$ by $fRg$ if $f(0)=g(0)$. Make sure it's an equivilence relation. What is $[\cos x]$ ? Describe all the equivalence classes ...
3
votes
1answer
57 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$, ...
3
votes
2answers
156 views

Equivalence classes of “$x \sim y \Longleftrightarrow x -y $ is rational”.

Given the equivalence relation $x \sim y \Longleftrightarrow x -y $ is rational on the interval $[0,1)$. How do we reason* that there are uncountably infinite number of equivalence classes? *A ...
3
votes
2answers
555 views

Working with Equivalence Classes and Quotient Sets

I have a doubt about working with equivalence classes and quotient sets. The definition that I know, is that given an equivalence relation $\sim$ on a set $A$, the set of all elements of $A$ ...
3
votes
2answers
331 views

Equivalence relations on natural numbers

How many equivalence relations are there on $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers? How can one compute it?
2
votes
2answers
1k 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: ...
2
votes
2answers
85 views

Proof of Equivalence relation ~ on $\mathbb{Z}\times\mathbb{Z}$ such that $(a,b)$~$(c,d)$ when $a+b=c+d$

Define a relation ~ on $\mathbb{Z}\times\mathbb{Z}$ such that $(a,b)$~$(c,d)$ when $a+b=c+d$. To prove ~ is an equivalence relation, I need to prove reflexive, symmetric, transitive, right? For the ...
2
votes
4answers
279 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
4answers
253 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 ...
2
votes
1answer
1k views

How to prove these three norm equivalence problems

Given $A \in R^{m\times n}$, I have these three norm equivalence equations: $\|A\|_2 \le \|A\|_F \le \sqrt {n}\|A\|_2$ $\frac {1} {\sqrt n}\|A\|_{\infty} \le \|A\|_2 \le \sqrt {m} \|A\|_{\infty}$ ...
2
votes
3answers
975 views

Equivalence Relation On A Set Of Ordered-Pairs

The question is, "Let R be the relation on the set of ordered pairs of positive integers such that $((a, b), (c, d)) ∈ R$ and only if $a+d=b+c$. Show that R is an equivalence relation." There are two ...
2
votes
4answers
2k views

Equivalence Relations

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 ...
1
vote
1answer
63 views

Number of Equivalence relations of $\{1,2,3\}$

Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists? My idea is to count the disjoint partitions of M: $K_1= ...
1
vote
1answer
116 views

Prove or disprove question with equivalence relation, classes and quotient group

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
1
vote
2answers
581 views

Number of equivalence relations

How many different equivalence relations can be defined on a set of five elements?
1
vote
0answers
156 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
2answers
130 views

Is this an equivalence relation (reflexivity, symmetry, transitivity)

Let $\theta(s):\mathbb{C}\to \mathbb{R}$ be a well defined function. I define the following relation in $\mathbb{C}$. $\forall s,q \in \mathbb{C}: s\mathbin{R}q\iff\theta(s)\ne 0 \pmod {2\pi}$ (and) ...
1
vote
3answers
785 views

Finding The Equivalence Class

Okay, so the question I am working on is, "Suppose that A is a nonempty set, and $f$ is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs $(x, y)$ such ...
0
votes
1answer
37 views

Proving that $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$

This assingment is preparation for exam. I need to prove with $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$ that $\sim$ is equivalence relatio. Can you tell me how to do this. ...
0
votes
1answer
54 views

Help visualize set of all equivalence relations

I want to prove that the poset $Eq(A)$ with $\subseteq$ as the partial ordering is a complete lattice. But before even beginning to prove it, I have trouble visualizing the poset of $Eq(A)$. Kindly ...
0
votes
1answer
76 views

Relation $R$: $R\circ R \subseteq R \implies R$ is transitive

Let $R$ be a relation on $X$, a set. If $R\circ R\subseteq R$, then is $R$ transitive?
0
votes
2answers
303 views

Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$.

Hello I need help with the proof strategy for this problem. Let $R$ be an equivalence relation on a set $A$ and let $a,b \in A$. Prove that $[a] = [b]$ if and only if $aRb$.