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

learn more… | top users | synonyms

2
votes
1answer
19 views

Checking the equivalence relations of sets

$S=\{0,1,2,3\}, R:SxS, (m,n)\in R \text{ if } m+n=4$. From the condition of $R$, I found that $R=\{(2,2),(1,3),(3,1)\}$. Now I have to see if $R$ is reflexive, symmetric, antisymmetric, and ...
0
votes
1answer
58 views

Let $H=\{2^m: m ∈ Z\}$ Where $m$ is any integer, and $ a\sim b\Leftrightarrow a/b $ is an element of $H$.

Show that is an equivalence relation and describe the elements in the equivalence class $\operatorname{cl}(3)$. We're studying sets and equivalence in my mathematical proofs class. As this is a ...
1
vote
1answer
30 views

Counting Ordered Pairs

Let $A$ be a finite set with $n \geq 4$ elements and let $\rho$ be an equivalence relation on $A$. Suppose that there are exactly $4$ equivalence classes, $C_1$, $C_2$, $C_3$, $C_4$. Moreover we know ...
1
vote
1answer
35 views

Equivalence Relation determined by $f(x)=x^2$

I have an exercise from my professor; For the function $f(x)=x^2$, for all $x\in \mathbb{R}$, describe the equivalence relation determined by $f$. So we are working in the set $\mathbb{R}$, so ...
0
votes
1answer
43 views

Let H be a (non-empty) subset of integers. Suppose a-b <=> a~b ∈ H is an equivalence relation.

Show that $0 \in H$. Show that if $a \in H$ then $-a \in H$, and lastly, if $a$ and $b \in H$ then $a + b ∈ H$. Last bonus question on our last unit test on sets, equivalence relations and proofs. I ...
3
votes
2answers
23 views

Equivalence relation confusion

Why is $\{(x,y)\mid x-y\text{ is a rational number}\}$ an equivalence relation and and why are $\{(x,y)\mid x-y\text{ is a irrational number}\}$ and $\{(x,y)\mid x+y\text{ is an integer}\}$ not?
0
votes
1answer
69 views

If $X = \{1, 2, 3, 4\}$ show there are just two equivalence relations on $X$ with $1\sim 2$ and $2 \sim3$

If $X = \{1, 2, 3, 4\}$ and $\sim$ is an equivalence relation on $X$, then if $1 \sim 2$ and $2 \sim 3$ show that there are just two possibilities for the relation $\sim$ and describe both ...
1
vote
1answer
15 views

An equivalence relation on filters

Let $F$ be a filter. We say $ X \sim_{f} Y $ iff $X \leftrightarrow Y$ $\in$ $F$. I am able to prove reflexivity and associativity of the relation but not the transitivity. Need help with that. Use ...
0
votes
1answer
30 views

Equivalence relation example

On the Wikipedia page about Equivalence Relations, there is a simple example: Let the set $\{a,b,c\}$ have the equivalence relation $\{(a,a),(b,b),(c,c),(b,c),(c,b)\}$. The following sets are ...
0
votes
3answers
60 views

Pigeonhole Principle and Equivalence Classes

Let $A$ be a finite set with $n \geq 4$ elements and let $\rho$ be an equivalence relation on $A$. Suppose that there are exactly four equivalence classes: $C_1, C_2, C_3, C_4$. Moreover we know that ...
0
votes
0answers
17 views

Bijection between partial order and $<$

How to show the correspondence between a less than relation and partial orders ? here A less than relation $<$ on a set $S$ is a relation that satisfies If $a < b$ , then $a \neq b$. ...
0
votes
3answers
36 views

What are Equivalence Classes

In most cases I can prove whether a relation is an equivalence relation or not but have no idea what "distinct equivalent classes" are. I tried to read some examples but couldn't figure out how to ...
1
vote
1answer
16 views

Little equivalence-relation problem

If $U=\{1,2,\ldots,1000\}$ and $A = \mathbb P(U) - \{ \emptyset \}$, the following relation $R$ is defined in $A$ $$XRY \Leftrightarrow (\min X = \min Y) \wedge (\max X = \max Y)$$ Calculate ...
2
votes
3answers
42 views

Relations and Combinatorics exercise

Be $A=\{1,2,3,\ldots,10\}$ Determine how many equivalence relations can be defined in $A$ with exactly two equivalence classes. Determine how many equivalence relations can be defined in $A$ with ...
1
vote
1answer
15 views

Verify an equivalence relation.

For a set $E $ of real numbers, define two points in $E $to be rationally equivalent if their difference belongs to $Q $. Prove that this defines an equivalence relation. (i) is trivial as 0 is a ...
0
votes
0answers
32 views

Prove that $R_1$ refines $R_2$ if and only if the partition with respect to $R_1$ is a refinement of the partition with respect to $R_2$.

