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

learn more… | top users | synonyms

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 $[...
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
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 ...
1
vote
2answers
101 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}$...
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 $...
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
31 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
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 ...
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 ...
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
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
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
48 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
55 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
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
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
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
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 ...
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
29 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
51 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
41 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
36 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 = \{(1,2),(...
0
votes
1answer
70 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 and ...
0
votes
2answers
98 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
35 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
42 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
71 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
40 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 ...