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
1answer
130 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 C(M),\subseteq\...
1
vote
1answer
58 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
116 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
93 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} \sqrt{(\frac{d\theta}{d\...
0
votes
1answer
55 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 \...
1
vote
1answer
66 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 ...
3
votes
2answers
86 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
46 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
59 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
5k 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
32 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)$ I'...
0
votes
1answer
33 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 R^2|=\...
1
vote
1answer
59 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
59 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
52 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
71 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 is a ...
-1
votes
1answer
98 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
43 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
36 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 ...
2
votes
1answer
250 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
50 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
68 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 Z\...
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
75 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
36 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
36 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 mod($0$,$...
0
votes
2answers
47 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
23 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
117 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
50 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 \...
0
votes
2answers
97 views

How many relations can be defined the this power set

Let $A=\{1,2,3\}$ What is the number of reflexive relations the can be defined on $P(A)$? I first thought the number is 3, but it seems I'm wrong. How can someone solve this problem? Thanks
0
votes
1answer
29 views

Hasse diagram of finite linearly ordered set

What form does the Hasse diagram of a finite linearly ordered set take? I think the linearly order set is nothing but totally ordered set which usually takes lattice form since every element is ...
1
vote
0answers
32 views

Partial and total orders

From Exercise 4.4.9 of How To Prove It: Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A \times B$ as follows: $L = \{((a, b), (a', b')) \in (A \...
1
vote
1answer
32 views

permutation on relations

Let $A = \{1, 2, 3, 4\}$. Call a binary relation on $A$ interesting if it is symmetric or it does not contain the pair $(1, 4)$. How to calculate the number of interesting binary relations on $A$. My ...
2
votes
1answer
551 views

Is this relation transitive? $R=\{(1,2),(1,1),(2,1),(2,2)\}$ over $A=\{1,2,3\}$

Is this relation $R$ over $A$ transitive?$$A=\{1,2,3\}$$ $$R=\{(1,2),(1,1),(2,1),(2,2)\}$$ Since from the definition a relation is transitive if $\forall x,y,z\in A (xRy,yRz\to xRz)$, so since $3$ ...
0
votes
1answer
149 views

Discrete Math dealing with Partition of Ordered Pairs. [closed]

Given the partition $\{a,b,c\}$ and $\{d,e\},\,$ of the set $S=\{a,b,c,d,e\},\,$ list the ordered pairs in the corresponding equivalence relation. How can I determine which elements are related to ...
2
votes
1answer
44 views

How to find efficient not transitive pairs in relations? (Discrete math)

I'm doing at the moment some math and struggle with the following. So there are relations and they can or can not hol specific properties. Most common are described reflexive, symmetric and ...
0
votes
2answers
76 views

Binary relation of composite function

Suppose S is a binary relation on a set X. If S ◦ S is reflexive, Is S is reflexive? can we prove this with example too and by definition "Let U be a non-empty set and let R be a binary relation ...
0
votes
1answer
80 views

Problem of understanding transitive relations

I would like to understand the transitive property in relations...I just cant get it in my brain. I mean the definition is crystal clear. However I still struggle. For example: Given the set $A=\{0,1,...
2
votes
2answers
21 views

Showing $R$ is transitive and reflexive $\to$ $R=R^2$, $R$ is transitive and reflexive $\to$ $R=R^2$

Let $R$ be a relation over $A$. Define $R^{-1}, R^2$ like so: $aR^{-1}b \iff bRa\\ aR^2b\iff\exists _{c\in A}(aRc\wedge cRb)$ Prove: $R$ is transitive $\iff$ $R^2\subseteq R$ $R$ ...
2
votes
1answer
42 views

Question about proving intersection of two transitive relation is transitive

Suppose $R,S$ are transitive relations over $A$, prove that $R\cap S$ is transitive. Let $x,y,z\in A$, since $R,S$ are transitive then $$(x,y),(y,z),(x,z)\in R \wedge S\Rightarrow (x,y),(y,z),(x,z)\...
0
votes
0answers
22 views

Finding maximal chains in an ordered set.

Let $R$={$((x_1,y_1),(x_2,y_2))$:$x_1\le x_2, y_1\le y_2$} find the maximal chaings. Could it be that every maximal chains is of the form {$(a,b)+t(1,1)|t\in\Bbb{R}$} such that every other chain of ...
0
votes
1answer
37 views

Why is $R$ not transitive?

$R = \{(2, 4), (4, 3), (2, 3), (4, 1)\}$ I know that $(2, 4) \in R$ and $(4, 3) \in R$ -> $(2,3)\in R$. But why my reference book said that the relation is not transitive? And why this $R = \{(1, 1),...
-1
votes
1answer
25 views

Ordered sets. Chain upper bounds.

Suppose I have an ordered set $A$ and a chain $B\subseteq A$ then does $B$ necessarily have a supremum? Let alone an upper bound? And if it is empty? This question is a bit confusing because I am not ...
0
votes
0answers
18 views

Zorn's lemma usage\problem. [duplicate]

Let $(A,\le)$ be an ordered set. Show that if any chain has an upper bound then for any $a\in A$ there exist a maximal element such that $a\le x$. I am stuck with this... Would appreciate any help......
0
votes
1answer
18 views

Equality: transitive property

Is the following relation a valid example for the transitive property of equality? If not, what is/are the name(s) of the property/ies involved? Given A, B, C, D. Given A = B, A = C, B = D. Then C =...
1
vote
1answer
36 views

Binary relations on sets

Sorry for such a query. But can a relation be both antisymmetric as well as asymmetric? for ex. is this relation {(3,4),(5,6)} both antisymmetric and asymmetric.
0
votes
1answer
27 views

Graph homomorphism with a non-mapping relation

In [1] it is said that a graph homomorphism is a mapping between two graphs, that is, between their vertices, where the edges are preserved. A mapping is a specific binary relation where any vertex ...
2
votes
3answers
246 views

Is an Anti-Symmetric Relation also Reflexive?

According to the definition of an Anti-Symmetric Relation if xRy and yRx then x = y Which means, effectively, x is in relation with itself. Does this mean that anti-symmetry implies reflexive ...