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

learn more… | top users | synonyms

1
vote
2answers
84 views

How many distinct equivalence classes does this equivalence on rationals have?

Let $$A = \{ r\in \mathbb Q \mid \exists p\in \mathbb Z,\text{ and $q\in \mathbb Z$, with $p$ even and $q$ odd, and $r = p/q$} \}$$ For example, $A$ contains such $2/9, 16/(-34)$, and $4$. $A$ does ...
0
votes
1answer
10 views

Partition inducing equivalence

In NPTEL Lecture 23 on Discrete Mathematics, the professor proves that every partition induces equivalence. But is it necessary that the elements in the partition blocks are necessarily reflexive ...
0
votes
0answers
29 views

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

Let $\mathcal R$ be the relation on natural numbers defined by $(a,b) \in \mathcal R \Leftrightarrow 2|(a+b)$ Show it is transitive.
0
votes
0answers
6 views

The normalizer of measurable full groups

I'm following Kechris' book Global aspects of ergodic group actions. Let $(X,\mu)$ be a standard measure space (i.e., isomorphic to $[0,1]$ with the Lebesgue measure on Borel sets) and $E$ an ...
0
votes
1answer
43 views

Why does $xRy$, where $R$ is equivalence relation, imply that $[[x]]_R=[[y]]_R$?

We have two objects, $x$ and $y$. Let there be an equivalence relation $R$ between them, such that $xRy$. How does this imply that their equivalence classes, $[[x]]_R$ and $[[y]]_R$, are equal? A ...
0
votes
2answers
37 views

Equal equivalence classes proof

Let there be two sets $A$ and $B$ and let their Cartesian product be $A{\times}B$. Let there be an equivalence relation $R:R\,{\subset}\,A{\times}B$. Let's define an equivalence class now: ...
0
votes
0answers
25 views

How do the equal equivalence classes under the relation defined below imply the following?

First, we have a commutative semigroup $(S,*)$. Now let $(S_1,*_{↾_1})$ and $(S_2,*_{↾_2})$ be its two subsemigroups, with $*_{↾_1}$ and $*_{↾_2}$ being the restrictions of $*$ to $S_1$ and $S_2$. ...
0
votes
2answers
27 views

Equivalence relations and binary operations

Let S be the set of all sequences of real numbers. Define a relation $\sim$ on S by $\{x_n\} \sim \{y_n\}$ if $x_n - y_n \rightarrow 0$. (i) Prove that $\sim$ is an equivalence relation. (ii) Let ...
0
votes
1answer
39 views

How to describe conjugacy classes for elements of $\mathbb{Z}_{2} \times \mathbb{Z}_{2}$? [closed]

I am totally new to mathematical analysis and just learn what group is. In a problem it says to describe conjugacy class for $\mathbb{Z}_{2} \times \mathbb{Z}_{2}$. But what is the conjugate class ...
0
votes
1answer
16 views

Composing equivalence relations

I´ve come across a problem regarding relation composition. The task is to show, whether a composition of two equivalence relations on a set X is again an equivalence on the set X. I´ve tried ...
4
votes
1answer
43 views

Lemmata about equivalence relations

We've defined relations and equivalence relations a few days ago at university. I tried to look at them a bit more abstract and came up with two lemmata. I am going to write them down with my proofs ...
1
vote
2answers
28 views

requirement on proposition

I want to draw a conclusion from an equivalent description of a relation. Let $R$ be a relation on a set $M$ with $R \subseteq M \times M$. First I have 2 examples of what I mean: $x \sim_R y ...
1
vote
3answers
114 views

What exactly does it mean to take something modulo an equivalence relation?

For instance, the complex projective space is defined as $\mathbb{C}{\mathbb{P}^n} = \left( {{\mathbb{C}^{n + 1}}\backslash \left\{ 0 \right\}} \right)/ \sim $ Where the equivalence relation is ...
2
votes
1answer
50 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
0
votes
2answers
17 views

Equivalence relations and classes

Let $S = [10]$ (the set containing the integers 1,...,10). Define an equivalence relation R on S by $xRy$ $iff$ $x^2 \equiv y^2$ (mod 5) is an equivalence relation and determine the equivalence ...
0
votes
0answers
45 views

Example of a relation on a finite set

In one of the exercises, I proved that $R^n+1\subseteq R^n$ for all $n \ge1$ But now I need to give an example of relation on finite set such that $R^3 \subsetneq R^2 $ Here $R^3$ =$R \circ R \circ ...
-2
votes
1answer
56 views

Define a relation $∼$ on $\mathbb Z \times \mathbb Z \setminus \{0 \}$ by the rule $(a,b)∼(c,d)$ if $ad=bc$. Is $∼$ an equivalence relation? [closed]

Define a relation $∼$ on $\mathbb Z \times \mathbb Z \setminus \{0 \}$ by the rule $(a,b)∼(c,d)$ if $ad=bc$. Is $∼$ an equivalence relation? I know that to prove an equivalence relation you need to ...
0
votes
2answers
35 views

