# Tagged Questions

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.

130 views

33 views

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 ...
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 ...
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 ...
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 ...
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 ...
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'...
33 views

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 ...
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 ...
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 ...
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 ...
43 views

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 ...
75 views

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$$
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 ...
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$ ...
50 views

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 ...
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$ ...
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 ...
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 ...
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 ...
80 views

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 ...
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......
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 =...
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.