This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

4
votes
5answers
5k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
26
votes
3answers
2k 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$ ...
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 ...
1
vote
2answers
2k views

Proving this relation is transitive

Let $r$ be a relation on $A \times A$ such that $(a,b) r (c,d) \iff ad = bc.$ How can I show that this relation is transitive, ie. $(a, b)r(c,d)$ and $(c,d)r(e, f) \implies (a,b)r(e,f)$? I tried to ...
1
vote
1answer
80 views

Equivalence relation question with cardinality and countability $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $

Let $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $ What is the cardinality of $[\pi]_S$ ? Prove that the quotient group $\mathbb R/S$ is uncountable. Well I think that cardinality is ...
1
vote
0answers
111 views

Example relations: pairwise versus mutual

There are by now several questions on math.se asking about pairwise versus mutual relations, eg: • When does “pairwise” strengthen and when does it weaken? • Relation: pairwise and mutually • ...
6
votes
2answers
2k views

If a relation is symmetric and transitive, will it be reflexive? [duplicate]

Possible Duplicate: Why isn't reflexivity redundant in the definition of equivalence relation? We had a heated discussion in class today and i still cant be sure if the professor was ...
2
votes
2answers
357 views

Distinguishing equality and isomorphism as relations

Is this relational characterization of equality in Wikipedia accepted? The identity relation is the archetype of the more general concept of an equivalence relation on a set: those binary ...
0
votes
3answers
189 views

Two questions about equivalence relations

Question 1: Let $x,y \in S$ such that $x\sim y$ if $x^2 =y^2\pmod6 $. Show that $\sim$ is an equivalence relation. This is what I tried: Reflexive: $x^2\pmod6 = x^2$ implying $x\sim x$ ...
12
votes
2answers
330 views

When does “pairwise” strengthen and when does it weaken?

"Pairwise disjoint" is stronger than "disjoint"; it sometimes happens that $\displaystyle\bigcap\limits_{i\in I} A_i=\varnothing$ but for every $i,j$, or at least for some, one has $A_i \cap ...
0
votes
1answer
48 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
7
votes
1answer
213 views

Can we extend the definition of a homomorphism to binary relations?

This is going to be quite a long post. The actual questions will be at the end of it in section "Questions." INTRODUCTION After receiving an answer to this question about extending the definition of ...
4
votes
2answers
88 views

Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
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 ...
4
votes
2answers
125 views

$<$ in a preorder

The author of the book I am studying defines $<$ for a poset as If $x, y \in X$, where $X$ is a poset, then we shall write $x < y$ to mean that $x \le y$ and $x \ne y$. From this, I can ...
3
votes
0answers
45 views

A relation on 2 countable sets [duplicate]

Let $R$ be a relation on two countable sets $A$ and $B$, where $R\subset A\times B$, with the following properties: $\forall a\in A$ the set $\{b\in B: (a,b)\in R\}$ is finite. For any finite set ...
3
votes
3answers
172 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!
3
votes
1answer
159 views

Relation: pairwise and mutually

Suppose we can define a relation $R$ over the sets $X_1, …, X_k$ for any natural number $k$, note not specified for a particular $k$. I was wondering if there is some definition or conditions ...
2
votes
3answers
2k 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 ...
2
votes
2answers
4k views

Transitive Relation

$$\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}$$ This is a matrix representation of a relation on the set $\{1, 2, 3\}$. I have to determine if this relation matrix is ...
2
votes
2answers
357 views

Proof of a Proposition on Partitions and Equivalence Classes

I stumbled upon a seemingly rudimentary proposition that I am having trouble writing out a proof for. The proposition goes something like, Proposition: If $\{A_i|i\in I\}$ is a partition of ...
1
vote
2answers
58 views

Transitive, symmetric $R$ such that for all $x$, there is $y$ such that $xRy$, is an equivalence relation

I'm stuck at one particular task I'm working on. Here is the task: Let R be a transitive and symmetrical relation on $S$. Assume that for all $x \in S$ there is a $y \in S$ so that $xRy$. ...
1
vote
1answer
105 views

relations - examples and counterexamples

The question is to find an example of a set $S$ and three relations $R_1$, $R_2$, and $R_3$ on it, such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is ...
1
vote
2answers
218 views

Is this alternative definition of 'equivalence relation' correct?

I was puzzling over another question: Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$. And this made me discover that $$(0) \; \langle \forall a,b :: aRb ...
1
vote
3answers
140 views

Congruence Relation with exponents and variables

I am currently trying to solve a congruence relation with a constant and a variable, both of which have attached exponents. The relation is as follows: $7^{95}\equiv x^{3} (mod 10)$ How does one ...
0
votes
1answer
223 views

Relation squared of $xRy$ iff $x-y=c$

Let $R$ be the relation on $\Bbb{Z}$ such that $xRy$ if and only if $x-y=c$. (a) Define $R^2$. Can anyone help me with $R^2$? I am not sure where to start. From similar questions, I saw that it ...
0
votes
1answer
119 views

