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

learn more… | top users | synonyms

1
vote
0answers
44 views

Showing properties of equivalence relation

I just started my abstract algebra class and I am struggling with the concept of equivalence relations. I know that in order to prove equivalence relations, I have to prove the reflexive, symmetric, ...
0
votes
1answer
92 views

Vector Spaces: difference between Equivalence Classes and Quotient Spaces

I'm reading Herstein's Topics in Algebra and Halmos's Finite Dimensional Vector Spaces. I think I understand that if $V_F$ is a vector space over $F$ and $W$ a subspace of $V$, then there is an ...
1
vote
0answers
55 views

Equivalence Relations with equivalence classes

Consider the following relation on $\mathbb{Z} \times \mathbb{Z}$: $(x, y)\sim (x', y')$ iff $xy' = x'y$. (a) Prove that it is an equivalence relation. (b) Consider the set of equivalence classes ...
1
vote
1answer
39 views

Proof of a equivalence relation

A set $A$ is equipotent to a set $B$ $(A\sim B)$, if a bijection $f: A \rightarrow B$ exists. How to prove, that $\sim$ is a equivalence relation? EDIT: I understand the concept of reflexivity, ...
2
votes
3answers
73 views

Trouble understanding equivalence relations and equivalence classes

I've read up a bit on equivalence relations and equivalence classes, but I'm a bit unsure on the whole concept. From what I've read and equivalence relation, ~, between two mathematical objects $a$ ...
3
votes
4answers
392 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 ...
-1
votes
1answer
10 views

For a preorder $R$ on a set $A$, show that $S=R \cap R^{-1}$ is an equivalence relation on $A$

Let $R$ be a preorder on a set $A$, and let $S$ be the intersection of $R$ and $R^{-1}$ (the relational inverse of $R$). Show that $S$ is an equivalence relation on $A$.
0
votes
1answer
23 views

Equivalence relation - Equilavence classes explanation

I have the following equivalence relation problem. $Let \ R\subseteq 2^S*2^S = \{(A,B):|A\cap T|=|B \cap T|\}\ where\ S=\{0,1,2\} \ and \ T=\{1,2\} \ Show \ that \ R \ is \ a \ equivalence \ ...
1
vote
2answers
915 views

Difference between Reflexive and Symmetric in Discrete Maths

Difference between Reflexive and Symmetric in Discrete Maths? This is what I understand: Reflexive -> <a,a=a>, <b,b=b> uses ...
0
votes
1answer
59 views

How to show the simple equivalence?

I come across the following equivalence of integrations: $$\int\left[-I \left(h\right){\partial h \over \partial \tau}+{\partial h \over \partial x}{\partial \over \partial \tau} \left({\partial h ...
0
votes
1answer
25 views

Determine if “$n \sim m$ iff $nm>0$” is an equivalence relation on $\Bbb Z$

Determine whether the given relation is an equivalence relation on the set. $n$ is related to $m$ in the set of integers if $nm>0$. So my teacher said this set is not an ...
0
votes
2answers
34 views

How many equivalence relations over $\mathcal P(\mathbb N)$ satisfy: $[\{8\}]_S=\{A\in \mathcal P(\mathbb N)|A\neq \{1\}\wedge A\neq \{2\}\}$

How many equivalence relations $S$ over $\mathcal P(\mathbb N)$ satisfy: $$[\{8\}]_S=\{A\in \mathcal P(\mathbb N)\mid A\neq \{1\}\wedge A\neq \{2\}\}$$ Just to make sure I understand, the ...
2
votes
1answer
83 views

Using first order sentences, axiomize the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes.

Problem Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes. Current Solution ...
1
vote
1answer
20 views

Is it possible for a relation to be transitive and symmetric but not reflexive with only one element?

E.g. On the set $A = \{1,2,3,4,5,6\}$, is the relation set $R = \{(1,1)\}$ a transitive and symmetric relation but not reflexive?
0
votes
1answer
27 views

Proving $|S/R^2|=\aleph$ , $(x_1,x_2)S(y_1,y_2)\iff x_1^2-x_2=y^2_1-y_2$

Let $S$ be an equivalence relation over $\mathbb R^2$ such that: $(x_1,x_2)S(y_1,y_2)\iff x_1^2-x_2=y^2_1-y_2$ Prove that $|S/R^2|=\aleph$ One side is pretty simple: $|S/R^2|\le |\mathbb ...
0
votes
1answer
76 views

Discrete Math dealing with Partition of Ordered Pairs. [closed]

Given the partition $\{a,b,c\}$ and $\{d,e\},\,$ of the set $S=\{a,b,c,d,e\},\,$ list the ordered pairs in the corresponding equivalence relation. How can I determine which elements are related to ...
0
votes
1answer
35 views

equivalence relation - checking

At $\mathcal P(\mathbb{Z})$ we define equivalence relation $\equiv$ : $A \equiv B \iff (A=B \vee (A \cup B)\cap\mathbb{N}=\emptyset)$ a)show that $\equiv$ is a equivalence relation at $\mathcal ...
0
votes
1answer
35 views

Equivalence Relation of Dice

Suppose you are rolling two dice, one red and one white. Two rolls of the dice are considered equivalent if the dice sum to the same number. The dice are six sided. a) Give the partition induced by ...
1
vote
1answer
49 views

How to find a representative of an equivalence relation on $\omega\times\omega$

In one of my exercises we are shown that the relation "$\sim$" is defined as the following: $$\langle n,m \rangle \sim \langle k,l \rangle \iff |(n\setminus m)| = |(k\setminus l)|$$ in which $|X|$ ...
2
votes
1answer
77 views

If $X,Y$ are equivalence relations, so is $X \times Y$

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
2
votes
1answer
72 views

Equivalence relation: cardinality of quotient set

At $A=\mathbb{Z}^{\mathbb{N}}$ we define equivalence relation $\equiv$ by: $$f\equiv g \iff \forall n\in \mathbb{N} ((f(2n)=g(2n)) \wedge(f(n)\cdot g(n)> 0 \ \vee f(n)=g(n)=0)) $$ a) ...
1
vote
0answers
27 views

