Questions tagged [relations]

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.

63
votes
6answers
13k 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$ ...
17
votes
4answers
14k views

Understanding equivalence class, equivalence relation, partition

I'm 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 ...
13
votes
6answers
25k 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 ...
6
votes
1answer
7k 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 ...
129
votes
15answers
38k 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 the ...
9
votes
2answers
27k 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 any good ...
14
votes
3answers
4k views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
12
votes
4answers
38k views

How to check whether a relation is transitive from the matrix representation?

$$\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 ...
4
votes
3answers
2k 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 ...
9
votes
3answers
35k views

How Many Symmetric Relations on a Finite Set?

How many symmetric relations are there for an $n$-element set? Thank you.
0
votes
3answers
256 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$ Symmetry: ...
19
votes
5answers
85k 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 $...
9
votes
1answer
19k 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 ...
6
votes
3answers
17k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is $$2^{{...
8
votes
3answers
3k 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 ...
8
votes
3answers
16k views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
4
votes
3answers
9k 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 ...
1
vote
0answers
261 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
4k 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
531 views

Define a relation and find its equivalence classes.

Define a relation $\sim$ on $\Bbb{N}$ as follows. For any $a,b∈\Bbb N$, $a\sim b$ if and only if $ab$ is a perfect square. Show that $\sim$ is an equivalence relation. What are the equivalence classes?...
4
votes
7answers
551 views

The map $f:\mathbb{Z}_3 \to \mathbb{Z}_6$ given by $f(x + 3\mathbb{Z}) = x + 6\mathbb{Z}$ is not well-defined

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is not a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ ...
4
votes
5answers
9k 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 ...
1
vote
4answers
22k views

Can a relation be both symmetric and antisymmetric; or neither? [closed]

Can some relation be at the same time symmetric and antisymmetric? And, can a relation be neither one nor the other? Please give me an example for your answer.
16
votes
3answers
61k 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 ...
8
votes
3answers
22k views

Is the relation $R = \emptyset$ is it reflexive, symmetric and transitive ? Why?

Can someone help me understand the properties of the relation $R = \emptyset$ ? It looks to me like it's not reflexive, since there is no element related to any element, so the elements are not ...
13
votes
2answers
716 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 $\rho\...
4
votes
2answers
1k 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 ...
-2
votes
2answers
296 views

How to prove reflexivity, symmetry and transitivity for the following relation? [closed]

I would like to know how to prove reflexivity, symmetry and transitivity for $\sim$ according to the following definition: Suppose $\sim$ is defined on the set of the integers as follows : $a\sim b$...
5
votes
7answers
1k views

Branch of math studying relations

There are many branches of mathematics (analysis, algebra, group theory, logic, ...). Now, I'm interested in relations and their special kinds (like equivalence relation) and their properties. I'd ...
7
votes
7answers
37k views

Example of a relation that is symmetric and transitive, but not reflexive

Can you give an example of a relation that is symmetric and transitive, but not reflexive? By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$. $R$ ...
4
votes
2answers
201 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
3
votes
1answer
392 views

How to prove partition into $A_k=\{2^kn | n \in \mathbb N \text{ and }n\text{ is odd}\}$

I am having trouble showing that this is a partition: $\{A_k|k\in \mathbb N \cup \{0\}\}$ where each $A_k=\{2^kn | n \in \mathbb N \text{ and n - odd}\}$ is a partition of the natural numbers. I ...
6
votes
3answers
7k 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
3answers
197 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!
0
votes
2answers
58 views

How many functions are possible to create in this example?

Let $A = \{ 1,2,3,4 \}$ Let $F$ be a set of all functions from $A \to A$. Let $S$ be a relation defined by : $\forall f,g \in F$ $fSg \iff f(i) = g(i)$ for some $i \in A$ Let $h: A \to A$ be the ...
10
votes
2answers
881 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 ...
12
votes
2answers
375 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 A_j\ne\...
4
votes
3answers
1k views

“Converting” equivalence relations to partitions

There is a direct relationship between equivalence relations and partitions. Is there a way to simply use an equivalence relation's definition to get the matching partition? And what about the other ...
2
votes
1answer
566 views

Direct products in the category Rel

Please describe direct products in the category Rel.
8
votes
2answers
508 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 ...
7
votes
3answers
755 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 Y ...
3
votes
1answer
199 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
4answers
27k views

Prove that the intersection of two equivalence relations is an equivalence relation. [closed]

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 \...
6
votes
1answer
271 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 ...
3
votes
4answers
1k views

Is an Anti-Symmetric Relation also Reflexive?

According to the definition of an Anti-Symmetric Relation if xRy and yRx then x = y Which means, effectively, x is in relation with itself. Does this mean that anti-symmetry implies reflexive ...
3
votes
1answer
249 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
2k views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
0
votes
1answer
136 views

A category of relations - or two different?

Objects in the category Rel2 (my notation) are the relations $r\subseteq A\times B$, $r'\subseteq A'\times B'$ (the morphisms in Rel) and morphisms are pair of relations $\alpha\subseteq A\times A'$ ...
10
votes
4answers
9k views

Can a relation with less than 3 elements be considered transitive?

The generalize rule for a transitive relation is a -> b b -> c therefor a -> c If an element has less than 3 elements, can it still be transitive? If ...
6
votes
2answers
2k 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 ...