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

learn more… | top users | synonyms

3
votes
0answers
31 views

Restriction to equivalence relation is equivalence relation

Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $. ...
3
votes
1answer
406 views

Show that the restriction of an equivalence relation is an equivalence relation.

Let $C$ be a relation on a set $A$. If $A_{0} \subset A$, define the restriction of $C$ to $A_{0}$ to be the relation $C \cap (A_{0} \times A_{0})$. Show that the restriction of an equivalence ...
0
votes
1answer
33 views

Equivalence relation and restriction

This is a HW question Suppose $B \subseteq A$ and $R_a$ is an equivalence relation on A. Let $R_b$ the restriction of $R_a$ to B; that is, $R_b = \{(a,b) \in R_a : a,b \in B\} $ Is $R_b$ an ...
0
votes
0answers
33 views

Relations on equivalence classes

To be short, I will abstract a bit from my particular problem. Let $S$ be a set and $\sim$ be an equivalence relation, defined on that set. Let $R \subseteq (S/\sim) \times (S/\sim)$ be a relation ...
1
vote
2answers
56 views

Prove that $[a]=[b]$ iff $a\sim b$.

If $[a]=[b]$ then $a$ is in $[b]$ and $b$ is in $[a]$. If $a \sim b$, then $[a]$ is a subset of $[b]$ and $[b]$ is a subset of $[a]$. Then using the equivalence properties and showing that there is a ...
0
votes
2answers
22 views

Prove that $aRb$ if $a = 2^kb$ is an equivalence relation.

Let $R$ be a relation on the set of integers given by $aRb$ if $a = 2^kb$, for some integer $k$. show that $R$ is an equivalence relation. I don't understand how it will be equivalence. Is it the ...
5
votes
3answers
6k views

Number of equivalence relations on a finite set

I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible ...
0
votes
2answers
71 views

Elementary math proof

Let $\sigma$ : $\mathbb{Z}_{11} \to \mathbb{Z}_{11}$ be given by $\sigma([a]) = [5a + 3]$. Prove that $\sigma$ is bijective. Approach It has to be one to one and onto so It is one to one if ...
0
votes
1answer
25 views

Transivity / Binary relation? [closed]

Discuss the Transitivity of Binary Relations $\mathcal{S} $ $a$ on $\Bbb R $ defined by $a (x, y)$ $\in \Bbb R^2 $--> $x \leq ay$ ( for some a $ \in \Bbb R$ ) I have this assignment about ...
0
votes
1answer
20 views

Let R be the relation on the set of ordered pairs of positive integers, Z+ × Z+, such that (a, b)R(c, d) if and only if ad = bc.

(For instance, (2, 4)R(6, 12) since 2·12 = 4·6.) Show that R is an equivalence relation. I was tasked to show that the sets is an equivalence relation if the three conditions Reflexive, symmetric and ...
2
votes
1answer
37 views

is this an equivalence relation? by Reflexive, Symmetric and Transitive.

i. {(a, b) : a and b have met} ii. {(a, b)} : a and b speak a common language i) Reflexive: yes Symmetric: yes Transitive: No, if a met b and b met a then a does not met c. ii) Reflexive: yes ...
1
vote
2answers
24 views

How to prove equivalence relation is disjoint?

I know how to prove when the equivalence are not disjoint, thus $[a]=[b]$. I see that the proof works for proving a equivalence relation is disjoint, but I don't get it. Can someone explain it to me? ...
0
votes
1answer
25 views

$X$ hausdorff and $ \big\{ (x, y) : x ∼ y \big\} ⊆ X × X$ is closed implies quotient map is open.

Let $∼$ be an equivalence relation on a topological space X. $\ Y = X/∼ $ equipped with the quotient topology. How to show that if X is Hausdorff and the set $ \big\{ (x, y) : x ∼ y \big\} ⊆ X × X$ ...
2
votes
3answers
59 views

How many equivalence relation can be defined on a set of $5$?

The question is how many equivalence relation can be defined on a set of $5$? I think this is asking how many different ways can we partition a set of $5$, right? So the answer is $1$ way: ...
0
votes
3answers
24 views

Prove transitivity or not of some relation

I'm trying to prove if this equation is an equivalence relation or not. $R =\{(x,y) \in N\times N: \mbox{There exist }m,n \in N\mbox{ such that } x^m = y^n\}$ It's relatively easy to prove both ...
2
votes
1answer
26 views

Norms Equivalence over $\mathbb R^n$

Let $\|\cdot\|$ be any norm on $\mathbb R^n$. Prove that a sequence in $\mathbb R^n$ is Cauchy under the $\|\cdot\|_2$ norm if and only if the sequance is Cauchy under the $\|\cdot\|$. Prove that a ...
0
votes
1answer
24 views

