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

learn more… | top users | synonyms

0
votes
3answers
20 views

Defining a relation to a set

I have a homework question that asks me to define a relation A2 on $Z$ which is an equivalence relation containing three equivalence classes. $$Z = \{a, b, c, d, e\}$$ I understand what equivalence ...
1
vote
0answers
18 views

Technical Language Usage: Verb for an Equivalence Relationship “Forgetting” an Attribute that is “Modded Away”

This question is one of English usage, but I'm sure only mathematicians can answer it for me. I want to say in a technical report that an attribute is "ignored" or "forgotten" by an equivalence ...
1
vote
1answer
31 views

Equivalence relation and class, Proof.

The relation $P$ on $ℝ$ is defined by $xPy$ iff $x^2=y^2.$ (a) Prove that the the relation $P$ is an equivalence relation. (b) Describe the equivalence class of $3$ and $0$. In order to ...
4
votes
4answers
487 views

Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and couldn'...
0
votes
2answers
96 views

Divisibility relation on nonnegative integers.

Definition: $a$ divides $b$ if $b = ak$ for some integer $k$. The book says that it is reflexive. But what about $0/0$ ? I am missing any point ? Is it not a paradox since for standard division ...
1
vote
2answers
10 views

Find total number of relations that are equivalence as well as partial order set

Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements. My attempt: As equivalence relation has property reflexive, symmetric and ...
4
votes
1answer
21 views

Constructing bijection from set of equivalence classes to another set

Suppose $f:A \to B$ is surjective. Define a relation on $A$ by setting $x\sim y$ if $f(x) = f(y)$. It is clear that $\sim$ is an equivalence relation on $A$. Let $\mathcal{E}$ be the set of ...
3
votes
0answers
37 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) $. $\mathbf{...
3
votes
1answer
417 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
41 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
60 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
30 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
73 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 $\sigma([...
0
votes
1answer
30 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
29 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
26 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
64 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: $$\{1\},\...
0
votes
3answers
25 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
27 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
43 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 transitive!...
0
votes
2answers
34 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
462 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
66 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
35 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
23 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
42 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
21 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
82 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
34 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
22 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 $\sim_\...
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 $\mathcal{R}\...
0
votes
1answer
71 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
28 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
22 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
21 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
23 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
41 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
39 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
39 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
40 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 ...