# Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

3,927 questions
Filter by
Sorted by
Tagged with
28 views

### If R,S, and T are binary relations on a nonempty set, which of these following statements are true and why? [closed]

$T \circ (R \cap S) = (T \circ R) \cap (T \circ S)$ $T \circ (R - S) = (T \circ R) - (T \circ S)$ $(R \cup S) \circ T = (R \circ T)\cup(S \circ T)$ $(R-S)\circ T = (R \circ T ) - (S \circ T)$
25 views

### equivalence relation and corresponding equivalence classes

On the set of integers $\mathbb{Z}$ consider the following relation: $$xRy \Leftrightarrow x-y\; is\; even$$ Prove that R is an equivalence relation and specify the corresponding equivalence classes....
30 views

### Can this be solved by mathematical induction?

So this is my question: $R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below: $R_0 := I = \{(x,x) : x ∈ S\}$ $R_{n+1} := R_n ∪ (R;R_n)$ for $n >= 0$ ($(R;R_n)$ implies R ...
14 views

### How is transitive closure of a relation related to the cardinality of the set?

This is my question, and I don't know how to approach it. $R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below: $R_0 := I = \{(x,x) : x ∈ S\}$ $R_{n+1} := R_n ∪ (R;R_n)$ for ...
17 views

### Prove that for every $X \in \mathscr{P}(A)$ there is exactly one $Y \in [X]_R$ such that $Y \cap B = \emptyset$

This is an exercise from Velleman's "How To Prove It". I strugled with this problem for a while, so I just want to make sure that it is correct. Suppose $B \subseteq A$, and define a ...
55 views

### How do I answer this question on relations?

I am unable to understand what this question means (except that I is the identity relation). Would really appreciate a simple explanation of what it is saying, and also some hints/tips on how to ...
5k views

### Example of an antisymmetric, transitive, but not reflexive relation

The question I'm tackling right now is this: Give an example of a relation R on a set S that is not reflexive, transitive and not symmetric. My answer: Let S = {1,2,3} and let R = {(1,1), (2,2), (1,...
45 views

### Why, exactly, does reflexivity depend on the domain of the relation?

For many properties of binary relations, like symmetry, asymmetry, and transitivity, it does not depend on what domain of the relation we are considering. More precisely, given a binary relation $R$ ...
22 views

### Is the relation $fRg$ iff $\exists k > 0 \mid f(x) + k < g(x + k)$ on real functions transitive?

Is the relation on the set of real functions $fRg$ iff exists $k > 0$ such that for all $x \in \mathbb{R}$, $f(x) + k < g(x + k)$ transitive? I have proved that it's not reflexive, not symmetric,...
19 views

### Which of the following relations on $\mathbb{R}$ are equivalence relations?

This is an exercise from Velleman's "How To Prove It": Which of the following relations on $\mathbb{R}$ are equivalence relations? For those that are equivalence relations, what are the ...
24 views

### Questions on determining if some relations are reflexive, symmetric or transitive. [closed]

Math Question: Suppose that R1={(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}, R2={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}, R3={(2,4),(4,2)}, R4={(1,2),(2,3),(3,4)}, R5={(1,1),(2,2),(3,3),(4,4)}, R6={(1,3),(1,4),(...
2k views

### What binary relation is neither symmetric, nor asymmetric nor antisymmetric?

I thought it was the relation $\varnothing$, but the answer in the textbook I am using does not mention this as a possible answer. I don't understand why it can't be the answer. Could anyone explain?
926 views

### Is a transitive and Euclidean relation necessarily symmetric?

The Wikipedia article on Euclidean relation reads: A transitive relation is Euclidean only if it is also symmetric. Only a symmetric Euclidean relation is transitive. It seems to be claimed that ...
10 views

### Equivalence of partial cyclic orders

I am studying partial cyclic orders (https://en.wikipedia.org/wiki/Partial_cyclic_order). Assuming we have two arbitrary partial cyclic orders of the same size on a set of letters, e.g. (from the ...
41 views

2k views

### Tricky transitive relations

I have a set $A = \{1, 2, 3\}$. Relation $S = \{(1, 1), (1, 2), (3, 1) \}$ Relation $T = \{(1, 1), (3, 2), (3, 1) \}$ $S$ is not transitive, but $T$ is transitive. Why is that? A relation $R$ ...
28 views

### is the binary relation "strictly higher than'' antisymmetric?

A order on a set X is a binary relation ≻,defined as:x≻y if x≽y and ¬y≽x. Is that binary relation antisymmetric?
33 views

### A real life example of equivalence class? [closed]

It's easy to find an example of equivalence relation, but I am not able to find a real-life example for equivalence class.
13 views

### Should a partial order and total order be related in the context of the “condition” specified in the relation?

I think using examples would convey my question the fastest. Let there be a set $A = \{ 1,2,3,5,10 \}$. Let $R$ be relation such that $a | b$. Note that in this case $a | b$ is what I mean by "...
19 views

### What does it mean by “A total order,$T$, $⪯$ is said to be compatible with the partial order $R$ if $aRb$ implies a $⪯$ b”?

In this definition: A total order, $T$, $⪯$ is said to be compatible with the partial order $R$ if $aRb$ implies a $⪯$ b There are 2 parts I am confused about. The 1st part: "with the partial ...
24 views

51 views

### Is $|x-y| \le 7$ symetric relation?

to prove $(x-y)$ divisible by $3$ as symmetric we use this method: let $xRy$ belongs to $A$ \begin{align} (x-y)&=3k \\ -(x-y)&=-3k \\ (y-x)&=3(-k) \end{align} therefore $yRx$ also ...
70 views

### Value For Which $x^k+y^k=1$ Matches $(x-1)^2+(y-1)^2=1$

Compute the real value $k$ for which the graph of $x^k+y^k=1$ is the same as the lower half of $(x-1)^2+(y-1)^2=1$ over $(0,1)$ or show that no such $k$ exists. I came up with this while daydreaming. ...
35 views

### Hasse diagram for the relation $\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,b),(b,c),(c,a),(c,b),(c,c)\}$ on set $M=\{a,b,c\}$

Hasse diagram for the the relation $\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,b),(b,c),(c,a),(c,b),(c,c)\}$ on set $M=\{a,b,c\}$ I tried to make the Hasse-Diagram for the relation. But as every element is ...
19 views

### math2 relations

please help me with answering this question In a list of two hundred numbers, some numbers are written in red pencil and some are written in blue pencil. If we erase all red numbers, we are left with ...
27 views

Let $R$ be a symmetric, transitive relation. If $(x, y) \in R$ then the symmetric property implies that $(y, x) \in R$. Using the the transitive property upon $(x, y)$ and $(y, x)$ we can conclude $(x,... 2answers 39 views ### Transitive relation. I have read transitive relation, if$a\mathrel R b$and$b\mathrel Rc$then$a\mathrel Rc$. But suppose we have a set of first cousins. $$\mathrel R: \{(a,b),(a,c)\}$$ Where$a$,$b$and$c$are first ... 1answer 18 views ### Proving transitivity with Power Set Relation? I have this question and am having trouble proving transitivity for this: For every$n \in \mathbb{N}$let$\sim_n$be the relation on$\mathcal{P}([n])$specified by$A \sim_n B$if and only if$A \...
49 views

Let $A = \{1,2,3\}$. Write the ordered pairs for a binary relation R on A which is reflexive and symmetric, but not transitive. From my understanding is when listing if we want reflexive we need every ...
55 views

### Number of Antisymmetric Relations that are both Reflexive and Symmetric

I came across this question that tells us to validate the following statement- For every non-empty finite set X, there exists a unique antisymmetric relation on X that is both reflexive and symmetric ...
44 views

### Subtracting a relation from a set

I encountered the notation $A/ \sim_{N}$ where $(A, +)$ is an abelian group and $N \subset A$ is a subgroup. The relation $\sim_{N}$ on $A$ is defined by: $a\sim_{N}b \iff a-b \in N$. What exactly ...
42 views

A Relation $R$ is a strict total order on $A$ if the following are true for all $x,y \in A$: $(i) \hspace{.75in}\neg xRx \hspace{.75in} \text{(irreflexive)}\\ (ii) \hspace{.30in} xRy \wedge yRz \... 2answers 16 views ###$A = \{1; 2; 3; 4; 5; 6\}$and define$aRb$if a has remainder ≤ 1 when divided by b. Give the domain and range of$R$.$A = \{1; 2; 3; 4; 5; 6\}$and define$aR\mkern 1mub$if$a$has remainder ≤ 1 when divided by$b$. E.g.$4R\mkern 1mu3$since$ \ 4/3 \ $has a remainder of$1$, but not$2R\mkern 1mu5$since$2/5$... 1answer 40 views ### Show that a binary relation ($a \le b$) or ($a = b$and$c \leq d $) is an order relation I have to show that if there are$a + bi$,$c + di$where$a,b,c,d\in C$and$i=\sqrt(-1)$and also$a + bi \preceq c + di \iff (a <b)$or ($a=b$and$c \leq d$) the$ \preceq$is an order ... 1answer 19 views ### How do I prove or disprove these relation compositions? [closed] So I am not told if these statements are true or not (although they appear true). I am asked to either prove them in general terms, or disprove them with specific examples. I am confused about ... 1answer 16 views ### Composition of a Realtion with identity is the relation itself I am completely lost as to how to prove the following, although it appears straightforward. I know how this holds for functions, but how do I prove it specifically for relations? I need to provide a ... 4answers 46 views ### Let$R$be an equivalence relation on set$A$. Prove that for any$x,y \in A$either$[x] = [y]$or$[x] \cap [y] = \varnothing$. For any$x$and any$y(x,x) \in R$and$(y,y) \in R$(since$R$is reflexive) So there exist$[x]$and$[y]$equivalence classes for$R$. When$[x]$and$[y]$are equivalence classes of$R$then, ... 1answer 43 views ### Let$R$be an equivalence relation on a set$A$. Prove that if$y\in [x]$then$[x] = [y]$for any$x\in A$.$y \in[x]\to (x,y) \in R\to (y,x) \in R$(since$R$is symmetric)$\to x \in [y]$. Therefore $$\tag{1} y\in [x] \to x \in [y].$$ Let$x \in [y]\to (y,x) \in R\to (x,y) \in R$(sine$R$... 1answer 60 views ### If a relation is defined such that$R=\{(A,B)\mid A \subseteq B\}$then, I understand that, it's reflexive and transitive but is it symmetric. $$R=\{(A,B)\mid A \subseteq B\}$$$R$is assumed to be a relation on a collection of sets Since$A$is a subset of itself, the relation is reflexive. And if$A$is a subset of$B$which is, in turn, a ... 1answer 46 views ### Reflexivity of a relation$R$transfered to other relations Let$ R $be a relation on$ E $. Demonstrate that:$ R $is reflexive then$R \subseteq R.R$and$R$.$R$are reflexive too; Here is my work though confused about few steps:$R$.$R$= {$(x,y) | \...
During class we had to come up with relations that are reflexive, but are not transitive or similar. I know the definitions of these terms. If we have a relation defined by the triple $$r = (A, B, R)$$...