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

learn more… | top users | synonyms

0
votes
2answers
22 views

Proving that if $E, F$ are equivalence relations on $A$ and $E \subseteq F$, then there is a surjection from $A\setminus E$ to $A\setminus F$

Proving that if $E, F$ are equivalence relations on $A$ and $E \subseteq F$, then there is a surjective function from $A\setminus E$ onto $A\setminus F$. What does $E \subseteq F$ even mean? Does it ...
0
votes
1answer
31 views

Equivalence relation and equivalence class question

Show that the relation $\sim$ defined on the set $X = \mathbb{N} \times \mathbb{N} = \{(a, b) : a \in \mathbb{N}; b \in \mathbb{N}\}$ as $(a,b) \sim (c,d)$ if and only if $a + d = c + b$ is an ...
1
vote
1answer
26 views

Equivalence Class.

Let R be the relation of congruence mod 4 on Z: a R b if a - b = 4k, for some k in Z. What integers are in the equivalence class of 31? How many distinct equivalence classes are there? What are ...
0
votes
1answer
25 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
2answers
40 views

How to find the Equivalence class for a given set?

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and ...
2
votes
2answers
561 views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
-1
votes
1answer
25 views

list all the equivalence relation [duplicate]

list all the equivanlance relations in the set A={1,2,3,4) so there should be 15 right? so what I got so far (1 1) (22) (33) (44) (12) (13) (14) (21) (23) (24) (31) (32) (34) (41) (42) (43) these ...
1
vote
1answer
23 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
1
vote
0answers
47 views

Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim $ is an equivalence relation.
1
vote
1answer
21 views

Show that $R \cap R^*$ and $R \cup R^*$ are equivalence relations.

Let $R$ be a reflexive and transitive relation on a set $S$. Let $R^*$ be the dual relation, $(a,b) \in R^*$ if and only if $(b,a) \in R$. Show that $R \cap R^*$ and $R \cup R^*$ are equivalence ...
0
votes
0answers
16 views

order definition [closed]

i'm in desperate need of your much appreciated expertise with trying to define the following order relation, guess it might be somewhat near a lexicographical order, not a straightforward alphabetical ...
0
votes
1answer
32 views

Equivalence relation: prove that $(X \cap Y) $\ $E $ $\subset (X$ \ $E) \cap (Y$ \ $E)$

I need to prove that $(X \cap Y) $\ $E $ $\subset (X$ \ $E) \cap (Y$ \ $E)$, where $E$ is an equivalence relation over $A$ and $X,Y \subset A$. I don't know where to begin. I know that $X$ \ $ E$ ...
1
vote
1answer
21 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
vote
0answers
36 views

On $N \times N $ define the relation R, setting $(a,b),(c,d) \in R$ if and only if $a+d=b+c$. Show that $R$ is an equivalence relation.

On $N \times N $ define the relation R, setting $(a,b),(c,d) \in R$ if and only if $a+d=b+c$ a. Show that $R$ is an equivalence relation. My attempt: By definition 6.2.3 $R$ is an equivalence ...
0
votes
1answer
25 views

Show that the equivalence classes of $\sim$ are left cosets of $H$ in $G$.

Let $H \leq G$ and define a relation on $G$ by $x \sim y$ if $y^{-1}x \in H$. Show that $\sim$ is an equivalence relation on $G$ and then show that the equivalence classes of $\sim$ are left cosets ...
1
vote
2answers
1k views

why is frobenius norm of a matrix greater than or equal to the 2 norm?

How can you prove that: $$\|A\|_2 \le \|A\|_F$$ I cannot use: $$\|A\|_2^2 = \lambda_{max}(A^TA)$$ It makes sense that the 2-norm would be less than or equal to the frobenius norm but I dont know how ...
1
vote
1answer
37 views

Equivalence relation necklaces problem

Consider the question of making necklaces by arranging n distinguishable beads on a string. Assume that once all $n$ beads are placed on the string its ends are carefully knotted so the knot cannot be ...
1
vote
0answers
17 views

What does a null relation on all real numbers look like?

