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

learn more… | top users | synonyms

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 ...
1
vote
1answer
120 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
44 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 ...
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 ...
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 ...
3
votes
3answers
223 views

Methods for proving an equivalence relation

I'll be taking introductory abstract algebra in the fall, and so to prepare, I'm working through Pinter's text. Chapter 12 includes a number of exercises asking the student to prove that something is ...
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 ...
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 ...
0
votes
2answers
47 views

Show that $R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$ is an equivalence relation

How can I show that this is an equivalence relation ? $$R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$$
2
votes
2answers
118 views

Equivalence relation on class of all sets

Let $\mathcal{A}$ be the class of all sets. Prove that "has the same cardinality as" defines an equivalence relation on $\mathcal{A}$. I know that equivalence relations must be reflexive, symmetric ...
1
vote
3answers
53 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 ...
0
votes
1answer
27 views

Homomorphism theorem on equivalence classes

How do I prove the following: given $\sim$ on set X. Let $h:X \to (X/\sim)$. Also let $f:X \to Y$ be a function so that $x \sim y$ $\Longrightarrow$ $f(x)=f(y)$. Prove that there is a $i:(X/\sim) ...
2
votes
1answer
107 views

Proving relation $\{(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\}$ is not a transitive relation

I have trouble proving how the following statement is false: The relation $g = \{\,(x,y)\in \Bbb R\times\Bbb R\mid y = x^2\,\}$ is transitive. I know you have to use $yRx$, $zRy$, and $xRz$, but I'm ...
1
vote
1answer
42 views

Equivalence relation in a commutative ring

Let $R$ be a commutative ring and $I \neq R$ ideal of $R$. For $x,y \in R$, define $$ x \sim y \iff \exists\ a,b \in I\ \text{such that } x(1+a) = y(1+b). $$ One can easily see this is an equivalence ...
0
votes
3answers
116 views

Proving Logical Equivalence with Laws of Logic

I'm working on Logical Equivalence problems and I'm having trouble understand what to do with this first problem. The problem is to show that these two statements are equivalent to one another ...
5
votes
2answers
51 views

For a set of symmetric matrices $A_i$ of order p, show that if the sum of their ranks is p, $A_iA_j=0$

Here's what I know. Matrices $A_i$ for $i=1,...,k$ are all symmetric p by p matrices. $\sum\limits_{i=1}^k A_i = I_p$ where $I_p$ is the p by p identity matrix $\sum\limits_{i=1}^k rank(A_i) = p$ ...
0
votes
1answer
49 views

Equivalence relation $a\sim b$ iff $a=10^kb$

Consider the relation on the set of all real numbers $\mathbb R$, defined by $a\sim b$ if, and only if, there exists an integer $k$ so that $a = 10^k b$. Prove or disprove: this is an equivalence ...
1
vote
1answer
27 views

Prove that there exists a unique injective map $\gamma:X/_R\to Y$ with image equals $f(A)$ with $f=\gamma \circ \phi.$

So recently I have established an equivalence relation $R$ on $X$, with $xRx'$ iff $f(x)=f(x')$. Let $\phi:X\to X/_R$ be the map of sets sending $x\mapsto \bar{x}$. Prove that there exists a unique ...
1
vote
4answers
221 views

Equivalence relation

So I'm pretty new to abstract mathematics being a biologist an all. My biggest issue is that I can't really wrap my head around how to solve problems. So I have the problem: Let $X$ be the set of ...
2
votes
3answers
76 views

Set question, relations, equivalence classes

Let S be the set of all bit strings (a sequence of 1s and 0s) of length 3 or more. Let R be a relation on S of all pairs (x, y) where x and y are in S if x and y have the same first two bits. Is R ...
5
votes
3answers
10k 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: ...
2
votes
2answers
26 views

Equivalence relations

Having trouble proving this is an equivalence relation. Is it suffice to say that let $x y z$ be any string in $\Sigma^*$, $(xz \in L \iff yz \in L) \rightarrow (yz \in L \iff xz \in L)$ shows ...
1
vote
1answer
22 views

Let $A$ be an equivalence relation on the set $X$ and $B$ be the equivalence on $Y$. Find equivalence class of $A\times B$.

The definition of $A\times B$ is given to be a condition on pairs. Let $a, c \in X$ and $b, d \in Y$, then $(a, b)\sim_{A\times B}(c, d)$ if $a\sim_Ac$ and $b\sim_Bd$. I have shown that this is an ...
0
votes
1answer
32 views

Equivalence Classes, Power Sets, and basic set theory question

Fixing $N \in P(X)$ (the power set of X), we say that $A,B \in P(X)$ agree away from $N$ if $A - N = B - N$. We denote $A \sim B$ if $A - N = B - N$. I have to show that every equivalence class has a ...
0
votes
1answer
21 views

Quotient Construction of a Power Set, equivalence relations, and symmetric difference.

