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 ...
28
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$ ...
6
votes
2answers
3k 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 ...
0
votes
3answers
212 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$ ...
6
votes
4answers
3k 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 ...
2
votes
1answer
105 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
127 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 • ...
72
votes
12answers
11k 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 ...
2
votes
2answers
454 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 ...
12
votes
2answers
338 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 ...
11
votes
2answers
300 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 ...
0
votes
1answer
57 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
250 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 ...
5
votes
1answer
74 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
97 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 ...
4
votes
2answers
114 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
2answers
275 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 ...
2
votes
3answers
5k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then ...
5
votes
1answer
279 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
1answer
111 views

The class of equivalence.

Let $Q$ be the following set of $\mathbb{Z}\times \mathbb{Z}$ \begin{align*} Q=\{(a,b)\in \mathbb{Z}\times \mathbb{Z} | b\neq 0\} \end{align*} Define the relation $\sim$ on $Q$ as ...
4
votes
2answers
113 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 ...
4
votes
2answers
133 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
3k 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 ...
3
votes
3answers
173 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
164 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
1answer
101 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
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
375 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
63 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
116 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
226 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
170 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
297 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
122 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
87 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
150 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
121 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
94 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
187 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 ...
4
votes
3answers
13k 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 ...
3
votes
3answers
87 views

Find $f(2a-x)$ from given equation

I have been trying to solve an exercise based on the relations and functions. Right now I had stuck to a question based on functions. The question says: A real valued function $f(x)$ satisfies the ...
7
votes
2answers
159 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 ...
3
votes
1answer
56 views

Rel: the category of relations

$\text{Rel}$ is the standard name for the category of sets and relations. Confusingly in "Abstract and concrete categories" (ACC), page 22, $\text{Rel}$ is defined as a category whose objects are ...
0
votes
1answer
213 views

Direct products in the category Rel

Please describe direct products in the category Rel.
6
votes
3answers
184 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
694 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 ...
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
348 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 ...