Find the multiplicative inverses of each nonzero element of the field $Z/(5), Z/(11), Z/(17).$

For $Z/(5)$, I figured that $[4]$ is a class that has an inverse of its own since $4 \equiv -1 (mod 5)$. Is that correct? Then I tried figuring that $[2]$ is also an inverse of its own since $2 \equiv ...
3
votes
1answer
72 views

Prove that $R = \{((m,n),(p,q)):m + q = n + p\}$ is an equivalence relation on $\mathbb N_0$.

Define the relation $R$ on $\mathbb{N}_0$ by $$R = \{((m,n),(p,q)):m + q = n + p\}.$$ (a) Prove that $R$ is an equivalence relation. Now I need to prove it's reflexive, symmetric, and ...
0
votes
2answers
32 views

Proving equivalence classes for a equivalence relation

I am having a bit of trouble trouble understanding how to start problems such as this one. I feel like I am given information that I understand separately but I can't seem to figure out how to they ...
0
votes
1answer
450 views

Equivalence Relations On a Set of All Functions From $\mathbb{Z} to $\mathbb{Z}$

The question is, "Which of these relations on the set of all functions from $\mathbb{Z}$ to $\mathbb{Z}$ are equivalence relations. $\{(f,g)|f(1)=g(1)\}$ I just want to make certain that I am ...
3
votes
1answer
51 views

Does the theory of equivalence relations have quantifier elimination?

I am aware that the theory of equivalence relations with infinitely many classes, all of which infinite, has quantifier elimination, as can be seen from the answer to this question. However, does the ...
2
votes
1answer
32 views

Why is this function well definded?

I have to take a look at the relation of $ x \sim y: \Leftrightarrow \exists k \in \mathbb{Z} : x-y=5k$ in $\mathbb{Z}$. I have no idea how to show at $\mathbb{Z} / \sim$ that the addition is well ...
1
vote
1answer
22 views

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function …

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function $f: A \to \Bbb N$ such that $\forall a, b \in A$ the following is true: $$a \mathcal R b \iff f(a) = ...
1
vote
0answers
39 views

How many equivalence classes in a set of well-orders of a set

The question: Let $S$ be a set and $\operatorname{wo}(S)=\{X: X\subseteq S \land (X,\le) \text{ is a well order}\}$. Furthermore, partition $\operatorname{wo}(S)$ into equvialence classes based on ...
1
vote
1answer
20 views

Solution check. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties.

I'm revising some old psets while preparing an exam and going through some things that I left unverified. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the ...
5
votes
2answers
51 views

Prove that $(H,\circ)$ is a subgroup of the group $(G, \circ)$

Question: Let $(G, \circ)$ be a group and $H$ be a non-empty subset of $G$. A relation $\rho$ defined on $G$ by $$a\,\rho\ b\quad \text{if and only if}\quad a\circ b^{-1}\in H$$ for $a,b\in G$, is an ...
1
vote
1answer
77 views

For a group $G$ and subgroup $H$, is $a \sim b \iff a^{-1}b\in H$ an equivalence relation even when $H$ is not normal?

Is it true or false that defining a relation on the group $G$ based on the definition $a \sim b$ if and only if $a^{-1}b\in H$ defines an equivalence relation regardless of whether $H$ is a normal ...
2
votes
1answer
32 views

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number ...
0
votes
0answers
21 views

How to phrase a proof of a equivalence relation of bijection

Define $\sim_\mathrm{bi}$ by $$\sim_\mathrm{bi} = \{(S_1,S_2)\mid \text{there is a bijection } f:S_1 \to S_2\}$$ for $S_1,S_2 \subseteq \mathbb{N}$ My proof comes as: In order to prove that ...
1
vote
0answers
28 views

Symmetry of a relation

Let $A\neq\emptyset$ and $\mathcal{R}\subset A\times A$ a binary relation on $A$ such that the domain $D(A):=\{x\in A\mid \exists y\in A \text{ such that }(x,y)\in\mathcal{R}\}=A$ and ...
0
votes
1answer
64 views

Quotient topology on unit sphere

Let $\sim$ be the equivalence relation $$a\sim b\iff a=b\text{ or }a=-b,$$ for $a,b$ on the unit sphere $S^2$. Let $Q$ be the quotient space. How do I show that the quotient map is a covering ...
0
votes
0answers
24 views

Bound the vc dimension of hypothesis class

Given some set $V$ of size $n$, define the domain $X = V \times V$. In addition, define the hypotheses class $H$ to be all the equivalence relations over $V$ with at most $k$ equivalent classes. I am ...
0
votes
3answers
23 views

