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
0answers
29 views

Proof for transitivity of $a-ab+b\le1$ [on hold]

Let $ R $ be a binary relation on natural numbers. We have: $$ aRb \Leftrightarrow a-ab+b\le 1 $$ Prove that $ R $ is transitive.
0
votes
1answer
23 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: ...
1
vote
1answer
30 views

Reflexive and transitive closure of a binary relation

If relation A is a binary relation between terms of the form (C,s), and relation B is the reflexive and transitive closure of A, could somebody briefly explain what it means to be a 'Reflexive and ...
1
vote
1answer
34 views

How do I determine whether this relation is transitive?

I've been given this relation, and I'm supposed to determine whether it is transitive. I understand the definition of transitive (sort of, in theory) but I'm not sure how to put it in action here. ...
0
votes
0answers
43 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
-1
votes
1answer
25 views

Transitivity of a binary relation on the power set

I'm studying for a test and there's a question that I've tried and I don't understand: Let $E$ be a binary relation on a set $A$; let a binary relation $F$ on $\mathcal P (A) \setminus ...
0
votes
1answer
21 views

Proving that divisibility in an integral domain is a partial ordering

Given that R is an integral domain. I'm trying to prove that divisibility on this set constitutes a partial ordering. In particular, I have defined the relation $y \leq_{\,d} x$ on R by $y|x$. ...
0
votes
1answer
22 views

What is the composition of the two given relations $R_1\circ R_2$?

I have a set $A = \{a,b,c,d\}$ on which two relations are $R_1=\{(a,b),(a,d),(b,c),(c,a),(c,d),(d,b)\}$ and $R_2=\{(a,b),(b,c),(d,c),(a,d),(a,c)\}$. What will $R_1\circ R_2$ be? $\circ$ is a the ...
2
votes
1answer
34 views

How do i determine whether a relationship is transitive and has the trichotomy property or not?

I have a relation on the set A {a,b,c,d}- R1={(d,c),(c,a),(b,d),(d,a),(a,a),(b,c),(b,a)} I need to determine whether this relation has the trichotomy property or not? P.S- If by any chance you do ...
0
votes
1answer
25 views

Denotation of composite of relations

We denote the composite of relation R and relation S by $S \circ R$. Since the order matters, meaning composite of R and S is not composite of S and R. I am trying to understand why the denotation of ...
1
vote
2answers
29 views

Is the relation $P$, for all real numbers $x$ and $y$ that satisfy $xPy $ iff $x^3 - y \ge y^3 - x$, a reflexive, symmetric and transitive relation?

Image of an exam question I am revising link: [1] For (i) I have stated the relation is reflexive as $\forall x ∈ \Bbb R, xPx$ is reflexive as $x^3 \ge x $ For (ii) I have stated that the relation ...
2
votes
1answer
22 views

Graph the straight line corresponding to the rule (y=7x) for 0≤x≤15

I have attempted this question but I don't really know where to even start. I have graphed y=7x but i'm not sure where to go from there. I am a bit stuck on graphing a line that is relating to 0≤x≤15. ...
-1
votes
1answer
22 views

Calculate the number of equivalence classes [closed]

Let $A = \{1,2,3,4,5,6\}$ and let $B = \{1,2,3\}$ Let $R$ be a relation such that $R=\{(x,y) \in P(A) \times P(A): x \cap B = y\cap B\}$ How many equivalence classes are possible? I'm kinda stuck ...
1
vote
1answer
29 views

Relation $ (x,y) \in \rho \Leftrightarrow (\exists k \in \mathbb{Z})\mid x- y=3k$

I know that there is a similar question here, but it's about classes of equivalence of this relation. I would like to know how to prove that this is an equivalence relation. It seems simple, but the ...
0
votes
1answer
23 views

Given two Numbers, Finding Relation to third

I'm trying to find the relation of three numbers. I know that two numbers have a relation that equate to the third. The tricky part is that they don't have to equal the third number exactly,but should ...
1
vote
2answers
24 views

How to find all relations of a set and determine which of them aren't functions?

Given the following question: "How many relations are there on {2, 3}, that aren't functions from {2, 3} to {2, 3}?" The answer gives 16 relations, of which 12 aren't functions. How did they ...
0
votes
1answer
20 views

How many reflexive relations on $P(A)$

There exist a set $A = \{1,2,3\}$. How many reflexive relations are there on $P(A)$? I don't even know how to begin (beside writting down the members of $P(A)$). Thank you
1
vote
1answer
35 views

What is the growth relationship of the number of digits a number has as numbers increase?

To clarify the question, since I'm sure the wording is awkward: In the decimal number system, to get from 1 digit to 2, it takes n=10 numbers. To get from 2 to 3, it takes 90 more numbers added to n. ...
1
vote
1answer
24 views

