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

learn more… | top users | synonyms

0
votes
2answers
31 views

What is the equivalence class of the following equivalence relation?

If we have a equivalence relation $R=_{def} \{((x_1,y_1),(x_2,y_2)) ~~| ~~x_1-y_1=x_2-y_2 \} \subseteq \mathbb{R}^2 \times \mathbb{R}^2 $ What is the equivalence class $[(0,1)]_R$? I thought it ...
0
votes
1answer
116 views

Show that R is an equivalence relation on X for x, y in X iff f(x) = f(y)

$f:X→Y$ $x,y ∈ X,xRy$ iff $f(x) = f(y)$ Show that R is an equivalence relation on X. Also when $X = Y = \mathbb{R}$ and $f: \mathbb{R} \to \mathbb{R} $ with $x \mapsto x^2$ for all $x∈R$ find the ...
1
vote
2answers
111 views

Prove that the relation on $X$ given by $x\sim y$ if $f(x)=f(y)$ is an equivalence relation

Let $f:X\to Y$ be a function between two sets. Prove that the relation on $X$ given by $x\sim y$ if $f(x)=f(y)$ is an equivalence relation. I know that it should have $3$ cases, reflexive (for all $x$...
0
votes
1answer
27 views

Stuck on equivalence relations

Let R be the relation on the set of ordered pairs of positive integers such that $((a, b), (c, d)) \in R$ if and only if $ad = bc$. What are the equivalence classes of this relation? I am completely ...
1
vote
0answers
20 views

equivalence class of kernel relation of floor function

By taking particular values of $k$, I found that equivalence class of $k$, $[k]=\{k,k+1,k+2,...,2k-1\}$, equivalence class of $2k$, $[2k]=\{2k,2k+1,2k+2,...,3k-1\}$ and so on, but how to present it ...
1
vote
0answers
9 views

Number of symmetric relations

Let set $A=\{1,2,3\}$ Find number of symmetric relations that can be defined on $A$ containing ordered pairs $(1,2)$ and $(2,1)$ is? Can someone give me some hint for this question?
1
vote
1answer
40 views

Show that either $[x] = [y]$ or $[x]$ and $[y]$ are disjoint?

An equivalence class $[x]_R$ is defined by $[x]_R = [y ∈ X : xRy]$. In this proof I'm supposed to start by assuming $[x]$ and $[y]$ are not disjoint. Therefore, there is some element $z$ that is in $[...
2
votes
4answers
155 views

How do you show one way equivalences in mathematics?

In the real world, it seems you can often take a set of things and create new things with them. Let's say you want to make bread, for example. Normally, you can create bread by putting together flour, ...
1
vote
5answers
27 views

Show that $x$ is an element of its own equivalence class?

If $R$ is an equivalence relation on $X$ and $x$ is an element of $X$, the equivalence class is defined as $[x]_R = [y ∈ X : xRy]$. Since $x$ is equivalent to itself, doesn't that automatically make ...
1
vote
1answer
37 views

Relations and their fallacies

I need to find a flaw in the proof of the following statement: Any relation that is symmetric and transitive is also reflexive. False Proof: aRb implies bRa,by symmetry. Then by transitivity, aRa ...
0
votes
2answers
53 views

Proving an equivalence relation on a $\mathbb Z\times \mathbb Z$

I am having some trouble understanding how to prove that a given binary relation is an equivalence relation. I understand that to prove that a relation is an equivalence relation, you must prove ...
1
vote
1answer
38 views

Which of the following equivalence classes are equal?

Let R be the relation of congruence modulo 3. Which of the following equivalence classes are equal. [7], [-4], [-6], [17], [4], [27], [19] The answer is: [7]=[4]...
0
votes
0answers
12 views

Is Congruence Class an example of Equivalence Class? (Understanding the definition through Examples)

Would you say a congruence class such as $[0]_{4}, [1]_{4}, [2]_{4},$ and $[3]_{4}$ an example of Equivalence classes since: the set of all elements of $\{..., -8, -4, 0, 4, 8,...\}$ is related to $[...
1
vote
2answers
38 views

What does it mean for f([x])=[2x] for a function mapping R/Z to R/Z?

Let X=R/Z (the circle), with a map $f : X → X$ given by $f([x]) = [2x]$. I'm a little lost on what $f([x]) = [2x]$ means. I thought the function was mapping the equivalence class [x] to the ...
0
votes
0answers
17 views

Find equivalence classes

A is set of all propositional expressions on the propositions p1 , p2 , . . . , pn. Relation R on A is defined as (P, Q) ∈ R if P ↔ Q is a tautology. I think it is an equivalence relation, what should ...
0
votes
1answer
30 views

Equivalence Classes of an Equivalence Relation Confusion (definition and solution included)

The Definition of Equivalence Classes of an Equivalence Relation is given as: Suppose $A$ is a set and $R$ is an equivalence relation on $A$. For each element $a$ in $A$, the equivalence class of a, ...
0
votes
1answer
26 views

Showing an equivalence relation

Let $[n]$ denote the set of all permutations. Let $R$ be the relation $$i_1 i_2\cdots i_n=j_1 j_2\cdots j_n$$ if and only if there exists a $k$ such that $j_1 j_2 \cdots j_n=i_k i_{k+1}\cdots i_n i_1 ...
0
votes
1answer
120 views

Equivalence classes under logical equivalence by 13 valuations

Let L be the set of 5 propositional variables. Under the equivalence relation given by logical equivalence, how many equivalence classes of propositional terms are given the value TRUE by 13 ...
1
vote
2answers
98 views

Why not just define equivalence relations on objects and morphisms for equivalent categories?

My question is regarding this blog post https://unapologetic.wordpress.com/2007/05/30/equivalence-of-categories/ which I will paraphrase below: The author gives the example of a category $\mathscr{C}$...
1
vote
1answer
47 views

definition of the directed colimit of a functor

Let $(\Lambda,\le )$ be a directed set, which we can understand as a small category: The set of all objects is $\Lambda$ and for $\lambda,\lambda '\in \Lambda$ there exists an unique morphism $i_{\...
0
votes
1answer
26 views

Proving Equivalence Relations by providing an example based on given subsets.

Let $X$ be the set of all nonempty subsets of $\{1, 2, 3\}$. Then $X= \{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$ Define a relation $ R $ on $X$ as follows: For all $A$ and $...
0
votes
1answer
30 views

Proving the Binary Relation is an Equivalence Relation

Let $R$ be a binary relation on a set A and suppose R is symmetric and transitive. Prove the following: If for every $x$ in $A$ there is a $y$ in $A$ such that $x R y$, then $R$ is an equivalence ...
0
votes
1answer
21 views

Finite group existence of equivalence relation

I was reading about cosets and, given the fact that if $H$ is a non empty subset of a finite group G, we have the following equality $[G:H]|H|=|G|$, I came up with the following question: If the ...
3
votes
2answers
53 views

Proving a function $\mathbb{Z}_m \to \mathbb{Z}_m,\ [a] \mapsto [a^2 + 3a + 1]$ is well defined

Prove that $\operatorname{poly}\colon \mathbb{Z}_m \to \mathbb{Z}_m$ given by $\operatorname{poly}\colon [a] \mapsto [a^2 + 3a + 1]$ is well defined. This is what I have so far, working in (mod m) ...
4
votes
3answers
479 views

Why is one relation transitive but the other is not?

From what I have read about a transitive relation is that if xRy and yRz are both true then xRz has to be true. I'm doing some practice problems and I'm a little confused with identifying a ...
1
vote
1answer
25 views

51 people enter a raffle with 10 prizes; 7 are pencils and 3 are cars. How may ways are there to give out the prizes?

Assume that no one can win more than one prize. If the prizes were all different, then we have the case that order matters and repeats are allowed, meaning there are $P(51, 10)$ ways of handing out ...
0
votes
1answer
25 views

Show that $[a][\star][b] :=[a \star b]$ defines an operation on $G/\sim$.

Let $G$ be a set equipped with an operation $\star$ and an equivalence relation $\sim$. Suppose that $\sim$ is compatible with $\star$, i.e., for elements $a$, $a'$, $b$, $b'$ of $G$, $$\text{if}\ a \...
1
vote
1answer
63 views

If $R$ is an equivalence relation, is $R = R^3$?

If $R$ is an equivalence relation, does $R = R^3$ ? I tried for about 40minutes to construct a relation $R$ that is an equivalence relation that when multiplied with itself twice, it will make $R = R^...
0
votes
1answer
29 views

Proving that rational equivalence is an equivalence relation on any set.

I seek to prove that the rational equivalence relation is an equivalence relation, in that it is reflexive, symmetric, and transitive. The rational equivalence relation is as follows "Two numbers in ...
0
votes
1answer
30 views

Relations and equivalence classes example

I'm studying discrete mathematics in my course at university and I'm going through notes on relations, equivalence relations and classes and such. I've come across an example on equivalence classes ...
0
votes
1answer
26 views

Equivalence Relations of n|(x1-x2)

How would one prove that if $x_1$ and $x_2$ are elements of $\mathbb{Z}$, then $x_1$ ~ $x_2$ <=> $n$|$(x_1 - x_2)$? Giving an example, such as $n=6$ or such would better help me understand the ...
1
vote
3answers
10 views

Equivalence Relations and Classes 3

I am studying for a discrete math exam that is tomorrow and the questions on equivalence classes are not making sense to me. Practice Problem: Let $\sim$ be the relation defined on set of pairs $(x, ...
0
votes
3answers
47 views

What are the equivalence classes for the relation “congruence modulo 5?”

I'm still a little mixed up on equivalence classes, so I'm trying to make some connections. I need to be specific of how many there are and what is in each. Here's what I have: Let $\mathscr R$ be ...
0
votes
1answer
48 views

Let ∼ be an equivalence relation on a set $A$, and let $a, b ∈ A$. Prove that $a ∈ [b]$ iff $b ∈ [a]$.

I have the following proof outline, but I am not sure how to get started proving this. Can anyone point me in the right directon? Proof. Suppose that $\sim$ is an equivalence relation on a set $A$, ...
0
votes
1answer
54 views

Prove that, with vector addition and scalar multiplication well-defined, $V/W$ becomes a vector space over $k$.

Let $V$ be a vector space over a field $k$ and let $W$ be a subspace of $V$. Prove that, with vector addition and scalar multiplication well-defined, $V/W$ = {$v+W | w\in W$} becomes a vector space ...
1
vote
1answer
17 views

Relation and proving reflexivity

The relation R is defined on integers by $xRy$ if and only if $x^2y=ymod6$. Prove that $R$ is reflexive. So far I have: Let $x=y$ $x^2x=xmod6$ I don't know how to go from here... because $x^2=...
1
vote
1answer
51 views

What is the formalism of category theory to express an equivalence relation?

Say I have an abstract set $X$ (could be points, functions, functors or whatever). Say I have an equivalence relation $R\in X\times X$. What would be the category-theory way to express $X/R$, that ...
0
votes
1answer
57 views

Equivalence Relations on Products

Let $G$ be a group, $p$ a prime dividing $|G|$ and $X = \{(x_0,..., x_{p−1})) ∈ G_p:∏_i x_i = 1\}.$ Let $E$ be the relation defined on $X$ by $(x_0, ..., x_{p−1})E(y_0,..., y_{p−1})$ if there exists $...
1
vote
2answers
52 views

Which of the following are partitions of $\mathbb R^2$

Is my answer correct? Can someone provide me better explanations for (a) ,(c) and (d)? Which of the following collections of subsets of the plane $\Bbb R\times\Bbb R$ are partitions? $(a)$ $\...
0
votes
2answers
172 views

How to prove the relation is transitive?

Problem: Consider the relation R on $N$ defined by $x$R$y$ iff $2$ divides $x + y$. Prove that R is an equivalent relation My work: I know that to prove that a relation is an equivalent relation, ...
0
votes
0answers
49 views

proof a code is equivalent to any code with the code word 00..0 of length n

Let $C$ and $C'$ be codes over a $q$-ary alphabet $A$. We say that $C$ and $C'$ are equivalent if one can be obtained from the other by repeatedly applying the following two operations ...
2
votes
2answers
37 views

Show given relation $R$ is equivalence relation on $S$

I will display the exact problem, then my questions. I have searched to the extremes to figure this out and can't: Show that the given relation $R$ is an equivalence relation on set $S$. $S$ is the ...
1
vote
1answer
72 views

Name of and references for the equivalence relation $x \sim y :\Longleftrightarrow x^2 = y^2$

Playing around with the concepts of negativity and positivity, I came across the following equivalence relation defined for all elements $x,y$ of a field $\mathbb{F}$: $$ x \sim y :\Longleftrightarrow ...
-1
votes
1answer
37 views

Transitivity of a binary relation on the power set

I'm studying for a test and there's a question that I've tried and I don't understand: Let $E$ be a binary relation on a set $A$; let a binary relation $F$ on $\mathcal P (A) \setminus \{\emptyset\...
1
vote
0answers
36 views

Prove that multiplication is well defined

Let $M = \mathbb{N} \ \mathbb{x} \ \mathbb{N}$. We define the following relation on $M$. Let $(a,b)R(a',b')$ iff $a + b'=a'+b$ We define the set of intergers $\mathbb{Z}$, to be the set of ...
1
vote
1answer
31 views

equivalence relation and quotient set, Given $A = \{0,1,2,3,4,5\}$

Given $A = \{0,1,2,3,4,5\}$, Write the appropriate equivalence relation of this quotient set: $$A/_R = \{\{1,2\},\{3\},\{4,0,5\}\}$$ Well, if it was to compute $$A/_R = \{\{0\},\{1\},\{2\},\{3\},\{4\}...
1
vote
2answers
20 views

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$. Well, I've proved really easily that it is reflexsive, symmetrical and transitive. But I'm ...
3
votes
4answers
86 views

Show that $R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid(5x+3y)\}$ is an equivalence relation.

Let $R$ be a relation on $\mathbb{Z}$ defined by $$ R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid (5x+3y)\}.$$ Show that $R$ is an equivalence relation. I'm having a bit of trouble with ...
3
votes
2answers
46 views

Give a complete set of equivalence class representatives for an equivalence relation on the natural numbers (including zero)

The full question: Having an equivalence relation $\sim$ on $\Bbb N$ defined by: $a \sim b$ meaning $a,b\in\Bbb N$ such that $a=b*10^k,$ for some $k\in\Bbb Z$, give a complete set of equivalence ...
0
votes
3answers
104 views

Compute equivalence classes of equivalence relation

I have already proven that the relation $R=\{(x,y) \in \mathbb Z \times \mathbb Z \mid x+y\text{ is even}\}$ is an equivalence relation by showing reflexive, symmetric, and transitive properties of ...