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
0answers
61 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
52 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
27 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
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
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
28 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
35 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
65 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
53 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
29 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
124 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
44 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
42 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
55 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
30 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
30 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
20 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
89 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
23 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
57 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
63 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
37 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
46 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
26 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
26 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 ...
0
votes
0answers
25 views

What the meaning 'directed'

What's the meaning of 'directed' and 'cofinal'.It's about a partially ordered set. Please give me an example? A preordered set (I, ≤) is directed if every finite subset F of I has an upper bound. A ...
0
votes
0answers
23 views

partially ordered set 3

What the meaning upper bound and lower bound.Its about of partially ordered set? and please give me any example? Given a subset S of (X, ≤), an element m of X is called an upper bound (resp. a lower ...
2
votes
1answer
39 views

Find the roots of the polynomial $ 3X^3 -32X^2+73X +28$ using Vieta's relations

They are asking me to find the roots of the polynomial $ 3X^3 -32X^2+73X +28$ using Vieta's relations. They also tell me that $x_1 - x_2 = 3$. I have tried to use first Vieta's relation($x_1 + x_2 + ...
0
votes
0answers
24 views

What are the possible relations?

If there are two sets A and B. Set A has two elements so does Set B. How many different possible relations can we have from A to B. For example. Set A has (David, Max) and Set B has (x,y). Would the ...
0
votes
2answers
53 views

Prove: Partitions and refinements

Problem: Let $ R $ be the set of partitions of a real interval. Then for all elements in $ R $, every pair of elements has an upper bound. I am having trouble structuring the proof; and intuitively ...
0
votes
1answer
34 views

partially ordered set

What is the meaning of: $A(x) := \{y ∈ X : x ≤ y\}$ $(x ≤ x$ or $x ∈ A(x)$ for all $x ∈ X)$ $(A ◦ A ⊂ A$, i.e., $x ≤ y, y ≤ z ⇒ x ≤ z$ for $x, y, z ∈ X)$ in the sentences: A preorder or ...
0
votes
0answers
26 views

Upper bound and lower bound(partial order)

I come across a graduate level introduction to real analysis course. In the lecture, the professor firstly define a set A, which is a subset of a partial order set X, for which the relation R1 is ...
2
votes
1answer
68 views

Does $\{(a,b), (b,a), (a,d), (b,d)\}$ hold transitive property?

I have been working on one of the problem from Velleman's How to prove book and there is a relation $R$ like this: $R = \{(a,b), (b,a), (a,d), (b,d)\}$ We have to ...
0
votes
1answer
26 views

Why is this Relation not Symmetric?

Given is a relation on bitstrings: $$R = \{(b,b') | ((b = b') \lor (b = 0b')) \}$$ $0b'$ means the concatenation of $0$ with $b'$. Is this relation symmetric? In my opinion it is. If $b = b'$ is ...
1
vote
1answer
34 views

Proving symmetry and transitivity

I want to prove $\mathbb{N} \sim \mathbb{Z}$ by indication of a bijection, thus the equipotency of the two sets. I know that I have to prove reflexivity, symmetry and transitivity. The reflexivity ...