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

2
votes
3answers
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 ...
4
votes
3answers
3k views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
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 ...
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 ...
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 ...
2
votes
1answer
1k views

How many relations are there between the set A and B?

$A =\{1,2,3\}$ and $B=\{a,b\}$ Based on the text, the number of relations between sets can be calculated using $2^{mn}$ where $m$ and $n$ represent the number of members in each set. Given this, I ...
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'$...
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
35 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 ...
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'$ ...
-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
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 ...
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$ ...
-1
votes
2answers
51 views

Prove that $\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$ is reflexive and symmetric but not transitive.

Question: Let $A=\{a, b, c\}$ and let $R=\{(a, a), (b, b), (c, c), (a, b), (b, a), (c, a), (a, c)\}$. Prove that $R$ is reflexive and symmetric but not transitive. I checked that the relation $R$ is ...
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{ ...
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 ...
0
votes
2answers
59 views

Discrete mathematics, equivalence relations, functions.

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking) Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on $A$...
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 ...
5
votes
4answers
3k views

Why is the empty set finite?

On page 25 of Principles of Mathematical Analysis (ed. 3) by Rudin, there is the definition (excluding the irrelevant parts for this question): Definition 2.4: For any positive integer $n$, let $...
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 ...
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 }...
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 ...
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 ...
42
votes
4answers
6k views

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
8
votes
3answers
978 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
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 $\...
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 ...
8
votes
1answer
97 views

Is there a first-order formula expressing this property?

Suppose $R$ is a binary relation on $\{0,1\}^*$ (where $\{0,1\}^*$ is the set of all finite words over the alphabet $\{0,1\}$), and suppose that for all $x \in \{0,1\}^*$, the number of $y$ such that $...
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 ...
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.
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 ...
1
vote
1answer
684 views

Classify relations “is greater than or equal to”

Classify the following relations as reflexive, irreflexive, symmetric, antisymmetric or transitive. Explain each property in the context of the question. “is greater than or equal to” on the set of ...
-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?"