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

learn more… | top users | synonyms

9
votes
1answer
389 views

Is the quotient map a homotopy equivalence?

It is well known that, if $A \subset X$ is a reasonable contractible subspace, then the quotient map $X \to X/A$ is a homotopy equivalence ("reasonable" means that the pair $(X,A)$ has the homotopy ...
9
votes
1answer
113 views

Does the Trace product in a semigroup have any relation with Trace of a matrix / matrix product

I recently read an article on generalized inverses and Green's relations (by X.Mary). The framework is semigroups, but obviously it has a lot of application within matrix theory. In the article ...
8
votes
4answers
4k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
8
votes
3answers
194 views

Can we take images of equivalence relations?

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This ...
7
votes
4answers
800 views

“$ x $ is a brother of $ y $.” Why is this not transitive?

I am working on a problem set at the moment, and while checking my answers I realized that I have listed "x is a brother of y" as a transitive relation, while the answers say that it is not. EDIT: I ...
7
votes
2answers
166 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
7
votes
4answers
238 views

How to find the appropriate equivalence class?

I would like find the system of representatives & equivalence class for $[(1,-1)]_{\equiv 1}$ and $[(1,-1)]_{\equiv 2}$ given: $R_1=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow ...
7
votes
1answer
68 views

When is the closure of an equivalence relation automatically an equivalence relation?

Let $X$ be a topological space, not necessarily nice, let $R$ be a subspace of $X \times X$, and let $\overline{R}$ be the closure of $R$ in $X \times X$. Then: If $R$ is a reflexive binary relation ...
6
votes
1answer
151 views

Confusion between an element and its preimage

Let $X$ be a set and $\sim$ is an equivalence relation on $X$, so that the quotient set $X/_\sim=\bigcup_{x\in X}{[x]}$ with $[x]=[y]$ if and only if $x\sim y$. Consider the quotient map $f:X\to ...
6
votes
1answer
465 views

Is “have the same cardinality” a equivalence relation?

A relation is a subset of the Cartesian product of two sets, if "have the same cardinality", denoted as $R$, is a relation, then there must exist set $A, B$, such that $R \subset A \times B$. What are ...
6
votes
1answer
189 views

How to simply show that there are “78 'strict ordinal' 2x2 game matrices”

In "Theory of Moves", Steven J. Brams analyses two-player games with two strategies per player, where each player can totally rank his payoffs, although payoffs need not be comparable among players. ...
6
votes
1answer
155 views

Solve for ? - undetermined inequality symbol

So I was solving a problem in Rudin (chapter 3 #16, to be specific) and I realized how convenient it would be to have a symbol that represented an undetermined equivalence relationship. As an example ...
5
votes
2answers
6k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
5
votes
3answers
2k views

Why is the empty set finite?

On page 25 of Principles of Mathematical Analysis (ed. 3) by Rudin, there is the definition (excluding the irrelevant parts for this question): Definition 2.4: For any positive integer $n$, let ...
5
votes
4answers
402 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...
5
votes
1answer
112 views

Prove $x^2 + 2y^2 \neq 805, x,y\in\mathbb{Z}$, using equivalence classes modulo 5

Prove $x^2 + 2y^2 \neq 805, x,y\in\mathbb{Z}$. We did this in class and, for the life of me, I cannot remember how to finish the problem. It starts out by taking all of the values to be $\mod5$. ...
5
votes
2answers
122 views

Categorical description of equivalence relation generated by a relation?

The notion of an equivalence relation generated by a relation is widespread and useful. How can one categorically describe it?
5
votes
1answer
93 views

Are these two equivalence relations the same ? (Equivalence relation defined using subgroups of a group)

I was solving the book Abstract Algebra by Charles Pinter. In one of the questions I was stuck. The question is as follows :- $H$ is a subgroup of group $G$.Two equivalence relations on $G$ are ...
5
votes
1answer
288 views

Is this alternative definition of 'equivalence relation' well-known? useful? used?

I discovered that $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ The nice thing about ...
5
votes
3answers
464 views

Equivalence class of polynomials

$X$ is the set of all polynomials over $\mathbb{R}$. We define an equivalence relation on $X$ such that $p$~$q$ iff $p(0)=q(0)$. ($1$) What is the equivalence class of $p(x)=x$? ($2$) Give a ...
5
votes
1answer
90 views

Question about right and left cosets.

I want to do a question about how my algebraic structures professor defined left and right cosets. I'll write here his way to present them. We first talked about quotient group. Let $G$ be a group, ...
5
votes
2answers
629 views

Sets, functions and relations problem

Yes this is a homework problem but I have attempted to solve it and my work is below, also this is my first question here so I'm sorry for any mistakes: Question: Context: Let $A$ and $B$ be subsets ...
4
votes
4answers
2k views

Proving an equivalence relation on $\mathbb{Z}\times\mathbb{Z}$

I'm working on some discrete mathematics problems, and have run into an issue involving proving an equivalence relation. The relation I'm tasked with proving is the relation $R$ defined on ...
4
votes
3answers
5k views

Prove that the intersection of two equivalence relations is an equivalence relation.

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R ...
4
votes
2answers
127 views

Equivalence relations on classes instead of sets

Can someone please explain to me how to deal with equivalence relations on classes instead of sets? Is there some sort of generalisation of relations? Thank you
4
votes
5answers
153 views

How do I work with a relation that is a set of 4-tuples?

Define the relation $\sim$ on $\mathbb{Z}\times\mathbb{Z}$ by $(a,b)\sim(c,d)$ if $a-c=b-d$. Show that $\sim$ is an equivalence relation. What is the equivalence class of $(1,2)$? I'm not sure ...
4
votes
4answers
696 views

$5 \mid n^2 - m^2$ is an equivalence relation

How can I show this is an equivalence relation: $$ n \operatorname{R} m \Longleftrightarrow n^2 - m^2 \textrm{ is divisible by } 5 $$ I know equivalence relations are symmetric, reflexive and ...
4
votes
2answers
133 views

“Tricky” wording on Congruence Modulo Question?

I'm asked for all possible values, but I can only see one. The question on my practice exam reads: Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. ...
4
votes
3answers
100 views

Is $\mathbb{Z}_p$ a Finite Field?

Denote the integers modulo $p$, $\mathbb{Z}$ mod $P$, as $\mathbb{Z}_P$. Denote the set of integers equivalent to $n$ mod $P$ - the equivalence class of $n$ as $\overline{n}$. We know that for any ...
4
votes
2answers
96 views

In topology $X$ is also $Y$ means homeomorphic?

E.g. $\mathbb{R}P^n$ is also the quotient space $S^n / (v \sim -v)$. And when is it safe to refer to a space as one of it's homeomorphic spaces and perform further deductions from that homeomorphic ...
4
votes
2answers
116 views

Uncountability of the equivalence classes of $\mathbb{R}/\mathbb{Q}$

Let $a,b\in[0,1]$ and define the equivalence relation $\sim$ by $a\sim b\iff a-b\in\mathbb{Q}$. This relation partitions $[0,1]$ into equivalence classes where every class consists of a set of numbers ...
4
votes
1answer
1k views

Myhill Nerode - is language regular or not?

I'm trying to understand how to find equivalence classes of a language to prove its regularity. I think that if I'm able to FULLY understand one example then I will get this topic right. Let's say I ...
4
votes
2answers
76 views

Using Logical Equivalences to prove $(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))$ is equivalent to $(\neg(r \land p) \lor q)$

I have been trying to solve the following proof: $$(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))\text{ is equivalent to } (\neg(r \land p) \lor q)$$ I am new to proofs and ...
4
votes
1answer
268 views

