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

learn more… | top users | synonyms

2
votes
1answer
46 views

Number of equivalence classes of binary sequences which differ only by finitely many elements.

This question rose up when i was reading a problem the author used to argue against the axiom of choice. Consider the set of all (infinite) sequences of 0's and 1's. Q1) How many such sequences are ...
1
vote
1answer
51 views

Is $R = \{ (x, y) \in \mathbb{R} \times \mathbb{R} \mid x - y \in \mathbb{N}\}$ an equivalence relation?

Note: I am also trying to answer my own question, but I am not sure if it is correct, please correct it, if it's wrong. Thanks :) I have an exercise where I have to say if a relation $R$ is or not an ...
0
votes
2answers
39 views

Pass from partition to the equivalence relations

I have a set $A = \{ 1, 2, 3\}$, which possible partitions are: $P_0 = \{ \{1, 2, 3 \} \}$ $P_1 = \{ \{1, 2 \}, \{3 \} \}$ $P_2 = \{ \{1 \}, \{2, 3 \} \}$ $P_3 = \{ \{1, 3 \}, \{2 \} \}$ $P_4 = ...
0
votes
2answers
122 views

Every equivalence relation on $\mathbb{Z}$ that is compatible with the addition structure is either the identity or the relation $\equiv \pmod{n}$

Let $R$ be an equivalence relation on $\mathbb{Z}$ such that the operation on the quotient set $\mathbb{Z}/R$ given by the rule $[x]_R + [y]_R = [x+y]_R$ is well-defined. Show that $R$ must either be ...
1
vote
3answers
305 views

Prove $(x, y)R(s, t)$ iff $2(x - s) = (y - t)$ defines an equivalence relation

Define the relation $R$ on the set of all ordered pairs of real numbers as follows: $(x, y)R(s, t)$ iff $2(x - s) = (y - t)$. Prove that $R$ is an equivalence relation. Find the ...
4
votes
4answers
696 views

$5 \mid n^2 - m^2$ is an equivalence relation

How can I show this is an equivalence relation: $$ n \operatorname{R} m \Longleftrightarrow n^2 - m^2 \textrm{ is divisible by } 5 $$ I know equivalence relations are symmetric, reflexive and ...
0
votes
3answers
130 views

Prove $a R b$ iff $a \equiv b \pmod 2$ and $a \equiv b \pmod 3$ is an equivalence relation

In the set $\mathbb{Z}$ we describe the relation: $a\mathrel{R}b \Leftrightarrow a\equiv b\pmod2 \text{ and } a\equiv b\pmod3$ Prove that $R$ is an equivalence relation. Describe ...
3
votes
2answers
155 views

Methods for proving an equivalence relation

I'll be taking introductory abstract algebra in the fall, and so to prepare, I'm working through Pinter's text. Chapter 12 includes a number of exercises asking the student to prove that something is ...
1
vote
1answer
176 views

Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

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
3answers
88 views

Proof that $(a, b) \mathrel{R} (c, d)$ iff $ad = bc$ is an equivalence relation

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...
3
votes
2answers
204 views

Proving that $4 \mid m - n$ is an equivalence relation on $\mathbb{Z}$

I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation. $F$ is the relation defined on $\Bbb Z$ as follows: ...
0
votes
1answer
57 views

Basic group algebra exercise

I'm working on this abstract algebra problem that was given as homework to me, I'm in my first year of university and have a semester's background in basic abstract algebra. Here is the problem: Let ...
0
votes
2answers
16 views

Equivalence relations-Discrete Math

Here is an equivalence relation R={ (x,y) | x-y is an integer} My question is: what is the equivalence class of 1 for this equivalence relation? Can say indicate the equivalence class of 1 as ...
1
vote
2answers
39 views

Corresponding partition in equivalence relation

The relation $R$ on the set $A=\{2,4,6,8,10\}$ is defined by $$R=\{(2,2),(2,6),(2,10),(4,4),(4,8),(6,2),(6,6),(6,10),(8,4),(8,8),(10,2),(10,6),(10,10)\}$$ Question 1 Verify if $R$ is an ...
-1
votes
3answers
209 views

When can we modify $a \propto \ b$ adding $\delta $?

This is a general, theoretical question about formalization of concepts, it is difficult for me to explain it adequately, please, if I fail, tell me in a comment what is not clear or feel free to edit ...
0
votes
3answers
14 views

Finding the relation for the partitions { 2x } and { 2x + 1 }

I have to find an equivalence relation in the set of natural numbers which has the two partitions { 2x } and { 2x + 1 } My first thought was ...
0
votes
1answer
146 views

