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
20 views

Sums and products of binary relations

Every function $f: X \rightarrow Y$ is actually a relation between $X$ and $Y$: $$R_f = \{ (x, f(x)) : x \in X \}$$ If $X$ and $Y$ are fields, we can take sums and products of two functions and say $...
0
votes
1answer
22 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
0
votes
3answers
57 views

What does it mean to say “a divides b”

I am not a number theorist and I am learning about relations. I encountered a relation that says $a \leq b$ if $a$ divides $b$ Can someone clarify what it means to a number to divide another ...
2
votes
1answer
29 views

Existence of an inverse relation for $R \subseteq A \times A$.

I'm stuck with the following problem: Given the set $A = \{1,2,3,4,5\}$, construct a relation $R \subseteq A \times A$ such $$ R \circ R^{-1} = \triangle_A = \{(a,a) \hspace{5pt} | \hspace{5pt} a \...
0
votes
0answers
24 views

(Order Relation) Monotone Continuous Complete Preorder on $\mathbb{R^L_+}$ has $y\geq x\rightarrow y\succsim x$

I am trying to show a monotone continuous complete preorder on $\mathbb{R^L_+}$ has $y\geq x\rightarrow y\succsim x$. Can you please share your 2cent on the below proof? Thank you! Point of ...
0
votes
1answer
38 views

$\succsim$ preorder on X being continuous imply lower contour set closed

