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

learn more… | top users | synonyms

17
votes
3answers
569 views

When are algebraic expressions equivalent?

This question arose when I was going to determine the domain for $f \circ f(x)$. Let $f(x) = \dfrac{1-x}{1+x}$. $f \circ f(x) = x, \quad$ But the domain is not $\mathbb{R}$ because $f(x)$ is undefined ...
12
votes
1answer
125 views

What do you get with this equivalence relationship for all $\mathbb{Q}$ sequences

Consider all $\mathbb{Q}$ Cauchy sequences with this equivalence relationship $\{x_n\} \sim \{y_n\} \iff \{x_n-y_n\} \rightarrow 0$ Then you get all real numbers as an equivalence class with this ...
11
votes
4answers
5k 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 ...
11
votes
5answers
1k views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
10
votes
1answer
130 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 ...
9
votes
3answers
6k views

why is frobenius norm of a matrix greater than or equal to the 2 norm?

How can you prove that: $$\|A\|_2 \le \|A\|_F$$ I cannot use: $$\|A\|_2^2 = \lambda_{max}(A^TA)$$ It makes sense that the 2-norm would be less than or equal to the frobenius norm but I dont know how ...
9
votes
1answer
662 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 ...
8
votes
3answers
223 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
4answers
358 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 x_1+y_1=x_2+...
8
votes
1answer
189 views

When is the topological 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 ...
7
votes
4answers
1k 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
1answer
856 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 ...
7
votes
2answers
180 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
168 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 X/_\...
6
votes
1answer
129 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 ...
6
votes
3answers
102 views

Quotient of a graph?

I want to understand quotient of a graph (also called quotient graph), my teacher says that the terms quotient of a graph and a modulo of a graph should be synonyms (even though modulo of a graph ...
6
votes
1answer
291 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
210 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
13k 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: {$(a,a)(a,b)(a,c)(a,d)(b,a)(b,...
5
votes
3answers
6k 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 ...
5
votes
3answers
3k 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
3answers
8k 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 \...
5
votes
4answers
495 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
2answers
2k views

What is the standard notation for a set of equivalence classes?

What is the standard notation for a set of equivalence relations? Specifically, I have a pair of objects, call them $x$ and $y$ and I denote the ordered pair as $\left(x,y\right)$. I have a set of ...
5
votes
1answer
145 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
154 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
2answers
178 views

Why are equivalence classes called “classes” and not “sets”?

Why are equivalence classes called so and not equivalence sets? I am kind of not able to find the difference between a class and a set. What properties that a set have that a class cannot have? It ...
5
votes
1answer
97 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 ...
5
votes
2answers
127 views

When is $(a+b)^n \equiv a^n+b^n$?

I remember a relation like $(a+b)^n \equiv a^n+b^n$, but I don't remember mod which numbers this is true. Where can I learn more about this?
5
votes
2answers
102 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 ...
5
votes
1answer
297 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
2answers
4k views

Definition of “quotient set”

I search and search about quotient set and cannot figure out what it is. At the beginning, I thought it was the same as partitions, but now I'm confused. Can someone show some examples and explain?
5
votes
3answers
644 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
2answers
53 views

For a set of symmetric matrices $A_i$ of order p, show that if the sum of their ranks is p, $A_iA_j=0$

Here's what I know. Matrices $A_i$ for $i=1,...,k$ are all symmetric p by p matrices. $\sum\limits_{i=1}^k A_i = I_p$ where $I_p$ is the p by p identity matrix $\sum\limits_{i=1}^k rank(A_i) = p$ ...
5
votes
1answer
81 views

Cardinality of equivalence relations in $\mathbb{N}$

I came across this long proof on this site: Cardinality of relations set But I would like to know whether my direction can work. Say we want to find the cardinality of all equivalence relations in $...
5
votes
2answers
51 views

Prove that $(H,\circ)$ is a subgroup of the group $(G, \circ)$

Question: Let $(G, \circ)$ be a group and $H$ be a non-empty subset of $G$. A relation $\rho$ defined on $G$ by $$a\,\rho\ b\quad \text{if and only if}\quad a\circ b^{-1}\in H$$ for $a,b\in G$, is an ...
5
votes
1answer
113 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
852 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
482 views

Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and couldn'...
4
votes
3answers
479 views

Why is one relation transitive but the other is not?

From what I have read about a transitive relation is that if xRy and yRz are both true then xRz has to be true. I'm doing some practice problems and I'm a little confused with identifying a ...
4
votes
4answers
123 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 ...
4
votes
4answers
3k 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 $\mathbb{...
4
votes
2answers
502 views

The fibres of a map form a partition of the domain.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post. This problem is from ...
4
votes
3answers
188 views

What's the name for the equivalence induced by a function on its domain?

Any function $f$ with domain $X$ induces an equivalence relation on $X$, with classes $$\{f^{-1}(\{y\})\,:\, y \in \operatorname{im}f\;\} .$$ Is there a name for this equivalence? Thanks!
4
votes
2answers
132 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
199 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 how ...
4
votes
4answers
130 views

About proving that $Aut(\mathbb{Z}_n)\simeq \mathbb{Z}_n^\times$.

I need to prove that $$ Aut(\mathbb{Z}_n) \simeq \mathbb{Z}_n^\times. $$ My definition of $\mathbb{Z}_n$ is that $$ \mathbb{Z}_n =\{\bar{m}: m\in \mathbb{Z}\} $$ where $\bar{m}$ is the equivalence ...
4
votes
1answer
38 views

Are there any distinct $a, b$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime?

Are there any distinct $a, b \in \mathbb{N}$ s.t. $a + x$ prime $\Longleftrightarrow$ $b + x$ prime for all $x \in \mathbb{N_0}$? I can show there are no coprime $a,b$ using Dirichlet's theorem: ...
4
votes
4answers
891 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
358 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 ...