1
vote
1answer
54 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
56 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
336 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 ...
3
votes
0answers
26 views

Proofs involving definitions of Well-Defined and One-to-One

Chartrand, 3rd Ed, P224-225: Define a relation $R$ as a relation from A to B. $R$ is well-defined means: $(a,b), (a,c) \in R \implies b = c$. P220: A function $f: A \to B$ is one-to-one ...
0
votes
3answers
50 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
113 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
62 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
248 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$.
2
votes
3answers
116 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
45 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
211 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
81 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
284 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
134 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
172 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)
2
votes
3answers
2k 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 ...
0
votes
4answers
450 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
142 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
141 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$ ...