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.

99 views

Define a relation for “is contained in”

Here is my question (should help with my understanding of this new topic): Consider two words $x, y$ and say that the word $x$ is contained in the word $y$ if it only uses characters from $y$. Only ...
30 views

Equivalence Classes of an Equivalence Relation Confusion (definition and solution included)

The Definition of Equivalence Classes of an Equivalence Relation is given as: Suppose $A$ is a set and $R$ is an equivalence relation on $A$. For each element $a$ in $A$, the equivalence class of a, ...
44 views

An example of a relation that is symmetric and antisymmetric, but not reflexive.

I am really stuck on if there is such an equation. The set given was A={1,2,3,4}. Is it even possible for a relation to be symmetric and antisymmetric, but not reflexive?
33 views

Relation is a function from domain to power set of range

Let $E$ and $F$ be sets. Then $\tau$ can be considered a function from $E$ to $P(F)$ by setting, for each $x \in E$, $\tau(x) = \{y \in F: (x, y) \in \tau\}$ . This is a claim from a text, but it ...
2k views

Proof that the empty set is a relation

In the book Naive Set Theory, Halmos mentions that the "The least exciting relation is the empty one." and proves that the empty set is a set of ordered pairs because there is no element of the empty ...
20 views

Ensure exact partitioning when performing masked equality comparison

This question arose from an informatics problem, but I do believe Math SE is the right stack to ask because I am not asking for a algorithm in a specific language but for properties to check using ...
26 views

31 views

If $R$ is an equivalence relation, does $R^2$ too?

I think that yes, $I_A \subseteq R$ $R = R^{-1}$ $R^2 \subseteq R$ And now we can show. Reflex: $I_A = I_A^2 \subseteq R \subseteq R^2$ A lil bit struggling with symm. And trans. ...
61 views

How many relations can you form that are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$

How many relations can you form the are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$, and $m \ge n$ From my understanding, ALL THE elements in $B$ must be in the right spot of the relation. for ...
59 views

Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Prove that $R \cap (B \times B)$ a partial order on $B$.

Can somebody show me how to prove this? I would much appreciate it if one could show the givens and goals similar to how it is set out in Velleman's 'how to prove it' book, though any help would be ...
70 views

Questions on equivalence relation and functions

I just found this question in my discrete math homework and just can't have the solution by looking through the textbook. The question contains two parts: a) If $R$ is an equivalence relation on ...
15 views

Find the division set ($A / R$)and index of set $A = \{\phi : 0 \le \phi \lt 2\pi\}$

Find the division set and index of set $A = \{\phi : 0 \le \phi \lt 2\pi\}$ The relation is $\phi_1 R \phi_2 \leftrightarrow sin\phi_1 sin\phi_2 \ge 0$ and $cos\phi_1 cos\phi_2 \ge 0$ So first, I ...
41 views

What are ordered tuples?

I've been asked to explain the concepts of relations and I'm unable to find what Ordered Tuples are on the internet. Could the answer please be given in the most basic form as I'm not brilliant at ...
51 views

Graphing Relations and Their Properties [closed]

I am working on a homework assignment for a discrete math course and am completely lost on relations. I'll put up some examples of problems, could somebody please push me in the right direction or ...
17 views

54 views

56 views

43 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
39 views

I'm studying for a test and there's a question that I've tried and I don't understand: Let $E$ be a binary relation on a set $A$; let a binary relation $F$ on $\mathcal P (A) \setminus \{\emptyset\... 1answer 35 views Proving that divisibility in an integral domain is a partial ordering Given that R is an integral domain. I'm trying to prove that divisibility on this set constitutes a partial ordering. In particular, I have defined the relation$y \leq_{\,d} x$on R by$y|x$. ... 1answer 29 views What is the composition of the two given relations$R_1\circ R_2$? I have a set$A = \{a,b,c,d\}$on which two relations are$R_1=\{(a,b),(a,d),(b,c),(c,a),(c,d),(d,b)\}$and$R_2=\{(a,b),(b,c),(d,c),(a,d),(a,c)\}$. What will$R_1\circ R_2$be?$\circ$is a the ... 1answer 44 views How do i determine whether a relationship is transitive and has the trichotomy property or not? I have a relation on the set A {a,b,c,d}- R1={(d,c),(c,a),(b,d),(d,a),(a,a),(b,c),(b,a)} I need to determine whether this relation has the trichotomy property or not? P.S- If by any chance you do ... 1answer 33 views Denotation of composite of relations We denote the composite of relation R and relation S by$S \circ R$. Since the order matters, meaning composite of R and S is not composite of S and R. I am trying to understand why the denotation of ... 2answers 39 views Is the relation$P$, for all real numbers$x$and$y$that satisfy$xPy $iff$x^3 - y \ge y^3 - x$, a reflexive, symmetric and transitive relation? Image of an exam question I am revising link: [1] For (i) I have stated the relation is reflexive as$\forall x ∈ \Bbb R, xPx$is reflexive as$x^3 \ge x $For (ii) I have stated that the relation ... 1answer 29 views Graph the straight line corresponding to the rule (y=7x) for 0≤x≤15 I have attempted this question but I don't really know where to even start. I have graphed y=7x but i'm not sure where to go from there. I am a bit stuck on graphing a line that is relating to 0≤x≤15. ... 1answer 24 views Calculate the number of equivalence classes [closed] Let$A = \{1,2,3,4,5,6\}$and let$B = \{1,2,3\}$Let$R$be a relation such that$R=\{(x,y) \in P(A) \times P(A): x \cap B = y\cap B\}$How many equivalence classes are possible? I'm kinda stuck ... 1answer 30 views Relation$ (x,y) \in \rho \Leftrightarrow (\exists k \in \mathbb{Z})\mid x- y=3k\$

I know that there is a similar question here, but it's about classes of equivalence of this relation. I would like to know how to prove that this is an equivalence relation. It seems simple, but the ...