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
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
63 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
37 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
69 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
37 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
46 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
78 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
87 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
20 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
22 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
166 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
78 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
32 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
39 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
63 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
43 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
37 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
56 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
29 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
27 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
36 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 ...
2
votes
2answers
44 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
21 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
34 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
26 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
27 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
31 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?
0
votes
0answers
23 views

How to prove the two relations to be equal?

If I have a relation $R$ defined on a set $A$ ,then when we calculate $R^n$ by performing cartesian product of $A^n$ ,then can we predict the value of $s$ and $t$ such that $R ^ s=R ^ t$. As we ...
1
vote
2answers
49 views

Prove that $f$ is NOT surjective

Let $f: Z \times Z \to Z \times Z$ defined like this: $f(x,y) = (x+y, x-y)$ Prove that $f$ is injective, and not surjective. For injectivity I did that: Let $(a,b) \in Z\times Z$ and $(c,d) \in ...
0
votes
2answers
40 views

If $|B\times A| = 15$ ,evaluate: $|A\cap B|$

If $|B\times A| = 15$ and $|A\times B \backslash B \times B| = 12$. Evaluate: $|A\cap B|$ I tried for myself and got to the conclusion that $|A\times B \cap B \times B| = 3 $ I couldn't get by ...
0
votes
1answer
19 views

A relation on the set with four elements which is reflexive, but not transitive

Give an example of a relation on the set A with 4 elements which is reflexive, but not transitive. Let $A = \{1, 2, 3, 4, 5 ,6\}$ be the set with 6 elements. I have worked out the relation $R = ...
1
vote
1answer
26 views

Shortcut for determining equivalence relations?

Is there a short cut to determine the number of equivalence relations on the set $\{1,2,3,4\}$? I mean I could do that manually but for a larger set it becomes annoying. Is there a general way to ...
1
vote
1answer
26 views

finding the equivalence class of modulo?

I would like to find the number of different equivalence classes for $\{(x,y)\mid x^2\equiv y^2$ mod $3 \}$ on $\mathbb{N}^2$. I would just set $x^2$ to $0$ or $1$ or $2$ or $3$. For example ...
0
votes
2answers
44 views

Show that $R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$ is an equivalence relation

How can I show that this is an equivalence relation ? $$R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$$
0
votes
1answer
22 views

Which are the equivalence classes for the following relation?

Here I have such an exercises related to equivalence relations. Given R defined on $Z \times Z$, $$(a,b)R(c,d)$$ and $$a+d=b+c$$ Let set $A$ be: $$A=\lbrace{0,1,2} \rbrace$$ Which are the ...
0
votes
0answers
49 views

Why relation “parallel” on the set of lines in a plane not transitive?

My book says relation "parallel" on the set of lines in the plane not transitive. And the definition in the book given is : A relation $R$ on a set $A$ is transitive if whenever $aRb$ and $bRc$ ...
0
votes
1answer
43 views

how to prove $pr_i(\alpha \setminus \beta) \supseteq pr_i\alpha \setminus pr_i\beta$

For those who are not familiar with the syntax $pr_i \alpha = \{ pr_i(a,b) / a \alpha b \} \text{ for }\alpha \subseteq A \times B$ which is same as $\begin{cases} (x= pr_1 \alpha) \Leftrightarrow ...