Let $R_1$ and $R_2$ be equivalence relations on a set $S$. Prove that $R_1$ refines $R_2$ if and only if the partition with respect to $R_1$ is a refinement of the partition with respect to $R_2$. ...
1
vote
1answer
29 views

Define a $T$ on $ A \times B$ by $((a_1,b_1),(a_2,b_2)) \in T \leftrightarrow (a_1,a_2) \in R$. Prove that $T$ is an equivalence relation.

Let $R$ be an equivalence relation on $A$ and let $S$ be an equivalence relation on $B$. Define a $T$ on $ A \times B$ by $((a_1,b_1),(a_2,b_2)) \in T \leftrightarrow (a_1,a_2) \in R$ and ...
0
votes
2answers
37 views

Inference Proof with Quantifiers

I am trying to figure out this implication proof. Can any of you guys tell me how to prove this? Prove ∀x((¬P(x) ∧ Q(x)) → R(x)) Implies ∀x(¬R(x) → P(x))
0
votes
0answers
19 views

Is an equivalence class same as residue class?

So my teacher's notes say this: An equivalence class consists of those integers which have the same remainder on division by n. They are also known as "congruence classes modulo n" Since ...
0
votes
1answer
54 views

Equivalence Relation Quotient

Let $S$, $R$ be two equivalence relations in $A$, with $S \subset R$. Let $1^* : A/S \to A/R$ be the map induced by relation preserving map $1_A$. Define $(S a) R/S (Sb)$ if $1^*(S a)=1^*(Sb)$. ...
2
votes
2answers
554 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: ...
0
votes
1answer
64 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
0
votes
3answers
45 views

Partition induced by the Equivalence Relation

I'm not sure I understand this concept. Let's say we have a "Is parallel to" relation from the set of all lines in the Cartesian plane. What would be the partition induced by this relation? Thank ...
0
votes
0answers
9 views

What kind of relation does an ambiguous organization scheme introduce?

Please consider an arbitrary set of items, i.e. products in a supermarket or news in a news channel. Let's say we want to apply an organization scheme to that items. There are unambiguous ones, like ...
0
votes
1answer
45 views

What is the proper way to format a hypothetical syllogism proof?

Problem: Show that these three statements are equivalent, where $a, b \in R:$ (i) $a < b$, (ii) the average of $a, b,$ is greater than $a,$ and (iii) the average of $a$ and $b$ is less than $b$. ...
2
votes
4answers
73 views

Equivalence relation and subgroup

I am taking abstract algebra now, and there's a lemma: Let $H$ be a subgroup of group $G$, for $a,b \in G$,define $a\sim b$ if $ab^{-1}\in H$, then it is an equivalence. I know how to prove it and how ...
0
votes
1answer
35 views

Proving that $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$

This assingment is preparation for exam. I need to prove with $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$ that $\sim$ is equivalence relatio. Can you tell me how to do this. ...
3
votes
1answer
40 views

What is the common preimage (in $Z$) and the equivalence relation for Pushouts

Here it says: Suppose that $X$, $Y$, and $Z$ as above are sets, and that $f : Z → X$ and $g : Z → Y$ are set functions. The pushout of $f$ and $g$ is the disjoint union of $X$ and $Y$, where elements ...
2
votes
1answer
22 views

Example of an equivlance relation that is transitive

I am just tying to figure our this example but am having difficulty understand the math being used. The example state: Let R be a relation on the set $\mathbb{Z}$ defined as $(m,n)\in$ R if and only ...
0
votes
2answers
38 views

Trying to understand an example of an equivlance relation that is symmetric

I am just tying to figure our this example but am having difficulty understand the math being used. The example state: Let R be a relation on the set $\mathbb{Z}$ defined as (m,n)$\in$ R if and only ...
0
votes
1answer
49 views

Understanding an equivalence relation

Let $$R = \{ \left\langle {x,y} \right\rangle \in \wp (\mathbb{Z}) \times \wp (\mathbb{Z})|\exists t \in \mathbb{Z}.y = x + t\} $$ This is the equivalence class for $\{0\}$ $$\begin{array}{l} ...
1
vote
1answer
31 views

Proving the transitive property of an equivalence relation

I have to prove an equivalence relation.. $x$ is related to $y$ in the reals if $|x-y|\le3$ Reflexivity was easy. Symmetry was just a matter of breaking up the +ve and -ve case and it worked out. ...
0
votes
1answer
44 views

Help visualize set of all equivalence relations

I want to prove that the poset $Eq(A)$ with $\subseteq$ as the partial ordering is a complete lattice. But before even beginning to prove it, I have trouble visualizing the poset of $Eq(A)$. Kindly ...
0
votes
1answer
35 views

