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

learn more… | top users | synonyms

0
votes
0answers
21 views

Question about Equivalence relation and partition

This is my first time of Abstract algebra, and I don't know how to solve this problem. Although I have an idea to solve this problem, I can't assure whather it is correct or not. Please show me how ...
2
votes
1answer
105 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 ...
-2
votes
1answer
53 views

Let ~ be an equivalence relation on a set S. Show that b is an element of cl(a) <=> cl(a) = cl(b) (Where all a,b are elements of S)

This was a question on my last equivalence relations quiz and I'm not yet comfortable with the whole "class" idea. I understand that I must show transitivity, reflexivity and symmetry however I'm not ...
0
votes
2answers
165 views

Determine the number of equivalence relations on the set {1, 2, 3, 4}

Hi this was a question listed on my last proofs and conjectures midterm. It is similar to my previous post however this asks a different question which is throwing me off.. Do I simply list all ...
0
votes
2answers
53 views

Determining whether relations are equivalence classes, and finding the equivalence classes

Determine if each of the following relations is an equivalence relation. If so, determine the equivalence classes. $S = \Bbb Z$, $a \sim b \iff a \equiv b \pmod 3$ or $a \equiv b \pmod 5$. ...
0
votes
1answer
42 views

Equivalence relation and quotient set

I'm studying for a test and got stuck in one question regarding equivalence relations and quotient set. Here is the question: Let $F=\mathbb{R}\to \mathbb{R}$ be the set of functions from ...
2
votes
1answer
24 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
62 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
39 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
44 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
27 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
78 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
17 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
36 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
64 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
18 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
38 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
50 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
16 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
35 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
32 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
38 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
24 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
58 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
1k 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
99 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
48 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
11 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 ...
1
vote
1answer
54 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
87 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
37 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
43 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
27 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
39 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
42 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
54 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
28 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
490 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
47 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
33 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
37 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
45 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
104 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
64 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
71 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?