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

learn more… | top users | synonyms

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 \ ...
3
votes
4answers
393 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 ...
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
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 ...
0
votes
1answer
29 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 ...
2
votes
1answer
84 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
36 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|$ ...
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 ...
3
votes
2answers
45 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 ...
2
votes
1answer
74 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) ...
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 ...
0
votes
1answer
47 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$) ...
1
vote
1answer
78 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
29 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
56 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
36 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 ...
0
votes
1answer
79 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 ...
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
13 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
61 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
1answer
54 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
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 ...
0
votes
2answers
17 views

Equivalence relations-Discrete Math

Here is an equivalence relation R={ (x,y) | x-y is an integer} My question is: what is the equivalence class of 1 for this equivalence relation? Can say indicate the equivalence class of 1 as ...
1
vote
2answers
47 views

Corresponding partition in equivalence relation

The relation $R$ on the set $A=\{2,4,6,8,10\}$ is defined by $$R=\{(2,2),(2,6),(2,10),(4,4),(4,8),(6,2),(6,6),(6,10),(8,4),(8,8),(10,2),(10,6),(10,10)\}$$ Question 1 Verify if $R$ is an ...
2
votes
2answers
75 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, ...
0
votes
1answer
32 views

How to deal with equivalence relations and equivalence classes

I have the following relation $m^3=n^3$ on $\mathbb{Z}$. I know how to show that it is an equivalence relation but I am facing a problem in finding the equivalence classes can u help me please?
-1
votes
3answers
209 views

When can we modify $a \propto \ b$ adding $\delta $?

This is a general, theoretical question about formalization of concepts, it is difficult for me to explain it adequately, please, if I fail, tell me in a comment what is not clear or feel free to edit ...
5
votes
2answers
127 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?
3
votes
2answers
261 views

An example in the fundamental theorem of equivalence relations?

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there ...
0
votes
1answer
24 views

If $\alpha\in X/R$ is an equivalence class, then $F:X/R\to Y$ defined by $F(\alpha)=f(a)$, is well-defined, 1-1 and onto.

Let $f:X\to Y$ be a surjection. Let $R$ be the subset of $X\times X$ consisting of those pairs $(x,x')$ such that $f(x)=f(x')$. Then $R$ is an equivalence relation. Let $\pi:X\to X/R$ be the ...
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 ...
1
vote
0answers
80 views

Prove $X\times Y$ is an equivalence relation [duplicate]

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in ...
1
vote
1answer
35 views

Proving projection map is onto

Let $X$ be a nonempty set and let $R$ be an equivalence relation on $X.$ Given $X/R={[a]:a \in X}$. Prove that there is a map called the projection where $p_x:X\to X/R$ given by $p_x(t)=[t].$ Then ...
1
vote
2answers
44 views

Orbits in G = $Z_6$ by listing 2 element subsets in G.

1) Let $G = \mathbb{Z}_6$. List all 2-element subsets of $G$, and show that under the regular action of G (by left addition) there are 3 orbits, 2 of length 6, one of length 3. Deduce that the ...
1
vote
1answer
35 views

How to show that the following relation is not an equivalence relation?

We have the relation $\sim$ in $\mathbb{R}^n$: $x\sim y \leftrightarrow d(x,y)\in \mathbb{Q}$, where $d(x,y)=\sqrt{\sum^n_{i=1}(x_i-y_i)^2}$. How do you prove that this isn't an equivalence relation ...
0
votes
1answer
29 views

Having trouble proving transitivity

We have a universal set of lowercase alphabet letters, $U = \{a, b, ... , z\}$ . For sets $A,B \subseteq U$ we can define a relation, $A \sim B$ as long as the number of elements that are in either ...
1
vote
2answers
41 views

How to prove $S=\{(x,y) \in \mathbb{R}\times \mathbb{R}|x - y \in \mathbb{Q} \}$ is an equivalence relation?

I am really stuck with this problem, and I cannot come out with a solution. I know that to prove a relation is an equivalence relation we have to prove that it's reflexive, symmetric and transitive, ...
0
votes
2answers
74 views

How many elements are there in the set R?

+Let A be a finite set with $n \geq 4$ elements and let R be an equivalence relation on A . Suppose that there are exactly $n-2$ equivalence classes and that no equivalence class can contain exactly ...
0
votes
1answer
159 views

How to prove the Cone is contractible?

Let $\sim$ be an equivalence relation on a topological space $X$ with a subset $A ⊂ X$ such that the equivalence classes are: $A$ itself and Singletons $\{x\}$ such that $x ∉ A$. Then define $X/A$ ...