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

learn more… | top users | synonyms

0
votes
1answer
23 views

Equivalence Relation Proof Question [duplicate]

Let $R$ be the relation on $N\times (N\setminus\{0\})$ defined by $((a, b),(c, d)) \in R$ if $ad = bc$. Prove that $R$ is an equivalence relation. I'm pretty confused with this problem, mainly ...
0
votes
2answers
26 views

If a relation is built with $=$, is the relation always an equivalence relation?

$R \subset \Bbb R \times \Bbb R$ I have now encountered a couple of relations that have the following form: $$R=\{(a,b)\in \Bbb R\times \Bbb R\,:\,a^2 = b^2\}$$ They seem to be always equivalence ...
-1
votes
1answer
42 views

Is $R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,(a - b)$ is an odd number $ \}$ an equivalence relation?

$R \subset \Bbb N \times \Bbb N$ Is this an equivalence relation? $R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,(a - b)$ is an odd number $ \}$ I say it is not because $(a, a)$ is always $0$ which is ...
3
votes
2answers
44 views

Is the relation $R$ on $\Bbb N$ given by $(a,b)\in R\iff a\mid b$ an equivalence relation?

$R \subset \Bbb N \times \Bbb N$ Is this an equivalence relation? $$R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,a\mid b\}$$ I would argue that it is reflexive because $a\mid a$, but it is not symmetric ...
0
votes
1answer
32 views

Why do we quotient only by equivalence relations?

In textbooks, I've always seen the notion of quotient set defined with equivalence relations, that is: if $R$ is an equivalence relation on a set $X$, we can define the quotient set $X/R = \{[x]_R \...
1
vote
1answer
24 views

Why study graph representations of equivalence relations?

What is the importance of representing a (an equivalence) relation using digraphs? Is there any geometric aspect to study relations using graphs (of vertices and edges)?
1
vote
2answers
43 views

Suppose X~Y, Prove that P(X) ~ P(Y)

My attempt: I imagined that if two sets are equivalent there would exist $ f:X→Y$ that is bijective. If I conceptually create P(X) and apply the function defined for the first equivalence relation to ...
-2
votes
3answers
87 views

Proving why $\Bbb Z_{4} \rightarrow \Bbb Z_{6} \text{ given by } f(\overline x) = [2x+1] $ is not a function. [duplicate]

Question presented: Is following a function from the indicated domain to the indicated co domain? $f:\Bbb Z_{4} \rightarrow \Bbb Z_{6} \text{ given by }$ $ \bbox[white,1px,border:1px solid red]{...
3
votes
7answers
257 views

The map $f:\mathbb{Z}_3 \to \mathbb{Z}_6$ given by $f(x + 3\mathbb{Z}) = x + 6\mathbb{Z}$ is not well-defined

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is not a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ ...
1
vote
3answers
36 views

Trouble proving that this is a function?

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ given ...
0
votes
2answers
59 views

Discrete mathematics, equivalence relations, functions.

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking) Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on $A$...
5
votes
4answers
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 $...
0
votes
2answers
23 views

Mapping of equivalence classes of integers modulo $n$

This is an exercise problem from Essentials of Discrete Mathematics (3rd Edition) by David J. Hunter. The problem is as follows: Consider the function $p : \mathbb{Z} \rightarrow \mathbb{Z}/n$ ...
2
votes
2answers
22 views

Proving that R is a partial Order.

Define the relation $\Bbb R \times \Bbb R$ by $(a,b) \; R$ $ (x,y)$ iff $a \le x$ and $b \le y$ , prove that R is a partial ordering for $\Bbb R\times\Bbb R $ . A partial order is if R is reflexive ...
0
votes
1answer
43 views

Describe the equivalence relation of the following set with the given partition.

Describe the equivalence relation of the following set with the given partition. $ \Bbb N $ , $ \{\{ 1 \}, \{2,3 \}, \{4,5,6,7\},\{8,9,10,11,12,13,14,15\}....\} . $ What this question has me ...
1
vote
2answers
18 views

Checking reflexive, symmetric and transitive properties of $\neq$ on $\mathbb{N}$

QS: Indicate if the relation on the given set are reflexive on a given set, which are symmetric, and which are transitive. $\not = \text{on } \Bbb N$ So for this problem I am trying to ...
1
vote
1answer
27 views

Proving that R is an Equivalence Relation.

