This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

0
votes
1answer
21 views

Describing equivalence classes over the set of natural numbers

So for this problem we are supposed to describe the equivalence class for the following relation. $x \thicksim y$ iff $x$ mod 2 = $y$ mod 2 and $x$ mod 4 = $y$ mod 4. I am confused on what is meant ...
1
vote
1answer
30 views

verifying properties of relations to test equivalence

We are doing some more with relations and this time we are given a relation and told that it is not equivalent. We need to find out which property it does not fulfill. So we at least know there is ...
1
vote
2answers
25 views

Determining whether a relation is transitive or not.

While trying to determine whether the following relations are transitive or not, I got stuck in between. The following are the two relations - Relation R in the set $\mathbb{N}$ of natural ...
3
votes
3answers
268 views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
1
vote
1answer
24 views

Equivalence Relation on the set of ordered pairs of positive integers

Have a homework question, but how can I show that the given relation R is reflexive, symmetric and transitive, so that it is an equivalence relation. Appreciate assistance from anyone. "Let R be the ...
0
votes
4answers
142 views

If $R=\{(x,y): x\text{ is wife of } y\}$, then is $R$ transitive?

If $R=\{(x,y): x\text{ is wife of } y\}$, determine whether the relation $R$ is transitive or not. My Try: For Transitivity, If $(a,b) \in R$ and $(b,c)\in R\;,$ Then $(a,c)\in R.$. Here If $x$ ...
0
votes
1answer
23 views

Is this relation P an equivalence relation or a partial order relation?

I am having trouble with partial order and equivalence relations. I was wondering if someone can guide me through this problem. Let $Σ$ be the set of letters {$a, b, . . . z$}. Let $Σ^∗$ be the set ...
0
votes
1answer
31 views

Help with equivalence classes for $x\sim$y iff $x-y\in\mathbb{Q}$.

Help with equivalence classes for $x\sim$y iff $x-y\in\mathbb{Q}$. I need to show the equivalence classes for $[0]_{\sim}$ and $[\sqrt{2}]_{\sim}$. Here is what I did: $[0]_{\sim}$ = ...
0
votes
1answer
28 views

Find transitive closure of $D_r = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid |x - y| = r\}$

This is one of the problems I have been solving in Velleman's How to prove book: Find the reflexive, symmetric and transitive closures of the following relations: $D_r = \{(x,y) \in ...
2
votes
1answer
35 views

how to prove that a relation is antisymmetric?

I have this question that I didn't know how to prove it and need your help. $R$ is a transitive and not reflexive relation on $A$. Prove that $R$ is antisymmetric. I tried to apply the definition of ...
-1
votes
1answer
37 views

Covering relation over functions

F is a group that includes all functions from N to N K is relation over F. For f,g ∈ F: (f,g) ∈ K iff ∀ n∈N, f(n)≤g(n). Obviously K is Partially ordered set and not Total Order. My problem is with ...
2
votes
1answer
24 views

The equivalence relation generated by a relation

Let $X$ be a non-empty set and let $r\subseteq X\times X$ be a relation on $X$. Let $R$ be the intersection of all equivalence relations on $X$ that contain $r$. Prove that if $xRy$, then one of the ...
0
votes
1answer
16 views

Equivalence Relations Reflexivity

Consider the relation on $\bf{R}$ defined by $n \simeq m$ if $(n-m)\in \bf{R}$ To say this is reflexive, I can say: Let $n\in \bf{R}$ and since $n-n = 0$ and $0 \in \bf{R}$ Then $n \simeq n$.
0
votes
1answer
29 views

Find transitive closure of the relation, given its matrix

Find transitive closure of relation $R$ described by the matrix $M_R$: $$M_R = \begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$ I tried doing it like this ...
0
votes
1answer
23 views

Make the set $R$ transitive

Let $R$ be a relation on a set $A=\{w,x,y,z\}$ defined by $R=\{(w,x),(y,x),(x,y),(z,z)\}$. Using the original relation, $R$, make the necessary minimal additions to make $R$ transitive. I thought ...
1
vote
1answer
42 views

Partial order relations and posets

Suppose you are given to prove this question: Let $P=\{2,3,4,\ldots,10\}$. Define $\le$ by $a\le b$ if and only if $a\mid b$, i.e, $a$ divides $b$. Prove that it is a partial order on $P$. I think ...
2
votes
3answers
90 views

Determining if a relation is reflexive, symmetric, or transitive [closed]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
0
votes
2answers
44 views

