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
18 views

Find transitive closure of $D_r$

This is one of the problem I have been solving in Velleman's How to prove book: Find the reflexive, symmetric and transitive closures of the following ...
2
votes
1answer
22 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
28 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
20 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
15 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
32 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
44 views

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

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
30 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
26 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
22 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
35 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
18 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
39 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
11 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
32 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
20 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
23 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
17 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
35 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
27 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
29 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
25 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
44 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
26 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
21 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
17 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
17 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
26 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
21 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 ...
-1
votes
0answers
19 views

Meaning of Square and cube of matrix of relation

Let a stand for the airport in the city of Manchester, let b stand for the airport in Boston, c stand for the Chicago airport, d for the airport in the city of Denver. $M_R$ =$\matrix{&a & b ...
0
votes
1answer
20 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
52 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
52 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
171 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
34 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
47 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
25 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
754 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
46 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
35 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 ...
0
votes
2answers
22 views

Transitivity of a relation

If a relation contains (a,b) and (a,c), in order for it to be transitive, is (b,c) required, or is (c,b) also required? In my mind, it should require both (b,c) and (c,b), but I'm not certain.
0
votes
1answer
42 views

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric.

Given the relation $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}\,$ determine whether it is reflexive, transitive, symmetric, or anti-symmetric. I found this set to be reflexive and symmetric. But not ...
1
vote
1answer
23 views

Asymmetric Relation Confusion

$A = \{1, 2, 3, 4\}, R \subset A \times A$ Why is $\{(1,1),(2,2),(3,3)\}$ an asymmetric relation? $(a,b)$ where $a=b$ must come under symmetric relation.
6
votes
1answer
23 views

How to determine an ordering relation?

I would like to determine an ordering relation: We are given a linear order on $\mathbb{N}$ $\leq'$ for all $m,n$ such that $ n\leq' m$ $\iff$ (n is odd and m is even) or ($n$$\leq$$m$ and $m-n$ is ...
2
votes
1answer
143 views

If a relation is to be reflexive, symmetric, transitive, etc., do the properties need to be satisfied by all values?

I want to know if different scenarios in relations must satisfy all the value in the relation. In mathematical relations, a given set relation is reflexive if all the elements in the set exhibit ...
1
vote
1answer
34 views

How can we get the approximate values $a,b,c$?

How can we get the approximate values $a,b,c$? The condition and relation are the followings : $0 < a,b,c < 1$ $a + b + c = 1$ $(1-a)^2 + b^2 + c^2 =1 $
7
votes
4answers
223 views

How to find the appropriate equivalence class?

I would like find the system of representatives & equivalence class for $[(1,-1)]_{\equiv 1}$ and $[(1,-1)]_{\equiv 2}$ given: $R_1=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow ...
0
votes
1answer
24 views

Finding smallest set of real numbers according to a property

This is one of the example problem that has been solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x ...