Proving that there are n Equivalence Classes Modulo n

For $a,b,n \in \mathbb{Z}$ and $n \geq 2$, I want to prove that there are $n$ equivalence classes mod $n$. I'm not sure how to do it - would I do it inductively? Any help would be appreciated.
4
votes
2answers
124 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
4
votes
2answers
220 views

Counting the number of functions

Let $A$ and $B$ be subsets of the set $\Bbb Z$ for all integers, and let $\mathscr F$ denote the set of all functions $f:A\rightarrow B.$ Assume $A = \{1,2,3\}$ and $B=\{1,2,...,n\}$ where $n\ge 2$ is ...
4
votes
1answer
36 views

Defining Equivalence relations

So I am not really comfortable with equivalence relations, so this example from Wikipedia gives me trouble. Here is what it says: Let the set $\{a,b,c\}$ have the equivalence relation ...
4
votes
2answers
141 views

Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$.

For $a,b \in \mathbb{R}$ define $a \sim b$ if $a - b \in \mathbb{Z}$ I don't understand how I'm suppose to prove this: Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$ Also can you ...
4
votes
2answers
653 views

Is $x = y \mod 7$ for a set of integers an equivalence relation?

Equivalence relation is the relation which is reflexive, symmetric and transitive. I have read somewhere that modulo operator defines an equivalence relation. But for this relationship I cant find ...
4
votes
1answer
141 views