Determining number of different equivalence relations in a set with 4 elements

I have a set with 4 elements. Let A be $A=\{a,b,c,d\}$ How would I find number of different equivalence relations in this set? Should I use Bell's number theorem in which n would be 4? Should I ...
0
votes
2answers
26 views

Equivalence relation- Equivalence Classes And Partitions

I had the following question A is a finite set and $R \subseteq A \times A$ is a equivalence relation. Prove that $|A|$ is odd iff $|R|$ is odd. I am trying to find a general formula for this ...
0
votes
1answer
135 views

Proving equivalence relations

I just started my abstract algebra class and I am struggling with the concept of equivalence relations. I know that in order to prove equivalence relations I have to prove the reflexive, symmetric, ...
4
votes
2answers
35 views

Using Logical Equivalences to prove $(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))$ is equivalent to $(\neg(r \land p) \lor q)$

I have been trying to solve the following proof: $$(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))\text{ is equivalent to } (\neg(r \land p) \lor q)$$ I am new to proofs and ...
0
votes
1answer
31 views

Is a relation$ R=\{(a,a):a\in I\}$ said to be reflexive, symmetric and transitive?

Consider a relation $R=\{(a,a): a\in A\}$ where $A=\{1,2,3\}$. i.e $R=\{(1,1),(2,2),(3,3)\}$ This clearly reflexive but is it necessary that all such relations are necessary to be symmetric and ...
0
votes
2answers
34 views

Logical Equivalence with →

I am given the problem of proving: $p → (q\land r) \equiv (p→q) \land(p→r)$ Using known logical equivalences. I'm not well practiced in transforming logical statements that contain →'s in them into ...
-2
votes
1answer
42 views

For a group $G$, show the relation $x\sim y$ defined by $\exists a(y=axa^{-1})$ is an equivalence relation on $G$.

Let G be a group. For $x,y\in G$, define $x\sim y$ if there exists some element $a\in G$ such that $y=axa^{-1}$. Show that ~ defines an equivalence relation on $G$.
1
vote
2answers
62 views

Conformal Equivalence of two Riemann metrics

I'm reading a paper and encountered a concept of conformal equivalence between two Riemannian metrics on a differentiable $2$-manifold $M$ : Two Riemannian metric $g$ and $f$ are conformally ...
1
vote
2answers
62 views

equivalence classes and cardinality

I need to prove that every equivalence class created by the equivalnce relation $\sim$ on $\mathbb{R}$, that is defined by: $a\sim b \Leftrightarrow (a-b) \in \mathbb{Q}$, is $\aleph_0$. Furthermore, ...
1
vote
0answers
34 views

The null set as the underlying set of a relation structure

Can the null-set underly a relation structure? Can it underly a well-order? If so, would such a well-order have order-type $0$? (Can one even have an order-type of $0$?) My motivation for this ...
0
votes
1answer
67 views

Transitive relations on a set of n elements

How to find out the total number of transitive relations in a set of n elements? I am facing a problem in finding all the possible cases, is it not possible to find all cases? If not possible, why?
1
vote
1answer
34 views

Proof that a given relation is an equivalence relation

Can someone can tell me if my proof of the next propostion is correct? Define the following relation: $$a\sim b \iff a-b=km, m\in \mathbb{Z}$$ Show $\sim$ is an equivalence relation And so here's my ...
1
vote
1answer
24 views

Show that f is a symmetric relation on A

I am learning about relations and I come across this exercise. And I don't understand the problem. Let me first state the problem here: Let $f: A \rightarrow A$ be a function for which $f(f(x))=x$ ...
2
votes
1answer
34 views

Equivalence and Order Relations

I have the following problem: Provide an example of a set $S$ and a relation $\sim$ on $S$ such that $\sim$ is both an equivalence relation and an order relation. Conjecture for which sets and this ...
0
votes
3answers
39 views

Equivalence Relation Statements Proof

Let $\sim$ be an equivalence relation on a class $X$. The following are equivalent for $x,y \in X$. 1) $[x]=[y]$ 2) $x \sim y$ 3) $x \in [y]$ 4) $y \in [x]$ 5) $[x] \bigcap [y] \neq \emptyset$ ...
0
votes
1answer
46 views

Show that homeomorphism is an equivalence relation in metric spaces

It needs to be shown that homeomorphism is reflexive, symmetric and transitive in all metric spaces. Reflexivity seems to be easy to show, but I'm not sure how to do the rest. Any help?
0
votes
0answers
32 views

A question on Partitioning regarding equivalence relations

Let $S$ be the Cartesian coordinate place $\mathbb R \times\mathbb R$ and define the equivalence relation $R$ on $S$ by $(a,b) R (c,d)$ iff $b-3a = d-3c$ Find the partition $D$ determined by $R$ by ...