equivalence relation problem - checking

We define eqiuvalence relation $\equiv$ at set $P(\mathbb{Z})$ as follow: $A \equiv B \iff |A \setminus \mathbb{N}| = |B \setminus\mathbb{N}|$ a)find equivalence class for $\emptyset$ b)find ...
2
votes
2answers
44 views

For what $z\in\mathbb{N}$ is “$x\equiv y\iff xyz$ is a square” an equivalence relation?

Consider the set $\mathbb{N}\cup\{0\}$ and fix $z\in \mathbb{N}\setminus\{0\}$. Define the relation $x \equiv y \iff xyz$ is a square number. I am trying to verify that this is an equivalence ...
0
votes
1answer
45 views

Proving something is an equivalence relation

Problem: For two subsets $A$ and $B$ of some set $X$, we define \begin{align*} A \triangle B = (A \cup B) \setminus (A \cap B). \end{align*} We now define a relation $R$ on $P(X)$ (power set of $X$) ...
0
votes
1answer
23 views

Equivalence Classes and Relations of Hexagons

Suppose there is a hexagon in the plane. Consider two colorings of the edges of the hexagon equivalent if you can rotate the hexagon so that edges of the same color map to each other. Suppose you ...
1
vote
3answers
31 views

Prove a relation using an equivalence relation

Prove the relation define on $\mathbb{R} \!\,^2$ by $$(x_1,y_1) \sim(x_2,y_2) \Leftrightarrow x_1^2+y_1^2=x_2^2+y_2^2$$ is an equivalence relation Ok, so I know what an equivalence relation is. It ...
1
vote
1answer
76 views

Functions that preserve equivalence relations

Quick question: Let $X$ and $Y$ bet two sets and $\sim$ an equivalence relation on $X$. I was wondering what it means to say that a function $f$: $X\to Y$ 'preserves' $\sim$ in this case. Does it ...
0
votes
1answer
26 views

how many reflexive relations but not equivalence, are in a set with 4 elements?

I know that for reflexive relations on a set with n elements the formula is: $2^{(n^2-n)}$ So for a set with $4$ elements: $2^{(4^2-4)}$ = $2^{12}$ But I don't know how to find the relations that ...
0
votes
0answers
53 views

Why relation “parallel” on the set of lines in a plane not transitive?

My book says relation "parallel" on the set of lines in the plane not transitive. And the definition in the book given is : A relation $R$ on a set $A$ is transitive if whenever $aRb$ and $bRc$ ...
0
votes
2answers
27 views

Equivalence Relations and 1-1 Correspondences

I have an engineering instructor who has claimed that "equivalence relations and one-to-one correspondences are pretty much the same thing". However, I believe the answers to both of the following ...
1
vote
1answer
44 views

Finding the relation between on set of natural numbers?

Each case below gives a relation on the set of all nonempty subsets of the natural numbers. Determine whether the relation is transitive,symmetric, or reflexive. Case 1: $R$ is defined by $ARB$ if ...
-1
votes
1answer
34 views

Equivalence Classes with 1 or 2 elements?

