# Tagged Questions

35 views

### Proving theorems on relations

I came across the following three statements about relations. I understand why the statements are true, but I am not sure how to demonstrate them mathematically. In the following, $A,B$ are sets and ...
27 views

### If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
15 views

### How do I derive a contradiction from an assumption that is “not asymmetric”

Let $R$ be a transitive relation on a set $A$. Define another relation, $S$, such that, for any $x,y \in A$, $Sxy$ iff $Ryx$. Moreover, let $S$ be irreflexive. Prove: $S$ is asymmetric on $A$. ...
30 views

### Need help with compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R1 \circ R2) \circ R3 = R1 \circ (R2 \circ R3)$ I don't know where exactly to ...
37 views

### Equivalence relations and power sets.

Let $\mathcal{A}$ be the class of all sets and define the relation $R$ on $\mathcal{A}$ as: $A\space R\space B$ iff there is a bijective function $f:A \to B$. Prove that $R$ is an equivalence relation ...
70 views

### Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$.

Question: Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$. My attempt: By definition 6.23,6.3.1, and ...
77 views

### Proving the dual and self-dual of a poset.

The dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$ if and only if $y \geq x$. A poset is self-dual if it is isomorphic to its dual. Questions: Verify ...
366 views

### Composite Relations - Give Examples of relations $R_1$ and $R_2$ such that $R_2 \circ R_1 = R_1 \circ R_2$ and $R_2 \circ R_1 \neq R_1 \circ R_2$

Let $S =[a,b,c]$. Give examples of a. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 = R_1 \circ R_2$ b. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 \neq R_1 \circ R_2$ My ...
59 views

### Class Transitivity Proof

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$. I know that I need to begin by proving the first statement implies ...
114 views

### Give proofs by induction for the following relation properties.

Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all ...
70 views

### Proof of “relations $R$ and $S$ are symmetric $\Rightarrow R \cap S$ is symmetric”

Claim: If the relations $R$ and $S$ are symmetric, then $R \cap S$ is symmetric Proof: Let $R$ be the relation of congruence modulo 10 and $S$ the relation of congruence modulo 6 on the integers. ...
17 views

### Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
306 views

### Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$.

Hello I need help with the proof strategy for this problem. Let $R$ be an equivalence relation on a set $A$ and let $a,b \in A$. Prove that $[a] = [b]$ if and only if $aRb$.
132 views

251 views

### Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.

Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive. First, I'm wondering if my proof is correct? Second, I'm really ...
86 views

### Is this a correct proof for this relation?

I feel like I am being too brief and maybe incorrect on my proof by contradiction for transitivity/antisymmetry. So is this proof flawed in any way? A relation R on the set of positive integers is ...
319 views

### Is cancellation of Cartesian product possible? I think so, but am having trouble with the proof…

So, Is a cancellation possible for the Cartesian product? ex. if you have two Cartesian products that are equal to eachother, do the 2nd sets for each product equal eachother? Lets say you have ...
150 views

This one is from Velleman's "How to Prove It, 2nd Ed.", exercise 4.3.23. Suppose $A$ is set, and $\mathcal{F}\subseteq\mathcal{P}(A)$. Let $$R=\{(a,b)\in A\times A : \text{for every } X\subseteq ... 2answers 203 views ### Does complementary relation(\overline R) is transitive? Let R be a relation that is transitive. Does complementary of R (\overline R) is transitive?(\overline Ris hold transitive) 3answers 3k views ### Prove that the intersection of two equivalence relations is an equivalence relation. I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose R and S are two equivalence relations on a set A. Prove that R ... 4answers 481 views ### Proving reflexivity, symmetry and transitivity on a relation. I am trying to see if the following relation is reflective, symmetric and transitive: (i, j),(k, l) are in relation R if: (i < k \land  k \le j \le l) \lor (k < i \land i \le l \le j ... 1answer 1k views ### Proving that if a relation is reflexive, the composition of that relation and itself is also reflexive. Here's the question: Prove or give a counterexample to the statement: If R is a reflexive relation on A, then R \circ R is also a reflexive relation on A. I completely understand how it ... 1answer 145 views ### Proof that (x,y)\sim (x',y') \iff x=x' , y-y'=n2\pi where n\in\mathbb Z is an equivalence relation? Have I made any mistakes in the following proof? THEOREM: If P=\{(x,y)\in\mathbb R^2|x>0 \} and if there exists a relation$$\sim|(x,y)\sim(x',y') \iff x=x' , y-y'=n2\pi where $n\in\mathbb Z$ ...
Define a relation $R$ on $\mathbb{Z}$ by $R = \{(a,b)|a≤b+2\}$. (a) Prove or disprove: $R$ is reflexive. (b) Prove or disprove: $R$ is symmetric. (c) Prove or disprove: $R$ is transitive. For ...
### Is this relation transitive if $n=m$?
If $X$ is a set and $n \in \mathbb N$, then $[X]^n$ will denote the set of all subsets of $X$ with exactly $n$ elements. For a set $X$ and natural numbers $n$ and $m$ define a relation $R$ on $[X]^n$ ...