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
1answer
11 views

Finding smallest set of real numbers according to a property

This is one of the example problem that has been solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x ...
0
votes
1answer
23 views

Finding $R^2$ and $R^3$ of relations [on hold]

Let $R$ be the relation on the set $\{ 1 , 2 , 3 , 4 , 5 \}$ containing the ordered pairs $(1 , 1) , (1 , 2) , (1 , 3) , (2 , 3) , (2 , 4) , (3 , 1) , (3 , 4) , (3 , 5) , (4 , 2) , (4 , 5) , (5 , 1) , ...
1
vote
3answers
40 views

For $f: A \to B$ with $S, T \subset A $, show that $f(S \cap T) \subset f(S) \cap f(T) $.

Let $f:A\mapsto B$ be given and let $S\subseteq A$ and $T\subseteq A$. Show that, $$f(S\cap T)\subseteq f(S)\cap f(T)$$
0
votes
1answer
45 views

connectivity relation to find the transitive closure

Hello I am having difficulties with this question: Use connectivity relation to find the transitive closure of relation $R = \{(a, e),(b, a),(b, d),(c, d),(d, a),(d, c),(e, a),(e, b),(e, c),(e, e)\}$ ...
-1
votes
1answer
23 views

Discrete MATH - RELATIONS- Show that R is an Equivalence [on hold]

This is a Homework problem I completely don't understand. Help would be appreciated. THANKS :) LET R be a relation on Z defined as ∀a,b ∈ Z :aRb ⇔ 2a+3b ≡ 0 (mod 5) Show that R is an Equivalence.
2
votes
1answer
26 views

cardinality of cartesian product of m sets

I was proving that the cardinality of Cartesian product of m(m>1) non-empty finite sets is the product of cardinalities of the m sets. it can be easily proved using the fundamental principle of ...
0
votes
0answers
20 views

Is it possible to make $R = \{(1, 0), (0, 1) \}$ antisymmetric without removing elements?

I was wondering if I have the relation $R = \{(1, 0), (0, 1) \}$, is there any way I can make the relation antisymmetric without removing elements? I think not, because since the first part of the ...
1
vote
2answers
26 views

Suppose R is a relation on A. Prove that if R is reflexive then R ⊆ R ◦ R. Counterexample?

Problem: Suppose R is a relation on A. Prove that if R is reflexive then R ⊆ R ◦ R. Counterexample: Let A = {1,2} and R = {(1,1),(2,2),(1,2)}. Then R ◦ R = {(1,2)}. Obviously R⊈ R ◦ R. This is an ...
3
votes
2answers
45 views

Associativity of cartesian product and nested ordered n-tuples

for 3 sets $A,B,C$ is $A\times B \times C = A\times (B\times C) = (A\times B)\times C$ OR to be more specific, is the ordered pair $((a,b),c)=$ ordered triplet $(a,b,c)=$ ordered pair $(a,(b,c))$? ...
1
vote
4answers
45 views

Prove $R$ is an equivalence relation.

I think I'm on the right track. Set $S = N \times N$, and for any two members $(a,b),(c,d)$ of $S$, define $(a,b) \simeq (c,d)$ provided that $ad = bc$. Prove that $\simeq$ is an equivalence ...
1
vote
1answer
38 views

Geometric description of composition of two convex polygons? [duplicate]

The composition was defined as follow: $(a,b)$ $\in$ $(R;S)$ $\Leftrightarrow$ $\exists c | (a,c) \in R \\ $&$ (c,b) \in S$ . Also the composition was defined as the binary product of two ...
1
vote
1answer
24 views

Find equivalence classes (Solution with questions)

I have to find the relation properties and the equivalence classes. $$X = \mathbb{R}^{2}$$ $$(x,y) \sim (u,v) \Leftrightarrow x - y = u - > v$$ Showing the relation properties of the ...
1
vote
2answers
42 views

Do these conditions on a relation imply that it is nontransitive? [closed]

Is this always true? $$((x,y)\in R\circ R \text{ and not }(x,y) \in R)\Rightarrow \text{not transitive}?$$ If it isn't, could anyone tell me why? Thanks.
-1
votes
1answer
22 views

Proving a relation is reflexive (discrete) [closed]

I have been assigned a problem in discrete mathematics that says: Supposes R is a relation on N4 (first 4 natural numbers) such that R•R=R, prove R is reflexive. (• is the composition symbol). How ...
0
votes
1answer
16 views

Let $R$ be a relation on $A$ and $S$ its transitive closure. Prove $\text{Dom}(S) = \text{Dom}(R)$ and $\text{Ran}(S) = \text{Ran}(R)$

