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
17 views

A counterexample for an equation between arbitrary relations

It seems that the following equation does not hold always for the arbitrary relations R1,R1 and R3: $R1.(R2\cap R3)=(R1.R2)\cap(R1.R3)$ Instead, the right axiom is the following: $R1.(R2\cap ...
1
vote
0answers
19 views

xor of three relations using Relation Algebra operations

Suppose I have three relations R1, R2, and R3. How can I specify xor of these three relations using relation algebra operations. How this scales up (for example, for four relations)? Thanks I add ...
1
vote
2answers
34 views

For what $z\in\mathbb{N}$ is “$x\equiv y\iff xyz$ is a square” an equivalence relation?

Consider the set $\mathbb{N}\cup\{0\}$ and fix $z\in \mathbb{N}\setminus\{0\}$. Define the relation $x \equiv y \iff xyz$ is a square number. I am trying to verify that this is an equivalence ...
0
votes
1answer
11 views

Mapping relations

Which of the following relations $f\colon \mathbb{Q} \to \mathbb{Q} \!\,$ define a mapping? In each case, supply a reason why $f$ is or is not a mapping. So my understanding is that a mapping ...
-1
votes
1answer
27 views

Counting relations question

I have a small question about relation counting, i'm looking for formulas. I know that there is a formula for reflexive and anti reflexive. I'm not sure about the simetric or a-simteric ones, and if ...
1
vote
3answers
18 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
1
vote
2answers
25 views

What's the term for antisymmetry where equal elements are not in the relation?

The most common definition of antisymmetry of a relation $R$ on a set $S$ is $$ \forall a, b \in S, R(a, b) \land R(b, a) \to a = b. $$ However, this doesn't cover a relation such as $<$, for ...
1
vote
1answer
19 views

Is an irreflexive and transitive set an anti symmetric set?

I have read that a simple ordered set is a total ordered set which is irreflexive and transitive. I want to know if irreflexivity and transitivity implies antisymmetry?
0
votes
0answers
18 views

How to prove the two relations to be equal?

If I have a relation $R$ defined on a set $A$ ,then when we calculate $R^n$ by performing cartesian product of $A^n$ ,then can we predict the value of $s$ and $t$ such that $R ^ s=R ^ t$. As we ...
1
vote
2answers
44 views

Prove that $f$ is NOT surjective

Let $f: Z \times Z \to Z \times Z$ defined like this: $f(x,y) = (x+y, x-y)$ Prove that $f$ is injective, and not surjective. For injectivity I did that: Let $(a,b) \in Z\times Z$ and $(c,d) \in ...
0
votes
2answers
36 views

If $|B\times A| = 15$ ,evaluate: $|A\cap B|$

If $|B\times A| = 15$ and $|A\times B \backslash B \times B| = 12$. Evaluate: $|A\cap B|$ I tried for myself and got to the conclusion that $|A\times B \cap B \times B| = 3 $ I couldn't get by ...
1
vote
1answer
23 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
23 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
40 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
22 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
31 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
36 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
22 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
23 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
26 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$ ...
0
votes
1answer
37 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
35 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
17 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
17 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
16 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
17 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
10 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
16 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
49 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
27 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
24 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
30 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 ...