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

learn more… | top users | synonyms

9
votes
1answer
282 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
103 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
3answers
178 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
2answers
161 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 ...
6
votes
4answers
3k 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 ...
6
votes
1answer
329 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
145 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
3answers
1k 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
377 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
80 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
1answer
88 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
284 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
396 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
136 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. ...
5
votes
2answers
535 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 ...
5
votes
0answers
196 views

Colored Picture for Equivalence Classes, Relations, Partitions, ..

Origin — A Book of Abstract Algebra — Charles Pinter — p120. I'm trying to sketch a colored picture for the ideas from equivalence classes, equivalence relations, partitions, etc... underneath. ...
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
4k 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
117 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
135 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
2answers
125 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
89 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
94 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
96 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
2answers
62 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
198 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
211 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
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
1answer
181 views

Picture - Equivalence Relation & Classes, Partitions, Quotient Set, & other related ideas

To get intuition for them and to remember them, I'd be grateful for a picture that combines and embodies the key definitions regarding Equivalence Relations & Classes, Quotient Sets, and ...
4
votes
2answers
124 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
401 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
139 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
136 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
0answers
44 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
7answers
156 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
105 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
226 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
2answers
3k 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: ...
3
votes
3answers
2k 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
324 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 ...
3
votes
2answers
194 views

Proving if a relation is an equivalence relation

I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation. $F$ is the relation defined on $\Bbb Z$ as follows: ...
3
votes
2answers
257 views

Would this relation be an equivalence relation?

I am a bit stuck on this one question from my homework and for some reason it isn't making any sense to me. I would really appreciate it if somebody could explain it to me how I can go about to ...
3
votes
2answers
745 views

For each of the following relations, determine whether it is reflexive, symmetric or transitive

a) X is the set of real numbers, n is a natural number $$R = \{(x, y) \mid x, y \in X, x^n = y^n\}.$$ b) X is the set of people in the world $$R = \{ (x, y) \mid x, y \in X, x\text{ and }y\text{ ...
3
votes
2answers
57 views

Functional relations : Trouble seeing transitivity

Given the following domain: $\;\{1,2,3,4\}$ And the following relation: $$\{(1,1),(1,3),(1,5),(2,2),(2,4),(3,1), (3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)\}$$ It states that this is an equivalence ...
3
votes
2answers
190 views

Equivalence classes of “$x \sim y \Longleftrightarrow x -y $ is rational”.

Given the equivalence relation $x \sim y \Longleftrightarrow x -y $ is rational on the interval $[0,1)$. How do we reason* that there are uncountably infinite number of equivalence classes? *A ...
3
votes
3answers
138 views

Is $f:\mathbb{Z}_{30}\longrightarrow\mathbb{Z}_{30}$ defined by $f([a])=[7a]$ well defined?

To tell the truth, I'm not even sure what this means. The professor gave an example saying that $\mathbb{Z}_m=\{[0],[1],[2],\dots,[m-1]\}$, and I sort of understand that.. but I have no idea what ...
3
votes
3answers
114 views

Confusion on understanding a proposition on equivalence classes

I am given to prove this proposition on equivalence classes. Each element of $A$ is an element of one and only one equivalent class. The part that is confusing is one and only one. It sounds ...
3
votes
3answers
118 views

$x,y$ related if and only if $x\cap\{{1,3,5\}}=y\cap\{{1,3,5\}}$.

Let A be the power set of $\{1,2,3,4,5\}$, let $z= \{1,2,3\}$, and let $(x,y) \in R$ if and only if $$x \cap \{1,3,5\} = y \cap \{1,3,5\}$$ I'm supposed to find the equivalence class, number of ...
3
votes
2answers
1k views

Determine whether this relation is reflexive, symmetric…

Determine whether this relation $R$ on the set of all integers is reflexive, symmetric, anti-symmetric and/or transitive where $x\,R\,y$ iff $x = y + 1$ or $x = y-1$ It is not reflexive: Let $x = ...
3
votes
2answers
264 views

Properties of Equivalence Relation Compared with Equality

I'm reading about congruences in number theory and my textbook states the following: The congruence relation on $\mathbb{Z}$ enjoys many (but not all!) of the properties satisfied by the usual ...