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

learn more… | top users | synonyms

0
votes
1answer
47 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
43 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
21 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
36 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
50 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. ...
0
votes
0answers
28 views

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

Just finished proving this to be injective, and well-defined. How would you prove it to be surjective? I understand surjective means that every element in the codomain is being used, and thus is the ...
2
votes
1answer
26 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
17 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
24 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 | ...
0
votes
1answer
26 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
15 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
13 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
32 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
36 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
46 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
45 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
33 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
12 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
28 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 ...
0
votes
1answer
24 views

How many relations on a set with 6 elements?

I know there is a lot of information on this internet for this, I've been going through it the past 30 minutes. I'm getting confused to if the answer is actually 203 relations, because when I try to ...
0
votes
1answer
31 views

Relations on set based off Cardinality [closed]

Let A be a set with cardinality 6. How many relations on A are there? How many are reflexive? symmetric? Not sure where to go with only this information. Thanks!
0
votes
1answer
19 views

Show that $W$ equivalence relation on $\mathbb{R}^2$

Define relation $W$ on $\mathbb{R}^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1-y_1=x_2-y_2$. Show that $W$ is an equivalence relation on $\mathbb{R}^2$. I believe it is reflexive, not sure about ...
0
votes
1answer
27 views

Determining equivalence classes

I have done (a), pretty straight forward. I understand an equivalence class as all the elements in the domain that map to the same result in the co-domain. For example in (mod 3), [|0|] would be the ...
2
votes
1answer
49 views

In $\mathbb{R}^{n}$ all norms are equivalent

While trying to prove the Theorem mentioned in the Title, I got stuck in the inequality shown below. I think that the proof uses the $\epsilon$ and $\delta$ definition of continuity but I am not ...
0
votes
0answers
40 views

Poker Hand Equivalent Relation

Let $P$ be the set of all possible poker hands. Define a relation $J$ of $P$ by $a$ is $J$-related to $b$ iff $a$ and $b$ have no cards in common. Is $J$ reflexive? Symmetric? Transitive? Having a ...
2
votes
1answer
47 views

Equivalence relation proof example. Starting off help

Now I need to prove its reflexive, symetric, and transitive! Now my biggest confusion is what do I let "a" equal? Obviously it will be an arbitrary element in N(sub 0). Any help would be great. ...
2
votes
2answers
20 views

Symmetric Relations and Cycles

Let's say I have the set: R = {(a,b),(b,c),(c,d),(d,a)} If you visualize this in graph form, it forms a cycle. My question is, is this already a symmetric relation, or do I have to add ...
1
vote
1answer
24 views

Finding the smallest binary relation in a given set including a relation

The following binary relation of the set {a, b, c, d, e} is given: R = { (a,b), (a,c), (b,c) } What I have to do is to find the smallest reflexive / symmetric / transitive / antisymmetric relation ...
0
votes
1answer
24 views

Determining the transversal for an equivalance relation

If you have an equivalence relation $c$ on $\Bbb{Z}$ defined by $$\{x,y\in\Bbb{Z}:p\in\Bbb{Z},x=5p+y\}$$ How would you proceed to determine if the following subset of $\Bbb{Z}$ $$\{-8,1,10,13,19\}$$ ...
1
vote
1answer
37 views

How many equivalence classes does this relation have?

I have this relation: $$A = \mathbb {R} \\ \quad\;\; x\sim y \iff x-y \in \mathbb {Z} $$ I have already proved if it is an equivalence relation. Now I am just searching for the equivalence classes ...
0
votes
1answer
43 views

Find the equivalence class of this relation!

I am having the following relation with the set A and B: $$ (x_1, y_1) \sim_{A\times B} (x_2, y_2) \iff\; x_1 \sim_A x_2\ \;\land\; \; y_1 \sim_B \; y_2 $$ I haved already proved, that it is a ...
0
votes
2answers
34 views

Relation of any set A

I've been learning of relations and I'm having trouble on how to proceed with this problem: $$ \begin{align} \text{On any set } A: a\sim b \enspace\enspace\forall \enspace a,b \in A \end{align} $$ ...
1
vote
1answer
28 views

implications, equivalence, disjunction

