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
2answers
22 views

Proving that this relation is an order relation on $\Bbb N$?

$S := \{(x, y) \in \Bbb N / \{1\} \times \Bbb N\ / \{1\}$ $x$ and $y$ have the same number of prime factors and $|x - {100\over{3}}| \leq |y - {100\over{3}}|$$ \}$ Is $S$ an order relation on $\Bbb ...
0
votes
0answers
23 views

I need help to verify 5 order relations

Which the following relations are order relations on the set $\Bbb M$? $$\Bbb M: \{1, 2, 3\}$$ $$R:\{(1, 1),(3, 3),(1, 2),(2, 3),(1, 3)\}$$ It is not an order relation because $(2,2) \not \in R$ => ...
3
votes
2answers
45 views

Is the relation $R$ on $\Bbb N$ given by $(a,b)\in R\iff a\mid b$ an equivalence relation?

$R \subset \Bbb N \times \Bbb N$ Is this an equivalence relation? $$R=\{(a,b)\in \Bbb N\times \Bbb N\,:\,a\mid b\}$$ I would argue that it is reflexive because $a\mid a$, but it is not symmetric ...
0
votes
0answers
12 views

What is Smallest order relation generated by $R$? [on hold]

If $R$ is a relation, then what is smallest order relation generated by $R$. $aRb$ if $b$ covers $a$.
0
votes
2answers
18 views

how is the relation defined by (x,y)$\in$ R iff and only if $x^2-4xy+3y^2$ not symmetric?

A Relation R on the set N of Natural numbers be defined as (x,y) $\in$R if and only if $x^2-4xy+3y^2=0$ for allx,y $\in$N then show that the relation is reflexive,transitive but not SYMMETRIC. i got ...
0
votes
1answer
22 views

Proving transitivity of a relation

Let R be a reflexive relation on a nonempty set X. The asymmetric part of R is defined as the relation $P_r$ on X as $xP_ry$ iff $xRy$ but not $yRx$. The relation $I_r$ = $R\setminus P_r$ on X is ...
1
vote
1answer
26 views

About normal spaces and proximities

I am trying to write another proof (using my theory) of Urysohn lemma. This question has appeared during this research. Let $\mu$ be a $T_4$ (normal) topology on some set $\mho$. Let $\delta$ be ...
1
vote
1answer
25 views

Why study graph representations of equivalence relations?

What is the importance of representing a (an equivalence) relation using digraphs? Is there any geometric aspect to study relations using graphs (of vertices and edges)?
0
votes
2answers
36 views

An elementary problem about binary relations

I am now trying to solve a research problem. I present its elementary special case so that you can participate in my research. Find binary relations $f$ and $g$ on a set $U$ such that the following ...
2
votes
1answer
80 views

Does this category have a name? (Relations as objects and relation between relations as morphisms)

Given two relations $R\subseteq A\times B$ and $R'\subseteq A'\times B'$. Is it known/used that every relation $r\subseteq R\times R'$ can be characterized by two relations $\alpha\subseteq A\times A'$...
0
votes
1answer
11 views

How is this relation not a Transitive relation?

The question says:- $A = \{1,2,3,4,5,6\}$ and $R = \{(S_1, S_2) :S_1, S_2 \subset A, S1\nsubseteq S2\}$. My thought:- $S_1$ contains the subsets of $A$ and $S_2$ contains the subset of $A$ and $S_1$ ...
-2
votes
3answers
87 views

Proving why $\Bbb Z_{4} \rightarrow \Bbb Z_{6} \text{ given by } f(\overline x) = [2x+1] $ is not a function. [duplicate]

