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

1
vote
1answer
20 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
17 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
2answers
37 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
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
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
33 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 ...
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
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 ...
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
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$ ...
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 ...
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
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 ...
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
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, ...
-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
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.
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 ...
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 ...
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 ...
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, ...
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
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
48 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 ...
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 ...
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\}$ ...
0
votes
1answer
23 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

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 ...
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 \\ ...
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 ...
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, ...
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 ...
3
votes
1answer
29 views

Partial order relations

Please help solve following: Let P be the set of all people who have ever lived and define a relation R on P as follows: For all r,s ∈ P, r R s ⇔ r is an ancestor of s or r=s. Is R a partial order ...
7
votes
4answers
1k views

Is Russell's paradox really about sets as such?

It seems to me that Russell's paradox rather is a "paradox" concerning relations. Suppose we want to construct a graph (with finite or infinite number of nodes) and want some node to be adjacent ...
1
vote
1answer
36 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 ...
3
votes
2answers
165 views

An example in the fundamental theorem of equivalence relations?

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there ...
1
vote
1answer
38 views

In what way are the elements in this list of numbers most simply related?

I will try to keep this as math related as possible, though I intend to use this from a computer science standpoint. Hopefully you can forgive some of my annotations. Consider an ordered list of ...
0
votes
2answers
83 views

How many one-to-one relations $A\rightarrow{A}$ are possible for a set $A$?

I have a set A of unique elements, I want to know how many one-to-one relations on itself are possible?
0
votes
1answer
31 views

Can totality be defined in terms of left-totality (or right-totality)?

In the context of relations, can totality be defined in terms of left-totality (or right-totality)? I ask this because both properties have the word "totality" in their names and one may think that ...