# Tagged Questions

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

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 ...
73 views

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 ...
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 ...
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 ...
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 ?
25 views

### Let $R_1$ and $R_2$ be reflexive relations on a set $S$. Prove that $R_1\cup R_2$ and $R_1 \cap R_2$ are reflexive.

How do I go about proving this?
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 ...
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. ...
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'$ ...
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 ...
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 ...
38 views

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 ...
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 ...
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 ...
35 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 ...
23 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 ...
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 ...
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 ...
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,...
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 ...
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$. ...
46 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?
78 views

27 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 ...
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 ...
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 ...
### 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\...