How to prove the Cone is contractible?

Let $\sim$ be an equivalence relation on a topological space $X$ with a subset $A ⊂ X$ such that the equivalence classes are: $A$ itself and Singletons $\{x\}$ such that $x ∉ A$. Then define $X/A$ ...
0
votes
1answer
31 views

How to deal with equivalence relations and equivalence classes

I have the following relation $m^3=n^3$ on $\mathbb{Z}$. I know how to show that it is an equivalence relation but I am facing a problem in finding the equivalence classes can u help me please?
5
votes
2answers
122 views

Categorical description of equivalence relation generated by a relation?

The notion of an equivalence relation generated by a relation is widespread and useful. How can one categorically describe it?
3
votes
2answers
229 views

An example in the fundamental theorem of equivalence relations?

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there ...
0
votes
1answer
22 views

If $\alpha\in X/R$ is an equivalence class, then $F:X/R\to Y$ defined by $F(\alpha)=f(a)$, is well-defined, 1-1 and onto.

Let $f:X\to Y$ be a surjection. Let $R$ be the subset of $X\times X$ consisting of those pairs $(x,x')$ such that $f(x)=f(x')$. Then $R$ is an equivalence relation. Let $\pi:X\to X/R$ be the ...
1
vote
0answers
80 views

Prove $X\times Y$ is an equivalence relation [duplicate]

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in ...
1
vote
1answer
33 views

Proving projection map is onto

Let $X$ be a nonempty set and let $R$ be an equivalence relation on $X.$ Given $X/R={[a]:a \in X}$. Prove that there is a map called the projection where $p_x:X\to X/R$ given by $p_x(t)=[t].$ Then ...
1
vote
2answers
43 views

Orbits in G = $Z_6$ by listing 2 element subsets in G.

1) Let $G = \mathbb{Z}_6$. List all 2-element subsets of $G$, and show that under the regular action of G (by left addition) there are 3 orbits, 2 of length 6, one of length 3. Deduce that the ...
4
votes
3answers
100 views

Is $\mathbb{Z}_p$ a Finite Field?

Denote the integers modulo $p$, $\mathbb{Z}$ mod $P$, as $\mathbb{Z}_P$. Denote the set of integers equivalent to $n$ mod $P$ - the equivalence class of $n$ as $\overline{n}$. We know that for any ...
1
vote
1answer
34 views

How to show that the following relation is not an equivalence relation?

We have the relation $\sim$ in $\mathbb{R}^n$: $x\sim y \leftrightarrow d(x,y)\in \mathbb{Q}$, where $d(x,y)=\sqrt{\sum^n_{i=1}(x_i-y_i)^2}$. How do you prove that this isn't an equivalence relation ...
0
votes
1answer
27 views

Having trouble proving transitivity

We have a universal set of lowercase alphabet letters, $U = \{a, b, ... , z\}$ . For sets $A,B \subseteq U$ we can define a relation, $A \sim B$ as long as the number of elements that are in either ...
1
vote
2answers
40 views

How to prove $S=\{(x,y) \in \mathbb{R}\times \mathbb{R}|x - y \in \mathbb{Q} \}$ is an equivalence relation?

I am really stuck with this problem, and I cannot come out with a solution. I know that to prove a relation is an equivalence relation we have to prove that it's reflexive, symmetric and transitive, ...
0
votes
2answers
53 views

How many elements are there in the set R?

+Let A be a finite set with $n \geq 4$ elements and let R be an equivalence relation on A . Suppose that there are exactly $n-2$ equivalence classes and that no equivalence class can contain exactly ...
1
vote
0answers
25 views

Describe an equivalence class

On the set N x N, define the following relation: (a, b) ~ (c, d) if and only if a + d = b + c (a). Show that this is an equivalence relation I have shown that this is an equivalence relation by ...
1
vote
1answer
11 views

Equivalence Relation Properties

I have to define whether the following relation is symmetric, reflexive, and transitive. Define a relation R on Z as follows: (x, y) ∈ R if and only if x = |y|: This is my answer so far: Is ...
0
votes
3answers
39 views

Equivalence relation example. How is this even reflexive?

Is the below question a mistake? How is this an equivalence relation? For example, how would it even be reflexive? E.g if you pick any A $\subseteq$ $U$, say A = {a, b}, then A ~ A is not true, ...
0
votes
1answer
43 views

Question about notation of sequences and equivalence classes.

In these notes (see pg3 second-to-last paragraph), what does $d(x_k,x^\ast_{N_k})$ mean? The term $x_k$ lies in $X$, but $x^\ast_{N_k}$ is a class of Cauchy sequences in $X$. Should I take ...
1
vote
2answers
24 views

