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

learn more… | top users | synonyms

5
votes
4answers
2k 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
80 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
2answers
356 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
65 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
317 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
268 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 ...
2
votes
3answers
2k 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 ...
2
votes
3answers
333 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
58 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
217 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
385 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
84 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
122 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
117 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
176 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
105 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
64 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
150 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 ...
0
votes
1answer
93 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
2answers
320 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
102 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
109 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
199 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
52 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
146 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
508 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
298 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
83 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
250 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
239 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
860 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
49 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
85 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
487 views

Number of equivalence relations

How many different equivalence relations can be defined on a set of five elements?
1
vote
0answers
140 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
127 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
725 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
35 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
44 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
72 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
248 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$.
0
votes
1answer
237 views

Equivalence Relations On A Set of All Functions From Z to Z

The question is, "Which of these relations on the set of all functions from $Z$ to $Z$ are equivalence relations. $\{(f,g)|f(1)=g(1)\}$ I just want to make certain that I am interpreting this ...
0
votes
1answer
149 views

Equivalence Classes and such for the Relation: x and y have the same first and third letter.

Let A be the set of all possible strings of 3 or 4 letters in alphabet ${A,B,C,D}$, let z = $BCAD$, and let $(x,y)\in R$ if and only if $x$ and $y$ have the same first letter and the same third letter ...
-1
votes
1answer
25 views

list all the equivalence relation [duplicate]

list all the equivanlance relations in the set A={1,2,3,4) so there should be 15 right? so what I got so far (1 1) (22) (33) (44) (12) (13) (14) (21) (23) (24) (31) (32) (34) (41) (42) (43) these ...