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

6
votes
5answers
8k 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 ...
31
votes
3answers
4k 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
6k 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 ...
83
votes
12answers
15k 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 ...
8
votes
4answers
4k 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 ...
2
votes
1answer
3k views

Number of reflexive relations defined on a set A with n elements

Problem: If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it? My solution Is the answer ...
2
votes
3answers
344 views

The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
0
votes
3answers
214 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$ ...
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
166 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
152 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 • ...
2
votes
2answers
609 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 ...
4
votes
3answers
1k views

Why is $y = \sqrt{x-4}$ a function? and $y = \sqrt{4 - x^2}$ should be a circle

So why is it a function, even though for example $x = 8$; you'll have $y = +2$ and $y = -2$. It'll fail the vertical line test. But every textbook considers it as a function. Did I misunderstand ...
2
votes
2answers
169 views

Is statistical dependence transitive?

Take any three random variables $X_1$, $X_2$, and $X_3$. Is it possible for $X_1$ and $X_2$ to be dependent, $X_2$ and $X_3$ to be dependent, but $X_1$ and $X_3$ to be independent? Is it possible ...
12
votes
2answers
343 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 ...
12
votes
2answers
373 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 ...
9
votes
2answers
364 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 ...
3
votes
4answers
10k 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 ...
1
vote
1answer
260 views

Direct products in the category Rel

Please describe direct products in the category Rel.
1
vote
1answer
63 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 ...
6
votes
1answer
93 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
156 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
127 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
2
votes
1answer
105 views

Prove that the empty relation is Transitive, Symmetric but not Reflexive

Question: Let $R$ be a relation on a set $A$. Prove that if $A$ is non-empty, the empty relation is not reflexive on $A$. the empty relation is symmetric and transitive for every set $A$. My ...
5
votes
1answer
288 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
152 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
140 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
3answers
5k 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 ...
4
votes
2answers
143 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 ...
4
votes
2answers
362 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 ...
4
votes
3answers
177 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!
4
votes
5answers
3k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
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
1answer
178 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
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
116 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
3answers
381 views

How many reflexive binary relations there are on a finite countable set?

We know that binary relation is subset of Cartesian product made by set on to itself. let's say we have a set with two elements $A=\{0,1\}$ So Cartesian product is $C=A\times A = ...
2
votes
4answers
307 views

Showing that $R$ is an equivalence relation on $X \times X$

Let $X = \{1,2,3,..,10\}$ define a relation $R$ on $X \times X$ by $(a,b)R(c,d)$ if $ad=bc$. Show that R is an equivalence relation on $X \times X$. I know that the $R$ have to be reflexive (because ...
2
votes
2answers
8k 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
421 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
1answer
48 views

Is it true that the relation |A| < |B| is a sufficient condition for claiming that $f$ is a bijection?

This is an exercise of an assignment I have: Suppose $A$ and $B$ are finite sets and $f\colon A\to B$ is surjective. Is it true that the relation “$|A| < |B|$” is a sufficient condition for ...
1
vote
2answers
70 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
162 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
232 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
233 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
39 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [closed]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
2answers
53 views

Check if a relation on a set is a function [duplicate]

What do I need to look for in order to tell if a relation on a set is a function? Can somebody provide some advice? For example, the relation is defined by $H$ on $A \times \mathcal P(A)$ for $a ∈ ...
0
votes
1answer
46 views

Equivalence relation for set given as matrix

I need a hint. My task is to proof that ((a11, a12), (b11, b12)) ((a21, a22), (b21, b22)) ∈ R ⇔ a11 + a12 + a21 + a22 = b11 + b12 + b21 + b22 R is equivalnce relation. My problem is that I ...
0
votes
1answer
61 views

Equivalence relations and power sets.

Let $\mathcal{A}$ be the class of all sets and define the relation $R$ on $\mathcal{A}$ as: $A\space R\space B$ iff there is a bijective function $f:A \to B$. Prove that $R$ is an equivalence relation ...
0
votes
1answer
487 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 ...