Fixing $N \in P(X)$ (the power set of X), we say that $A,B \in P(X)$ $agree \ away \ from \ N$ if $A - N = B - N$. I have to show that $A \sim A', B \sim B'$ implies that $(A \Delta B) \sim (A' ...
1
vote
1answer
53 views

Prove that $R$ given by $L(a,b)\cap W =\varnothing$ is an equivalence relation.

Let $V$ be a real vector space and suppose $W$ is a subspace of $V$ with $\dim(W)=n-1$. Now define a relation $R$ on $V-W$ s.t. $$aRb\iff L(a,b)=\{ra+(1-r)b | 0\leq r \leq 1\}\text{ has the property ...
1
vote
2answers
37 views

Prove that $M/{\sim}$ forms a partition of $M$.

My attempt: Suppose $\sim$ is an equivalence relation on $M$. If $a \in M$, let $\bar{a}=\{m \in M \,|\, m\sim a\}$. Since each element $a$ of $M$ is in its own equivalence class $\bar{a}$, the union ...
1
vote
5answers
52 views

Prove that $(\mathbb{R}\setminus \{0\},\sim):= ab>0$ is transitive.

I have the following problem: A relation $\sim$ on $\mathbb{R}\setminus\{0\}$ is defined by $a\sim b$ if $ab>0$. Show that $\sim$ is an equivalence relation and identify the equivalence ...
0
votes
1answer
30 views

Equivalency of two definitions of WARP (Weak Axiom of Revealed Preference)

I have two definitions for WARP as follows. How can I prove they are equivalent? First Definition: $C(A) \cap B \neq \emptyset \Rightarrow C(B) \cap A \subset C(A)$ Second definition from ...
0
votes
1answer
28 views

Prove relation $\rho:(\forall x,y \in G)(x\rho y \Leftrightarrow x * y^{-1}\in H),H\le G$ is equivalence relation

Prove relation $\rho:(\forall x,y \in G)(x\rho y \Leftrightarrow x * y^{-1}\in H),H\le G$ is equivalence relation $H\le G\Rightarrow(\forall a,b\in H)a*b^{-1}\in H$ $(\forall x \in G)x\rho x$ ...
1
vote
1answer
43 views

Equivalent vs equal. When to use what?

When do you use equal and when equivalent? Why do I see on this site: (this is a random formula taken from this site): $\frac{\partial}{\partial \mu}F_X(x; \mu, \sigma^2) =\frac{\partial}{\partial ...
3
votes
1answer
113 views

Equivalence Relation using Binary Operations.

Question: Let ∗ be a binary operation on a set A. Assume that ∗ is associative with identity. Let R be the relation on A defined on elements a,b ∈ R as follows: aRb if there exists an invertible ...
0
votes
0answers
12 views

Equivalence Relation on the common restriction of two functions

I need to determine whether the following is an equivalence relation on $X$: $X = \{ f|f: A \to \mathbb{R}, A \subseteq \mathbb{R}\}$ (the set of functions from a subset of $\mathbb{R}$ to ...
3
votes
1answer
92 views

Proof that every open set in $\mathbb{R}$ is a countable union of disjoint open intervals using equivalence classes

We were told to prove that every open set in $\mathbb{R}$ is a countable union of disjoint open intervals using equivalence classes in the following way: Consider the following relation on a given ...
0
votes
1answer
33 views

Question on equivalence relations

In set theory a relation is said to be equivalence if the relation is,. Reflexive Symmetric Transitive I would like to know if the following relation is an equivalence one. $R = \{ (m,n) \in Z ...
0
votes
1answer
26 views

Proving symmetry in an equivalence relation

Let $H$ be a subgroup of a group $G$ and let $a,b \in G$. Define the relation $\equiv$ on $G$ by $a\equiv b$ if and only if $ab^{-1} \in H$. Show that $\equiv$ is an equivalence relation on $G$. Well ...
0
votes
1answer
34 views

Logical equivalence with truth tables

I'm trying to solve the highlighted part. I understand how they got the left side of the equation. They wrote out the truth table for a or b and then negated it. Easy. However for the right side I ...
0
votes
1answer
48 views

Defining an Operation

Let $R$ be the relation on $X=\mathbb Z\times \mathbb N$ such that $(a,b)R(c,d)$ if and only if $ad=bc$. Define an operation $\bullet$ on $X/R$ as follows: for $x=(a,b)$ and $y=(c,d)$ let: ...
0
votes
1answer
15 views

Proving equivalences and bijection

Define $\equiv$ and $\sim$ on $\mathbb{R}$ by $x\equiv y$ if $x-y \in \mathbb{Z}$ and by $x\sim y$ if $x-y\in \mathbb{Q}$. a) Show that $\equiv$ and $\sim$ are equivalences. b) Show that ...
1
vote
1answer
85 views

Prove the relation ~ on $A$ defined by $a$~$b$ if and only if $a = hb$ is an equivalence relation.

Let $H$ be a group acting of a set $A$. Prove that the relation ~ on $A$ defined by $a$~$b$ if and only if $a = hb$ for some $h \in H$ is an equivalence relation. (For each $x\in A$ the equivalence ...
0
votes
1answer
18 views

These maps from the components into a directed system are injective when the directed system maps are.

Let $I, p_{ij} : A_i \to A_j$ be a directed system of maps such that $p_{jk}\circ p_{ij} = p_{ik}$ whenever $i \leq j\leq k$ and $p_{ii} = \text{id}$. Directed means that for any $i,j \in I$ there ...
0
votes
1answer
23 views

Proving that the direct limit of a directed system is an equivalence relation.

From Dummit & Foote, pg. 268: Let $I$ be an index set with a partial order. Suppose for every pair of indices $i, j \in I$ with $i \leq j$ there is a map $\rho_{ij} : A_i \to A_j$ such that ...