binary relations

I am having a hard time understanding some things dealing with these relations. The five relations we are dealing with are reflexive, symmetric, transitive, irreflexive, and antisymmetric. $R$ is ...
0
votes
2answers
57 views

Proof of every asymmetric relation is irreflexive

I came across a question as follows: Show that every asymmetric relation over a set $A$ is irreflexive. The solution instructs one to use the relation < and suppose that it is asymmetric but not ...
1
vote
1answer
46 views

Properties of binary relations

I am so lost on this concept. We are doing some problems over properties of binary sets, so for example: reflexive, symmetric, transitive, irreflexive, antisymmetric. This particular problem says to ...
3
votes
1answer
44 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
0
votes
1answer
23 views

Defining a relation on a set with conditions

Define a relation R on R (All Real Numbers) as follows: For all real numbers x and y mTn if and only if 3 | (m - n). I'm not sure what the vertical bar here means. Normally it means "such as" but ...
0
votes
1answer
47 views

Defining A Binary Relation On All Real Numbers

Define a relation R on $\mathbb R$ (Set of all Real Numbers) as follows: For all real numbers $x$ and $y$, $x \mathrel{R} y$ if and only if $x = y$. Since the set of all real numbers is infinite, how ...
0
votes
1answer
16 views

Prove that the relation $R = \{(f,g)\in F \times F \mid \exists h \in P:(f = h^{-1}\circ g\circ h)\}$ is reflexive.

Prove that the relation $R = \{(f,g)\in F \times F \mid \exists h \in P:(f = h^{-1}\circ g\circ h)\}$ is reflexive, where $F = \{ f \mid f : A \to A\}$ and $P = \{f\in F \mid f\text{ is one-to-one ...
1
vote
1answer
37 views

Interpret a relation definition, it's meaning and and how it should be applied

I'm unsure of the definition below : $\mathbb{Z} = (\dots,-2,-1,0,1,2,\dots)$ Take a relation $\rightarrow$ on $\mathbb{Z}^2$ define as $(x,y)$ $\rightarrow$ $(x',y')$ only when: $(x',y')= ...
1
vote
2answers
25 views

Is transitive closure defined uniquely?

I'm encountering questions where I'm required to find a transitive closure (and the questions seem to suggest that there is only one), but I probably don't understand something in the definition, ...
-2
votes
2answers
27 views

Prove tautology by using boolean laws $\neg q \to \neg(q\wedge(p\to\neg q))$

$$\neg q \to \neg(q\wedge(p\to\neg q))$$ Please help me to prove if it's tautology or not by using the logic law.
0
votes
0answers
21 views

Show that the relation R is reflexive on R(two)

Problem: Let $S$ be a relation on the set of $\mathbb R \times\mathbb R $ such that the relation is defined to be $(a,b)\ R\ (c,d)$ if $b = d.$ I am having issues showing that $S$ is reflexive. I ...
0
votes
2answers
42 views

Help Showing a Relation is/isn't a Partial Order

Define the relation $\le$, as $(a,b)\le(c,d)$ if and only if $a+b\le c+d$ and $a\le c$. Is this a partial order? I know it's definitely not if we remove the $a\le c$ (because then it's not ...
1
vote
1answer
46 views

Is a total order compatible with a partial order?

I was given the following multipart problem. Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; ...
1
vote
1answer
57 views

Which of the following relations on the set of all people are equvilance relations?

Determine the properties of an equivalence relation. I'm not sure if I am understanding this correctly. A. $\{(a,b)|\ a$ and $ b$ are the same age$\}$ B.$\{(a,b)|\ a$ and $ b$ have the same ...
0
votes
2answers
27 views

Prove $(n,m)R(r,s) \equiv (n>r) \text{ or } (n=r \text{ and } m\geq s)$ is an order relation.

Prove $(n,m)R(r,s) \equiv (n>r)\text{ or } (n=r\text{ and } m\geq s)$ is an order relation. So I have to prove reflexivity, antysimmetry and transitivity. I could prove reflexivity but I'm having ...
1
vote
1answer
55 views

If there are Predicates before Predicate Calculus, why is it called such?

In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False" Well, propositional calculus comes before predicate calculus, and ...
0
votes
2answers
32 views

How do I find a partition of an equivalence relation?

Say I have the function: $$x\,R\,y \iff y = 3^k$$ for some $k \in \mathbb Z$ and the set is: $$A = \{1,1/3,1/27,1/4,3,1/36 , 2,2/9,9/4, 5\}$$ So in this scenario, how do I find the partitions of the ...
0
votes
1answer
23 views

Relations and Equivalence Sequences

A relation is defined on the set $A=\{a + b\sqrt{2} \; : \; a, b \in \mathbb{Q} \text{ and } a + b\sqrt{2} \neq 0\}$ by $xRy$ if $x/y$ is in $\mathbb{Q}$. Show that $R$ is an equivalence relation and ...
0
votes
1answer
19 views

Equivalence Classes points on the plane

I'm confused about the topic of equivalence classes. $x=(a,b) , y=(c,d)$ are points on the plane. $xRy$ iff: 1) $a+b = c+d$ 2) $a^2-b = c^2-d$ 3) $a=c=5 , b=d=20$ 4) $a^4+b^4 = c^4+d^4$ For each ...
0
votes
1answer
20 views

Relations equivalence

$f) x^2-5x+6=y^2-5y+6$ $g) x^2+y^2=1$ Decide whether or not it’s a reflexive, symmetric, transitive and equivalence relation. If R is an equivalence relation, describe the equivalence classes. I ...
0
votes
1answer
22 views

