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
2answers
28 views

Can this relation be transitive but not symmetric and reflexive?

Let $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$. Give an example of a relation $T$ on $A$ with at least three elements that is not reflexive, not symmetric, but transitive. Explain clearly why ...
0
votes
2answers
41 views

Show that the function $f:\mathbb{Z} \rightarrow \mathbb{2Z}$ by $f(a)=a^3+3a+2$ is not onto

If the function $f:\mathbb{Z} \rightarrow \mathbb{2Z}$ by $f(a)=a^3+3a+2$, then show that $f$ is not onto. Hint: Show that $f(a)\neq 0$. I have a feeling I have to use the root theorem test, but I ...
3
votes
1answer
41 views

Does type-theory have a concept of “relation”?

Set theory cares about sets and relations. And then functions are relations betweens sets of inputs and outputs. Type theory, on the other hand, seems to say that there are no formal ideas of ...
0
votes
1answer
15 views

Prove that the relation $f$: ($\mathbb{Z^*} \times \mathbb{Z^*}$) $\rightarrow$ $\mathbb{Q}$ by $f(a,b)$ = $\frac{a+b}{a+b-3ab}$ is a function

Prove that the relation $f$: ($\mathbb{Z^*} \times \mathbb{Z^*}$) $\rightarrow$ $\mathbb{Q}$ by $f(a,b)$ = $\frac{a+b}{a+b-3ab}$ is a function I believe that f is a function and I am attempting to ...
0
votes
1answer
30 views

Is $f:\mathbb{Q^*} \rightarrow \mathbb{Q}$ by $f(\frac{a}{b}) = \frac{\max{(a,b)}}{\min{(a,b)}}$ a function?

Suppose that the relation $f:\mathbb{Q^*} \rightarrow \mathbb{Q}$ by $$ f \Bigl(\frac{a}{b} \Bigr) = \frac{\max{(a,b)}}{\min{(a,b)}} $$ is defined. Then is $f$ a function? If so, how would we prove ...
0
votes
0answers
15 views

Question Concerning a General Method to Show that a Relation is Not a Function

When showing that a relation is not a function, is there an efficient method for finding particular preimages that are mapped to more than one image, rather than attempting to find particular ...
3
votes
2answers
27 views

why are equivalence relations called so?

"an equivalence relation is the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of ...
2
votes
0answers
21 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
2
votes
1answer
21 views

Calculate transitive closure of a relation

I am trying to understand how to calculate the transitive closure of a set and I have read several times the definition of the transitive closure but I still cannot understand some answers I see when ...
0
votes
2answers
33 views

Why is this an equivalence relation, and what does the equivalence classes contain?

I'm doing some discrete mathematics exercises, but I can't seem to wrap my head around this relation: $$R(x, y) \text{ if } \exists z(\text{LiesInPart}\circ\text{LiesInCountry}(x,z) \wedge ...
2
votes
1answer
29 views

Order relations and counting the number of cases (Fubini numbers)

I have $n=2$ numbers $a$ and $b$, $a\in\Bbb{N}$ and $b\in\Bbb{N}$. Then I have the function $f$ defined as: $ f(x,y) = \begin{cases} -1, & \text{if $x<y$} \\ 0, & \text{if $x=y$} \\ +1, ...
1
vote
1answer
26 views

Binary Relations - Reflexive, Symmetric, Transitive and anti symmetric

$R$ is defined on $P(N) − \{\varnothing\}$ by $ARB$ if and only if $A \cap B \ne \varnothing$ Identify if the relation is reflexive, symmetric, transitive and anti symmetric Finding it hard to work ...
0
votes
1answer
15 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
13 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
19 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
96 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
16 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
3answers
96 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
17 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
25 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
23 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
25 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
31 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
21 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
19 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
17 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
36 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
48 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
31 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
36 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
23 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
36 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
19 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
40 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
13 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
23 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
24 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
20 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
36 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
30 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
33 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
45 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
28 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
22 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 ...