I have the following exercise from the book "How to prove it", chapter 4.5, p.211, problem 9. Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that ...
1
vote
1answer
13 views

Proof that $S$ is a partial order when it is the reflexive closure of a strict partial order

Suppose $R$ is a strict partial order on $A$. Let $S$ be the reflexive closure of $R$. Show that $S$ is a partial order on A. ("How to Prove it", Chapter 4.5 exercise 4.a) To prove that $S$ is a ...
0
votes
3answers
23 views

multiplying term on sum

Say I know the following relation holds $$ \sum_i f_i + \sum_i g_i = 0 $$ Now I multipy both sides with a set of vectors $\mathbf v_i$. Will it still be true that $$ \sum_i f_i \mathbf v_i + \sum_i ...
0
votes
1answer
26 views

Divisibility relation: transitivity proof

I'm a bit confused about the proof for this relation. I get the first part, but the second line is where I'm totally muffled! Any help is greatly appreciated :) ** An example would also be ...
2
votes
1answer
30 views

Discrete Mathematics: Relations

Confused about this question: Describe two binary relations $R$ and $S$ on $\{1, 2, 3\}$ that are not equivalence relations, but whose composition $R\circ S$ is an equivalence relation.
3
votes
0answers
42 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
1
vote
2answers
27 views

What is subset partial order

This is one of the example problem solved in Velleman's How to prove book: Find the smallest set of real numbers X such that $5 \in X$ and for all real numbers $x$ and $y$, if $x \in X$ and $x ...
1
vote
0answers
53 views

How to construct a transitive relation?

Given a binary relation $\mathcal{R}$ on a set $A$, you can be assured that the relation $\mathcal{R} \cup \mathcal{R}^{-1}$ is symmetric. (I can give a proof of this, if you would like.) I wanted to ...
0
votes
2answers
16 views

Why is this relation not Symmetric

$R_1$ = {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)} Is this not symmetric ONLY due to the ordered pair (2,4) not having symmetry with (3,4)? I can't seem to find a lot of information on how to deal with a ...
0
votes
2answers
51 views

Is this relation reflexive?

Suppose $R$ is a relation on $N_4=\{1,2,3,4\}$ such that $R\circ R = R$. How would I prove that $R$ is reflexive? Could you give me some tips about how to start off?
1
vote
1answer
44 views

equivalences relation on set $A$

I ran into a Pure Math Contest Problem that was took 1 month ago on my Schools, and I do lots of search, but i couldent any progress to solve it. If $R_1$ and $R_2$ be a equivalences relation on ...
2
votes
1answer
42 views

Is the $\in$ relation a dyadic, or a monadic, relation?

I believe that it's true (correct me if I'm wrong) that When we predicate something of an argument we're saying that that argument is a member of a set intensionally defined just by that predicate? ...
1
vote
1answer
25 views

Order relation of complex numbers

Show what order relations apply: Set $X = \mathbb{C}$. $(z_1,z_2) \Leftrightarrow Re(z_1) \leq Re(z_2)$ "($z_1$ in relation to $z_2$) is equivalent to ((the real part of $z_1$) $\leq$ ...
1
vote
3answers
39 views

Is this relation transitive? $S = \{1,2,3,4\}, R = \{(x,y) | x - y \text{ is even and } x - y \geq 0 \}$

This is my first attempt to make up a relation that is transitive, reflexive, but not symmetric. I can't find a counterexample. There are only a few examples, one being: $$(3,1) \text{ and } (1,1) ...
0
votes
1answer
19 views

Solve the following recurrence by using telescoping

a(n)=2a(n-1) + 2n-1 a(0)=1 I tried below; a(n)-2a(n-1)=2n-1 from here I found P(n)=1, q(n)=2 r(n)=? according to below formula p(n)an()-q(n)a(n-1)=r(n) for n>=1 Since I can not find r(n) ...
2
votes
3answers
29 views

Trying to figure out whether the following relation is an equivalence relation

LEt $R$ be a relation on $\mathbb{N}$ given by $m R n$ iff $m$ and $n$ have the same digit in the tens place. What does it mean to have the same in digit in the tens place?
2
votes
1answer
47 views

Is the following an equivalence relation on $\mathbb{R} \times \mathbb{R} $?

Define $(x,y) R (z,w) $ iff $x + z \leq y + w $. Is $R$ an equivalence relation on $\mathbb{R} \times \mathbb{R} $? So far I got reflexivity and symmetry which are obvious. However, I am stuck on ...
1
vote
2answers
22 views