Does a statement have to be true for all conditions to be transitive,symetric,reflexive?

I'm trying to determine if the following are symmetric, reflexive, transitive, equivalence for all-natural numbers but am struggling because they aren't in set notation. Examples of confusing ...
1
vote
1answer
30 views

Prove if $x$ is greatest lower bound of $U$ then $x$ is the least upper bound of $B$

This is one of the problem I have been solving from Velleman's How to prove book; Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Let $U$ be the ...
1
vote
2answers
34 views

Antisymmetric Relation: How can I use the formal definition?

So I can determine whether a certain relation is antisymmetric, by using a digraph. My understanding through a digraph is that if there is only 1 way streets and/or loops between edges, it's ...
0
votes
1answer
22 views

Complementary Relation Proof

If $R$ is reflexive, prove that $R^c$ is irreflexive. If $R$ is asymmetric, prove that $R^c$ is reflexive. Where $R^c$ = complement of $R$. I just can't figure out anything to say for the first one ...
-4
votes
1answer
59 views

How to figure out how many entries are in a relation

I have the domain $A = \{1, 2, \ldots , 1000\}$. I need to figure out how many non zero entries are in each relation: a. $R_1 = \{\;(a, b) \;|\; a \le b\;\}$ b. $R_2 = \{\;(a, b) \;|\; a + b = ...
1
vote
2answers
60 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
1
vote
4answers
220 views

Is this relation transitive, reflexive, symmetric?

I am having a hard time identifying transitive relations. I think I understand those that are symmetric, but do correct me if I'm wrong. For a set $S = \{0,1,2,3,4\}$ and a relation $Z = ...
2
votes
1answer
38 views

In a transitive relation does x and z have to be the same element?

I am new to relations on sets and am trying to get my head around transitive relations. I understand the definition of $(x,y) \in R, (y,z) \in R$ and $(x,z) \in R$ However what i am not sure about ...
1
vote
1answer
68 views

Find if relation is reflexive, symmetric or transitive

Let $A = \{1, 2, 3, 4\}$ and let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by "For all $f, g$ in $F$, $(f, g)$ in $R$ if and only if $f (i) = g (i)$ for ...
1
vote
1answer
26 views

Which of these relations are maps?

List all relations $\{a,b\} \to \{c,d\}$, assuming $a \neq b$ and $c \neq d$. Which of them are maps? So I know the cartesian product gives $\{(a,c),(a,d),(b,c),(b,d)\}$. And the relations will be ...
7
votes
4answers
841 views

“$ x $ is a brother of $ y $.” Why is this not transitive?

I am working on a problem set at the moment, and while checking my answers I realized that I have listed "x is a brother of y" as a transitive relation, while the answers say that it is not. EDIT: I ...
0
votes
2answers
49 views

How do I prove this? (Relations Proof)

So I can't seem to figure out how to prove this. Any help would be greatly appreciated. My professor said a contradiction would work but I don't see where I can make a contradiction. Show that {X ...
1
vote
1answer
42 views

Meaning of at least as late in the alphabetical order

I'm working some problem in Velleman's How to prove book and is faced with a set in it which goes like this: $R1 = \{(x,y) \in A \times A \mid \text{the word $y$ occurs at least as late in ...