Question presented: Is following a function from the indicated domain to the indicated co domain? $f:\Bbb Z_{4} \rightarrow \Bbb Z_{6} \text{ given by }$ $ \bbox[white,1px,border:1px solid red]{...
1
vote
3answers
36 views

Trouble proving that this is a function?

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ given ...
1
vote
1answer
43 views

Is “closedness” a proper word?

In one of my papers I had to prove a list of properties of a set, say, $S=\{a,b,c\}$. Among them we have a fact that $S$ is downward closed with respect to a binary relation $R$. I found it awkward to ...
2
votes
0answers
12 views

Notation for the projection of a relation onto one component space

Suppose $R \subseteq S \times T$, i.e. $R$ is a relation between $S$ and $T$. What is the notation for the projection of $R$ onto $T$, i.e. for $\{t: \forall t \in T, \exists s \in S, s.t. (s,t) \in ...
1
vote
1answer
95 views

A category of relations - or two different?

Objects in the category Rel2 (my notation) are the relations $r\subseteq A\times B$, $r'\subseteq A'\times B'$ (the morphisms in Rel) and morphisms are pair of relations $\alpha\subseteq A\times A'$ ...
1
vote
6answers
64 views

Definition of Relation of a Set

The standard definition of a relation of an arbitrary set A is a subset of the set product of A, AxA. Is it okay to define relation R to be a subset of the set product AxA such that R has at least ...
2
votes
1answer
61 views

Geometric arithmetic: triangular number triples [closed]

Call a triple $x, y,$ and $z$ of numbers triangular if and only if there is a triangle whose sides are in the triple ratio $x:y:z$. Since the sum of two sides of a triangle exceeds the remaining side, ...
2
votes
1answer
27 views

a question on linear relations

Given that $R\subseteq \mathbb{C}^n\times \mathbb{C}^n$ is called linear relation $\Leftrightarrow R$ is a linear space. Its inverse relation is $R^{-1}:=\{(y,x)\in \mathbb{C}^n\times \mathbb{C}^n:(...
-3
votes
1answer
52 views

Why does $<^{-1}$ not equal $>$?

Let us investigate the powers of $<$: ${<^1} = \{(0,1);(0,2);(0,3);...;(1;2);...\}$ ${<^2} = \{(0,2);(0,3);(0,4);...;(1;3);...\}$ ${<^3} = \{(0,3);(0,4);(0,5);...;(1;4);...\}$ ... ${<^...
0
votes
2answers
50 views

How to Show that this relation is not well defined. [duplicate]

We represent an element of the domain as an equivalence class $\bar x$, and use the notation $ \left[ x \right]$ for equivalence classes in the codomain. Show that this is not well defined. $ f: \...
2
votes
2answers
22 views

Proving that R is a partial Order.

Define the relation $\Bbb R \times \Bbb R$ by $(a,b) \; R$ $ (x,y)$ iff $a \le x$ and $b \le y$ , prove that R is a partial ordering for $\Bbb R\times\Bbb R $ . A partial order is if R is reflexive ...
0
votes
1answer
43 views

Describe the equivalence relation of the following set with the given partition.

Describe the equivalence relation of the following set with the given partition. $ \Bbb N $ , $ \{\{ 1 \}, \{2,3 \}, \{4,5,6,7\},\{8,9,10,11,12,13,14,15\}....\} . $ What this question has me ...
1
vote
2answers
18 views

Checking reflexive, symmetric and transitive properties of $\neq$ on $\mathbb{N}$

QS: Indicate if the relation on the given set are reflexive on a given set, which are symmetric, and which are transitive. $\not = \text{on } \Bbb N$ So for this problem I am trying to ...
2
votes
2answers
25 views

Proving that S is not an equivalence relation.

Consider the relations R and S on $\Bbb N$ defined by $x\; R\; y$ iff $2 \;$divides $x + y$ and $x \;S \;y$ iff $3$ divides $x + y.$ $\text{QN: Prove that S is not an equivalence ...
1
vote
1answer
27 views

Proving that R is an Equivalence Relation.

Consider the relations R and S on $\Bbb N$ defined by $x\; R\; y$ iff $2 \;$divides $x + y$ and $x \;S \;y$ iff $3$ divides $x + y.$ $\text{QN: Prove that $R$ is an equivalence Relation }...
3
votes
7answers
257 views

The map $f:\mathbb{Z}_3 \to \mathbb{Z}_6$ given by $f(x + 3\mathbb{Z}) = x + 6\mathbb{Z}$ is not well-defined

By naming an equivalence class in the domain that is assigned at least two different values prove that the following is not a well defined function. $$f : \Bbb Z_{3} \to \Bbb Z_{6} \;\;\;\text{ ...
0
votes
0answers
24 views

How do relations apply in software development?

not sure if I should be asking this here or on Math exchange, anyway. I've been tasked with discussing how mathematical relations apply to software development. I have to do three case studies and I'...
1
vote
1answer
22 views

Explain why this relation has a reflexive, symmetric, antisymmetric, and transitive propery

Let S = {1, 2, 3} Let R = {(1,1),(3,3),(2,2)} So the answer is that it is reflexive, symmetric, antisymmetric, and transitive. I understand that it is reflexive, however I do not understand how it ...
0
votes
1answer
23 views

Is rounding over addition distributive?

I am trying to answer the question whether: Round(a + b + c) = Round(a) + Round(b) + Round(c) (Forgive me if "distributive" is the wrong term, been some time ...
0
votes
0answers
21 views

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation Reflexivity: Obviously it is not Reflexive since $x=\sqrt{2}$ and $y=\sqrt{2}$ and $\...
8
votes
3answers
979 views

Is every relation which is transitive and symmetric also reflexive?

I have seen a proof that every relation which is symmetric and transitive is also reflexive. if $A=\{1,2,3\}$ Then if $R=\{(1,2)(2,1)(1,1)\color{blue}{(2,2)}\}$ here $R$ is symmetric and transitive ...
0
votes
1answer
24 views

Composition method and constructing a relation.

Let $R = \{(1, 5), (2, 2), (3, 4), (5, 2)\}$, $S = \{(2, 4), (3, 4), (3, 1), (5, 5)\}$, and $T = \{(1, 4), (3, 5), (4, 1)\}$. Find (1)$\quad R ∘ S$ (2)$\quad T ∘T.$ (3) $\quad T∘S$ ...
0
votes
0answers
24 views

Transitive Connnectivity

Can someone help me find the transitive closure I'm so confused, additionally how do u find $S \circ R$? of a set suppose $S=\{(2,1), (3,2) (1,3)\}$ and $R= \{(1,2), (2,3), (3,1)\}$ What I'm doing ...
0
votes
0answers
37 views

If R is a relation, then what is $R^0$?

I'm sorry if this seems like a question asked before doing any research, but the discrete math textbook I'm using doesn't mention it, and I tried googling it, but I don't even know the name of it, so ...
0
votes
2answers
58 views

Is it possible to have a linear order that is not “on a line”?

I am looking at some problems on linear order. It seems in all the problems, I am dealing with things that are 1D Whether it is $\mathbb{R}$ itself, or $\left\{\dfrac{1}{n}|n \in \mathbb{Z}_+\right\}\...
1
vote
1answer
19 views

Proportionality between two quantities

Its known that if one variable is proportional to two others than it is also proportional to their product. $$\forall a,b,c\in ℝ:a\propto b\wedge a\propto c\Rightarrow a\propto b\cdot c$$ I think i`ve ...
2
votes
0answers
19 views

Do automorphisms generate any specific equivalence?

I am thinking about a structure (in terms of predicate logic), where we have a carrier set A and some relations over A (no functions). I am thinking about all the automorphisms for that structure. I ...
0
votes
1answer
37 views

Good Books on relations and functions [closed]

What are the books you would recommend to starters on the topics of Relations and functions. In your opinion why is this book better than the others.
-1
votes
1answer
49 views

Relations: How to prove $R^2R^3 = R^5$?

Relations: How to prove $R^2R^3 = R^5$ ? I tried to go by this definition but I'm not quite sure I'm in the right path. $RS = \{(x,y) | \exists z, (x,z) \in R$ ^ $(z,y) \in S\}$
0
votes
0answers
45 views

Relations, Ordered Pairs, Naive set theory by Halmos

I quote: "Explicitly: a set R is a relation if each element of R is an ordered pair;" The question is: "what about the converse? is a set of ordered pairs could be considered a relation?"
2
votes
1answer
25 views

Prove that if $R$ is a symmetric, transitive relation on $A$ and the domain of $R$ is $A$, then $R$ is reflexive on $A$.

Assume, $R$ is a symmetric, transitive relation on $A$ and the domain of $R$ is $A$. $Dom(R)=A$ implies $(\forall x \in A)(\exists y \in A)[xRy]$. Since, $xRy$ is true it follows that $yRx$ is ...
1
vote
2answers
22 views

Is there a faster way to determine partial orderings of basic finite sets?

For example, consider the set $S = \{ 0, 1, 2, 3 \}$, and the following relation on $S$: $$ R = \{(0,0), (1,1), (1,2), (1,3), (2,0), (2,2), (2,3), (3,0), (3,3) \}. $$ Obviously, I can go through ...
0
votes
0answers
26 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
30 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)...
1
vote
3answers
92 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
35 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
1answer
43 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, ...
0
votes
1answer
42 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 ...
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),...