Let ~ be the relation on R defined by a ~ b if and only if |a| = |b|: (a) Prove that is an equivalence relation. (b) Give an example of an equivalence class with two elements. (c) Give an example ...
2
votes
3answers
33 views

Not a precise question on equivalence class.

Consider $f:X\longrightarrow Y$. Define a relation $\sim$ on $X$ by $a\sim b$ iff $f(a)=f(b)$. I proved that $\sim$ is an equivalence relation and that if $f$ is onto and $X/\sim$ is the set of ...
2
votes
1answer
27 views

Equivalence class of $(x_1,y_1)\sim(x_2,y_2)$ iff $ x_1=x_2$

I proved that $x\sim y$ iff $x-y\in \mathbb Z$ is an equivalence relation on $\mathbb R$. I'd like to know if $[x]=\{x+n:n\in\mathbb Z\}$ is an equivalence class for every $x\in \mathbb R$ (if it is ...
0
votes
1answer
12 views

Equality: transitive property

Is the following relation a valid example for the transitive property of equality? If not, what is/are the name(s) of the property/ies involved? Given A, B, C, D. Given A = B, A = C, B = D. Then C ...
0
votes
0answers
55 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
3answers
86 views

What’s wrong with this proof that $5$ is prime?

I’m reading How To Prove It and I’m confused as to how the proof of “$x$ is prime” is correct. I've written proof given below and also my conclusion after substituting in values for $x$, $y$ and $z$: ...
2
votes
2answers
71 views

Mathematical Relations in Computing - Unary

I have this question that's bugging my mind: "Discuss by giving suitable examples the role of mathematical relations (Unary, binary and ternary) in computing." I'm sure it's a very simple question, ...
2
votes
1answer
49 views

Number of equivalence classes of binary sequences which differ only by finitely many elements.

This question rose up when i was reading a problem the author used to argue against the axiom of choice. Consider the set of all (infinite) sequences of 0's and 1's. Q1) How many such sequences are ...
1
vote
1answer
51 views

Is $R = \{ (x, y) \in \mathbb{R} \times \mathbb{R} \mid x - y \in \mathbb{N}\}$ an equivalence relation?

Note: I am also trying to answer my own question, but I am not sure if it is correct, please correct it, if it's wrong. Thanks :) I have an exercise where I have to say if a relation $R$ is or not an ...
0
votes
2answers
40 views

Pass from partition to the equivalence relations

I have a set $A = \{ 1, 2, 3\}$, which possible partitions are: $P_0 = \{ \{1, 2, 3 \} \}$ $P_1 = \{ \{1, 2 \}, \{3 \} \}$ $P_2 = \{ \{1 \}, \{2, 3 \} \}$ $P_3 = \{ \{1, 3 \}, \{2 \} \}$ $P_4 = ...
0
votes
2answers
122 views

Every equivalence relation on $\mathbb{Z}$ that is compatible with the addition structure is either the identity or the relation $\equiv \pmod{n}$

Let $R$ be an equivalence relation on $\mathbb{Z}$ such that the operation on the quotient set $\mathbb{Z}/R$ given by the rule $[x]_R + [y]_R = [x+y]_R$ is well-defined. Show that $R$ must either be ...
1
vote
3answers
312 views

Prove $(x, y)R(s, t)$ iff $2(x - s) = (y - t)$ defines an equivalence relation

Define the relation $R$ on the set of all ordered pairs of real numbers as follows: $(x, y)R(s, t)$ iff $2(x - s) = (y - t)$. Prove that $R$ is an equivalence relation. Find the ...
4
votes
4answers
705 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 ...
0
votes
3answers
132 views

Prove $a R b$ iff $a \equiv b \pmod 2$ and $a \equiv b \pmod 3$ is an equivalence relation

In the set $\mathbb{Z}$ we describe the relation: $a\mathrel{R}b \Leftrightarrow a\equiv b\pmod2 \text{ and } a\equiv b\pmod3$ Prove that $R$ is an equivalence relation. Describe ...
3
votes
2answers
158 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 ...
1
vote
1answer
180 views

Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
1
vote
3answers
90 views

Proof that $(a, b) \mathrel{R} (c, d)$ iff $ad = bc$ is an equivalence relation

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...
3
votes
2answers
207 views

Proving that $4 \mid m - n$ is an equivalence relation on $\mathbb{Z}$

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: ...
0
votes
1answer
58 views

Basic group algebra exercise

I'm working on this abstract algebra problem that was given as homework to me, I'm in my first year of university and have a semester's background in basic abstract algebra. Here is the problem: Let ...