Clarification needed, show it is not an equivalence relation: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$.

A question from HW: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$. Show it is not an equivalence relation. My problem - For instance, how can I even check for ...
0
votes
2answers
29 views

Describing the Partition for a given equivalence relation.

In $\mathbb{R}$ let $a\sim b$ iff $a-b$ exists $\in$ $\mathbb{Q}$. I have already proven that $\sim$ is an equivalence relation. However, the second part of the question asks to describe the ...
0
votes
0answers
33 views

finest equivalence relation classes

"$\sim$" is the finest equivalence relation on $M = \mathbb{Z}^2$ with $(a,b) \sim (a,-b)$, $(a,b) \sim (b,a)$ and $(a,b) \sim (a,a+b)$ for all $a,b \in \mathbb{Z}$. My task is to find every ...
3
votes
2answers
69 views

let $a\sim b$ iff for some integer $k$, $a^k = b^k$

Let $G$ be a group, Let $a\sim b$ iff for some integer $m$, $a^m = b^m$. I am having a problem trying to figure out how to prove that the transitive property. I know that you start off by Assuming ...
1
vote
1answer
57 views

Define a relation and find its equivalence classes.

Define a relation $\sim$ on $\Bbb{N}$ as follows. For any $a,b∈\Bbb N$, $a\sim b$ if and only if $ab$ is a perfect square. Show that $\sim$ is an equivalence relation. What are the equivalence ...
0
votes
2answers
33 views

Define a equivalence relation For any (x,y)∈N… [duplicate]

For any $(x,y)∈ \Bbb N$ , x ~ y is an equivalence relation if and only if $xy$ is a perfect square. What are the equivalence classes? Here is my progress so far. By the rules of multiplication we ...
0
votes
1answer
65 views

Proving equivalence relations and showing equivalence classes

For any $(x,y) \in \mathbb{N}$, $xRy $ iff $xy$ is a perfect square. Show that $R$ is an equivalence relation and what are the equivalence classes? Here is my progress so far. By the rules of ...
0
votes
1answer
20 views

Proving an equivalence relation $(A_1,B_1)$ ~ $(A_2,B_2)$