Relation on countable sets

Let $R$ be a relation on two countable sets $A$ and $B$, where $R\subset A\times B$, with the following properties: $\forall a\in A$ the set $\{b\in B: (a,b)\in R\}$ is finite. For any finite set ...
0
votes
1answer
77 views

Reflexivity, Transitivity, Symmertry of the square of an relation

$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is reflexive/symmetric/transitive ...
0
votes
1answer
124 views

Rational Numbers and Equivalence Classes

Describe the rational numbers as the equivalence classes for an equivalence relation on certain pairs of integers.
0
votes
1answer
117 views

Proving $\;x-y \in2\pi \mathbb Z\;$ defines an Equivalence Relation

Prove that $\;x-y \in2\pi \mathbb Z\;$ defines an equivalence relation on $\;\mathbb R.$
0
votes
1answer
93 views

Question about relation on rational numbers

Define the relation on $\mathbb{Q}$ by $$[m,n]<[j,k]$$ if and only if $jn-mk$ belongs to $\mathbb{N}$, $j$ and $m$ belong to $\mathbb{Z}$, $n$ and $k$ belong to $\mathbb{N}$. (a) Show that ...
0
votes
1answer
176 views

Equivalence Relation? Column-equivalence on the set of all $m\times n$ matrices.

How do I show that column equivalence on the set of all $m\times n$ matrices is an equivalence relation? I know that to show it is an equivalence relation, I need to show that column equivalence is ...
65
votes
12answers
9k views

Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have ...
10
votes
1answer
234 views

Can we extend the definition of a continuous function to binary relations?

Let $X,Y$ be topological spaces. A function $\phi:X\to Y$ is continuous iff for any open subset $A\subseteq Y,$ the preimage $\phi^{-1}(A)$ is open in $X.$ We could similarly define a relation ...
7
votes
2answers
152 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 ...
2
votes
3answers
10k views

Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
0
votes
1answer
192 views

Direct products in the category Rel

Please describe direct products in the category Rel.
6
votes
3answers
159 views

Unambiguous terminology for domains, ranges, sources and targets.

Given a correspondence $f : X \rightarrow Y$ (which may or may not be a function) I generally use the following terminology. $X$ is the source of $f$ $Y$ is the target $\{x \in X \mid \exists y \in ...
4
votes
3answers
608 views

Relations (Binary) - Composition

Let $R = \{(a,b), (b,c), (c,d)\}$ How can I figure out why $R^{2} = \{(a,c), (b,d)\}$? This there a mathematical proof (or formula) to determine this for larger set of relations? Is it always first ...
4
votes
2answers
244 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 ...
3
votes
4answers
193 views

Are $4ab\pm 1 $ and $(4a^2\pm 1)^2$ coprime?

Let $a\ne b$ be two positive integers. Are $4ab+1$ and $(4a^2+1)^2$ coprime always? Can you find $a$ and $b$ such that they are not coprime? Edit: It has been proved that $4ab-1$ is not a divisor ...
3
votes
1answer
275 views

Confusion between operation and relation: Clarification needed

I'm doing some old exams and found following question: Set $S={{1,2,3}}$ is given. Provide an example of binary operation in set S, binary relation in set S and a function $f:S\rightarrow ...
2
votes
3answers
100 views

$(a,b)R(x,y) \iff ay=bx$ is an equivalence on $\Bbb Z \times (\Bbb Z\setminus\{0\})$ [duplicate]

Define a relation $R$ on $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ by $(a,b)R(x,y)\iff ay=bx.$ $a)$ Prove that $R$ is an equivalence relation. $b)$ Describe the equivalence classes ...
0
votes
2answers
86 views

Transitive closure

Given $M=\{n\in\Bbb Z: 0\le n\le 30\}$ find the transitive closure of the relation $R\subset M\times M$ defined by $R=\{(n,m): m=3n+1\}\cup\{(8,16)\}$ So, I know that a transitive closure is the ...
7
votes
5answers
658 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$ ...
5
votes
2answers
325 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 ...
5
votes
2answers
436 views

Cardinality of relations set

I was thinking about cardinality of all symmetric relations, for example in $\mathbb{Z}$. I know, that if I have finite set (which contains $n$ elements), there are $2^{\frac{n(n+1)}{2}}$ symmetric ...
4
votes
1answer
455 views

How many transitive relations on a set of $n$ elements?

If a set has $n$ elements, how many transitive relations are there on it? For example if set $A$ has $2$ elements then how many transitive relations. I know the total number of relations is $16$ but ...
4
votes
1answer
59 views

Let R be a relation on set A. Prove that $R^2 \subseteq R <=>$ R is transitive $<=> R^i \subseteq R ,\forall i \geq 1$

this is my first question here. I'm still relatively new to more advanced mathematics and don't have much experience with proofs yet. I'm self-studying at the moment and therefore have no one to check ...
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 ...