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

0
votes
1answer
30 views

how to prove $pr_i(\alpha \setminus \beta) \supseteq pr_i\alpha \setminus pr_i\beta$

For those who are not familiar with the syntax $pr_i \alpha = \{ pr_i(a,b) / a \alpha b \} \text{ for }\alpha \subseteq A \times B$ which is same as $\begin{cases} (x= pr_1 \alpha) \Leftrightarrow ...
1
vote
1answer
19 views

Shortcut for determining equivalence relations?

Is there a short cut to determine the number of equivalence relations on the set $\{1,2,3,4\}$? I mean I could do that manually but for a larger set it becomes annoying. Is there a general way to ...
1
vote
1answer
16 views

finding the equivalence class of modulo?

I would like to find the number of different equivalence classes for $\{(x,y)\mid x^2\equiv y^2$ mod $3 \}$ on $\mathbb{N}^2$. I would just set $x^2$ to $0$ or $1$ or $2$ or $3$. For example ...
0
votes
1answer
21 views

Which are the equivalence classes for the following relation?

Here I have such an exercises related to equivalence relations. Given R defined on $Z \times Z$, $$(a,b)R(c,d)$$ and $$a+d=b+c$$ Let set $A$ be: $$A=\lbrace{0,1,2} \rbrace$$ Which are the ...
0
votes
2answers
35 views

Show that $R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$ is an equivalence relation

How can I show that this is an equivalence relation ? $$R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$$
0
votes
0answers
30 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
1answer
9 views

Hasse diagram of finite linearly ordered set

What form does the Hasse diagram of a finite linearly ordered set take? I think the linearly order set is nothing but totally ordered set which usually takes lattice form since every element is ...
0
votes
2answers
19 views

How many relations can be defined the this power set

Let $A=\{1,2,3\}$ What is the number of reflexive relations the can be defined on $P(A)$? I first thought the number is 3, but it seems I'm wrong. How can someone solve this problem? Thanks
1
vote
0answers
25 views

Reflexive, symmetric and transitive closure of the following graph

First of all, I have to understand which relation this graph represents: Since there are 4 different elements, suppose there's the set $A = \{ a, b, c, d\}$ The relation drawn above, I think, can ...
1
vote
0answers
20 views

Partial and total orders