Describes Equivalence Classes

Let $R$ be the relation on the natural numbers defined by $(a,b)\in R$ if and only if $2\mid(a+b)$ I already proved this was an equivalence relation, but how do I determine the number of equivalence ...
1
vote
1answer
30 views

English wording around equivalence relation

What is the English word to mean an element of an equivalence class of an equivalence relation? In French we say "représentant".
0
votes
0answers
22 views

Showing relation is transitive (a,b) $\in$ R iff 2|(a+b)

Let R be the relation on natural numbers defined by (a,b) $\in$ R iff 2|(a+b) show it is transitive.
1
vote
1answer
42 views

Proving $S$ is the unique smallest relation on $A$ containing $R$

Suppose $R$ is a reflexive and symmetric relation on a finite set $A$. Define a relation $S$ on $A$ by declaring $xSy$ if and only if for some $n \in \mathbb{N}$ there are elements $x_1,x_2,\ldots,x_n ...
0
votes
1answer
35 views

Construct equivalence classes for a relation R

Define relation R as follows: xRy if x and y are bit strings with |x| >= 2 and |y| >= 2 such that x and y agree in their first two bits. Show that R is an equivalence relation. Construct the ...
1
vote
1answer
30 views

Consider P a partition of set A. Given relation R on A and xRy if and only if x, y $\in$ X for some X $\in$ P. Show R is equivalence relation on A

Consider $P$, a partition of a set $A$. Define a relation $R$ on $A$ such that $x\mathrel{R}y$ if and only if $x, y \in X$ for some $X \in P$. Show that $R$ is an equivalence relation on $A$. Next ...
-4
votes
2answers
45 views

How to find $R^2$ given $S$ and $R$. [closed]

If $S = \{1,2,3\}$ has a relation $R = \{(1,2), (1,3), (2,3)\}$, find the relation $R^2$? I am not able to find $R^2$, can anyone please help me with this?
0
votes
1answer
106 views

Prove that if R is a symmetric relation, so is R^2.

Prove that if R is a symmetric relation, so is R^2. My attempt : The Relation R has (a,b) provided (b,a) is a member of R. So if I go on to find R^2 it will always have element (a,a) that makes R^2 ...
2
votes
4answers
488 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 ...
0
votes
1answer
26 views

Let E1, E2 Equivalence relations on A, Prove or disprove :

Let E1, E2 Equivalence relations on A, Prove or disprove : 1) E1 ∩ E2 an equivalence relation on A 2) E1 ∪ E2 an equivalence relation on A
1
vote
2answers
100 views

Proofs with Relations and functions

I need help with setting up a homework problem. I am having trouble finding where to start. Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation ...
2
votes
1answer
165 views

how to find relation R^2

Suppose S is a set of airports, and R is the following relation on S: aRb if and only if there is a direct flight from a to b. Explain your answers to the following questions and use common sense. a. ...
2
votes
1answer
28 views

Define $f : Z/3Z → Z/3Z$ by $f ([a]) = [2a + 1]$

Just finished proving this is well-defined, how do I prove it's surjective and injective? I know that injective means that if $x1 \neq x2$, then $f(x_1) \neq f(x2)$, i.e. each value in the domain is ...
0
votes
1answer
19 views

Determine whether the relation is an equivalence relation:

xRy in Z iff x,y > 0 Apparently this is the answer: This is not an equivalence relation since 0 ∈ Z and 0 is not related to 0. So I know that x relates to y iff x and y are in the same cell of the ...
0
votes
1answer
27 views

Define f: Z/4Z → Z/4Z by f([a]) = [3a+1]

I need to show this function is well defined For well defined, I was thinking something along the lines of: Assume [a1] = [a2] in Z/4Z. Then, a1 is congruent to a2(mod4). So, 4 | a1 - a2. Thus, 4 | ...
-2
votes
1answer
35 views

Z / 6Z being a set of well dedfined equivalence classes, and a congruent to b(mod 6)

why is this = [0],[1],[2],[3],[4],[5],[6] and how would I define f Z/6Z - Z/6Z by f([a]) = ([2a]). I have the proof but I don't understand it. Proof: Assume [a1] = [a2] in Z/6Z. then a1 congruent to ...
0
votes
1answer
17 views

Define f: Z /6Z by g(5[a]) = [5a]

So, in our notes, we had an example where we defined f: Z / 6 Z by g([a]) = [5a] (where z is set of all integers) Already, I don't follow what the g([a]) = [5a] means, I'm assuming they are ...