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

4
votes
1answer
136 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
46 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
47 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
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
34 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
35 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
21 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
98 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
25 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
60 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
74 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
40 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
27 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
60 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
35 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
29 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
35 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 ...
1
vote
3answers
44 views

Relationship between functions and relations

In Discrete math I remember learning that "a function is a relation that is both 1 to 1 and onto." Every time I try to look this up I can't find this definition of "function", all I can find is that ...
0
votes
1answer
60 views

How to show a relation is/isn't reflexive, transitive, or symmetric

I was tasked with this: Define a relation on Z by setting x R y if xy is even. (a) Give a counterexample to show that R is not reflexive. How do I go about proving this? Do I express this ...
1
vote
2answers
86 views

Semi group presentation $<a, b | a^{2} = b^{2} = 0, aba = a, bab = b>$

Another semi group question here, trying to get my head around the topic. Consider the semi group $S=\left<a, b | a^{2} = b^{2} = 0, aba = a, bab = b\right>$ I need to prove that $S$ has order ...
0
votes
1answer
25 views

Why symmetric relation doesn't have loops

I have been reading Velleman's How to prove book and have come across following section while reading "Relations" chapter: Suppose R is a relation on A. ...
0
votes
1answer
38 views

Is this example of an ordered set correct?

Example of an ordered set: Let us define a set $C$. Let $C$ is the set of circles of all radii. The circles are all lying on a plane. (The point circle is excluded.) If we take any two circles ...
0
votes
0answers
17 views

Finding the relative pose of a robot gripper

I have a robot arm with a gripper. I know the gripper pose (relative to the robot base coordinate system) at any moment. At startup, I record the pose of the gripper and set this as the original pose ...
0
votes
1answer
21 views

Question regarding symmetric difference - Please check my work

Let $S$ be a relation on $P(\Bbb{R})$, such that $\displaystyle S=\{<A,B>\in\left(P(\Bbb{R})\right)^2.\left|A\triangle B\right|\le \aleph_0$ Is $S$ an equivalence relation? My try: ...
1
vote
1answer
165 views

If S is finite and $x/\rho$ is an idempotent of $S/\rho$ then $x/ \rho$ contains an idempotent

Currently working on the following problem, need a little help with the solution to the last part, any hints? Q: Let S be a semigroup, and let ρ be a congruence on S. Prove that if e ∈ S is an ...
1
vote
1answer
74 views

Existence of infimum and supremum in a totally ordered set

Problem: Let $M=\langle A,R\rangle$ be a partially ordered set and $C(M)$ is the set of all totally ordered parts of $M$. Prove that each nonempty totally ordered part of $\langle ...
1
vote
1answer
47 views

Statement regarding the restriction of a function

All terminology below is related to Set Theory. Definition: Let $f$ be a function and $n∈N$. We say that $f$ is of order $n$ if the inverse image of each element from the range has at most $n$ ...
-1
votes
2answers
62 views

Give me an example of a relation.

Give me an example of a relation which is: (i) Reflexive and Symmetric but not Transitive. (ii)Symmetric and Transitive but not Reflexive. I'm confused because I think a Ref. and Sym. relation must ...
1
vote
0answers
53 views

Equivalence Relations with equivalence classes

Consider the following relation on $\mathbb{Z} \times \mathbb{Z}$: $(x, y)\sim (x', y')$ iff $xy' = x'y$. (a) Prove that it is an equivalence relation. (b) Consider the set of equivalence classes ...
0
votes
2answers
31 views

I need help finding the length of the curve represented by this particular relation.

I need help finding the length of the curve represented by the following relation: $$x = 5\,cos^3\theta; y = 5\,sin^3 \theta$$ Here is what I've tried: $$s = \int_0^{2\pi} ...
0
votes
1answer
34 views

Names for left- and right-total relations

Let $X$ and $Y$ be finite sets. I am interested in subsets $r \subseteq X \times Y$, which contain each $x \in X$ and each $y \in Y$ at least once: $$ \forall_{x \in X} \exists_{y \in Y} (x, y) \in r ...
0
votes
1answer
38 views

Transitive Elements on Set

i get trouble in one problem... if we have relation R={(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a)}, on set {a,b,c,d,e,f}. how many elements the transitive closure of R has? I try ...
0
votes
0answers
60 views

cpuboss rating calculations

I was using cpuboss earlier today and noticed they converted all the benchmark scores from numbers into a score out of 10. IE/ 8.1, 6.7 etc. Being the OCD person I am. I started to try to figure out ...