I'm being asked to test for reflexivity, symmetry, transitivity, and antisymmetry on a null relation for all real numbers, i.e. $X=\mathbb{R}; R = \emptyset $. What would such a resulting set look ...
1
vote
1answer
15 views

Determining equivalence classes on $\Bbb{R}$.

Say we have the following equivalence relation on $\Bbb{R}$: $$a\sim b\iff a-b\in\Bbb{Q}$$ What do the equivalence classes look like? On a preliminary investigation I got the following equivalence ...
0
votes
1answer
27 views

Proof of equivalence relation on set.

I'm new to the whole relations topic and stumbled upon a problem. I know that an equivalence relation is a relation that is symmetric, transitive, reflexive, (and not usually anti-symmetric). But ...
1
vote
2answers
47 views

theorems on equivalence classes

I have a few short proofs that I wish to be checked regarding equivalent classes. Suppose that R is an equivalence relation on set X. If $a, b \in X$, then $a\in [a]$ $[a] = [b] \iff (a, b) \in R$ ...
0
votes
1answer
31 views

Equivalence Relation on R (real numbers)

Let R be the relation on R(real numbers) defined by: For all x, y (that belong) to R(real numbers), x relates y <=> x-y (that belongs) to Z. (a) Is R an equivalence relation? Prove your answer. ...
0
votes
3answers
28 views

Describing Equivalence Classes using set builder notation

How would you describe all the equivalence classes for the relation: $congruence$ $modulo$ $5$ over $Z$, using set builder notation?
1
vote
2answers
30 views

How to show properties of a given relation?

I am given that R is a relation on the given set X, and I have to show if the relation is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) asymmetric, and (v) give an example of an element of ...
0
votes
1answer
23 views

Size of partitions

I am looking at a problem and really confused. Let $X$ be a set and $R$ a subset of $ X×X $. We write $x1 ∼ x2$ if and only if $(x1, x2) ∈ R$ Suppose now that $R$ defines an equivalence relation and ...
1
vote
1answer
55 views

Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$.

Question: Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$. My attempt: By definition 6.23,6.3.1, and ...
1
vote
1answer
21 views

An empty relation on a non-empty set — can it be an equivalence relation?

Given a non-empty set, A, and an empty relation, R, on that set A, can it be the case that the relation R is an equivalence class? Transitivity. (a,b) in R, (b,c) in R ===> (c,a) in R. This is ...
0
votes
0answers
21 views

Relation R in the set N of natural numbers defined as R = {(x, y): y = x + 5 and x < 4}

Determine whether each of the following relations are reflexive, symmetric and transitive:Relation R in the set N of natural numbers defined as R = {(x, y): y = x + 5 and x < 4}
0
votes
1answer
29 views

How to determine a equivanelce relation?

I have a problem to understand the following output: Determine "representative system" or a "system of representatives" :).....for the following equivalence relation ...
0
votes
0answers
52 views

About Kernel and the coimage of a function

Introduction I was serching for a concept of "equivalence relations" induced by an arbitrary function in a "natural" way and I found the concept of Kernel. But I'm not sure that I understand it and ...
0
votes
3answers
58 views

Equivalence relation help

If $|A| = 30$ and the equivalence relation $R$ on $A$ partitions $A$ into (disjoint) equivalence classes $A_1$, $A_2$, and $A_3$, where $|A_1| = |A_2| = |A_3|$, then what is $|R|$?
0
votes
0answers
24 views

A proper term for equivalence relation with a finite quotient set

Is there a proper term for an equivalence relation $\sim$ on some set $M$ such that it partitions $M$ into finitely many equivalence classes? Finite equivalence relation? or co-finite? or equivalence ...
1
vote
2answers
26 views

Sets equivalence relations