Let $(A_1,B_1),(A_2,B_2) \in \Bbb R^{n\times n} \times \Bbb R^{n \times m}$. We say that $(A_1,B_1)$ and $(A_2,B_2)$ are similar written $(A_1,B_1)$ ~ $(A_2,B_2)$, if there exists $S \in$ GL (n, $\Bbb ...
1
vote
1answer
31 views

Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime

I am faced with the following problem: Let $p$ be a prime number and $\gcd(p,n)=1$. Define an equivalence relation on $\mathbb{Z}_{p}$ as follows: $x \sim y$ iff $n^{r}x = n^{t}y$ for some $r,t ...
0
votes
2answers
29 views

Reflexivity of Relations

Explain why the relation $$T=\{(a,b)\in\mathbb{R}\times\mathbb{R}:a≤b\}$$ is reflexive, but the relation $$ Q=\{(a,b)\in \mathbb{R}\times\mathbb{R}:a<b\}$$ is not reflexive. Is $T$ reflexive ...
1
vote
0answers
30 views

equivalence relations example

determine if the relation on $\mathbb{Z} \times \mathbb{Z}$ is an equivalence relation. $$R=\{((a,b),(c,d)) \in A \times A: a+3b=c+3d\}$$ What I have thus far I need to show that R is reflexive, ...
2
votes
3answers
45 views

Finding the equivalence class of a relation |a| = |b|

For the following relation $R$ on the set $X$ determine whether it is $(i)$ reflexive, $(ii)$ symmetric and $(iii)$ transitive. Give proofs or counter examples. In the case where $R$ is an equivalence ...
0
votes
0answers
24 views

Proving transitivity for a relation on Q

Say you have the set $A = \{r\in\mathbb{Q}:\exists\,q,p\in\mathbb{Z},$ with $p$ odd and $q$ even, and $r=\frac{p}{q}\}$, and a relation $R$ on $\mathbb{Q}$ where for $x,y\in A$, then $xRy$ if $x-y\in ...
1
vote
0answers
24 views

Symmetry of a relation

There is a professor in our University who each year posts some homework for his students (1st years at computer studies) and I am trying to solve it for fun. However, now I got stuck on something ...
1
vote
1answer
28 views

Let $v,w$ be vectors of some vectorial space $V$. If $v=w$, are they said to be equivalent?

Of course two geometrical vectors are called equivalent if they have the same magnitude, direction and orientation. But what about a generic vectorial space? Does the relation $v=w$ keep this name? I ...
1
vote
1answer
18 views

Show $\phi (a)=\phi (x)$ iff $a^{-1}x \in N$ iff $aN=xN$

disclaimer: This is not a homework question, it's purely a question to reinforce my understanding: Let $\phi :G \rightarrow H$ be a homomorphism of groups with kernel N. $ \forall a,x \in G$ show ...
0
votes
2answers
42 views

How to show if relation on $\mathbb N\times\mathbb N$ defined $(a,b) \sim (c,d)$ by $ad(b+c)=bc(a+d)$ is transitive?

I can show it is reflexive and symmetric but I don't know how to show transitivity using only the properties of natural numbers (no division).
0
votes
1answer
33 views

Equivalence classes and equivalent relationship

We define a relation S on the set of all integers by: $nSk$ iff $n^2$ $=$ $k^2$ Decide if S is an equivalence relation. If so, what is the equivalence class of $9$? It can be proven that S is an ...
3
votes
3answers
68 views

if $x\mathcal R y$ defined by $|x|+|y| =|x+y|$. Is it an equivalence relation?

Reflexive and symmetric can be proved as $|x|+|x|=|x+x|$ hence reflexive and $|y|+|x|=|y+x|$ hence symmetric but how transitive?
3
votes
2answers
364 views

Is '=' antisymmetric?

I know that an antisymmetric relation must meet the following condition: If x <=y and y<=x then x=y. That being said, can one consider ...
2
votes
2answers
598 views

How to prove that equality is an equivalence relation?

Probably, it's a elementary question, but I would like some explanation. Everyone knows that equality relation is (i) reflexive, (ii) symmetric and (iii) transitive, that is, satisfies (i) $x=x$; ...
-1
votes
1answer
38 views

Transitivity, symmetry on empty set X, non-empty relation R [closed]

If I had an empty set X, with a relation R containing elements 1 and 2 In my directed graph if I had (1,2) and (2,1), would I still have transitivity and symmetry even though this is an invalid ...
4
votes
4answers
128 views

About proving that $Aut(\mathbb{Z}_n)\simeq \mathbb{Z}_n^\times$.

I need to prove that $$ Aut(\mathbb{Z}_n) \simeq \mathbb{Z}_n^\times. $$ My definition of $\mathbb{Z}_n$ is that $$ \mathbb{Z}_n =\{\bar{m}: m\in \mathbb{Z}\} $$ where $\bar{m}$ is the equivalence ...
1
vote
1answer
110 views

Prove that $df_{x}: TM_{x} \rightarrow TN_{f(x)}$ is a well-defined map

I was wondering if someone could help me with the following problem, any help would be greatly appreciated. Let $f:M \rightarrow N$ be a $C^{\infty}$ map between smooth manifolds. Given $x \in M$, ...
2
votes
1answer
2k views

How to determine the equivalence classes of a relation?

I don't fully understand how to find the equivalence classes of a relation. Over $\mathcal P(E)$, where $E = \{1,2,3,4,5,6\}$, $ARB \iff |A\cap\{1,2\}| = |B\cap\{1,2\}|$ From what I've seen, ...
0
votes
1answer
23 views

equivalence relation. Prove transition property and find equivalence class.

I have a question from my book. The question is $ \mathbb{R^2} - (0,0)$, where $(a,b) \sim(c,d)$ if $ad-bc=0$. The question is to prove that it is equivalence relation. I get to the transition ...
-1
votes
1answer
60 views

How to find reflexive, symmetric and transitive closure of a relation R?

I have to solve this question. Any hints or what closure actually means? Let $R = \{(1,2),\ (2,3),\ (3,1)\}$ and $A = \{1,2,3\}$. Find the reflexive, symmetric, and transitive closure of $R$ using ...
1
vote
1answer
29 views

Verifying partial order relation

I have the following question where i have to verify if the relation is partial order: $A=\{1,2,3,\ldots,100\}$, relation $x\mathrel{R}y \leftrightarrow \frac{y}x=2^k$, where $k\ge 0$ is an ...
0
votes
1answer
33 views

Equivalence class clarification

I'm slightly confused on the definition of an equivalence class. Suppose $R$ is a relation on $Z \times (Z - {0})$ by $(a,b)R(c,d)$ if and only if $ad = bc$. What would a single equivalence class from ...
0
votes
1answer
49 views

Is this a valid Answer?

First off, I am quite open to changing the name of the question if anyone has suggestions, so that it might be more accessible and helpful to future mathonaughts. I need to describe partitions for ...
1
vote
2answers
35 views

Does this proof that $\chi(\mathbb{Q}^2) = 2$ rely on choice?

I'm teaching a course on discrete math and came across a paper related to the Hadwiger-Nelson problem. The question asks how many colors are needed to color every point in $\mathbb{Q}^2$ such that no ...
0
votes
2answers
20 views

equivalence class of function, picking proper x

Defining R to be the relationship on real numbers given by xRy iff x-y is rational, I've been asked to find the equivalence class of $\sqrt2$. My instincts say that the equivalence class of $\sqrt2$ ...
0
votes
1answer
36 views

Why do non regular languages have infinitely many equivalence classes?

Let's say I have a language L = {a^nb^m|n != m}, The Myhill-Nerode relation $\equiv_L$ of $L$ is a relation on $\Sigma^*$. It is for words $x,y \in \Sigma^*$ defined by $$ x \equiv_L y \iff ...