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
2answers
59 views

How are there are 16 relations on a two element set?

Let $A=[{a_{1}, a_{2}}]$ I can only think of four those being [(${a_{1}, a_{2}}$), (${a_{2}, a_{1}}$), (${a_{1}, a_{1}}$), (${a_{2}, a_{2}}$)] supposedly there 16 relations and All but three ...
1
vote
0answers
24 views

Symmetry of a relation

There is a professor in our University who each year posts some homework for his students (1st years at computer studies) and I am trying to solve it for fun. However, now I got stuck on something ...
0
votes
1answer
31 views

Discrete Mathematics. Set Relations [closed]

(a) Let A = {1, 2, 3}. For each of the below relations, indicate which of the 4 properties it satisfies: reflexive, symmetric, antisymmetric, transitive. (i) {(1, 1),(1, 2),(2, 3)} (ii) {(1, 1),(1, ...
0
votes
3answers
34 views

Is this relation antisymmetric?

3) Let S={0,1,2,4,6}. Test the following binary relation on S for reflexivity, symmetry, antisymmetry, and transitivity: R={(0,0),(1,1),(2,2),(4,4),(6,6),(0,1),(1,2),(2,4),(4,6)} Don't worry about ...
1
vote
1answer
25 views

How can I prove $R^T\ ;R^T$ is transitive if $R$ is transitive.

If $R$ is transitive relation. How can I prove that composition of its transpose is also transitive. i.e. $R^T\ ;R^T$ is transitive too.
0
votes
1answer
23 views

How to prove that $(R; S;R)^n \subseteq (R; S)^n;R$ for all $n \geqslant 1$.

If $R; S$ be relations on a set $U$. Given $R$ is transitive. How to prove that $(R; S;R)^n \subseteq (R; S)^n;R$ for all $n \geqslant 1$.
0
votes
1answer
25 views

Relations on cartesian product

The relation $T$ is defined as follows: $T \subseteq \mathbb{R}\times \mathbb{R} : xTy \Leftrightarrow y > x + 1$. Is $T$ a function and why? Thanks.
0
votes
1answer
18 views

If $R$ is transitive and $S$ is reflexive, Prove $(R\ ; S\ ;R)^2 \subseteq (R\ ;S)^3$

$ R $ and $S$ are two relations. Given $R$ is transitive and $S$ is reflexive How can I Prove $(R\ ; S\ ;R)^2 \subseteq (R\ ;S)^3$
0
votes
1answer
14 views

For Relation $R$ Prove $R^*=I \cup R^+$

Given R is a relation, I need to prove 2 things. 1) $R^+=R \ ;R^* $ 2) $R^*=I \cup R^+$ For (1) I proceeded as $ \Rightarrow R^+$ $ \Rightarrow \bigcup\limits_{n=1}^\infty R^n ...
3
votes
2answers
36 views

What is the etymology of the term “reflexive” in the context of binary relations?

A binary relation $R$ over a set $A$ is called reflexive if the following is true: $$\forall a \in A. aRa$$ Why are relations called these "reflexive?"
0
votes
1answer
32 views

Equivalence classes and equivalent relationship

We define a relation S on the set of all integers by: $nSk$ iff $n^2$ $=$ $k^2$ Decide if S is an equivalence relation. If so, what is the equivalence class of $9$? It can be proven that S is an ...
3
votes
3answers
68 views

if $x\mathcal R y$ defined by $|x|+|y| =|x+y|$. Is it an equivalence relation?

Reflexive and symmetric can be proved as $|x|+|x|=|x+x|$ hence reflexive and $|y|+|x|=|y+x|$ hence symmetric but how transitive?
1
vote
1answer
11 views

The order deduced from relations in $D_n$

If $D_n \triangleq \langle a,b | a^n=e, b^2=e, abab=e \rangle$, can it be proved that the order of $a, b$ is actually $n$ and $2$ respectively ? I mean can the relations on the right somehow after ...
0
votes
1answer
51 views

Find four binary relations from $\mathbf{\{a,b\}}$ to $\mathbf{\{x,y\}}$ that are not functions from $\mathbf{\{a,b\}}$ to $\mathbf{\{x,y\}}$

Question: Find four binary relations from $\mathbf{\{a,b\}}$ to $\mathbf{\{x,y\}}$ that are not functions from $\mathbf{\{a,b\}}$ to $\mathbf{\{x,y\}}$. Thoughts: I know that a relation $\mathbf R$ ...
0
votes
1answer
31 views

Is this relation anti symmetric

Was asked to Work out transitive closure of: R = {(1, 1),(1, 3),(2, 2),(2, 1),(3, 3),(4, 4),(4, 3),(4, 2)} I did using Warshall's, getting: ...
0
votes
1answer
44 views

