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
26 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
35 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
40 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
37 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
56 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
39 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
18 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
41 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
19 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?
-1
votes
0answers
28 views

Is $R = \{(a,a),(b,b),(c,c)\}$ an equivalence relation on $\{a, b, c\}$?

My intuition is yes is it an eq. rel., but I'm not sure. If $a \sim a \in R$, then $a \sim a \in R$ (inverse which is just the same), and so $a \sim a \in R$ (transitivity). Is this a valid argument ...
0
votes
1answer
34 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
24 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
126 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
26 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
66 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
66 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
236 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
22 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
31 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 ...
0
votes
0answers
32 views

Reflexivity of a relation between different sets

How are you doing? I have a question in Algebra: how can we describe the reflexivity of a relation defined in a set that is resultant of a cartesian product of two different sets A={a,b,c} and ...
1
vote
4answers
43 views

Proof: $R^n=R$ where $R$ is relation

I have a problem with this exercise: Proove that if $R$ is a reflexive and transitive relation then $R^n=R$ for each $n \ge 1$ (where $R^n \equiv \underbrace {R \times R \times R \times \cdots \times ...
0
votes
1answer
9 views

Finding the matrix of a relation $R$ on $X$

Given the relation: $$ R = \{(x, y)|x < y\} $$ and the ordering of $x$ is $\{ 1,2,3 \}.$ How to find the matrix of this relation? I honestly cannot understand the question. Any ...
1
vote
1answer
56 views

How to identify lattice in given hasse diagrams?

Consider the following Hasse diagrams. and given here , Counter example on wiki : Says " Non-lattice poset: b and c have common upper bounds d, e, and f, but none of them are the least ...
2
votes
0answers
45 views

Identification Topology (Mendelson's 'Introduction to Topology', page 103)

Let $f: (X, \sigma) \rightarrow (Y, \tau)$ be continuous and let $a \sim b$ if $f(a) = f(b)$. Noting $\sim$ is an equivalence relation, let $\pi(x)$ map $x$ to its equivalence class. Noting $\pi: X ...
1
vote
1answer
37 views

Discrete Mathematics - POSETs

My task is to find out what is the lowest # of elements a partial ordered set can have with the following characteristics. If such a set exists I should show it and if it doesn't I must prove it. 1) ...
0
votes
1answer
38 views

Prove or disprove that if a relation $R^2$ is transitive then $R$ is also transitive

Prove or disprove that if $R^2$ is transitive then $R$ is also transitive. I tried to prove $(R\circ R)^2\subseteq (R\circ R)\implies R^2\subseteq R$ this way $(R\circ R)\circ (R\circ ...
1
vote
1answer
19 views

prove or disprove reflexive of $R$

How to prove or disprove that if $R^2$ is reflexive then also $R$ is reflexive ? I tried to prove $R^2 \supseteq (x,x)\forall x \in R\implies R_{rex}$ but without success, maybe I have to find ...
1
vote
1answer
20 views

How is this relation transitive?

$$R = \{(0,1), (0,2)\}$$ I drew out a directed graph; however, I still do not see how this relation is transitive. If $0$ was reflexive, then it is transitive; however, that is clearly not the case ...
0
votes
1answer
21 views

Cartesian product of a set containing all real numbers?

Let S be the set of all sequences of real numbers. Let R be the relation $R = \{(a, b) \in S \times S | a_3 = b_3\}$ I'm trying to find out whether R satisfies the properties reflexive, ...
0
votes
1answer
18 views

Trouble with understanding transitive, symmetric and antisymmetric properties

If $A = \{1,2,3\}$, $R$ an equivalence relation on $A$ if $R = \{(1,1), (2,2), (3,3)\}$? I'm having trouble understanding when a relation is symmetric, antisymmetric, or transitive. Does the ...
0
votes
0answers
27 views

properties of relation product

I do know all definitions of relation properties such as reflexivity, transitivity, asymmetry etc. I have to answer questions if relation $R$ has property $A$, does $R^2$ has property $A$ too? ...
0
votes
1answer
25 views

$a^2 \equiv b^2$ mod 4 equivalence classes.

so we have the relation $a^2 \equiv b^2$ mod 4. And to find equivalence classes we say b or a = 0 so $a^2=4k$ so $a=+-2\sqrt{k} $ so all even numbers. But when we get to a=1 then $a^2=4k+1$ after ...
0
votes
0answers
24 views

Let $R={(x,y)∈R^ 2∣x^2+y^2=1}$ and S =$R^2$ . Write R o S using set-builder notation and graph it.

Let $R={(x,y)∈R^ 2∣x^2+y^2=1}$ and S =$R^2$ . Write R o S using set-builder notation and graph it. I don't understand how to write S in set-builder composition in this. I feel that the graph itself ...
0
votes
1answer
27 views

Inverse relation of $x<y$ defined on $\mathbb N$

The relation is this: $R=\{(a,b):a<b\}$ on $\mathbb{N}$. How do I find an inverse of this relation? I can see that it is $R^{-1}=\{(a,b):b<a\}$ but I do not know how to prove it. Can someone ...
0
votes
0answers
25 views

Prove that this is a partial order

I am reading Charles Pinter's "Set Theory" and I found an exercise which I can't resolve. Maybe someone can help me. It says: We will consider pairs $(B,G)$ where $B \subseteq A$, and $G$ is an ...
0
votes
0answers
23 views

Proof on exponential Relation R

Prove that $(R^a)^b = R^{ab}$ for any integers $a,b >= 1$. A handy fact: The connectivity relation $R^*$ consists of the pairs $(x, y)$ such that there is a path of length at least $1$ from $x$ to ...
0
votes
0answers
19 views

What common relations on Z are the transitive closures of the following relations?

(a) aSb if and only if a+1=b (b) aRb if and only if |a-b|=2 (c) What common relation on Zis the transitive closure of the relation T, where aTb if and only if |a-b| = 4 or 6? Explain. I don't know if ...
0
votes
1answer
21 views

Reflexive, Symmetric, and Transitive. How to read?

I'm a little confused on these problems as far as the wording goes. I know how to tell if one is reflexive, symmetric, or transitive. The way the problem is set up is: ...
1
vote
2answers
43 views

Discrete math - confusion in onto functions

The question that I'm trying to solve is: At the CH Company, Joan, has a secretary Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can ...
1
vote
0answers
24 views

Problem with understanding natural number difference

Proofwiki says the following about difference in natural numbers: In the context of the natural numbers, the difference is defined as: $n−m=p⟺m+p=n$ from which it can be seen that the ...
0
votes
1answer
59 views

Is $xRy$ iff $x$ and $y$ were born less than one week apart reflexive?

So I asked this question before without getting a solid answer. I went and studied a bit more about binary relations and reflexive relations. I understand the theory, but am unsure about whether my ...
1
vote
2answers
41 views

Determine which of the following relation is a function?

Given two set $ A = \{0, 2, 4, 6\}$ and $B = \{1, 3, 5, 7\}$, determine which of the following relation is a function? $(a) \{(6, 3), (2, 1), (0, 3), (4, 5)\}$, $(b) \{(2, 3), (4, 7), (0, 1), (6, ...
2
votes
2answers
61 views

Why Is $x \ne y$ Not Transitive on the Set of All integers?

I know this is a pretty simple question, but I'm just not getting the textbook... I'm taking a basic CS course and on one of the problems (not an assigned homework problem, just one I'm practicing ...
0
votes
1answer
34 views

Properties of the relation $(x,y) \in R$ if $| x-y | = 2 $

Is the following relation reflexive, symmetric, transitive, anti-symmetric and/or partial order : $$(x,y) \in R \text{ if }| x-y | = 2 $$ I think it's reflexive, I don't understand how to find for ...
2
votes
1answer
31 views

The binary relation $S=\phi$ on set $A=\{1,2,3\}$

I came across this question: The binary relation $S=\phi$ (empty set) on set $A=\{1,2,3\}$ is a) Neither reflexive nor symmetric b) Symmetric and reflexive c) Transitive and refelxive d) Transitive ...