Consider the relations R and S on $\Bbb N$ defined by $x\; R\; y$ iff $2 \;$divides $x + y$ and $x \;S \;y$ iff $3$ divides $x + y.$ $\text{QN: Prove that $R$ is an equivalence Relation }...
2
votes
2answers
25 views

Proving that S is not an equivalence relation.

Consider the relations R and S on $\Bbb N$ defined by $x\; R\; y$ iff $2 \;$divides $x + y$ and $x \;S \;y$ iff $3$ divides $x + y.$ $\text{QN: Prove that S is not an equivalence ...
0
votes
1answer
37 views

How to prove equivalence of different definitions for compactness?

My workbook considers three different definitions for compactness in logic. It says that it can be shown that these are equivalent, but what would be a strategy to show this? I'm familiar with showing ...
6
votes
3answers
4k views

Definition of “quotient set”

I searched and searched 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?...
42
votes
4answers
6k views

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
0
votes
0answers
21 views

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation Reflexivity: Obviously it is not Reflexive since $x=\sqrt{2}$ and $y=\sqrt{2}$ and $\...
-2
votes
0answers
34 views

Symmetric difference with Identity relation - equivalence relation?

I have the following question and could not find any contradiction.. Let R,S be an equivalence relations on a set A. Determine if $(R\Delta S)∪I_A$ an equivalence relation on set A. ...
1
vote
1answer
52 views

Circles and generic implicit functions

I have some problems understanding circles. $x^2+y^2 = 1$ is a circle. It defines equivalence class where all (x,y) points belonging to the circle are in the same equivalence class. $(\cos a, \sin a)$...
3
votes
2answers
50 views

Can a simple (atomic) proposition be a tautology?

Definition: "A tautology is a propositional formula that is true under any truth assignment to each of the atomic propositions in the domain of propositional function." Let $p$ be a simple (or atomic)...
1
vote
1answer
19 views

Proportionality between two quantities

Its known that if one variable is proportional to two others than it is also proportional to their product. $$\forall a,b,c\in ℝ:a\propto b\wedge a\propto c\Rightarrow a\propto b\cdot c$$ I think i`ve ...
0
votes
1answer
33 views

Prove that this is an Equivalence Relation.

Then give information about the equivalence classes as specified for The relation $R$ on $ℝ$ given by $xRy$ iff $x-y∈ℚ$. Give the equivalence class of $0$; of $1$ ; $\sqrt{2}$. First In order to ...
0
votes
0answers
16 views

Induced operation and anticommutativity

Let $\odot$ and $\circledast$ be operations on X and Y. Let $f:X\to Y$ satisfy $f(r_x)=r_y,\ f(x\circledast y)=f(x)\odot f(y),\ x,y\in X$. Prove: $\ x\sim y:\Leftrightarrow f(x\circledast y)=r_y \...
2
votes
1answer
42 views

Describe the equivalence classes generated by T

Suppose $S = \{(x,y) \in \mathbb{R}^2\mid y = x + 1\text{ and } 0 < x < 2\}$. Question Describe the equivalence relation T on the real line that is the intersection of all equivalence ...
0
votes
1answer
29 views

Is $R$ an equivalence relation?

Let $X,Y$ be infinite sets. Define $F$ as $F=\{f:X\rightarrow Y\}$ . We define a binary relation $R$ on $F$: $fRg$ if there is no countable $S\subseteq X$ such that $\forall x\in S \ f(x)\neq g(x)$. ...
0
votes
1answer
88 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
1
vote
1answer
30 views

Number of distinct equivalence classes of $\mathbb Z_n$ of the “ associate ” equivalence relation

Define an equivalence relation on $\mathbb Z_n$ as : For $a,b \in \mathbb Z_n $ , $a\sim b$ iff $\exists k \in U_n=\mathbb Z_n^{\times}$ such that $a=kb$ (i.e. $a,b$ are related if they are "...
2
votes
1answer
38 views

Prove that $R\cap S$ is symmetric, transitive, and anti-symmetric.

If you can confirm these are done correctly or offer another way to do so I would greatly appreciate it. Also how would you go about proving $R\cap S$ is reflexive? What assumption if any would be ...
1
vote
0answers
14 views

Word for equivalence preserving transformations of equations

I am searching for a mathematical term describing an algebraic manipulation of an equation which preserves equivalence. So while adding $2$ to both sides of an equation results in an equivalent ...
0
votes
1answer
19 views

Proving $g(x) = E_x$.

I'm pretty new to mathematical proof and set theory and I'm having trouble proving this problem. I've started on it, but I don't know where to progress. Problem: Suppose that $f: A \rightarrow B$. ...
0
votes
2answers
56 views

Equivalence relations and commutative diagrams

Let $\sim$ and $\dot\sim$ be equivanlence relations on the sets X and Y respectively. Suppose $f \in Y^X$ is such that $x \sim y$ implies $f(x) \dot\sim f(y)$ for all $x,y \in X$. Prove that there is ...
0
votes
0answers
19 views

How can i prove this equivalence relation problem when R isn't defined?

Problem: Prove that if $R\subset A\times A$, and $R\circ R^{-1}\circ R=R$. Then $R^{-1}\circ R$ is a equivalence relation. in $D(R)$ I have nowhere to take the properties i need from... what do I do? ...
1
vote
1answer
23 views

How can i prove that if $x_0$ is a solution then $[x_0]$ is unique?

$4x\equiv10\pmod6$ I'm not sure what they asking when they say that the equivalence relation of a solution is unique. Also I was able to find the solution -5 with euclids algorithm, is there a more ...
6
votes
3answers
109 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 ...
3
votes
2answers
57 views

We Quotient an algebraic structure to generate equivalence classes?

Till now I visualized Quotient groups as a technique to generate equivalence classes whenever needed, as in $\mathbb{Z}/n\mathbb{Z}$. But now I have a feeling of doubt since I haven't seen a book that ...
1
vote
2answers
31 views

infinite equivalence classes

How would you prove that this relation $$(a,b)R(c,d)$$ if and only if $$a+d=b+c$$ has infinite equivalence classes if it is defined in a set with only non negative integers? I've already proved that ...
0
votes
0answers
22 views

Show that $E / \sim $ is an affine space over $V/U$

Let $E$ be an affine space over the vector space $V$, and let $U \subseteq V$ be a vector subspace. We define the equivalence relation $$P \sim Q := \exists v \in U \text{ such that } P = Q + v$$ on $...
0
votes
1answer
33 views

what is the complete set of representatives of an equivalence class?

I have been researching the topic, but I can't find anything that explains specifically and in detail what it is. I just find a bunch of exercises about the topic.
0
votes
1answer
22 views

Proof about set of representatives

Let $X = \left\{(m, n)\in \mathbb{Z}\times\mathbb{Z}, n \neq 0\right\}$. Define a relation $\sim$ on $X$ by $(k, l) \sim (m, n)$ if $kn = lm$. Prove that $\left\{(m, n)|m \in \mathbb{Z}, n \in \...
-1
votes
1answer
36 views

Proof the existence of a certain bilinear form on the vector space V/T

Let $\mathbf V$ be a vector space (over a field $\mathbf K$) together with a symmetric bilinear form <-,->, and let $\mathbf T $ $\subseteq$ $\mathbf V$ be the orthogonal complement (since I'm not ...
0
votes
0answers
18 views

Differentiating between equivalence relations and partitions

What is the purpose of defining equivalence relations and partitions separately when they are the same? Are they used for different purposes?
0
votes
1answer
44 views

Prove that $\mathbb{|Q|} = \mathbb{|Q \times Q|} $ [duplicate]

This question exists, but both cases have a specific answer for the OP's situation. I do not know how to prove that $\mathbb{Q}$ is countable. Questions I am referring to: Prove that $\mathbb{|Q| = |...
2
votes
1answer
43 views

An uncountable chain of equivalence relations

First, an example: We know that, for two real valued, Lebesgue-integrable functions, the relation "equals almost everywhere" is an equivalence relation. In particular, if $f_0$ is Lebesgue-integrable, ...
0
votes
1answer
26 views

Equivalence relations proof example?

Let $A$ = {$a,b,c$}. Give an example of a relation on $A$ that is anti-symmetric, reflexive on $A$ and symmetric. The first thing that one must do to proceed with this question is to first define ...
1
vote
1answer
27 views

Fewest number of possible ordered pairs in a relation

There are many different equivalence relation possible on the set $A = \{a, b, c, d\}.$ For example, here are just two different ones: (a) $E_1 = \{(a, a), (b, b), (c, c), (d, d), (a, c), (c, a), (b, ...