Partial ordering on Natural numbers

Preparing for exams, and came across this past year question. Any ideas? I know that for partial order, it must be reflexive, transitive and anti-symmetric, but how exactly do i show this?
0
votes
0answers
9 views

Generalizing equality and relational operations for a variable number of arguments

I'm curious if the six numerical comparison operators (is equal, is not equal, greater than, greater than or equal, less than, less than or equal) are generalizable to any number of arguments? For ...
0
votes
0answers
25 views

strict and non-strict partial ordering

Show that if < is a strict partial order on A, then the relation ≤ defined by a≤b iff a< b or a = b is a non-strict partial order. I know a non-strict partial order is reflexive, anti ...
3
votes
2answers
364 views

Is '=' antisymmetric?

I know that an antisymmetric relation must meet the following condition: If x <=y and y<=x then x=y. That being said, can one consider ...
0
votes
0answers
45 views

Example of a relation on a finite set

In one of the exercises, I proved that $R^n+1\subseteq R^n$ for all $n \ge1$ But now I need to give an example of relation on finite set such that $R^3 \subsetneq R^2 $ Here $R^3$ =$R \circ R \circ ...
0
votes
2answers
23 views

Set theory : Anti-symmetric but transitive (proof)

The exam practice question is as follows: We call a relation $R$ anti-reflexive iff $\forall a \in A : (a,a) \notin R$ and anti-symmetric iff $\forall a,b \in A : (a,b) \in R \rightarrow ...
-1
votes
1answer
38 views

Transitivity, symmetry on empty set X, non-empty relation R [closed]

If I had an empty set X, with a relation R containing elements 1 and 2 In my directed graph if I had (1,2) and (2,1), would I still have transitivity and symmetry even though this is an invalid ...
1
vote
1answer
29 views

Verifying partial order relation

I have the following question where i have to verify if the relation is partial order: $A=\{1,2,3,\ldots,100\}$, relation $x\mathrel{R}y \leftrightarrow \frac{y}x=2^k$, where $k\ge 0$ is an ...
0
votes
1answer
33 views

Equivalence class clarification

I'm slightly confused on the definition of an equivalence class. Suppose $R$ is a relation on $Z \times (Z - {0})$ by $(a,b)R(c,d)$ if and only if $ad = bc$. What would a single equivalence class from ...
1
vote
2answers
34 views

Relations - Very basic notation

I'm struggling to understand some basic notation regarding relations. Say I'm given some relation Z × (Z \ {0}) "on" (a,b)R(x,y) if and only if ab=xy, what exactly is this asking? and is this an ...
1
vote
2answers
17 views

Correct Terminology for Semi Inverse Mapping

Suppose we have two finite sets $X$ and $Y$ and a many to one mapping $f:X\rightarrow Y$. Now let me define another mapping $g:Y\rightarrow\mathcal{P}(X)$ where $\mathcal{P}$ denotes the power set. ...
0
votes
1answer
13 views

binary relations defining an equivalence relation on S

Is this a true statement for binary relations defines an equivalence relation on S: S is the set of all n-digit binary sequences. We say that two binary sequences are in a relation if and only if ...
0
votes
0answers
11 views

Which of the following binary relations defines an equivalence relation on S

So i was given this question Which of the following binary relations defines an equivalence relation on S: a)S is the set of all n-digit binary sequences. We say that two binary sequences are in a ...
0
votes
1answer
23 views

Does the following equation show transitive nature, symmetric and reflexive?

Does the following equation show transitive nature, symmetric and reflexive? $$d(a,b) = \lvert a-b \rvert \le 2 $$ I am really having trouble with this problem any help would be appreciated. I ...
0
votes
0answers
71 views

a good book on relations in discrete mathematics

I am self-studying discrete mathematics and I have troubles in solving the exercises that are included at the end of the chapter in my book. The book that I'm reading is already a good one, but it ...
0
votes
1answer
29 views

Check if relation $\rho$ defined as $x\rho y \Leftrightarrow (x^2-y^2)(x^2y^2-1)=1$ is equivalence relation on $\mathbb{R}$

Check if relation $\rho$ defined as $x\rho y \Leftrightarrow (x^2-y^2)(x^2y^2-1)=1$ is equivalence relation on $\mathbb{R}$ Relation is not reflexive: $(\forall x \in\mathbb{R})x\rho x ...
0
votes
2answers
24 views

finding binary relations between two Finite sets?

If there are two finite sets $A$ and $B$, then how to achieve the below How many binary relations between $A$ and $B$? How many functions from $A$ to $B$? $A$ and $B$ should be in terms of ...
1
vote
1answer
17 views

