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

-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
566 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
33 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
52 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
526 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
61 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
93 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
47 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
84 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
42 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
32 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
16 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
23 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
45 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
30 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 ...
0
votes
3answers
41 views

Construct an equivalence relation on a given set

can anyone help me on this problem? I have the set $\{0,1,3,8,9\}$ and I want to define an example of an equivalence relation. I know that to be an equivalence relation it needs to be reflexive, ...
2
votes
2answers
53 views

Is the relation $a $~$ b$ iff $ ab$ is square on $\mathbb{Z}$ transitive?

I'm trying to determine whether the relation given above is a equivalence relation. I've already proved it is reflexive and symmetric, but I'm stuck trying to prove (or disprove) its transitivity. I ...
0
votes
1answer
25 views

Number of relations that are anti-symmetric

Consider set A containing n objects. How many relations of all $2^{n^2}$ on A, are anti-symmetric? I saw in book that it is $2^n *$ $3^{(n^2 -n)/2}$ but I can't understand why we use 3 as base?
0
votes
0answers
29 views

Check if equivalence relation

Check if $(x,y)\rho(a,b)\Leftrightarrow sgn(y-\pi x)=sgn(b-\pi a)$ is equivalence relation on $\mathbb{R^2}$, find the set of equivalence classes and $C_{(1,\pi)}$. Give geometric representation. ...
-1
votes
1answer
60 views

Prove that if a relation R on a set A is reflexive, symmetric and antisymmetric, then $R=I_A$ [closed]

Prove that if a relation $R$ on a set $A$ is reflexive, symmetric and antisymmetric, then $R=I_A$ I know a relation is a set of ordered pairs and that $I_A = (x,x)$ but I have no idea how to do this ...
1
vote
1answer
34 views

Solving recurrence relations of n rabbits on island

Okay so one pair of rabbits is left in an island. After 1 month it produces 2 pairs of rabbits, and 2 months or older they produce 6 every month. I came up with the recurrence relation $ A_{n} = ...
0
votes
2answers
30 views

Relations on groups.

Let $G$ be a group and $H$ a subgroup of $G$. Define a relation on elements of $G$ by saying that $a \sim b$ if $b^{-1} a \in H$. This relation is : a) reflexive and symmetric, but transitive only ...
1
vote
3answers
51 views

Proving equivalence relation for 7 | (3a + 4b)

I know this might be quite trivial, but I just can't seem to figure out how to prove $$R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : 3a + 4b \text{ is divisible by } 7\}$$ is a symmetric relation, ...
1
vote
3answers
48 views

Understanding Reflexive Relations

I'm reviewing some problems to try and get a better understanding of relations. I get how a reflexive relation works on a defined relation with numbers, but not so much when its done with a set ...
1
vote
2answers
41 views

Few group theory questions

I am trying to solve the following; First, given G is a group and H a subgroup of G, what can we say about the relation $a \cong b$ if $b^{-1}a \in H$ I can show that it is reflexive as the ...
1
vote
1answer
24 views

Elements in partial ordered set.

Let $(S, ≤)$ be a partial order with two minimal elements $a$ and $b$, and a maximum element $c$. Let $P: S → \{$True, False$\}$ be a predicate defined on $S$. Suppose that $P(a) =$ True, $P(b) =$ ...
0
votes
3answers
50 views

Is $a\sim b$ exactly when $a \times b$ is divisible by $3$ an equivalence relation?

Let $\sim$ be define so that $a\sim b$ exactly when $a \times b$ is divisible by $3$. Is this an equivalence relation? If not, which of the three properties (reflexive, symmetric, transitive) does not ...
1
vote
1answer
157 views

Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive

Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive. In order for a relation to be transitive it must satisfy $$aRc \wedge bRc \rightarrow aRc$$ for all $a,b,c ...
0
votes
1answer
63 views

Determine the number of relations on A that are

I'm sure this is a super simple question but I'm a bit stuck on how exactly I'm supposed to solve this. I have a feeling this might be a counting related question but I'm not sure. If anyone could ...
2
votes
1answer
24 views

Proof: Sum / Intersection of family of equiuvalence relations is equivalence relation

I have to check if sum and intersection of family of equivalence relations is equivalence relation. Here is the exercise: Let $\mathcal{R}$ be a family of equivalence relations defined on some set ...
1
vote
2answers
33 views

Trivial proof writing regardings reflexive relations

