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

learn more… | top users | synonyms

3
votes
1answer
64 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
40 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
80 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
33 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 $\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
69 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
21 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
36 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
37 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
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
22 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
33 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
14 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
57 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 a,...
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$. ...
0
votes
1answer
13 views

Which language L have exactly one equivalence class

Consider the alphabet {a,b}, for which language does the equivalence relation R have exactly one equivalence class? From what i understand about equivalence class, each state is consider a class. So ...
0
votes
1answer
45 views

How to describe an equivalence class?

For example: the relation given is $x\sim y$ if $f(x)=f(y)$. What do you have to say when describing a equivalence class?
0
votes
1answer
78 views

Prove that $f : \mathbb R \smallsetminus \{−1\} \to\mathbb R \smallsetminus \{1\}$ given by $f(x) = \frac{x − 3}{x + 1}$ is bijective

I know for a function to be bijective it must be one to one and onto. Here's what I have Take by cases Case 1 (one to one) $$ \begin{align*} \frac{x-3}{x+1} &= \frac{y-3}{y+1} \\[1ex] (x-3)(y+1)...
0
votes
1answer
16 views

Cocycle condition on bundles as some equivalence relation?

The three cocycle conditions on the transition maps of a fiber bundle look alot like the three condition defining equivalence relation - refelxivity, symmetry, and transitivity. I was wondering ...
5
votes
1answer
81 views

Cardinality of equivalence relations in $\mathbb{N}$

I came across this long proof on this site: Cardinality of relations set But I would like to know whether my direction can work. Say we want to find the cardinality of all equivalence relations in $...
0
votes
2answers
64 views

Show that R is an equivalence relation and determine all distinct classes

Let R be a relation on Z define as follows: m R n <--> 3|($m^2$-$n^2$) show that R is an equivalence relation and determine all distinct equivalence classes. EDIT: I looked several places and ...
1
vote
0answers
31 views

prove that for any pair of natural, there is a power of 2 that separates the pair of natural

i need to prove that: $$ \forall i,j \in \{1, \_ ,N \} \subset \mathbb{N} \ \exists k \in \mathbb{N} / (r_{2^k}(i) \leq 2^{k-1} \wedge r_{2^k}(j) > 2^{k-1})\vee (r_{2^k}(i) > 2^{k-1} \...
0
votes
1answer
26 views

equivalence relation and sets

The question: Let $X$ and $Y$ be two sets, and let $S$ be an equivalence relation on set $X$ and $T$ be an equivalence relation on set $Y$. Define a relation $R$ on $X ×Y$ by $(a,b)R(c,d)$ if and ...
0
votes
1answer
24 views

Equivalence classes in the logical equivalence on some finite set of propositional formulas

I'm having trouble understanding the following problem: Let $S_n$ be the set of all formulas that can be built up with the atoms $\{A_1,...,A_n\}$. How many equivalence classes does the ...
0
votes
1answer
25 views

Equivalence relations and composition, intersections of them

I've been having some trouble with this one, I hope someone get's it. Let S and R be equivalence relations within X. Prove that if R∘S is an equivalence relation, then it is equal to the ...
0
votes
0answers
42 views

Lagrange's theorem intuition

I cannot grasp the intuition behind |G|/|H|=[G:H]. Starting from the equivalence relation x~y if and only if x^(-1)*y is in H, I can see a sort of division, but in my mind, the equivalence relation ...
0
votes
0answers
17 views

Prove that $P_{1}$ and $P_{2}$ have only one common refinement iff $E^{P_{1}} \cap E^{P_{2}} = =_{a}$

Let $A$ be a set. $P_{1}$,$P_{2}$ Are partitions of $A$. Let $E^P$ be the equivalence relation associated to a partition $P$ $$E^P:=\{\langle a,b\rangle \mid \exists \mathcal B\in P\ (b\in\mathcal B\...
1
vote
2answers
39 views

Prove that the union of two equivalence relations on the same set an equivalence relation iff?

Let $R$ and $E$ be equivalence relations on set $A$. Prove that $R\cup E$ is an equivalence relation on set A iff for all $a\in A$, $[a]_{R} \subseteq [a]_{E}$ OR $[a]_{E} \subseteq [a]_{R}$. ...
1
vote
1answer
29 views

What is an equivalence class of an equivalence relation?

I might be interpreting this wrong but in my book it says: If ~ defines an equivalence relation on $A$ then the set of equivalence classes of ~ form a partition of $A$. To me, this means that the set ...
0
votes
1answer
26 views

Proved that if $R\cup E$ equivalence relation so $a / E \subseteq a / R$ OR $a / R \subseteq a / E$

Let R, S be equivalence relations on A. Proved that if $R\cup E$ Is an equivalence relation on A So $\Rightarrow$ For all $a\in A$ , $$a / E \subseteq a / R$$ OR $$a / R \subseteq a / E$$ I ...
2
votes
1answer
38 views

Can $R=\{(1,6),(2,7),(3,8)\}$ be said transitive?

Given a relation $R=\{(1,6),(2,7),(3,8)\}$. It is clear that it is not reflexive and symmetric but can we say that it is transitive?
0
votes
1answer
21 views

Determinate the quotient topology

I was trying to find the quotient topolgy for the next example: Let R be the real numbers with the usual topology ($\tau$) and define the relationship $\mathcal{R}$ over R as follows, a $\mathcal{R}$...
0
votes
0answers
13 views

Determine the given relation is Equivalence Relation or not.

$R_{1} \oplus R_{2}$ I know that $R_{1} \oplus R_{2} = R_{1} \cup R_{2} - R_{1} \cap R_{2}$, and $R_{1} \cup R_{2}$ is not necessarily an equivalence relation but $R_{1} \cap R_{2}$ is always an ...
0
votes
2answers
16 views

How do I prove symmetry of a relation given a function?

Let G be a group. For all $g\in G$ , define the function f: G → G that sends x to $gxg^{-1}$. Define the relation ~ on G by a~b if $a = f(b)$ for some $g\in G$. Prove that ~ is an equivalence relation....
3
votes
6answers
71 views

Why $yC_1x \iff yC_2x$ implies $C_1 = C_2$? $C_i$ is a relation.

Here is the text from the book Topology by Munkres: Studying equivalence relations on a set $A$ and studying partitions of $A$ are really the same thing. Given any partition $\scr D$ of $A$, there ...