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

5
votes
0answers
80 views

Is there a standard name for the relation $X \times Y$?

Given sets $X$ and $Y$, is there a standard name for the relation $f : X \rightarrow Y$ whose graph equals $X \times Y$? Something like the full/maximum/top/total/complete relation?
5
votes
0answers
103 views

Directed and projective limit in Rel

I'm looking for the directed (or equivalently projective) limit of a directed family of relations in the category of sets with relations between them. Consider a family $\{ R_{ij} \subseteq U_i ...
4
votes
0answers
68 views

Where can I learn more about the concept that is dual to “relation”?

Let $X$ and $Y$ denote sets. Then a relation $X \rightarrow Y$ is, by definition, a subset of $X \times Y$. Dually, we can define that a "corelation" $X \rightarrow Y$ is a partitioning of $X \uplus ...
4
votes
0answers
50 views

Metric-like families of relations

Let $X$ be an arbitrary set and to start with, let us consider a relation $\leq$ on $X$ (that is $\leq$ is a subset of $X^2$) which is reflexive and transitive. such a relation is called a preorder. ...
3
votes
0answers
39 views

Divisibilty as relation set on $(\mathbb N \setminus \{0,1\})$

So i have to see if $\prec$ is order relation where two elements $(a,b)$ and $(c,d)$ are in relation $\prec$ if $a|c$ and $2b^{2}+6b\leq2d^{2} + 6 d$. This relation is defined on set $(\mathbb N ...
2
votes
0answers
31 views

Which of the following is always true for A and B

Given that: $ P(A) = 0.5$ $P(B) = 0.7$ $P(A \cap B) = 0.3$ I have to choose one option that is true... However they all seem to be false which means I am possibly making a mistake.. The only option ...
2
votes
0answers
40 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is ...
2
votes
0answers
71 views

Using the ELO Rating System on Static Objects

The Setup Suppose we have a list of movies $m_1, m_2, \dots, m_n$ that we wish to rank in order of "quality." We define the "strength" of a movie $a$ by a function $f$ which takes in numerical ...
2
votes
0answers
24 views

How would I show the relations on this set of S?

I want to show that the set below is reflexive, anti-symmetric, and transitive. Let $S$ be the set of positive integer divisors of $180$ and consider the relation $\mid$ on $S$. I understand that ...
2
votes
0answers
244 views

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Proof or counterexample

Suppose $R$ is a relation on $A$ and $R^{-1}$ is the inverse. Give a proof or counterexample for each of the following statements. (a) If $R$ is reflexive, then $R^{-1}$ is reflexive. Let $x \in A$; ...
2
votes
0answers
66 views

Extension theorem on acyclic relations

By Sziplrajn's Theorem, we know that every partial order $\succsim$ (i.e. reflexive, transitive and asymmetric relation) on a nonempty set $X$ can be extended to a linear order (i.e. a complete ...
2
votes
0answers
94 views

How to denote the set of binary relations of which a particular ordered pair is a member?

Given a universe $U$ and two subsets $S$ and $T$ (also, both members of $U$), what is the name given to denote the set of all binary relations in $U$ where the ordered pair $(S,T)$ is a member? The ...
2
votes
0answers
42 views

Terminology for some special sets

The following predicates are used in the definition of total boundness of uniform spaces: a space is bounded if the predicate holds for every entourage, specifically for the first predicate (the ...
2
votes
0answers
721 views

Equivalence of norms is a equivalence relation

Two norms $||-||_1 $, $||-||_2$are equivalent if: for two constants $a,b$ and $x$ from $V$ a vector space over a field it holds that : $$a||x||_1\leqslant ||x||_2\leqslant b||x||_1.$$ This is a ...
2
votes
0answers
129 views

positive definite binary matrix

What are the conditions for a binary matrix $A$ (matrix with elements 0 or 1) to be positive definite (not even symmetric), i.e. $\forall x\neq 0, x^TAx>0, A_{ij}\in \{0,1 \}$ Put it another way, ...
2
votes
0answers
238 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
2
votes
0answers
146 views

How to describe all continuous maps from T to T'?

How to describe all continuous maps from $T'$ to $T$, where $T=\mathbb{R}$ with natural topology (base given by the intervals $(a,b)$ ), and $T'=\mathbb{R}$ with the topology with basis given ...
1
vote
0answers
22 views

Partial and total orders

From Exercise 4.4.9 of How To Prove It: Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Define a relation $L$ on $A \times B$ as follows: $L = \{((a, b), (a', b')) \in (A ...
1
vote
0answers
26 views

Reflexive, symmetric and transitive closure of the following graph

First of all, I have to understand which relation this graph represents: Since there are 4 different elements, suppose there's the set $A = \{ a, b, c, d\}$ The relation drawn above, I think, can ...
1
vote
0answers
44 views

Real life example of relations with various combination of properties

Attempted a set of questions as below: ...
1
vote
0answers
31 views

Does R(5,7) hold or not in this relation?

This is the question: Let $A=\{1,...,7\}$ and let $R\subseteq A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is ...
1
vote
0answers
38 views

Inverse Relation of Irreflexive Property.

We are taking the inverse of relation to check that inverse of R is transitive, reflexive , symmetric and anti-symmetric to as it is on R (not inverse).. My question is that why we are not taking the ...
1
vote
0answers
46 views

Finding Equivalence Classes for Infinite Sets

Let R be the relation on the set of rational numbers Q defined as follows: for all q, r ∈ Q, qRr iff q − r ∈ Z, where Z is the set of integers. R is an equivalence relation on Q. What is the ...
1
vote
0answers
18 views

Finding Relations algebraically

I have selfstudy on this subject and want to know if I am grasping the concept well. Here is the question: Let $A=Z^+$, all integers that are positive; Let $R$= relation defined by $aRb$ iff there ...
1
vote
0answers
119 views

Proving Reflexivity, Symmetry and Transitivity of a Relation

I'm currently taking an intro discrete math course, and I'm having some trouble understanding the rules of reflexivity, symmetry, and transitivity. The book isn't making a lot of sense to me, and my ...
1
vote
0answers
31 views

Suppose A and B are sets. If $|A| = m$ and $|B| = n$, then how many relations are there from $A$ to $B$?

Coudn't I say that it is $m\times n$ relations because the collection of all ordered pairs is the Cartesian Product $A\times B$?
1
vote
0answers
28 views

Uniqueness of smallest element in poset

Prove that a smallest element, if it exists, is determined uniquely. This is follows directly for definition. An element $a \in X$ is called the smallest element of $(X, \preceq)$ if for every $x \in ...
1
vote
0answers
38 views

Properties of relations on Z

$$R_3 = \{(x,y) \in \mathbb{Z} \times \mathbb{Z}|\frac{x-y}{5} \in \mathbb{Z}\} $$ $$R_4 = \{(x,y) \in \mathbb{Z} \times \mathbb{Z}|x > y \} $$ I need to know which one is reflexive, symmetric, ...
1
vote
0answers
33 views

A partial order with more properties than would be expected

Consider the relation: $$\langle x_1,x_2\rangle\prec\langle y_1,y_2\rangle\iff x_1,x_2,y_1,y_2\in\Bbb N\wedge x_1y_2<x_2y_1.$$ This is usually used for defining the (positive) fractions $\Bbb ...
1
vote
0answers
88 views

Have you seen this property of tolerance relations before?

Let $A$ be a set equipped with a binary reflexive and symmetric relation $\uparrow$ (such relations are often called tolerances, see also "Are there real-life relations which are symmetric and ...
1
vote
0answers
60 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
1
vote
0answers
44 views

Hasse Diagrams - Relations

I have the following question: Draw the Hasse diagram for the following partially-ordered set: The relation $X$ is a subset of $Y$, on the set $\{ \{0\}, \{2\}, \{0,1\}, \{0,2\}, \{2,4\}, ...
1
vote
0answers
32 views

What does a null relation on all real numbers look like?

I'm being asked to test for reflexivity, symmetry, transitivity, and antisymmetry on a null relation for all real numbers, i.e. $X=\mathbb{R}; R = \emptyset $. What would such a resulting set look ...
1
vote
0answers
41 views

Composition relation of P∘P

Consider the following relation P on the set B = {a, b, {a, b}}: P = {(a, a), (a, b), (b, {a, b}), ({a, b}, a)}. Answer questions 6 to 8 by using the given relation P. Question 6 Which one of ...
1
vote
0answers
120 views

General (Set Builder) definition for a relation composed with itself n times

Questions What does the set builder notation for $S\circ R$ look like? I'm having the most trouble knowing when there is too much information or not enough information on either side of the 'such ...
1
vote
0answers
36 views

Prove the following $(R\cap S)^n=R^n \cap S^n$

I would like to prove the following without induction. $$(R\cap S)^n=R^n \cap S^n$$ We can start by take $(a,b)\in (R\cap S)^n$ its represent a path from $a$ to $b$ right? Any hints? Thanks.
1
vote
0answers
66 views

Not closed under equality?

One of the Peano axioms state that "For any $a \in \Bbb N : a = b, b \in \Bbb N$." An example where transition is not closed under equality is the relation to friends. C may not be B's friend, but A ...
1
vote
0answers
31 views

Relation which is only locally a function

Is there a term for a relation which is not a function (because it maps multiple inputs to the same output), but which looks like one locally? That is, for any $\langle x,y\rangle\in R$, there's some ...
1
vote
0answers
45 views

Preordering on a set

I am given a definition which states that a 'preodering on a set is a relation that is reflexive and transitive.' Show that a relation $\leq$ defined on $\mathbb{C}$ by $z_1 \leq z_2$ iff $|z_1| = ...
1
vote
0answers
105 views

Prove that for any $W\in Q$, there exist a bijection $f:[0]\to W$

Suppose $R$ be the relation on $[0,1)$ s.t. $aRb\iff a-b$ is rational. Let $[0]$ be the equivalence class with respect to relation $R$ on $[0,1)$. Let $Q$ be the set of all equivalence class on [0,1). ...
1
vote
0answers
86 views

Function on equivalence relation on functions

Let $E$ be the set of all functions from a set $X$ into a set $Y$. Let $b \in X$ and let $R$ be the subset of $E \times E$ consisting of those pairs $(f,g)$ such that $f(b) = g(b)$. Prove that $R$ is ...
1
vote
0answers
144 views

Example relations: pairwise versus mutual

There are by now several questions on math.se asking about pairwise versus mutual relations, eg: • When does “pairwise” strengthen and when does it weaken? • Relation: pairwise and mutually • ...
1
vote
0answers
104 views

Total order and $\inf,\min,\max,\sup$ of set?

I have a relation $\mathbb{R\subseteq M\times M}$, which is not even a partially order : $$ M=\{x\in\mathbb{R}:-3\leq x\leq3\}, R=\{(x,y):x>y\}. $$ Well what I'm trying to do is to make this ...
1
vote
0answers
209 views

Partially ordered set proof

I'm trying to proof if the following Relations R ⊆ M×M total order or partially order are. $M = \{1,2,3\} , R = \{(x,y) : x|y\}$ $M = {\bf Z} , R = \{(x,y) : x\vert y\}$ $M = {\bf N}, R = \{(x,y): y ...
1
vote
0answers
83 views

Properties Of Relations

The question asks if there can be a relation on a set that is neither reflexive or irreflexive. The example the book give makes perfect sense: "Yes, for instance $\{(1,1)\}$ on $\{1,2\}$." I was ...
1
vote
0answers
43 views

Product of relations described in categorical terms?

Can cartesian product of several (not necessarily binary) relations be described in categorical terms? Don't propose me direct product in the category Set, as it does not preserve the structure of ...
1
vote
0answers
69 views

About function inj, surj and something else. Is this exercise resolved correctly?

This is my problem: For every couple of integers $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with $r(a,b)$ the remainder of the division between $a$ and $b$. Consider the ...
1
vote
0answers
55 views

Term for generalized antisymmetry?

As I understand it, a binary relation $R$ over a set $A$ is antisymmetric if for all $a, b \in A: aRb \land bRa$ implies $a = b$. Now, suppose that I have an equivalence relation $E$ over the set ...
0
votes
0answers
17 views

How to prove the two relations to be equal?

If I have a relation $R$ defined on a set $A$ ,then when we calculate $R^n$ by performing cartesian product of $A^n$ ,then can we predict the value of $s$ and $t$ such that $R ^ s=R ^ t$. As we ...
0
votes
0answers
30 views

Why relation “parallel” on the set of lines in a plane not transitive?

My book says relation "parallel" on the set of lines in the plane not transitive. And the definition in the book given is : A relation $R$ on a set $A$ is transitive if whenever $aRb$ and $bRc$ ...