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

learn more… | top users | synonyms

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 ...
1
vote
2answers
88 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 ...
0
votes
1answer
25 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 ...
1
vote
1answer
45 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 ...
0
votes
1answer
17 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 ...
0
votes
1answer
113 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 ...
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 ...
4
votes
3answers
476 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 ...
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 = ...
0
votes
1answer
28 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
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 ...
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
9 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
39 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
46 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
44 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
16 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 ...
1
vote
1answer
50 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
24 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
56 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
49 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
0answers
48 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
36 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
71 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
35 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 ...
1
vote
0answers
35 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
28 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 = ...
1
vote
2answers
19 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
2answers
43 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 ...
1
vote
1answer
30 views

Relation $ (x,y) \in \rho \Leftrightarrow (\exists k \in \mathbb{Z})\mid x- y=3k$

I know that there is a similar question here, but it's about classes of equivalence of this relation. I would like to know how to prove that this is an equivalence relation. It seems simple, but the ...
2
votes
1answer
28 views

congruent modulo S

This is most likely a silly English question, but in Roman's "Advanced Linear Algebra," on page 21, he writes that: Let $S$ be a subset of a commutative ring $R$ with identity. Let $\equiv$ be the ...
1
vote
1answer
48 views

Show that the equivalence classes give a partition of $X$. [duplicate]

"... the following subset of $X$ denoted by $[x]$ $(x\in X)$ is called the equivalence class generated by $x$: $$[x]:= \{y \in X; x\sim y \}$$ Show that the equivalence classes give a partition of ...
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 ...
1
vote
0answers
40 views

relations and equivalence classes

$S$ is the set of all equivalence relations on set $A = \{1,2,3,4,5,6,7,8,9\}$ in which one of the equivalence classes is $\{1,3,5,7,9\}$. What is the size of $S$? I don't even know how to start... ...
0
votes
1answer
35 views

Propositional Equivalence

Are the following two propositions equivalent? p IMPLIES (q IMPLIES r) p IMPLIES (q AND r) From what I can tell, using the logical equivalences, this should be false, correct? p ...
0
votes
1answer
17 views

Is this relation symmetric?

While solving questions related to reflexivity, symmetricity and transivity of relations, I came across this question: Show that the relation $R$ in the set $A = \{1,2,3\}$ given by $R = ...
0
votes
1answer
68 views

Isn't x/E = y/ E ⇔ x E y deduced, not just x/E = y/ E ⇒ x E y from (a) x/ E≠ Ø, (b) x/E ∩ y/ E ≠ Ø ⇔xEy?

"Theorem 3. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. Then (a) Each $x/\mathscr E$ is a nonempty subset of $X$. (b) $x/\mathscr E \cap y/\mathscr E \neq \emptyset$ if ...
0
votes
2answers
75 views

Total Number of Equivalence classes of R

I was given the following question for homework: Let P denote the set of all compound propositions involving the simple/atomic propositions p, q, and r and the logical connectives ∨, ∧, and ¬ ...
0
votes
0answers
34 views

Determine which of the following are equivalence relations:

Let $\mathbf{X}$ be the set of all residents in New Jersey. Determine which are equivalance relations: a) $x\sim y$ provided $y$ has the same natural parents as $x$ b) $x\sim y$ provided $y$ lives ...
0
votes
1answer
39 views

Addition in the space of orbits (under group action)

This question may be very trivial in this area, but I am a beginner to this and I stuck here. Could anyone please help me here! Let $\Gamma$ be a group whose identity is $e$. Let $X$ be a set and ...
1
vote
1answer
28 views

Prove that $\sigma^*$ is the least group congruence on $S$

Let $S$ be an inverse semigroup and consider the relation $\sigma$ on $S$ given by $$a \sigma b \iff ab^{-1} \in E(S)$$ Consider the congruence generated by $\sigma$, say $\sigma^*$. Prove that ...
1
vote
1answer
65 views

How to prove equivalence relations

I'm going through Pinter's "A Book of Abstract Algebra" and I'm currently on the topic of Partitions and Equivalence Relations. I'm having a little trouble understanding the way he (and apparently ...
1
vote
1answer
39 views

Equivalence class of functions with commutative diagram.

Let $S$, $T$ be sets, and $f,g: S \to T $ be function satisfying a condition that, there exist $\phi : S \to S, \rho : T \to T$, bijections, such that $f = \rho^{-1} \circ g \circ \phi$. Then we call ...
2
votes
1answer
53 views

Geometric description of equivalence classes.

For $X = R^2$ define the relation $R$ on $X$ by $(x_1, y_1)R(x_2, y_2)$ if $x_1 = x_2$. a). Verify that $R$ is an equivalence relation on $X$. I've already shown that this is reflexive, symmetric, ...
1
vote
1answer
51 views

Is the relation on a singleton set an equivalence relation?

So I understand that for a relation on a set to be an equivalence relation, it must satisfy three axioms: For all $x, y, z \in X$ and the relation $R$ on $X$, $(x,x) \in R$ if $(x,y) \in R$ then ...
0
votes
1answer
11 views

What is the meaning of cyclically equivalence classes of multiple indices?

Can you please give me an example for the cyclic equivalence classes of multiple indices on the following set? $$ I(w,d)=\{\ (k_1,...k_d)\mid k_1+\ldots+k_d=w, k_1,...k_d \ge 1\,\}$$ where $ w$: ...
1
vote
1answer
27 views

given definition of a relation $R$, prove that $R$ is an Equivalence Relation

The relation is on set $\mathbb{R}^\mathbb{R}$ and the definition of the relation $R$ is: $f \mathop{R} g \iff \exists _{y\in \mathbb{R}} \forall_{x\in \mathbb{R}}\ ((x>y)\to(f(x)-g(x)\in ...