Calculate the number of equivalence relations $S$ that satisfies $R \subseteq S$

Let $A=\{1,2,3,4,5,6,7,8\}$ and let $R=\{(1,2),(5,4),(4,5),(6,2),(4,4),(6,5),(7,8)\}$ be a relation on A. What it the number of equivalence relations $S$ that satisfies $R \subseteq S$ I know what ...
0
votes
1answer
17 views

Is this relation symmetric?

While solving questions related to reflexivity, symmetricity and transivity of relations, I came across this question: Show that the relation $R$ in the set $A = \{1,2,3\}$ given by $R = ...
0
votes
2answers
34 views

Total Number of Equivalence classes of R

I was given the following question for homework: Let P denote the set of all compound propositions involving the simple/atomic propositions p, q, and r and the logical connectives ∨, ∧, and ¬ ...
2
votes
1answer
21 views

If A is the range of $f(x) = ^{7-x}C_x$ then the no. of reflexive relation from A to A is…

Problem : If A is the range of $f(x) = ^{7-x}C_x$ then the no. of reflexive relation from A to A is (a) $2^6$ (b) $2^{12}$ (c) $2^{16}$ (d)$2^{20}$ My approach : $f(x) = ^{7-x}C_x = ...
1
vote
1answer
27 views

Prove that $\sigma^*$ is the least group congruence on $S$

Let $S$ be an inverse semigroup and consider the relation $\sigma$ on $S$ given by $$a \sigma b \iff ab^{-1} \in E(S)$$ Consider the congruence generated by $\sigma$, say $\sigma^*$. Prove that ...
0
votes
1answer
10 views

Are any two pairs in a cyclic path of a transitive relation symmetric?

Suppose $R$ is a transitive binary relation that contains a cycle $a_1Ra_2$, $a_2Ra_3$, $\dots$, $a_{n-1}Ra_n$, $a_nRa_1$. Does this imply that $R$ is symmetric for any pairs in this cycle, i.e. ...
1
vote
1answer
27 views

given definition of a relation $R$, prove that $R$ is an Equivalence Relation

The relation is on set $\mathbb{R}^\mathbb{R}$ and the definition of the relation $R$ is: $f \mathop{R} g \iff \exists _{y\in \mathbb{R}} \forall_{x\in \mathbb{R}}\ ((x>y)\to(f(x)-g(x)\in ...
0
votes
2answers
19 views

Relation of equivalence with sgn

Test if the relation $$(x, y)ρ(a, b)\Leftarrow\Rightarrow sgn(y+\pi x) = sgn(b + \pi a)$$ is a relation of equivalence on $R^2$ and if so, determine the quotient set and $C_{(2, \pi)}$. Also, ...
0
votes
0answers
102 views

Is there any partial order that extends $\delta$?

Let $M = \{(x_n)_{n\ge1} | x_n \in \mathbb Z, \forall n \in \mathbb{N}^{*}\}$ We define relations $\delta$ and $\sim$ on $M$ as: $(x_n)_{n\ge1}\ \delta\ (y_n)_{n\ge1} \iff \forall n \in ...
0
votes
1answer
57 views

Whether Subset of a Power Set is a Lattice?

$A=$ countably infinite set $p(A)=$ power set of $A$ $p(A)$ is uncountably infinite I have this question as book i am using explicitly mentioned it as A:finite set now, poset $(P(A)$,subset) is it ...
1
vote
0answers
39 views

Topology given by a relation

I have a problem with creating an equivalence relation ~ in a set : $ S^{1}\times S^{2}$ so that $ (S^{1}\times S^{2})/$~ (a quotient space of the given relation) is homeomorphic to 3-dimensional ...
-2
votes
1answer
33 views

Compositions of Sets 2 [closed]

Given set A = {a, b, c} relation R = {(a,b),(b,c),(c,a)} relation S = {(a,c),(c,a)} ...
2
votes
1answer
78 views

Which of the sets are well ordered? Which ones are isomorphic?

I'm new to StackExchange and I'd like to ask you for help. I have been trying to solve this exercise: $$A = \left\{3 - \frac{1}{2n} : n \in \mathbb{N} - \left\{ 0 \right\} \right\}$$ $$ B = \left\{ ...
1
vote
1answer
25 views

Relation of divisibility - hasse diagram

$A = \{3,4,5,10,15,20,30,60\}$ Relation $R: \forall x,y \in A : (x,y) \in R \Leftrightarrow y \mid x $ Here is my Hasse diagram Is my Hasse diagram drawn correctly?
1
vote
5answers
38 views

Proving a relation on Z×(Z-{0}) is an equivalence relation

Question:Let $X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$. Define a relation $\sim$ on $X$ by declaring that $(a, b)\sim(c, d)$ if and only if $ad = bc$ Prove that the relation $\sim$ is an ...
0
votes
0answers
47 views

Relations Question

I have some trouble understanding relatons. Below there is a question that I am working on. I believe that the a) part its correct but I have no idea how to do the b) and c) As part of a computer ...
2
votes
1answer
32 views

