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

learn more… | top users | synonyms

8
votes
3answers
154 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 ...
8
votes
1answer
177 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 ...
7
votes
2answers
150 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
1answer
209 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 ...
5
votes
4answers
2k 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 ...
5
votes
1answer
65 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
73 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
268 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
330 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
92 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
321 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
1k 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
417 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 ...
4
votes
2answers
99 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
109 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
119 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
2answers
93 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
77 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
138 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
193 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
766 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
35 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
2answers
102 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
229 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
130 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
82 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
89 views

Colored Picture for Equivalence Classes, Relations, Partitions, .. [closed]

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
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
144 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
85 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
183 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
201 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
236 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
136 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
660 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
148 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
107 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
117 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
88 views

Having the same equivalent class imply that the elements are equivalent?

You have given that the equivalence class of $x$ and the equivalence class of $y$ is equal. $[x]=[y]$. Does this imply that $x\sim y$? If yes, how do I prove it, if no, what sort of counter-examples ...
3
votes
2answers
47 views

Functional relations : Trouble seeing transitivity

I've been 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 ...
3
votes
2answers
183 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 ...
3
votes
2answers
83 views

Methods for proving an equivalence relation

I'll be taking introductory abstract algebra in the fall, and so to prepare, I'm working through Pinter's text. Chapter 12 includes a number of exercises asking the student to prove that something is ...
3
votes
2answers
646 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
1answer
40 views

What is the common preimage (in $Z$) and the equivalence relation for Pushouts

Here it says: Suppose that $X$, $Y$, and $Z$ as above are sets, and that $f : Z → X$ and $g : Z → Y$ are set functions. The pushout of $f$ and $g$ is the disjoint union of $X$ and $Y$, where elements ...
3
votes
4answers
146 views

how to show/prove 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 ...
3
votes
2answers
298 views

Equivalence relations on natural numbers

How many equivalence relations are there on $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers? How can one compute it?
3
votes
3answers
163 views

Disjoint Equivalence

Why do equivalence classes, on a particular set, have to be disjoint? What's the intuition behind it? I'd appreciate your help Thank you!
3
votes
1answer
206 views

Class of all finite sets

In a higher algebra book that I'm working through, the natural numbers are constructed in the following manner:- Consider the class $S$ of all finite sets. Now, $S$ is partitioned into equivalence ...
3
votes
2answers
508 views

Working with Equivalence Classes and Quotient Sets

I have a doubt about working with equivalence classes and quotient sets. The definition that I know, is that given an equivalence relation $\sim$ on a set $A$, the set of all elements of $A$ ...
3
votes
1answer
115 views

Name of a simple equivalence relation on real numbers?

Define the relation $x \sim y$ where $x$ and $y$ are real numbers to hold if and only if there exist natural numbers $n$ and $m$ such that $x^n = y^m$. It is easy to see that $\sim$ is an equivalence ...