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
1answer
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 ...
0
votes
1answer
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, ...
1
vote
2answers
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?
1
vote
2answers
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 ...
21
votes
7answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
26 views

Proving Equivalence Relations by providing an example based on given subsets.

Let $X$ be the set of all nonempty subsets of $\{1, 2, 3\}$. Then $X= \{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$ Define a relation $ R $ on $X$ as follows: For all $A$ and $...
4
votes
1answer
104 views

A possible alternative to the Axioms of Pair, Union, Infinity and Replacement

In this question we assume that all formulae are in the language of $\sf ZFC$ and that $\sf ZFC$ is consistent. Recall that we say that a formula $\varphi(x,y)$ represents a set-like class relation ...
0
votes
1answer
33 views

Proving the Binary Relation is an Equivalence Relation

Let $R$ be a binary relation on a set A and suppose R is symmetric and transitive. Prove the following: If for every $x$ in $A$ there is a $y$ in $A$ such that $x R y$, then $R$ is an equivalence ...
0
votes
0answers
14 views

Prove that $L = \{((a,b), (a',b')) ∈ (A × B) × (A × B) \mid aRa', \text{and if } a = a' \text{ then } bSb'\}$ is a partial order.

I am working on a problem from Velleman's book "How to Prove it." If you are able to show the work with the "Givens" and "Goals" style like the book shows, that would be much appreciated, if not, ...
0
votes
1answer
14 views

Elements of a relation

So I proved this was a relation, but I'm having real trouble identifying the elements of the relation. I'm not quite sure what I am supposed to do. Are the elements of the relation [(0,3)] all of the ...
1
vote
2answers
40 views

Properties of given binary relation?

A binary relation R on $N×N$ is defined as follows$: (a,b)R(c,d)$ if $a≤c$ or $b≤d$. Consider the following propositions: $P: R$ is reflexive $Q: R$ is transitive Which one of the following ...
4
votes
3answers
479 views

Why is one relation transitive but the other is not?

From what I have read about a transitive relation is that if xRy and yRz are both true then xRz has to be true. I'm doing some practice problems and I'm a little confused with identifying a ...
1
vote
1answer
63 views

If $R$ is an equivalence relation, is $R = R^3$?

If $R$ is an equivalence relation, does $R = R^3$ ? I tried for about 40minutes to construct a relation $R$ that is an equivalence relation that when multiplied with itself twice, it will make $R = R^...
1
vote
1answer
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. ...
2
votes
3answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
-5
votes
1answer
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 ...
1
vote
1answer
17 views

Relation and proving reflexivity

The relation R is defined on integers by $xRy$ if and only if $x^2y=ymod6$. Prove that $R$ is reflexive. So far I have: Let $x=y$ $x^2x=xmod6$ I don't know how to go from here... because $x^2=...
0
votes
1answer
32 views

Relations and equivalence classes example

I'm studying discrete mathematics in my course at university and I'm going through notes on relations, equivalence relations and classes and such. I've come across an example on equivalence classes ...
0
votes
1answer
27 views

Initial condition for recurrence relation

I have a question regarding the solution of this problem. The problem is: Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we ...
1
vote
1answer
28 views

How can an antisymmetric relation be not reflexive? [duplicate]

Reading a book (I do not know if I can mention its title) I found these definition (the following is exactly the quotation from the pages of the book): "For a binary relation R on a set Y, that is, R⊆...
0
votes
1answer
57 views

Equivalence Relations on Products

Let $G$ be a group, $p$ a prime dividing $|G|$ and $X = \{(x_0,..., x_{p−1})) ∈ G_p:∏_i x_i = 1\}.$ Let $E$ be the relation defined on $X$ by $(x_0, ..., x_{p−1})E(y_0,..., y_{p−1})$ if there exists $...
1
vote
2answers
54 views

Which of the following are partitions of $\mathbb R^2$

Is my answer correct? Can someone provide me better explanations for (a) ,(c) and (d)? Which of the following collections of subsets of the plane $\Bbb R\times\Bbb R$ are partitions? $(a)$ $\...
1
vote
1answer
20 views

How do find if a relation is a function algebraically

Is there a way to see if a relation is a function without having to do a "vertical line test" (where you draw a vertical line on the graph and if there line touches two points then it's not a function)...
0
votes
0answers
85 views

Prove that any relation that is a partial order / equivalence is identity relation

Prove that any relation that is both an equivalence relation and a partial ordering is the identity relation. That is, if X is a set and R is a relation on X that is both a partial ordering and an ...
0
votes
0answers
54 views

Relation on a set of relations with these limitsprove equivalence / partial order

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R=\{(\mathscr P,\mathscr Q)\mid \mathscr ...
1
vote
0answers
59 views

Is this relation $\mathscr R$ on the set of relations, reflexive?

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R = \{(\mathscr P, \mathscr Q) \mid \...
0
votes
1answer
226 views

Bijection preserves equivalence relation

Suppose f is a bijection between two sets A and B. Then x, y ∈ A gives us f(x), f(y) ∈ B. Prove that bijections preserve equivalence relations. That is, if R is an equivalence relation on A, then R' ...
2
votes
2answers
37 views

Show given relation $R$ is equivalence relation on $S$

I will display the exact problem, then my questions. I have searched to the extremes to figure this out and can't: Show that the given relation $R$ is an equivalence relation on set $S$. $S$ is the ...
0
votes
0answers
19 views

Relation and Cartesian Product

Let $A=\{-1,2,5,8\}$, $B=\{0,1,3,6,7\}$ and $R$ be the relation is one less than form $A$ to $B$. Then, 1) Find $R$ as a set of ordered pairs 2) Find domain and range of $R$. 3) Find $R^{-1}$ as a ...
1
vote
1answer
34 views

The maximum possible size of $R$ is_____?

A function $f : N^+ → N^+$, defined on the set of positive integers $N^+$, satisfies the following properties: $f(n) = f(n/2)$ if $n$ is even $f(n) = f(n+5)$ if $n$ is odd Let $R = \{i|∃ j : f(j) = ...
0
votes
1answer
56 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: $$A=\{...
1
vote
1answer
51 views

Reflexive and transitive closure of a binary relation

If relation A is a binary relation between terms of the form (C,s), and relation B is the reflexive and transitive closure of A, could somebody briefly explain what it means to be a 'Reflexive and ...
1
vote
1answer
36 views

How do I determine whether this relation is transitive?

I've been given this relation, and I'm supposed to determine whether it is transitive. I understand the definition of transitive (sort of, in theory) but I'm not sure how to put it in action here. $$\{...
0
votes
0answers
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
-1
votes
1answer
39 views

Transitivity of a binary relation on the power set

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\...
0
votes
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$. ...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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. ...
-1
votes
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 ...
1
vote
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 ...
0
votes
1answer
31 views

Given two Numbers, Finding Relation to third

I'm trying to find the relation of three numbers. I know that two numbers have a relation that equate to the third. The tricky part is that they don't have to equal the third number exactly,but should ...
1
vote
2answers
37 views

How to find all relations of a set and determine which of them aren't functions?

Given the following question: "How many relations are there on {2, 3}, that aren't functions from {2, 3} to {2, 3}?" The answer gives 16 relations, of which 12 aren't functions. How did they ...