Find the domain and image of the relation $R=\{(a, b), (c, b), (a, b)\}$

Let $A={a, b, c}$, and let $R=\{(a, b), (c, b), (a, b)\}$. Find the domain of $R$ and the image of $R$. This would be very elementary, but I want to get my answer checked. Let $R$ be a relation ...
3
votes
5answers
493 views

example of a relation that is symmetric and transitive, but not reflexive

Can you give an example of a relation that is symmetric and transitive, but not reflexive? By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$. $R$ ...
1
vote
3answers
30 views

Intrepreting tuples as functions

I have been mulling over this for a while now. I am told $\mathbb R^n$ can be interpreted as a set of functions. Take $\mathbb R^2$, for example I can see how we might interpret it as a set containing ...
-2
votes
3answers
49 views

Find the equivalence classes for $a T b \iff \frac a b \in \Bbb Q$

Given the set $S = \{ x − \sqrt 5 y : x,y \in \Bbb Q, \ x − \sqrt 5 y \ne 0 \}$, assume the relation $T$ is defined on $S$ by $a T b \iff \frac a b \in \Bbb Q$. How can I find the distinct ...
5
votes
5answers
504 views

Example of a relation that is reflexive but not symmetric

By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$, and $R$ is symmetric if and only if $x\,R\,y\implies y\,R\,x$. I think $x\,R\,x$ can also be ...
0
votes
3answers
56 views

Equivalence relation and Distinct equivalence classes

Given the set $S = \{x-y \sqrt5: x, y$ are rational numbers and $x-y \sqrt5 \neq 0\}$. Assume the relation $T$ is de fined on the set $S$ by $a T b$ if $a/b$ is a rational number. Question has ...
2
votes
1answer
77 views

Finding distinct equivalence classes

Q: Given the set $S = \{x - y\sqrt 5 : \text{x, y are rational numbers and }x - y \sqrt5 \neq 0 \}$. Assume the relation defined on the set $S$ by $a\ T\ b$ if $a/b$ is a rational number. Find ...
1
vote
2answers
37 views

Transitive relation

Consider $A$ is a relation de fined on $R$ (real numbers) where $A = \{(a,b):|a-b|<4, a, b \in R\}$. Prove/disprove $A$ is transitive. I know if $|a-b|<4$ and $|b-c|<4$, then, ...
0
votes
3answers
46 views

Equivalence relation: $aRb$ iff $2a+3b$ is divisible by $5$

Prove that $R$ is an equivalence relation: $aRb$ iff $2a+3b$ is divisible by $5$. Here $a,b\in \mathbb{Z}$ (set of integers). I can prove that $R$ is reflexive and transitive. How to prove it's ...
0
votes
2answers
36 views

What does the last condition in the following corollary about monomial orderings mean?

In class, I was given the following useful corollary in judging whether a given ordering ">" is a monomial ordering or not. Let > be a relation on $\mathbb{Z}_{\geq 0}^n$ that satisfies i) > ...
5
votes
1answer
38 views

Counting Subsets of a relation $\mathcal R$

I'm studying for my discrete math final and my professor gives us practice questions but no solutions. Counting is not my forte so I was hoping you could check over my work, make sure my end result is ...
0
votes
0answers
25 views

E1 and E2 are equivalent then they are “almost equivalent”

Given : 2 statements E1, E2 in relational algebra are "almost equivalent" if every phase in the database D ,except finite number of D's E1(D)=E2(D). E(D) means the result of activating the statement E ...
0
votes
1answer
15 views

Extending relation to be transitive

I am lookign for an easy "algorithm" to extend relation (add some elements to it) to be transitive, say I use matrix representation of relation is there any trick that can help me to say if it is ...
1
vote
2answers
21 views

Find transitive relations

Is this relation on $A$ transitive? I know that the relation is reflexive and symmetric but I can not tell if it's transitive. $\mathcal R =\{(a,a), (a,b), (a,c), (b,a), (b,b), (b,d), (c,a), (c,c), ...
0
votes
1answer
41 views

Suppose that $R_1$ and $R_2$ are reflexive relations?

I need some help with this problem, Suppose that $R_1$ and $R_2$ are reflexive relations on a set $A$. Show that $R_1 ⊕ R_2$ is irreflexive?
3
votes
2answers
29 views

Symmetric & Transitive Sets

Let $A={a,b,c,d,e,f}$ and let $R\subset A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is that the following ...