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

learn more… | top users | synonyms

0
votes
1answer
28 views

$a^2 \equiv b^2$ mod 4 equivalence classes.

so we have the relation $a^2 \equiv b^2$ mod 4. And to find equivalence classes we say b or a = 0 so $a^2=4k$ so $a=+-2\sqrt{k} $ so all even numbers. But when we get to a=1 then $a^2=4k+1$ after ...
4
votes
1answer
38 views

Are there any distinct $a, b$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime?

Are there any distinct $a, b \in \mathbb{N}$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime for all $x \in \mathbb{N_0}$? I can show there are no coprime $a,b$ using Dirichlet's theorem: ...
1
vote
2answers
26 views

Describe equivalence classes from equivalence relations

I don't really understand the way to do these. Describe equivalence classes for the following equivalence relations on the given set $S$: (i) $S$ is the set of all points in the plane, and $a\sim b$ ...
1
vote
1answer
62 views

Is “to be conjugate” is an equivalence relation?

Let denote $P_x$ the minimal polynomial of $x$ over a field $K$. We say that $x$ and $y$ are conjugate if $P_x(y)=0$. Is "to be conjugate" is an equivalence relation ? The question behind this ...
0
votes
1answer
34 views

Proving bijection is an equivalence relation

If $ M = \{A_n\}_{n=1}^\infty$ is a collection of sets. Consider a relation R on M where $ A_mRA_n$ if there exists a bijection from $A_m$ to $A_n$. Here is my work so far. For symmetry if we assume ...
0
votes
1answer
9 views

Conjecture about a finest equivalence relation

I've thought about finest equivalence relations and came up with a conjecture but I am neither able to prove nor able to disprove it. A hint would be great. Be $M$ a set, be $f$ a bijective function ...
2
votes
2answers
29 views

Prove that $xRy \iff 5 |(x+4y)$ is an equivalence relation

Prove that $xRy \iff 5 |(x+4y)$ is an equivalence relation. Reflexive: $xRx$, since $x+4x = 5x$, which is a multiple of $5$. Transitive: Suppose $xRy$ and $yRz$. Then $$x+4y=5k_1,\quad y+4z = ...
1
vote
0answers
24 views

Problem with understanding natural number difference

Proofwiki says the following about difference in natural numbers: In the context of the natural numbers, the difference is defined as: $n−m=p⟺m+p=n$ from which it can be seen that the ...
0
votes
1answer
22 views

fine the inverse of $[2]$ and $[23]$ in$ \mathbb{Z}_{41}$

I know the inverse of [23] is [23] * [25] = 575 575 congruent to 1 mod 41 [25] is the inverse I have started the other one but I am doing something wrong I got [2] * [41] = [82] = [0] 82 ...
-2
votes
2answers
66 views

Prove or disprove this is an equivalence relation

Let $R$ be a relation defined on the set $\Bbb N$ by $a R b$ if either $a|2b$ or $b|2a$. Prove or disprove: $R$ is an equivalence relation. I able to prove reflexive and symmetric. I understand that ...
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
1answer
45 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
43 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
26 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
28 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 ...
-1
votes
1answer
36 views

Connections between Posets and WQO's

Here is the question that I posted on the Mathematics Chat Room that I was unable to find an answer to: Question: Under what conditions/properties is a poset ever a wqo (well-quasi-order)? Can we ...
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
18 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
44 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
117 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
70 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
18 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
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
33 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
38 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 ...
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 ...
1
vote
1answer
64 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
1answer
22 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 ...
1
vote
0answers
33 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, ...
0
votes
2answers
31 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 ...
2
votes
3answers
49 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
1answer
92 views

Show that a relation is equivalent if it is both reflexive and cyclic.

A relation $R$ on set $X$ is called cyclic if whenever both $xRy$ and $yRz$ then $zRx$ where $x,y,z\in X$. Show that a relation on $X$ is an equivalence relation if and only if it is both reflexive ...
0
votes
1answer
67 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
0answers
27 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
26 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
2answers
85 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 ...
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
19 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
1answer
35 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 ...
0
votes
2answers
44 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).
3
votes
3answers
72 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
365 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 ...
0
votes
0answers
46 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 ...
-1
votes
1answer
47 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 ...
1
vote
1answer
117 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$, ...
0
votes
1answer
24 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
vote
1answer
32 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 ...