Question about possible relations [duplicate]

Hello I have a question about possible equivalence relations. I know that a relation can be Reflexive, Symmetric , Transitive. But my question is, is there any strict limitations one has on the ...
1
vote
1answer
23 views

Relations and equivalence relations

I'm self-studying discrete mathematics and right now I'm reading a chapter about "Relations". I've tried to solve some of the exercises that are included at the end of the chapter. But they are too ...
0
votes
0answers
31 views

Relations and logic

$R$ is a relation defined on the set $\mathbb Z$ of integers. For any $a,b \in \mathbb Z$, $a\,R\,b$ iff for any prime number $p$,one has $p\,|\,a$ if and only if $p\,|\,b$. I'm trying to prove or ...
0
votes
1answer
21 views

Prob. 12, Sec. 3 in Munkres' TOPOLOGY, 2nd ed: How to relate these order relations?

Let $\mathbb{Z}_+$ denote the set of positive integers. Consider the following order relations on $\mathbb{Z}_+ \times \mathbb{Z}_+$: (i) The dictionary order: $x_0 \times y_0 \prec x_1 \times y_1$ ...
3
votes
3answers
47 views

Prob. 5 (c), Sec. 3 in Munkres' TOPOLOGY, 2nd ed: How to find this equivalence relation?

Let $S$ be the following subset of the plane: $$S \colon= \{ \ x \times y \ | \ y = x+1, \ 0 < x < 2 \ \}.$$ Let $T$ be an equivalence relation on the real line such that $T$ is the ...
1
vote
2answers
22 views

How to find equivalence class of this relation?

In solving this problem: Let $R$ be an equivalence relation on the set $A = \{a,b,c,d\}$, defined by partitions $P = \{\{a,d\},\{b,c\}\}$. Determine the elements of the equivalence relation and ...
0
votes
0answers
33 views

Relations in $U_q(sl(3))$ by induction

I am looking to the quantum group $U_q(sl(3))$ with generators $E_1,E_2,F_1,F_2,K_1$ and $K_2$. I want to find out what the elements to to the elements of the form $F_2^mF_1^nv$ where v is a vector ...
0
votes
1answer
29 views

Relations and functions.

let $f:S\rightarrow T $ for non-empty sets $S$ and $T$ and let $C$ be a partition of $S$. Define a relation ~ on the set $T$ such that, $t_1$ ~ $t_2$ if $\exists_{A\in C}$ : $f^{-1}( \{t_1,t_2 \} )$ ...
-2
votes
2answers
45 views

Let R be the following relation on the set of pairs of integers:

Let $R = \left\{\bigl((a, b), (c, d)\bigr) \in \mathbb{Z}^2 \times \mathbb{Z}^2; a + d = b + c\right\}$. Prove that $R$ is an equivalence relation. Find the equivalence class of the pair $(0, 0)$.
-3
votes
4answers
134 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.
1
vote
1answer
37 views

Hasse diagram with “≥” relation

We have a set S= {1,2,3,4} with following relation: aRb <-> a ≤ b ≤ a^2 With focus on the relation we get following partially ordered set: {1,2},{1,3},{1,4}, {2,3},{2,4}, {3,4} which gives the ...
0
votes
2answers
23 views

Symmetric relation proof

Prove that the following relation is symmetric: For all $x,y\in\Bbb N$, $xRy$ iff $x+y$ is even. My attempt: Assume $x,y$ are in $\Bbb N$, and $x+y$ is even. Since $x+y$ is even, then $x+y=2a$ for ...
1
vote
1answer
51 views

For every partial order ≤ is the relation < transitive?

For every general partial order ≤ is the relation < := ≤ ∩ ≠ transitive I tried working with the definition of the partial order. A partial order is antisymmetric, transitive and reflexive. The ...
3
votes
0answers
61 views

Principia Mathematica Part VI “Quantity” vs Part IV “Relation Arithmetic”

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments: "I think relation-arithmetic important, not only as an interesting ...
-1
votes
4answers
79 views

Reflexive, symmetric or non transitive relations? [duplicate]

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...
0
votes
1answer
32 views

Defining relations on a power set

I'm determining whether the relation is: reflexive, symmetric, transitive or anti-symmetric. Let $X$ be a non-empty set and let $\mathcal{P}(X)$ be the power set of $X$. Let $R_3$ be the relation ...
1
vote
1answer
40 views

Partial order involving cartesian product: P x Q

So I'm a bit confused with the concept of a partial order. P = {1, 4} Q = {1, 2} How do you define a partial order Z on (P x Q)? and how would the hasse diagram of Z look like? is it even possible ...
0
votes
1answer
32 views

Help with a relation to Congruences Modulo 5?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on ...