Relation antisymmetry check

Hello the question I am having trouble with is Describe a binary relation on 1, 2, 3 that is reflexive and transitive, but not symmetric nor antisymmetric. I Have the answer ...
0
votes
0answers
26 views

What does the Dedekind Rule `say'?

In Relation Algebra, the modal law or dedekind rule $$R;S \,\cap\, T \;\subseteq\; (R \cap T;S^\circ);S$$ appears often and I wonder what is the motivation behind it. Moreoever, what does it "say". I ...
2
votes
3answers
32 views

Reflexivity and Order

It seems to me that the most important concept that the idea of an order brings, is tied to the notion of assymetry ( or the weak antisymmetry, if you may ). However, the way the order ...
5
votes
3answers
62 views

Proving transitive property

I have been working on this problem from Velleman's How to prove book: Suppose A is a set, and F ⊆ P (A). Let R = {(a, b) ∈ A × A | for every X ⊆ A \ {a, b}, if X ∪ {a} ∈ F then X ∪ {b} ∈ F}. Show ...
1
vote
0answers
43 views

Cartesian Product characterization in Rel Category (Category of sets and relations) in simpler terms

The question here explains how a cartesian product of sets are specified. It is difficult for me to follow it; for example, I do not know about "symmetric monoidal category". Can anybody please ...
-1
votes
1answer
27 views

Examples for Relations [closed]

Give an example to each of the following: 1.If it is Symmetric relation,reflexive relation,but not transitive relation. 2.If it is Symmetric relation,transitive relation,but not reflexive relation. ...
4
votes
1answer
113 views

Can someone verify my answers to these questions regarding this poset?

Problem: 18. Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4},{1,3,4}, {2,3,4}}, $\subseteq$) $\quad$a.Find the maximal elements $\quad$b.Find the minimal elements ...
0
votes
0answers
9 views

Relations that satisfy certain properties

I've been trying to come up with functions that are, at the same time, symmetric, bijective and are either irreflective or transitive. I created this question from something my younger brother had ...
0
votes
2answers
42 views

How to mathematically show that the relation is transitive?

Problem: Show that the relation $x R y$ iff $x \leq y$ is a poset over the set of integers $\mathbb{Z}$ My work: I know that to show the relation is a poset or a post order, I have to show the ...
-1
votes
1answer
35 views

How to find union and intersection of these relations?

Problem: Let $R_1$ and $R_2$ be the "divides" and "is the multiple of " relations on the set of all positive integers respectively. That is, $R_1 = \{(a,b) | a \text{ divides }b\}$ and $R_2 = \{(a,b) ...
2
votes
0answers
53 views

Relations in a finitely complete category with images

I can't use tikz inside MathStackExchange; so my question is on an image below.
0
votes
1answer
19 views

why this is transitive relation?

$\rho\subseteq \mathbb{N}\times \mathbb{N},\rho=\{(x,y):y=x+5,x<4\}$ is the relation, so $\rho=\{(1,6),(2,7),(3,8)\}$ in my book it is written that $\rho$ is an transitive relation, but why? I know ...
0
votes
2answers
26 views

How to prove the relation is transitive?

Problem: Consider the relation R on $N$ defined by $x$R$y$ iff $2$ divides $x + y$. Prove that R is an equivalent relation My work: I know that to prove that a relation is an equivalent relation, ...
1
vote
0answers
27 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
1
vote
0answers
14 views

Can someone verify my work for finding the following relations?

I am working on this problem Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs {(1,1), (1, 2), (1,3), (2,3), (2,4), (3,1), (3,4), (3,5), (4,2), (4,5), (5,1), (5,2), ...
0
votes
1answer
57 views

Why can the author just switch the order of the inequality without any reprecussions?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 2, page 598]. I understand the idea of a symmetric closure. You add all ...
2
votes
2answers
48 views

Can a relation from A to some other set B also be considered symmetric?

Note: This definition is from Discrete Mathematics and Its Applications [7th ed, page 577]. This is my book's definition of a relation R on a set A My ...
0
votes
1answer
17 views

Transitive Closures

Let the relation R = {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, 2)} Find the Transitive closure of the relation. So far this is what I'm coming up with: {(0, 0), (0, 3), (1, 0), (1, 2), (2, 0), (3, ...
0
votes
4answers
86 views

Is antisymmetric the same as reflexive?

Note: The following definitions from my book, Discrete Mathematics and Its Applications [7th ed, 598]. This is my book's definition for a reflexive relation This is my book's definition for a anti ...