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
4answers
55 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
61 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
33 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 ...
0
votes
1answer
19 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
16 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 ...
1
vote
3answers
26 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
32 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
31 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
49 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
34 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
63 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
19 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 ...
-1
votes
2answers
56 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?
0
votes
1answer
47 views

equivalences relation on set $A$ [closed]

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
46 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
33 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
40 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
31 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
48 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
25 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
31 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
37 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
78 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
1answer
57 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
30 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
143 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
10 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
48 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
59 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
56 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
20 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
39 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
41 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
15 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
50 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
24 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
102 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 ...
1
vote
1answer
30 views

Understanding comparability in a partially ordered sets with Hasse diagrams

I'm doing a section on directed graphs and Hasse diagrams right now on partially ordered sets, and I'm trying to understand what it means for two elements in a Hasse diagram to be comparable. For ...
0
votes
0answers
62 views

Set theory proof question on rational numbers

I was assigned a problem by my Discrete Mathematics professor that goes as follows: Prove that on $\mathbb{Q}$ (the set of all rational numbers), the relation "$<$" satisfies " $< \circ <~ = ...
1
vote
1answer
32 views

Why can't a relation have an infinitely long chain from a to b?

A relation $R$ has a "chain" that connects $a$ to $b$ if there exists some sort of $$(a, x_0),(x_0, x_1),\cdots,(x_{n-1}, x_n),(x_n,b)$$ made out of the elements in $R$. Why doesn't there exist a ...
1
vote
1answer
75 views

Proof: if $R$ is symmetric then so is $R^{-1}$

This is one problem I have been solving in Velleman's How to prove book: Suppose $R$ is a relation on $A$, prove that if $R$ is symmetric, then so is ...
1
vote
0answers
42 views

Is my answer for the composite relation correct and not the textbook's?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 5 pg 593] Here is how my textbook's way of representing a relation with a matrix And the definition of a ...
1
vote
2answers
47 views

Why does a set of m elements have 2$^m$ subsets?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 576], shout out to @crash. I understand why $A \times A$ has $n^2$ elements(because every member of set $A$ ...
0
votes
0answers
21 views

About finding a binary relation

Let $δ_{n},β_{n}$ two sequences of rational numbers. Assume that the points $$P_{p}=(δ_{p-1},β_{p-1})$$ $$Q_{p}=(δ_{p},β_{p})$$ $$R_{p}=(δ_{p+1},β_{p+1})$$ are colinear and assume also that the ...
1
vote
0answers
18 views

Examples of upper and lower bound, directed and cofinal [duplicate]

I'm learning a partially ordered set. Can you give me some example of each these definitions: Upper and lower bound: Given a subset $S$ of $(X, \le)$, an element $m$ of $X$ is called an upper ...
0
votes
1answer
28 views

In Novice Terms, How Does an Ordered Pair Relate to a Database Row (Tuple)?

Im putting a technical presentation for an interview (topic I chose). I am researching real-time data streaming. I am familiar with what an ordered pair is as it pertains to a graph i.e (x, y) ...
0
votes
1answer
34 views

Is transitive Relation closed under composition?

it's true that equivalence relations is closed under composition, i.e., if R is a equivalence relation RoR is so.(Because RoR =R) But this not imply that any transitive Relation is so. Briefly; i ...
0
votes
0answers
23 views

What's the meaning 'filtering',and 'chain'

What's the meaning 'filtering' and 'chain'? It's about of partially ordered sets. And can you please give me any example? Definitions: A preordered set $(I, \leq)$ is directed if every finite ...