I might not be very clear with this but i hope someone gets it Prove that $f : X→Y$ is surjective then and only then when $g_1, g_2$ which $Y → Z$ we have $g_1 \circ f= g_2 \circ f \Rightarrow g_1 = ...
1
vote
1answer
26 views

Proving a simple partially ordered set

I am losing my mind over this: (a) The relation $A=\{(1,1),(2,2),(3,3),(4,4),(3,2),(2,1),(3,1),(4,1)\}$ on the set $S=\{1,2,3,4\}.$ I'm having trouble figuring out if it's reflexive, symmetric, ...
0
votes
1answer
33 views

Equality of equivalence classes for congruence modulo 7

Let R be the relation of congruence modulo 7. Which of the following equivalence classes are equal? [35], [3], [−7], [12], [0], [−2], [17] I got 3) [35] = [-7] = [0], [3] = [17], [12] = [-2] ...
0
votes
2answers
39 views

Finding the equivalence class of this relation

I am having this relation: $$ A=\mathcal P(\mathbb {N} \diagdown 0) , $$ A~B :<=> min A = min B I haved already ...
0
votes
0answers
7 views

Prove that $cl_{eq}(R) = (cl_{sym}(R))^*$

Prove that $cl_{eq}(R) = (cl_{sym}(R))^*$ $cl_{eq}(R) = \bigcap\{S | $ S is an equivalence relation and $R \subseteq S\}$ is the equivalence closure of R. $R^* = \bigcap\{S | $ S is reflexive, ...
0
votes
1answer
26 views

Ordered Pair Proof

Below are two relations on $R.$ For each one, determine (with proof) whether or not it is an equivalence relation. If it is an equivalence relation, describe the partition it induces (i.e., describe ...
2
votes
0answers
40 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is ...
0
votes
1answer
17 views

Doman and range of a simple relation

Relation xRy if x≥y^2 (on real numbers), I'm assuming the domain is (o, infinity) and the range is all real numbers?
0
votes
1answer
45 views

Equivalence relation for set given as matrix

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I ...
1
vote
1answer
36 views

Define a relation ~ on ℝ² by (x,y)~(w,z) if x+y=w+z

So, it comes in two parts: a. Prove that ~ is an equivalence relation on ℝ². b. Give a geometric description of the partition of ℝ² formed by the equivalence classes. For a, I have to prove that ~ ...
0
votes
0answers
29 views

equivalnce relation for sets given as matrix [duplicate]

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I have ...
1
vote
1answer
26 views

Find the set of a given equivalence relation

What is the set $[4]$ but I haven't seen any examples in the text that describe how to approach a question such as this one. ...
1
vote
0answers
113 views

Equivalence relation over groups $a\asymp_sb :\rightarrow\exists n\in\Bbb Z:as^n=b$: terminology and decision problem

Let's define this relation over the elements of an infinite group $(G,\cdot,e)$ $$a\asymp_sb :\rightarrow\exists n\in\Bbb Z(as^n=b)$$ where $a^n$ is defined as follow 1)$a^0=e$ 2)$a^{n+1}=aa^n$ ...
0
votes
1answer
23 views

Non-empty intersection of equivalence classes.

I'm having troubles with the following exercise about equivalence classes on a defined set. Let $R$ be an equivalence relation on a set $A$. Given $a,b \in A$ prove the following statements are ...
1
vote
1answer
77 views

Being contractible in homotopy theory vs. homotopy type theory

I'm trying to clarify the notion of being contractible in homotopy theory vs. homotopy type theory. Is the following right? "In homotopy theory the real interval $[0,1]$, considered as a subset ...
1
vote
0answers
72 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
0
votes
0answers
45 views

Well-defined functions using mod $p$ equivalence classes

Prove that if $m, n$ are elements in the set $\mathbb{Z}$ and $m \equiv n \pmod p$, then $m^2 \equiv n^2 \pmod p$. Also, is the function $f: [\mathbb{Z}]_p \to [\mathbb{Z}]_p$ given by $f([n]_p) = ...
0
votes
1answer
58 views

Equivalence classes of multiples of 3

I'm having a little trouble wrapping my head around the elements of the equivalence classes using the following definition: for m, n in N, define m ~ n if m^2 - n^2 is a multiple of 3. 1) List four ...