0
votes
1answer
34 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 ...
1
vote
2answers
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: ...
0
votes
1answer
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$. ...
0
votes
1answer
29 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 ...
0
votes
1answer
36 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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
-1
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
0
votes
1answer
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, ...
0
votes
2answers
304 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$.
1
vote
3answers
131 views

Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$

The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if $$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$ and it is antireflexive if $$\forall a\in ...
4
votes
2answers
46 views

$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$ If R is symmetric, must S be symmetric?

I'm working on an exercise from How To Prove It by Velleman, and I'm having a hard time. Suppose $R$ is a relation on $A$ and define a relation S on $\mathcal{P}(A)$ as follows: $$S=\{(X,Y) \in ...
2
votes
1answer
249 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 ...
1
vote
1answer
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 ...
1
vote
2answers
316 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 ...
3
votes
1answer
147 views

Prove transitivity of $\forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))$

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 ...
-2
votes
2answers
196 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 R$is hold transitive)
3
votes
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 ...
1
vote
4answers
477 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 ...
0
votes
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 ...
1
vote
1answer
144 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$ ...
3
votes
2answers
147 views

Prove whether a relation is an equivalence relation

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 ...
2
votes
1answer
88 views

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$ ...