Q: Suppose $R_{1}$ and $R_{2}$ are relations on A. Give a proof or counterexample to justify your answer. If $R_{1}$ and $R_{2}$ are reflexive, must $R_{1} \cup R_{2}$ be reflexive? A: My reasoning ...
0
votes
0answers
14 views

graphing of two realtions

We have the following relations: $$S_1=\{(x,y) \in Z^2:x+y>1 \text{ and } x>0 \}$$ $$S_2=\{(x,y) \in P^2:x+y>1 \text{ and } x>0 \}$$ We have to make the graph for each occasion. My ...
0
votes
0answers
49 views

How to find lower bound , upper bound , greatest lower bound ,lowest upperbound from this problem?

Problem : Relation $R$ from the following sets : $ xRy \iff x|y $ $A=(1,2,3,4,6,8,9,12,16,18,24,27,36,4854,72,81,108,144,162,216,324,432,648,1296)$ Question A : draw the hess diagram Question B ...
0
votes
1answer
24 views

$R_1=\{(x,y) \in R^2:-1 \le x \le 1,-3 \le y \le 2 \}$ graph

We have the following relation: $R_1=\{(x,y) \in R^2:-1 \le x \le 1,-3 \le y \le 2 \}$ Could anyone tell me how to make the graph for the above relation?
0
votes
1answer
39 views

Consider the relation $R$ on $\mathbb Z$ as: $\forall m,n\in \mathbb{Z}, mRn \iff m−n \text{ is odd}$ . Is $R$ reflexive, symmetric, or transitive?

Consider the relation $R$ on $\mathbb Z$ as: $\forall m,n\in \mathbb{Z}, mRn \iff m−n \text{ is odd}$. Is $R$ reflexive, symmetric, or transitive? Provide a complete proof or counterexample for ...
2
votes
1answer
58 views

Proving that restrictions of partial orders are partial orders

Prove: A set has a partial-order relation $R$ on it. $P$ is a subset of this set. Prove that the restriction of $R$ to $P$ is itself a partial-order relation. Assume that this relation, $T$, ...
-4
votes
2answers
134 views

Recurrence Relations, calculating [closed]

http://puu.sh/lEJIB/941352c776.png How do you calculate u2 and u3? u2 = 2(2)-3, u3 = 2(3)-3?
0
votes
0answers
32 views

The separated uniform space associated with $(X,\mathfrak{U})$

If $\mathfrak{U}$ is a not necessarily separated uniform structure for some set $X$, then an equivalence relation $R$ can be introduced on $X$ by letting $x R y$ provided $(x,y)\in U$ for every $U\in ...
0
votes
0answers
14 views

Does the usual law for image also hold for relations?

Let $R \subseteq U \times V$ be a relation, and $S_0, \dots, S_{m-1} \subseteq U$ Then does the following hold? $$R\left(\bigcap_{j=0}^{m-1} S_j \right) \subseteq \bigcap_{j=0}^{m-1} R(S_j)$$ It ...
1
vote
1answer
84 views

How to read this Function/Relation? One-to-One Proof? (Discrete Mathematics)

Define function J : Q×Q → R by the rule J(r, s) = r+ sqrt(2)s for all (r, s) ∈ Q×Q I have no real idea how to read this. My thoughts are: For every pair of rationals in QxQ, or the pair of any two ...
1
vote
1answer
68 views

How to proof that nested intervals are an equivalent relation?

I want to show that a relation on the space of all sequences of nested intervals is an equivalence relation. Definition: Let $[a_n,b_n]_{n\in\mathbb{N}}$ and $[c_n,d_n]_{n\in\mathbb{N}}$ be two ...
0
votes
2answers
281 views

Transitive Closure and Composite relations in set builder notation

I'm having some trouble with a couple of questions on relations: Let $R$ be the relation on positive integers defined by $xRy \iff x < y$. Then, in the Set Builder Notation, $R = \{(x, y) ...
0
votes
1answer
26 views

Proof: $\bigcup _{n=1}^\infty R^n$ is transitive closure of $R$

I have this exercise: Let $R\subseteq A^2$ be any relation. Proove $\bigcup _{n=1}^\infty R^n$ is the transitive closure of $R$. I have no idea what to do. Could you help me, please?
2
votes
1answer
45 views

Describing Distinct Equivalence Classes of a Relation

Suppose that $R$ is a relation on the set of complex numbers $\mathbb{C}$. The relation $R$ is defined as follows: For any two complex numbers $w,z \in \mathbb{C}$, $$w R z \Leftrightarrow ...