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

learn more… | top users | synonyms

0
votes
0answers
19 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
19 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
44 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
16 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
29 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
34 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 ...
-4
votes
1answer
41 views

Equivalence Class help? [closed]

http://www.cdhmhome.com/uic/math215/S.pdf Defining the Equivalence Class in example 37:3 for the general case. Please help. It's a relation. Similarily if one could help define the general ...
0
votes
2answers
33 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
30 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
37 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
0answers
25 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
29 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 ...
0
votes
1answer
18 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 ...
1
vote
1answer
9 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
50 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
13 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
1answer
12 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
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
43 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
76 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] ...
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 ...
1
vote
0answers
30 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
19 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
23 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
38 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
16 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 ...
1
vote
2answers
35 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 ...
2
votes
1answer
36 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 ...
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 ...
0
votes
0answers
12 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 ...
0
votes
1answer
13 views

Counting ordered pairs in quotient set

We have equivalence relation E on the set $$A = \{1,2,3,4,5\}$$ So the quotient set: $$A/E = \{\{1,2,3\}, \{4\}, \{5\}\}.$$ How much orderd pairs we can find in E? How to count the ordered ...
1
vote
0answers
44 views

LEN-Model equivalency

Starting position is a principal-agent-model with incomplete information (moral hazard) and the following properties: Agent utility: $u(z)=-e^{(-r_az)}$ Principal utility: $B(z)=-e^{(-r_pz)}$ Effort ...
0
votes
2answers
31 views

What is the equivalence class of the following equivalence relation?

If we have a equivalence relation $R=_{def} \{((x_1,y_1),(x_2,y_2)) ~~| ~~x_1-y_1=x_2-y_2 \} \subseteq \mathbb{R}^2 \times \mathbb{R}^2 $ What is the equivalence class $[(0,1)]_R$? I thought it ...
1
vote
0answers
16 views

equivalence class of kernel relation of floor function

By taking particular values of $k$, I found that equivalence class of $k$, $[k]=\{k,k+1,k+2,...,2k-1\}$, equivalence class of $2k$, $[2k]=\{2k,2k+1,2k+2,...,3k-1\}$ and so on, but how to present it ...
1
vote
0answers
9 views

Number of symmetric relations

Let set $A=\{1,2,3\}$ Find number of symmetric relations that can be defined on $A$ containing ordered pairs $(1,2)$ and $(2,1)$ is? Can someone give me some hint for this question?
1
vote
1answer
37 views

Show that either $[x] = [y]$ or $[x]$ and $[y]$ are disjoint?

An equivalence class $[x]_R$ is defined by $[x]_R = [y ∈ X : xRy]$. In this proof I'm supposed to start by assuming $[x]$ and $[y]$ are not disjoint. Therefore, there is some element $z$ that is in ...
1
vote
5answers
26 views

Show that $x$ is an element of its own equivalence class?

If $R$ is an equivalence relation on $X$ and $x$ is an element of $X$, the equivalence class is defined as $[x]_R = [y ∈ X : xRy]$. Since $x$ is equivalent to itself, doesn't that automatically make ...
1
vote
1answer
33 views

Relations and their fallacies

I need to find a flaw in the proof of the following statement: Any relation that is symmetric and transitive is also reflexive. False Proof: aRb implies bRa,by symmetry. Then by transitivity, aRa ...
3
votes
6answers
70 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 ...
0
votes
2answers
51 views

Proving an equivalence relation on a $\mathbb Z\times \mathbb Z$

I am having some trouble understanding how to prove that a given binary relation is an equivalence relation. I understand that to prove that a relation is an equivalence relation, you must prove ...
1
vote
1answer
34 views

Which of the following equivalence classes are equal?

Let R be the relation of congruence modulo 3. Which of the following equivalence classes are equal. [7], [-4], [-6], [17], [4], [27], [19] The answer is: ...
0
votes
2answers
54 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 ...
0
votes
0answers
12 views

Is Congruence Class an example of Equivalence Class? (Understanding the definition through Examples)

Would you say a congruence class such as $[0]_{4}, [1]_{4}, [2]_{4},$ and $[3]_{4}$ an example of Equivalence classes since: the set of all elements of $\{..., -8, -4, 0, 4, 8,...\}$ is related to ...