From Exercise 4.4.9 of How To Prove It: Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A \times B$ as follows: $L = \{((a, b), (a', b')) \in (A ...
1
vote
1answer
31 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. Sorry for the bad formatting before. All the comments have been ...
-1
votes
0answers
22 views

How to draw a hasse diagram using simple method?

I just passed to this link: How to draw hasse diagram for divisibilty. After I read the solution, I just try to solve my problem using this solution. But, It never get the right diagram and always ...
0
votes
1answer
23 views

permutation on relations

Let $A = \{1, 2, 3, 4\}$. Call a binary relation on $A$ interesting if it is symmetric or it does not contain the pair $(1, 4)$. How to calculate the number of interesting binary relations on $A$. My ...
2
votes
1answer
45 views

Is this relation transitive? $R=\{(1,2),(1,1),(2,1),(2,2)\}$ over $A=\{1,2,3\}$

Is this relation $R$ over $A$ transitive?$$A=\{1,2,3\}$$ $$R=\{(1,2),(1,1),(2,1),(2,2)\}$$ Since from the definition a relation is transitive if $\forall x,y,z\in A (xRy,yRz\to xRz)$, so since $3$ ...
2
votes
1answer
18 views

How to find efficient not transitive pairs in relations? (Discrete math)

I'm doing at the moment some math and struggle with the following. So there are relations and they can or can not hol specific properties. Most common are described reflexive, symmetric and ...
0
votes
2answers
31 views

Binary relation of composite function

Suppose S is a binary relation on a set X. If S ◦ S is reflexive, Is S is reflexive? can we prove this with example too and by definition "Let U be a non-empty set and let R be a binary relation ...
0
votes
1answer
22 views

Composition of relations - check my method

I just want to check that the method I am using for the composition of relations is right. If a pair in R (z,y) and a pair in S (x,z) then (x,y) yield and become a pair in SoR?
0
votes
1answer
29 views

Problem of understanding transitive relations

I would like to understand the transitive property in relations...I just cant get it in my brain. I mean the definition is crystal clear. However I still struggle. For example: Given the set ...
2
votes
2answers
16 views

Showing $R$ is transitive and reflexive $\to$ $R=R^2$, $R$ is transitive and reflexive $\to$ $R=R^2$

Let $R$ be a relation over $A$. Define $R^{-1}, R^2$ like so: $aR^{-1}b \iff bRa\\ aR^2b\iff\exists _{c\in A}(aRc\wedge cRb)$ Prove: $R$ is transitive $\iff$ $R^2\subseteq R$ ...
1
vote
1answer
15 views

Question about proving intersection of two transitive relation is transitive

Suppose $R,S$ are transitive relations over $A$, prove that $R\cap S$ is transitive. Let $x,y,z\in A$, since $R,S$ are transitive then $$(x,y),(y,z),(x,z)\in R \wedge S\Rightarrow ...
-1
votes
1answer
15 views

Ordered sets. Chain upper bounds.

Suppose I have an ordered set $A$ and a chain $B\subseteq A$ then does $B$ necessarily have a supremum? Let alone an upper bound? And if it is empty? This question is a bit confusing because I am not ...
0
votes
1answer
24 views

Why is $R$ not transitive?

$R = \{(2, 4), (4, 3), (2, 3), (4, 1)\}$ I know that $(2, 4) \in R$ and $(4, 3) \in R$ -> $(2,3)\in R$. But why my reference book said that the relation is not transitive? And why this $R = \{(1, ...
0
votes
0answers
16 views

Finding maximal chains in an ordered set.

Let $R$={$((x_1,y_1),(x_2,y_2))$:$x_1\le x_2, y_1\le y_2$} find the maximal chaings. Could it be that every maximal chains is of the form {$(a,b)+t(1,1)|t\in\Bbb{R}$} such that every other chain of ...
0
votes
0answers
16 views

Zorn's lemma usage\problem. [duplicate]

Let $(A,\le)$ be an ordered set. Show that if any chain has an upper bound then for any $a\in A$ there exist a maximal element such that $a\le x$. I am stuck with this... Would appreciate any ...
0
votes
1answer
9 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
1answer
26 views

Binary relations on sets

Sorry for such a query. But can a relation be both antisymmetric as well as asymmetric? for ex. is this relation {(3,4),(5,6)} both antisymmetric and asymmetric.
1
vote
3answers
270 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
1answer
20 views

Graph homomorphism with a non-mapping relation

In [1] it is said that a graph homomorphism is a mapping between two graphs, that is, between their vertices, where the edges are preserved. A mapping is a specific binary relation where any vertex ...
2
votes
2answers
38 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, ...
1
vote
3answers
30 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 ...
0
votes
1answer
27 views

If $R_1$ and $R_2$ are symmetric and transitive, prove that also $R_1 \cup R_2$ is symmetric and transitive

I have to prove or confute (with a counter example) that, if $R_1$ and $R_2$ are symmetric and transitive, then $R_1 \cup R_2$ is also symmetric and transitive. Note: To prove the transitive case, ...
1
vote
1answer
15 views

If $S = \{ (p, q) \in P \times P \mid \text{p is an ancestor of q}\}$, what is $S \circ S^{-1}$?

Suppose $S = \{ (p, q) \in P \times P \mid \text{p is an ancestor of q}\}$. What is $S \circ S^{-1}$? To achieve the desired result, I would start by identifying what $S^{-1}$ (the inverse of ...
0
votes
3answers
434 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
2
votes
1answer
28 views

Suppose $R$ is partial order, prove that $R^{-1}$ is also a partial order

Suppose $R$ is partial order, prove that $R^{-1}$ is also a partial order. A partial order is a binary relation that is reflexive, anti-symmetric and transitive. So if $R$ is a partial order, ...
1
vote
1answer
19 views

Truth set for the following formula $\forall x R(x, x) \land R(a, b)$?

I have this exercise: Let $R$ be a binary relation. For each of the following formulas, define a truth set over a universe of size at least 3 satisfying it. Example: a truth set over a ...
2
votes
1answer
29 views

Is “person p is sitting immediately to the right of the person q” a function?

This is the simple exercise I am trying to solve, where I have to say if $R$ is a function, but I would like to have some feedback on my solution: John, Mary, Susan, and Fred go out to dinner and ...
1
vote
1answer
47 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
37 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
32 views

If $R$ is a strict partial order prove that is asymmetric

Suppose $R$ is a relation on a set $A$, and $R$ is asymmetric if: $\forall x \in A$ $\forall y \in A$ $((x, y) \in R \rightarrow (y, x)\not \in R)$ The first point of the exercise was to demonstrate ...
0
votes
1answer
19 views

Why the transitive closure for this relation $R = \{(x, y) \in \mathbb{R} \times \mathbb{R} \mid x < y\}$ is R?

I have read a chapter on closures: reflexive, symmetric and transitive, and it seems I have not fully understand the concepts, at least for transitive closures. Why the transitive closure for this ...
1
vote
1answer
27 views

Why do we have to include the pairs $(b, b)$ and $(c, c)$ in the transitive closure?

The problem is: Find the reflexive, symmetric and the transitive closure of the following relation: $R = \{ (a, a), (a, b), (b, c), (c, b)\}$ on the set of elements $A = \{a, b, c\}$ ...
1
vote
2answers
28 views

What does exactly this syntax $S = R \cup i_{A}$ mean?

I am trying to understand what is a reflexive closure and, more or less, I understood the properties: Let $R$ be a relation on $A$. Then the reflexive closure of $R$ is the smallest set $S \in A ...
0
votes
0answers
33 views

Warshall's algorithm in transitive closure

Let $A=\{0,1,2,3\}$ and let $R$ and $S$ be the relations on $A$ described by the matrices $M_R= \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ ...
4
votes
4answers
584 views

$5 \mid n^2 - m^2$ is an equivalence relation

How can I show this is an equivalence relation: $$ n \operatorname{R} m \Longleftrightarrow n^2 - m^2 \textrm{ is divisible by } 5 $$ I know equivalence relations are symmetric, reflexive and ...
1
vote
1answer
168 views

Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
1
vote
3answers
78 views

Proof that $(a, b) \mathrel{R} (c, d)$ iff $ad = bc$ is an equivalence relation

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...
3
votes
2answers
200 views

Proving that $4 \mid m - n$ is an equivalence relation on $\mathbb{Z}$

I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation. $F$ is the relation defined on $\Bbb Z$ as follows: ...
0
votes
1answer
29 views

How many partial order relations are there over N, the set of positive integers?

I have been trying to calculate it in several ways but I get stuck when it comes to many combinatorial issues... Like taking the number of possible relations and subtract the number different kinds of ...
1
vote
2answers
523 views

Difference between Reflexive and Symmetric in Discrete Maths

Difference between Reflexive and Symmetric in Discrete Maths? This is what I understand: Reflexive -> <a,a=a>, <b,b=b> uses ...
0
votes
1answer
53 views

Rel is a concrete category over Sets, but how to concretize that?

The traditional denotation of a structured set object is something like $(1)\qquad(X,\mathcal S_1,\dots\mathcal S_n)$ for some "structures" $\mathcal S_1,\dots\mathcal S_n$ on a set X. The modern ...