Prove the relation $R$ in $N \times N$ defined by $(a,b) \simeq (c,d)$ iff $ad=bc$ is an equivalence relation.

If $N$ is the set of all natural numbers, $R$ is a relation on $N \times N$, defined by $(a,b) \simeq (c,d)$ iff $ad=bc$, how can I prove that $R$ is an equivalence relation ?
0
votes
0answers
18 views

Symmetry and transitivity with the existential quantifier

I can't find any resource that would indicate whether symmetry and transitivity relations are possible or not with the existential quantifier or when quantifiers are combined. I'm interested in the ...
0
votes
2answers
20 views

Matrices Eqvialence Relation

How can I prove that $A\mathcal{R}B$ is an equivalence relation if there exists an invertible matrix $C$ such that $B = CA$? I know there there is a reflexive, symmetric, and transitive steps. ...
0
votes
2answers
45 views

$(X \times X) /{\sim'}\cong (X/{\sim}) \times (X/{\sim})$

The full description of this problem is: Let $X$ be a topological space. Let $\sim'$ be the equivalence relation on $X\times X$ defined by $(x,y)\sim'(x',y')$ iff $x \sim x'$ and $y \sim y'$ ...
0
votes
1answer
21 views

What is the difference between partial order relations and equivalence relations?

From googling it i understood that a relation is both partial order relation and equivalence relation when they are reflexive, symmetric and transitive. So it appears they are the same. But as far I ...
0
votes
1answer
34 views

Group action and equivalence relation

Let $G$ be finite, and group action on $X\subseteq G$: $g\cdot x:=g^{-1}xg$. Let $G=S_n$, and $X=S_n.$ Show that $[x]_R$ consists of all elements of $S_n$ that are of the same cycle-type as $x$. I ...
1
vote
1answer
35 views

Equivalence Class of functions and properties examples

(1) A function $f:\mathbb{R}^d \rightarrow \mathbb{R}$ is continuous almost everywhere, if the set {x: $f$ is not continuous at x} is a null set (2) There exists a continuous function $g:\mathbb{R}^d ...
0
votes
2answers
36 views

Equivalence relation and equivalence classes given function and relation

Given a function $f : A → B$, let $R$ be the relation defined on $A$ by $aRa′$ whenever $f(a) = f(a′)$. Prove that $R$ is an equivalence relation and determine the equivalence classes. To prove that ...
0
votes
0answers
31 views

Which of the following are equivalence classes?

For example 37, I've determined which ones are equivalence relations but am having trouble on example 37: 1-7 determining which of the following are equivalence classes. I'm having trouble ...
0
votes
1answer
39 views

How to prove something is an equivalence class?

I don't understand equivalence class and representative function: http://www.cdhmhome.com/uic/math215/S.pdf , I'm looking at examples 37, 1-7 and have already determined which ones are equivalence ...
0
votes
1answer
21 views

Finding equivalence classes in a set of functions with a condition

I can't seem to work around this problem... Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if ...
0
votes
0answers
26 views

Does $\lim\limits_{x\rightarrow a}(f-g)(x)=0$ then $f(x)\sim_{x\rightarrow a}g(x)$ and revert?

Why does $\lim\limits_{x\rightarrow a}(f-g)(x)=0$ then $f(x)\sim_{x\rightarrow a}g(x)$ false and $f(x)\sim_{x\rightarrow a}g(x)$ implies $\lim\limits_{x\rightarrow a}(f-g)(x)=0$ false? I was given ...
0
votes
0answers
31 views

Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
1
vote
1answer
12 views

Explain this step in solving this system of linear congruences.

I'm looking at this example and it doesn't make sense to me. We have to solve the following systems of linear congruences : $x\equiv 1\pmod 5$ $x\equiv 2\pmod 6$ $x\equiv 3\pmod 7$ We take ...
3
votes
4answers
54 views

Equivalence relation on $\mathbb{N}$ with infinitely many equivalence classes

Does there exist an equivalence relation, defined on $\mathbb{N}$, with infinitely many equivalence classes, all of which contain infinitely many elements? I see no reason for such a relation not to ...
0
votes
1answer
14 views

Relations and restriction of a function.

This is a homework question: "Let R be an equivalence relation on a set S. For A ⊆ S, we define RA to be the restriction of R to elements of the set A, i.e., RA is a relation on A such that for any ...
0
votes
2answers
23 views

Equivalence relations on intersections

Let $R_1$ and $R_2$ be equivalence relations on a set $S$. Their intersection is on the relations considered as sets of ordered pairs. Identify the equivalence classes of the relation $R_1 \cap R_2$. ...