I seem to be having a hard time understanding some basic sets concepts. In week 5 of my class, I learnt about the cross product of 2 sets to be the following $A \times B = \{(a,b) : a \in A, b \in B ...
2
votes
1answer
102 views

The closures of a binary relation

I have the following dilemma concerning the equivalence closure of a binary relation. Let $X$ be a nonempty set and $R\subseteq X\times X$ (i.e., a binary relation over $X$). Consider the following ...
1
vote
1answer
67 views

I don't understand equivalence relations

I'm trying to show that the left coset with a subgroup is an equivalence relation. So taking some element $g \in G$ and a subgroup $H$, the left coset is defined as $gH = \{gh : h \in H\}$. That means ...
1
vote
0answers
29 views

Equivalence Set, Subsets

Just a quick question: If a = [A] and a belongs to N (set of all natural numbers) doesn't that mean that A is a subset of N? The reason I'm asking this is because I'm trying to prove the theorem ...
1
vote
1answer
65 views

Determine if R is an equivalence relation

I've got this question: Consider the relationship $R$ between ordered pairs of natural numbers such that $(a, b)$ is related to $(c, d)$ (denoted by $(a, b) R (c, d)$) if and only if $ad = bc$. ...
0
votes
1answer
42 views

Determining Equivalence Relation on $\Bbb{Z}$

Alright, I have a homework problem which I have researched, read up on and I (think) solved. I just need someone to either confirm my answer (and re-affirm my knowledge) or explain why I am wrong. ...
0
votes
0answers
26 views

Prove congruence relation.

Let $\sim$ be a relation where $x \sim y \Leftrightarrow x = y \lor (x \in I \land y \in I)$. Show $\sim$ is a congruence relation on $S$ where $S= \{a,b, c, d, e\}$ and $I = \{a, d\}$. One of the ...
2
votes
1answer
37 views

Prove transitivity of relation.

Let $\sim$ be a relation where $x \sim y \Leftrightarrow x = y \lor (x \in I \land y \in I)$. Show $\sim$ is a congruence relation on $S$ where $S= \{a,b, c, d, e\}$ and $I = \{a, d\}$. One of the ...
0
votes
4answers
43 views

Is $x \sim y \Leftrightarrow x,y$ are even an Equivalence relation?

The following instruction defineds an Equivalence relation on the set of natural numbers. $x \sim y \Leftrightarrow x,y$ are even My idea: Reflexivity: $x \sim x \Leftrightarrow x,x$ is even ...
3
votes
2answers
577 views

Equivalence Relations On A Set of All Functions

The question is, "Which of these relations on the set of all functions from $Z$ to $Z$ are equivalence relations." The first relation to consider is, $\{(f,g)|f(0)=g(0)\vee f(1)=g(1)\}$ For this one, ...
4
votes
2answers
119 views

“Tricky” wording on Congruence Modulo Question?

I'm asked for all possible values, but I can only see one. The question on my practice exam reads: Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. ...
1
vote
1answer
52 views

Number of Equivalence relations of $\{1,2,3\}$

Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists? My idea is to count the disjoint partitions of M: $K_1= ...
2
votes
1answer
37 views

$R$ is transitive if and only if $ R \circ R \subseteq R$

Question: Let $R$ be a relation on a set $S$. Prove the following. $R$ is transitive if and only if $ R \circ R \subseteq R$. Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a ...
0
votes
0answers
24 views

Equivalence Relations and Order? Homework help

Having some trouble on these questions: c) Describe a partial order on {1, 2, 3} that is not a total order d) Describe a binary relation on {1, 2, 3} that is both a partial order and an equivalence ...
1
vote
2answers
291 views

Reflexive but not Transitive relation

What is an example of a Relation R on a set S such that R is reflexive but not transitive Here is what I come up with. Let S be the set of all Integers then R = {x and y are both positive OR x and y ...
-3
votes
2answers
50 views

Finding an equivalence relation on $\{1, 2, 3\}$ with two equivalence classes [closed]

I need some help on a particular question, this one: Describe an equivalence relation on $\{1, 2, 3\}$ that has exactly two equivalence classes. Regards.
1
vote
2answers
34 views

Let $x\in \mathbb{R}$ and $z\in\mathbb{C}$. And define equality ($x=z$) iff $x=(0,x)$. Is this equality well defined?

Let $x\in \mathbb{R}$ and $z\in\mathbb{C}$. And define equality ($x=z$) iff $x=(0,x)$. Is this equality well defined ? Okay. It is easily shown that something goes wrong if you define equality in ...
0
votes
2answers
53 views

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation? I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$. ...