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

learn more… | top users | synonyms

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 ...
-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 ...
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
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
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 ...
1
vote
0answers
31 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
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 ...
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
1answer
77 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
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
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
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 ...
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
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 ...
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).
3
votes
3answers
69 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 ...
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
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 ...
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$, ...
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
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 ...
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
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 ...
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 ...
0
votes
1answer
13 views

binary relations defining an equivalence relation on S

Is this a true statement for binary relations defines an equivalence relation on S: S is the set of all n-digit binary sequences. We say that two binary sequences are in a relation if and only if ...
0
votes
1answer
23 views

Does the following equation show transitive nature, symmetric and reflexive?

Does the following equation show transitive nature, symmetric and reflexive? $$d(a,b) = \lvert a-b \rvert \le 2 $$ I am really having trouble with this problem any help would be appreciated. I ...
0
votes
1answer
21 views

Proof: a relation is a partially ordering

I tried to solve this problem, but I really don't know how to break the problem down into different parts so that it becomes easier. The problem is: Suppose $A$ is a set and $p$ a transitive and ...
0
votes
1answer
31 views

Show all of the implications and equivalences between the following relationships.

A: $x=y$, B: $x^2 = y^2$, C: $xy=x^2$, D: $xy=y^2$ The answers are: $$A \implies B$$ $$A \implies C$$ $$A \implies D$$ I don't understand how $A \iff C$ among others is not an answer, there is no ...
2
votes
1answer
42 views

Is this a grammatically correct way to show equivalence?

$$ \frac{1}{k} - \frac{1}{k+1} > \frac{1}{(k+1)^2} \iff \frac{1}{k(k+1)} > \frac{1}{(k+1)(k+1)} $$ Im just trying to figure out if I've used the '$\iff$' correctly. Thanks in advance.
1
vote
1answer
23 views

Relations and equivalence relations

I'm self-studying discrete mathematics and right now I'm reading a chapter about "Relations". I've tried to solve some of the exercises that are included at the end of the chapter. But they are too ...
0
votes
1answer
45 views

What is wrong with the following “proof” that $\sim$ is reflexive?

Let ~ be a symmetric and transitive relation on a set A. What is wrong with the folloing "proof" that $\sim$ is reflexive? Proof: $a\sim b$ implies $b\sim a$ by symmetry; then $a\sim b$ and ...
1
vote
2answers
44 views

Defining an equivalence relation

For the set $ \Bbb R$, define two elements in $ \Bbb R$ to be equivalent if their difference belongs to $ \Bbb Q$. I can prove that this defines an equivalence relation. (see Verify an equivalence ...
2
votes
1answer
36 views

Measure theory Vitali nonmeasurable set.

On $[0,1]$ I've got the relation $\sim$ defined as: $x \sim y \iff x-y \in \mathbb Q$ this is a relation of equivalence and so: we can make a factor class ...
3
votes
3answers
47 views

Prob. 5 (c), Sec. 3 in Munkres' TOPOLOGY, 2nd ed: How to find this equivalence relation?

Let $S$ be the following subset of the plane: $$S \colon= \{ \ x \times y \ | \ y = x+1, \ 0 < x < 2 \ \}.$$ Let $T$ be an equivalence relation on the real line such that $T$ is the ...
-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 ...
2
votes
0answers
49 views

Partitioning functions into equivalence classes based on running time?

I'm studying for my midterm and doing some practice problems, and I would be grateful if someone showed how to solve this. From my understanding you have to partition the functions into equivalence ...
-2
votes
2answers
45 views

Let R be the following relation on the set of pairs of integers:

Let $R = \left\{\bigl((a, b), (c, d)\bigr) \in \mathbb{Z}^2 \times \mathbb{Z}^2; a + d = b + c\right\}$. Prove that $R$ is an equivalence relation. Find the equivalence class of the pair $(0, 0)$.
1
vote
1answer
37 views

Hasse diagram with “≥” relation

We have a set S= {1,2,3,4} with following relation: aRb <-> a ≤ b ≤ a^2 With focus on the relation we get following partially ordered set: {1,2},{1,3},{1,4}, {2,3},{2,4}, {3,4} which gives the ...
2
votes
2answers
30 views

Prove equivalence of a complex function

How to prove that, $(z+1)^{100} = (z-1)^{100}$ is equivalent to $(z+1) = (z-1) e^\cfrac{2\times \pi \times k \times i}{100}$ Thank you. Edit: Okay sure, and I have attempted to do it. First ...
-1
votes
2answers
70 views

Is the set $\Bbb Q$ a quotient set of $\Bbb Q^*$?

Let $\Bbb Q^*=\{\frac a b: a\in \Bbb Z, b\in \Bbb N\}$. From this definition we can see $c=\frac 2 3$ and $d=\frac 4 6$ are elements of $\Bbb Q^*$. Claim: $$\frac 2 3\neq \frac 4 6$$ Proof: ...