$\succsim$ is preorder (i.e. preference relation) on X that is continuous. This implies the lower contour set is closed. Would you please share your 2 cent on my parenthesis explanation (e.g. line ...
0
votes
1answer
42 views

(Proof) Representing preorder $\succsim$ as a real-valued function.

I am reading a proof and having a hard time understanding on some parts. In math language, the proof is trying to show the existence of continuous preorder $\succsim$ (i.e. preserved under limits, ...
1
vote
0answers
45 views

I am confused about this notation for matrix representation.

I am confused about this notation from the image below. How can you represent something like (1,2),1 as a 2D matrix? For S1 = (0,1,2) and S2 = (0,1) I would expect two matrices like: [(1,0),(1,0),...
1
vote
1answer
28 views

Find the minimum, maximum, minimals and maximals of this relation

Tell if the following order relation is total and find the minimum, maximum, minimals and maximals: $$\forall a,b \in\mathbb Z,\ \ a\ \rho\ b \iff a \leq b\ \text{ and }\ \pi(a) \subseteq \pi(b)$$ ...
1
vote
0answers
16 views

Are there established names and/or symbols for these orderings?

Consider the following orderings on $\mathbb{Z}^2$. Say $(a, b) \leq_1 (c, d)$ if $a \leq c$ or if $a = c$ and $b \geq d$. So for instance $$(1,3) <_1 (1,2) <_1 (1,1) <_1 (2, 3) <_1 (2,...
1
vote
2answers
3k views

Finding all partial order relations on a set

Suppose I have a set $A$ such that $A$ = $\{1, 2, 3, 4, 5\}$ (or $A$ = $\{1, 2, 3, 4\}$ or $A$ = $\{1, 2, 3\}$ or any other finite small set). How can I find the total number of partial order ...
0
votes
0answers
5 views

Dependency and Independency relation in Trace monoid.

I was reading the paper on Trace Theory. Author introduces Dependency and Independecy relations as finite, reflexive and symmetric relation and Independecy relations as symmetric and irreflexive ...
0
votes
2answers
33 views

Which one of these two is an equivalence relation

I'm having an issue with the following exercise: Given $\alpha$ and $\beta$ two binary relationships defined in $Z$ such that: $$\forall m,n \in Z, n\ \alpha\ m \iff n = m\ \ \vee\ \ rest(n,7)\ +...
1
vote
2answers
14 views

Section and segment of a relation $R$

$\mathbf{Definitions:}$ $Z$ is a $R$-section of a set $X$ iff $Z\subseteq X$ and $x\in Z$ whenever $x\in X \ \land y\in Z \land \ xRy$, $\ $for some relation $R$ on $X$ The $R$-segment of a set $X$...
1
vote
0answers
17 views

Determine whether or not the poset $(\mathbb{N}, \propto$) has a least element

"Define a relation $\propto$ on the natural numbers $\mathbb{N}$ by declaring that for $x, y \in \mathbb{N}$, $x \propto y \iff (x=y)$ or $(3x \leq y)$ a) Show that $\propto$ is a partial order on $\...
0
votes
2answers
22 views

What is the reflexive closure of the empty relation ∅ over a set A?

What is the reflexive closure of the empty relation ∅ over a set A? I understand that R is reflexive if A=∅, and isn't if A is nonempty. But what about the reflexive closure of R?
2
votes
1answer
31 views

Prove that $R\cap S$ is symmetric, transitive, and anti-symmetric.

If you can confirm these are done correctly or offer another way to do so I would greatly appreciate it. Also how would you go about proving $R\cap S$ is reflexive? What assumption if any would be ...
0
votes
1answer
45 views

(Conceptual) Continuity of binary relation $\succsim$ and definition using contour sets

Some background information: $\succsim$ is a binary relation that represents preference between two goods. $\succsim$ means "x is at least as good as y." Continuity of this relation is defined to be ...
3
votes
3answers
5k views

Is it possible for a relation to be symmetric, antisymmetric, but NOT reflexive?

If $A$ is a set $\{2,4,6,8\}$, and we are asked to give a relation on $A$ that is: symmetric, antisymmetric, but not reflexive, is this possible? If we were to say $\{(2,2),(4,4)\}$, it would indeed ...
0
votes
2answers
33 views

Find the least upper bound of S in $\mathbb{N}$?

"Define a relation on the set N of natural numbers by declaring that for all x, y ∈ N, $x \propto y \iff $(x = y) or (4x ≤ y). Let S = {2, 4, 6, 8, 10, 12} be a subset of $\mathbb{N}$ . (i) Find all ...
2
votes
1answer
47 views

How many transitive relations on a set of four elements are functions?

How many functions $f:\left \{ a,b,c,d \right \}\rightarrow \left \{ a,b,c,d \right \}$ are also transitive relations? Sorry if I have mistakes in my English. I understand that $f$ is supposed to ...
1
vote
3answers
22 views

Infimum and supremum of subset of inclusion Power set

I'm having trouble understanding the following exercise: Given $U=\{1,2,3,4\}$ with $A=P(U)$ the power set of the elements of $U$ and $R$ the inclusion relation over $A$. Determine the infimum and ...
0
votes
1answer
21 views

There exist partition of set $X$ due to relation $R$ and surjection $g: X\to X|_R$ and injection $h:X|_R \to Y$ such as $h \circ g=f$

$f: X\to Y$ is function. Prove: There exist partition of set $X$ due to relation $R$ on $X$ and surjection $g: X\to X|_R$ and injection $h:X|_R \to Y$ such as $h \circ g=f$
0
votes
2answers
30 views

Discrete Mathematics (Closure Problems)

$R = \{(x, x+1)|x \in \mathbb{Z}\}$ $\mathbb{Z}$ is the integers and could be negative or positive. Create the closure of the the following: a. $t(R)$ --> transitive closure of R b. $rt(R)$ --> ...
0
votes
0answers
17 views

Image maps for Relations

So I noticed a rather interesting thing about the image function and preimage function. The wikipedia page for Image: https://en.wikipedia.org/wiki/Image_(mathematics) (notation for image section) ...
0
votes
1answer
29 views

Transitive closure of $p=\{(1,3),(2,1),(3,2),(4,1)\}$

What is the transitive closure of the relation $p$? I thought it would just be $t=p \cup p^2$. But in the solution I have, there is also $p^3$. Why is this so? What I showed is already the smallest ...
0
votes
0answers
17 views

Increasing induced functions.

I am studying partial ordered sets. I have a problem with the following example: $ \text{Let X and Y be sets and } f \in Y^X. \text{The induced functions } f:P(X) \to P(Y)$ and $f^{-1}:P(Y)\to P(X) \...
0
votes
0answers
31 views

Closure of Poset $Q_n = \{x : x \mid n\}$

Let $(S, <)$ be a poset. A smallest poset $(S', <)$ is called a closure of poset $(S,<)$ iff $S$ is a subset of $S'$, $\operatorname{glb}(x,y)$ is in $S'$, and $\operatorname{lub}(x,y)$ is in ...
1
vote
1answer
24 views

What does “induced operations” means in congruence operations

It says: prove that R is a congruence (it means it's a relation of equivalence and it preserves operations) ith respect to sum and multiplication in $\mathbb{R}$. $a,b\in \mathbb{R}: aRb \iff a-b \in ...
0
votes
1answer
38 views

The difference between congruence and equivalence class?

I've got an excercise solved by my teacher, it says I've got to prove a relation $R$ of elements in $\mathbb{R}^2$ is a congruence. In the solved exercise he just proved Reflexivity, transitivity and ...
3
votes
3answers
52 views

Can Relations have a Domain and Codomain?

Does it make sense to talk about the domain and codomain of a relation? For example if the relation, $R$ $$x^2+y^2=r^2$$ only takes values $(x,y)\in\mathbb{R}^2$ its domain would be $\mathbb{R}^2$ ...
1
vote
2answers
29 views

infinite equivalence classes

How would you prove that this relation $$(a,b)R(c,d)$$ if and only if $$a+d=b+c$$ has infinite equivalence classes if it is defined in a set with only non negative integers? I've already proved that ...
0
votes
2answers
30 views

If $A=\{1, 2, 3\}$ and $R=\{(1, 1),(2, 2), (1, 2), (2, 1), (1, 3)\}$ then is $R$ transitive?

OK this is a general question. How do I determine if a relation given to me is transitive or not? Let the following be sets $A=\{1, 2, 3\}$ and $R=\{(1, 1),(2, 2), (1, 2), (2, 1), (1, 3)\}$ then is $...
-2
votes
1answer
34 views

How do I determine whether a function is onto or not without drawing the graphs?

OK this is a general question. Please explain with examples if you can. How do I determine whether a function is onto or not without drawing the graphs? I know the function is onto when both the range ...
0
votes
2answers
96 views

What is the period of $f(x) = \cos (x) \cos(2x) \cos(3x)$? [closed]

What is the period of $f(x) = \cos(x) \cos(2x) \cos(3x)$? Please tell me the method plus the logic behind solving these kind of problems .. Plus is there any property for even functions like even ...
0
votes
3answers
45 views

Check for an onto function

Why is $y= x^{2006} + x^{-2006} +5$ not an onto function if $f(x):\mathbb{R} \rightarrow \mathbb{R}$ Please provide an explanation.
0
votes
1answer
21 views

How to construct a symmetric, transitive and reflexive relation

If R is a binary relation in a set X ≠∅ that is symmetric, transitive, then R is reflexive. This is false and I have to change the argument to make it true. How can I do this? Thanks!
3
votes
3answers
62 views

Solution set for $\lfloor x\rfloor\{x\}=1$ [closed]

What is the solution set for $\lfloor x\rfloor\{x\}=1$ , where $\{x\}$ and $\lfloor x\rfloor$ are respectively fractional part and greatest integer function of $x$. P.S.: the answer is $\{m+1/m:m\in\...
0
votes
1answer
168 views

What is confluence?

I got a worksheet at university last week, and the first task is: A relation $R$ of a set $M$ is confluent, if $ \forall x \in M \forall w_1,w_2 \in M :((xRw_1 \land xRw_2 ) \to \exists z \in M (...
2
votes
2answers
27 views

Proof about equivalence relations

Let $R$ be a reflexive and symmetric relation on a set $X$. A pair $x,y ∈ X$ are connected via $R$ if there are elements $x = x_0, x_1, . . . , x_k = y$ such that $(x_i, x_{i+1}) ∈ R$ for all $i = 0, ...
0
votes
0answers
16 views

Proof about intersection of relations

a) Assume R and S are symmetric. Prove that R ∩ S is symmetric $R \cap S$ is set of all orders pairs in the form $(a,b)$ that are in both $R$ and $S$ Let $(a,b) \in R$ and $(a,b)\in S$, so $(a,b)\...
0
votes
3answers
33 views

Are two relations equal if they are both equivalence relations

If R and S are both equivalence relations on a non empty set A, then does R=S? That was the question on my assignment, I think they are because equivalence relations have to be reflexive, symmetric ...
0
votes
1answer
22 views

Is this the correct directed graph for this relation?

The relations is defined by the set of ordered pairs $$R = \{(1,2),(1,3),(2,3),(3,4),(3,1),(3,2),(3,3),(4,4)\}.$$ Please excuse my drawing, I'm very sorry for it, I hope it's understandable though.
0
votes
2answers
17 views

Determine if the binary relation is reflexive, symmetric, anti-symmetric, or transitive.

Let $X$ be any set containing at least three distinct elements $a,b,c\in X$. Let $S$ be the relation on $\mathbb{P}(X)$ such that $(A,B)\in S$ when $A\cap B=\{a\}$. I'm not even sure how to write ...
0
votes
1answer
20 views

Is the complement of a symmetric relation symmetric?

My assignment asks us to prove or provide a counter example for If R is symmetric, then Rc is symmetric. I know that if R is symmetric, then (x,y) and (y,x) are both in R, but what I do not ...
0
votes
1answer
19 views

Help with set theory question about binary relations

On my assignment I was asked the question: Determine, with reason, if the binary relation is reflexive, symmetric, antisymmetric, or transitive. Let X be any set containing at least three distinct ...
6
votes
2answers
153 views

Is my understanding of Binary relations correct?

On my assignment it asks Determine with reason if the binary relation is reflexive, symmetric, antisymmetric or transitive. $$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \text{ is ...
1
vote
2answers
23 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
-1
votes
0answers
21 views

Find the domain and ranges of the following relation

$R$ from $A=\left\{1,2,3,4\right\}$ and $B=\left\{2,3,4,5,6,8,10\right\}$, where $R$ is a relation from $A$ to $B$ defined by $a|b$ (a divided b), $\left(a,b\right) \in R$.