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

learn more… | top users | synonyms

1
vote
3answers
84 views

What’s wrong with this proof that $5$ is prime?

I’m reading How To Prove It and I’m confused as to how the proof of “$x$ is prime” is correct. I've written proof given below and also my conclusion after substituting in values for $x$, $y$ and $z$: ...
2
votes
1answer
39 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
50 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
1answer
56 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
14 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
35 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 ...
2
votes
2answers
57 views

Mathematical Relations in Computing - Unary

I have this question that's bugging my mind: "Discuss by giving suitable examples the role of mathematical relations (Unary, binary and ternary) in computing." I'm sure it's a very simple question, ...
0
votes
1answer
30 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?
-1
votes
3answers
207 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 ...
5
votes
2answers
118 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
206 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
21 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 ...
2
votes
1answer
76 views

If $X,Y$ are equivalence relations, so is $X \times Y$

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
1
vote
0answers
78 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
32 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
41 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 ...
1
vote
1answer
32 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
26 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
38 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
51 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 ...
0
votes
1answer
136 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$ ...
1
vote
0answers
23 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
37 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
42 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
32 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
26 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 ...
0
votes
1answer
84 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 ...
-4
votes
2answers
44 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
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
73 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
124 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
18 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
25 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
34 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 ...
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
0answers
46 views

Help with logical equivalence proof regarding a lemma for equivalence relations.

So the question is this: Suppose A is a set. Let ~ be an equivalence relation on A and let a,b be elements of A. Then Ta = Tb if and only if a ~ b. I need to prove this statement to be true. I know ...
-2
votes
1answer
40 views

What means $A \subsetneq X$ with A ~ X? [closed]

How it is possible to have a subset A, which is $\neq$ to X and at the same time they have an equivalence relation ~? When $A \subset X$ therefore a $\in$ A is also a $\in$ X. With A ~ X ...
1
vote
0answers
56 views

Finding Equivalence Classes for Infinite Sets

Let R be the relation on the set of rational numbers Q defined as follows: for all q, r ∈ Q, qRr iff q − r ∈ Z, where Z is the set of integers. R is an equivalence relation on Q. What is the ...
1
vote
1answer
46 views

What is wrong with the following argument?

Say we have a set $X$ and an equivalence relation $C$ on $X$. Why do we need reflexivity? Let $x,y \in X$ with $xCy $. By symmetry we obtain $yCx$. Applying now transitivity, we have $xCx$. So, we ...
1
vote
1answer
34 views

Is this undergrad equivalence class question solvable?

Let x,y be real numbers. Define the relation S as x S y if |x - y| $\epsilon$ Q where Q is the set of rational numbers. Find all equivalence classes of S. I work in the undergrad tutor center ...
1
vote
1answer
18 views

Prove that a partial equivalence relation in set Dom(A) is an equivalence relation

We know that $r$ is a partial equivalence relation in set $$Dom(r) = \{x|\exists y.(x,y)\in r\}$$ The problem is to prove that this is an equivalence relation. Here is my proof. Did I do it right? ...
0
votes
0answers
36 views

Define another Equivalence Relation from Geometric Figure?

Define relation $W$ on $R^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1−y_1=x_2−y_2$. I have the equivalence classes to be given by $f^{-1}(r)=\{(x,y)\mid x−y=r\}$, where $r∈R$. So how would you define ...