Mean values theorem and countable sets

The mean values theorem says that there exists a $c∈(u,v)$ such that $$f(v)-f(u)=f′(c)(v-u)$$ My question is: Assume that $u$ is a root of $f$, hence we obtain $$f(v)=f′(c)(v-u)$$ Assume that $f$ is a ...
4
votes
1answer
152 views

The class of equivalence.

Let $Q$ be the following set of $\mathbb{Z}\times \mathbb{Z}$ \begin{align*} Q=\{(a,b)\in \mathbb{Z}\times \mathbb{Z} | b\neq 0\} \end{align*} Define the relation $\sim$ on $Q$ as ...
4
votes
5answers
3k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
4
votes
0answers
46 views

Equiv Relation of Orbits - Group Action [duplicate]

Let $G$ be a group that acts on $X$. I want to show that the orbits of $G$ partition $X$. I am given the relation $x\sim y \iff x\in Orb(y)$. Now: $x\sim y\iff x\in Orb(y) \iff x=gy$ for some $g\in G ...
3
votes
4answers
387 views

When a determinant is zero

Is it true that if $C$ is a square matrix of size $n$ and $\det(C) = 0,$ then $C^n = O_n$ or the $0$ matrix? If yes, then why is that? I know that the reverse is obviously true, so I wondered if ...
3
votes
7answers
164 views

Define a quotient structure for $(a,b)\sim(c,d)$ iff $a+d=b+c$ in terms of $+$ and $\times$ operators

This is a past paper exam question, I don't really understand how to define this quotient structure. The relation is on $\Bbb{N}$ In the preceding question I proved that this relation is an ...
3
votes
4answers
111 views

Different equivalence relations of the set $\{a,b\}$

In the book of Richard Hammack, I come accross with the following question: There are two different equivalence relations on the set $A = \{a,b\}$. Describe them. OK, I found that the solution ...
3
votes
2answers
230 views

An example in the fundamental theorem of equivalence relations?

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there ...
3
votes
2answers
256 views

Equivalence Classes in the cartesian plane

The relation $\sim$ on $R \times R$ is defined by $(a,b) \sim (c,d)$ iff $a^2 +b^2 = c^2 + d^2$. I have already proven that this is an equivalence relation but I need to give a geometric description ...
3
votes
3answers
3k 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 ...
3
votes
3answers
390 views

Equivalence relation question with functions

We'll define on the set: $A=\Bbb R^{[0,1]}$ the relation $R$ by $fRg$ if $f(0)=g(0)$. Make sure it's an equivilence relation. What is $[\cos x]$ ? Describe all the equivalence classes ...