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
0answers
65 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
33 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
85 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
49 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
51 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
35 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
53 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
26 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
42 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
79 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
36 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
53 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
75 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
27 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
41 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
97 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
98 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
88 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
26 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
39 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
25 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
23 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
170 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
87 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
51 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
66 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
57 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
33 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
42 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
43 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
80 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 ...
3
votes
2answers
46 views

Does a reflexive element constitute asymmetry and anti-symmetry?

I'm studying properties of relations and there is one area that i'm kind of unsure about regarding the properties of asymmetry and anti-symmetry. Suppose R = {(1,2),(3,4),(2,2)} It would follow that ...
1
vote
2answers
39 views

Prove there is either a chain or an antichain of infinite cardinal.

Let $K$ be an set of infinite cardinal, $X$. Let $(K,\le)$ be a partially ordered set. Prove there is either a chain $C$ such that $|C|=X$ or there is an antichain $A$ such that $|A|=X$. I guess I ...
0
votes
3answers
53 views

Clarification regarding domain definition

I have been reading the fourth chapter of Velleman's How to prove book and this is the definition for domain which I have encountered: Suppose $R$ is a relation ...
2
votes
1answer
601 views

How are ∈ and ⊂ defined to be relations?

I understand a relation to mean, for elements $x\in X$, $y\in Y$ and for subset $R\subset X\times Y$, if $(x,y)\in R$ then $x$ is in the relation $R$ to $y$. But how are $\in$ and $\subset$ defined as ...
1
vote
4answers
30 views

How to interpret the following function?

The question says : If $f:X\rightarrow Y$ and $a,b \subseteq X$, then $f(a \cap b)$ is equal to? - $f(a)-f(b)$ - $f(a)\cap f(b)$ - a proper subset of $f(a)\cap f(b)$ - $f(b)-f(a)$ ...
0
votes
1answer
27 views

Proving $|S/R^2|=\aleph$ , $(x_1,x_2)S(y_1,y_2)\iff x_1^2-x_2=y^2_1-y_2$

Let $S$ be an equivalence relation over $\mathbb R^2$ such that: $(x_1,x_2)S(y_1,y_2)\iff x_1^2-x_2=y^2_1-y_2$ Prove that $|S/R^2|=\aleph$ One side is pretty simple: $|S/R^2|\le |\mathbb ...
1
vote
1answer
31 views

A counterexample for an equation between arbitrary relations

It seems that the following equation does not hold always for the arbitrary relations R1,R1 and R3: $R1.(R2\cap R3)=(R1.R2)\cap(R1.R3)$ Instead, the right axiom is the following: $R1.(R2\cap ...
1
vote
0answers
43 views

xor of three relations using Relation Algebra operations

Suppose I have three relations R1, R2, and R3. How can I specify xor of these three relations using relation algebra operations. How this scales up (for example, for four relations)? Thanks I add ...
3
votes
2answers
45 views

For what $z\in\mathbb{N}$ is “$x\equiv y\iff xyz$ is a square” an equivalence relation?

Consider the set $\mathbb{N}\cup\{0\}$ and fix $z\in \mathbb{N}\setminus\{0\}$. Define the relation $x \equiv y \iff xyz$ is a square number. I am trying to verify that this is an equivalence ...
0
votes
1answer
23 views

Mapping relations

Which of the following relations $f\colon \mathbb{Q} \to \mathbb{Q} \!\,$ define a mapping? In each case, supply a reason why $f$ is or is not a mapping. So my understanding is that a mapping ...
-1
votes
1answer
37 views

Counting relations question

I have a small question about relation counting, i'm looking for formulas. I know that there is a formula for reflexive and anti reflexive. I'm not sure about the simetric or a-simteric ones, and if ...
1
vote
3answers
28 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
1
vote
2answers
30 views

What's the term for antisymmetry where equal elements are not in the relation?

The most common definition of antisymmetry of a relation $R$ on a set $S$ is $$ \forall a, b \in S, R(a, b) \land R(b, a) \to a = b. $$ However, this doesn't cover a relation such as $<$, for ...
1
vote
1answer
38 views

Is an irreflexive and transitive set an anti symmetric set?

I have read that a simple ordered set is a total ordered set which is irreflexive and transitive. I want to know if irreflexivity and transitivity implies antisymmetry?