Tagged Questions

2
votes
3answers
77 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
28 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
35 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
58 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
77 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
94 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
66 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
328 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
184 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 ...
1
vote
3answers
254 views

How to show that two equivalence classes are either equal or have an empty intersection?

For $x \in X$, let $[x]$ be the set $[x] = \{a \in X | \ x \sim a\}$. Show that given two elements $x,y \in X$, either a) $[x]=[y]$ or b) $[x] \cap [y] = \varnothing$. How I started it is, if ...
0
votes
1answer
294 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
110 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
104 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
85 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$ ...