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

1
vote
1answer
17 views

Relation and proving reflexivity

The relation R is defined on integers by $xRy$ if and only if $x^2y=ymod6$. Prove that $R$ is reflexive. So far I have: Let $x=y$ $x^2x=xmod6$ I don't know how to go from here... because ...
0
votes
1answer
24 views

Relations and equivalence classes example

I'm studying discrete mathematics in my course at university and I'm going through notes on relations, equivalence relations and classes and such. I've come across an example on equivalence classes ...
0
votes
1answer
23 views

Initial condition for recurrence relation

I have a question regarding the solution of this problem. The problem is: Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we ...
1
vote
1answer
27 views

How can an antisymmetric relation be not reflexive? [duplicate]

Reading a book (I do not know if I can mention its title) I found these definition (the following is exactly the quotation from the pages of the book): "For a binary relation R on a set Y, that is, ...
0
votes
1answer
56 views

Equivalence Relations on Products

Let $G$ be a group, $p$ a prime dividing $|G|$ and $X = \{(x_0,..., x_{p−1})) ∈ G_p:∏_i x_i = 1\}.$ Let $E$ be the relation defined on $X$ by $(x_0, ..., x_{p−1})E(y_0,..., y_{p−1})$ if there exists ...
1
vote
2answers
50 views

Which of the following are partitions of $\mathbb R^2$

Is my answer correct? Can someone provide me better explanations for (a) ,(c) and (d)? Which of the following collections of subsets of the plane $\Bbb R\times\Bbb R$ are partitions? $(a)$ ...
1
vote
1answer
18 views

How do find if a relation is a function algebraically

Is there a way to see if a relation is a function without having to do a "vertical line test" (where you draw a vertical line on the graph and if there line touches two points then it's not a ...
0
votes
0answers
57 views

Prove that any relation that is a partial order / equivalence is identity relation

Prove that any relation that is both an equivalence relation and a partial ordering is the identity relation. That is, if X is a set and R is a relation on X that is both a partial ordering and an ...
0
votes
0answers
52 views

Relation on a set of relations with these limitsprove equivalence / partial order

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R=\{(\mathscr P,\mathscr Q)\mid ...
1
vote
0answers
57 views

Is this relation $\mathscr R$ on the set of relations, reflexive?

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R = \{(\mathscr P, \mathscr Q) \mid ...
0
votes
1answer
193 views

Bijection preserves equivalence relation

Suppose f is a bijection between two sets A and B. Then x, y ∈ A gives us f(x), f(y) ∈ B. Prove that bijections preserve equivalence relations. That is, if R is an equivalence relation on A, then R' ...
0
votes
0answers
8 views

scaling second order linear non-homogeneous recurrence

I came across this post about scaling a second order linear recurrence. My question is, how would you go about scaling a non-homogeneous recurrence? That is, if $a_n = \alpha a_{n-1} + \beta a_{n-1} ...
2
votes
2answers
36 views

Show given relation $R$ is equivalence relation on $S$

I will display the exact problem, then my questions. I have searched to the extremes to figure this out and can't: Show that the given relation $R$ is an equivalence relation on set $S$. $S$ is the ...
0
votes
0answers
18 views

Relation and Cartesian Product

Let $A=\{-1,2,5,8\}$, $B=\{0,1,3,6,7\}$ and $R$ be the relation is one less than form $A$ to $B$. Then, 1) Find $R$ as a set of ordered pairs 2) Find domain and range of $R$. 3) Find $R^{-1}$ as a ...
1
vote
1answer
34 views

The maximum possible size of $R$ is_____?

A function $f : N^+ → N^+$, defined on the set of positive integers $N^+$, satisfies the following properties: $f(n) = f(n/2)$ if $n$ is even $f(n) = f(n+5)$ if $n$ is odd Let $R = \{i|∃ j : f(j) = ...
0
votes
1answer
40 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
41 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
36 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
35 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
34 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
26 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
40 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
28 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
34 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
27 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
30 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
26 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
31 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
24 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
2
votes
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
27 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
75 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
22 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
28 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
11 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
23 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
104 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
81 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
42 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
105 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
28 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
41 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
48 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
36 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
6answers
555 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$ ...