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
0answers
46 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
0answers
18 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,...
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 ...
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)$$ ...
0
votes
2answers
34 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 $\...
2
votes
1answer
38 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 ...
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
51 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
25 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
19 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
32 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
39 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
55 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$ ...
0
votes
0answers
19 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) \...
1
vote
2answers
31 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
3answers
46 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.
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
23 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!
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
17 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
2answers
101 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
2answers
41 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
39 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
3answers
34 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
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
29 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
20 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 ...
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.
1
vote
2answers
50 views

Is the intersection of a relation that is antisymmetric and a relation that is not antisymmetric, antisymmetric

Given a binary relation R,S on set A, assume that R is anti-symmetric. Show R intersection S is anti-symmetric. I started this proof by stating the definition of anti-symmetric with R which is $$ ∀...
0
votes
2answers
18 views

Proving a relation is anti-symmetric and transitive

$P$ is a binary relation. $P ⊆ \mathbb{R}^2$. $P = \{(x,y): y = |x|\}$. As I understand for relation to be transitive: $(a,b) \in P$ and $(b,c) \in P$ then $(a,c \in P)$ for this particular relation ...
1
vote
1answer
31 views

Equivalence relation and class, Proof.

The relation $P$ on $ℝ$ is defined by $xPy$ iff $x^2=y^2.$ (a) Prove that the the relation $P$ is an equivalence relation. (b) Describe the equivalence class of $3$ and $0$. In order to ...
1
vote
0answers
26 views

Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup A_2$.

Suppose $R_1$ is a partial order on $A_1$, $R_2$ is a partial order on $A_2$, and $A_1 \cap A_2 = \emptyset$. Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup ...
4
votes
4answers
487 views

Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and couldn'...
0
votes
0answers
21 views

Let $L= \{(x,y)\in \mathbb R \times \mathbb R : x \leq y\}$, and let $C=\{x \in \mathbb R : x > 7 \}$. Prove that C has no L-smallest.

Definition: Suppose R is a partial order on a set A, $B \subseteq A $ and $b \in B$ . Then b is called an R-smallest element of B iff $\forall x \in B [b R x]$ Goal is to prove the following: Let ...
-1
votes
1answer
25 views

Discrete Maths Relations on the set {1,2,3,4}

I just want to make sure that I am doing these correctly. Here is what I have: Reflexive, symmetric, antisymmetric and transitive: And i have - {(1,1) (2,2) (3,3) (4,4)}. not Reflexive, not ...
0
votes
0answers
19 views

What is a transitive relation on set S

MY answer: Given r,s,t$\in S$ a transitive relation on the set $S$ is when the elements $rRs$ and $sRt$ then $rRt$ i.e., $rRs\land sRt\rightarrow rRt$ Does my definition words correct?
0
votes
0answers
22 views

Define symmetric relation R on set S

Answer: A symmetric relation R on S is that For all $x,y\in S$ such that $xRy$ implies $yRx$. meaning if the element x is related to y, then it is also true the other way around that element y is ...
0
votes
1answer
40 views

Can someone explain why is $R=\{(1,1), (1,2)\}$ transitive?

Using a digraph I understand transitive relation to be a loop, but $R=\{(1,1), (1,2)\}$ is not a loop. Thank you for your time!
3
votes
0answers
37 views

Restriction to equivalence relation is equivalence relation

Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $. $\mathbf{...
1
vote
1answer
39 views

Can someone explain antisymmetric versus symmetric relation of sets?

If $$A = \{1,2,3,4\} $$ and $$R = \{(3,3), (4,4), (1,4)\}$$ This example is antisymmetric but not symmetric. However, the definition of Antisymmetric taken from Merriam-Webster is this: ...
2
votes
2answers
24 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 ...
0
votes
2answers
23 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?