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
74 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?
4
votes
0answers
65 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
47 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. ...
4
votes
0answers
84 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 ...
3
votes
0answers
34 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
62 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
22 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
175 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
85 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
41 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
616 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
203 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
29 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
28 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
16 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
25 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
33 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
65 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
35 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
62 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
30 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
52 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 ...
1
vote
0answers
37 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
100 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
80 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
120 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
46 views

Find the Equivalence Class of b.

Let $x,y \in \Bbb R$ and $xby \Leftrightarrow \exists k\in \Bbb Z \ tg(x)+k=tg(y)$. Find $[x]_b$.
1
vote
0answers
96 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\epsilon\mathbb{R}$:$-3$$\leq x\leq3\}, R=\{(x,y):x>y\}$ Well what i'm trying to do; to make this ...
1
vote
0answers
166 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
64 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 wondering, if ...
1
vote
0answers
117 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, ...
1
vote
0answers
42 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
53 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
34 views

Is a set of some $m \times n$ matrices a relation?

A relation between sets $A_i, i = 1, \dots, n$ is defined as a subset of $\prod_i A_i$. Given $m, n \in \mathbb N$, is a set of (some or all) $m \times n$ matrices over $\mathbb R$ considered a ...
0
votes
0answers
29 views

Properties of R, R^n, R*

I was talking to a friend who mentioned that eventually, R^n and R* are equivalent. This confuses me because I don't see how it's necessarily the case. But it does seem to hold, for instance: R = ...
0
votes
0answers
29 views

Proof for a relation

Define a relationship $R$ on $\mathbb{Z}$ by declaring that $xRy$ if and only if $x^2 \equiv y^2 (mod 4)$. Prove that $R$ is reflexive, symmetric and transitive. I'm unsure of where to start with ...
0
votes
0answers
37 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, ...
0
votes
0answers
51 views

Is this connected relation?

My task is to check if this is preference relation (connected and transitivited) $$ f \succeq g \Leftrightarrow \forall x\in [0,1] f'(x) \leq g'(x) $$ My solution is: that this relation is not ...
0
votes
0answers
25 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
0
votes
0answers
28 views

Finding the composition of relation?

Let $R=\{(1,5),(2,2),(3,4),(5,2)\}$ $S=\{(2,4),(3,4),(3,1),(5,5)\}$ $T=\{(1,4),(3,5),(4,1)\}$ 1.Find $R$ composite $T$ 2. Find $R$ composite $R$ 3. Find $T$ composite $T$ For all these I made a ...
0
votes
0answers
107 views

preference relation.

In the exercise below I need to check whether the relation below is a preference relation ( need to be transitive (if $x>y$ and $y>z$ then $x>z$) and connected ). But I cannot find an ...
0
votes
0answers
13 views

For which sets, $X$ the relation is a partial function

Given $T=\left\{\ \left<A,B\right> \in (P(X))^2 | A\subseteq B \right\}$ For which sets, $X$, the relation $(P(X))^2-T \cap (P(X))^2-T^{-1}$ is a partial function? Here's my solution: ...
0
votes
0answers
70 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 ...
0
votes
0answers
22 views

Relations that are closed to union and intersection

Let's define that sets are closed to union if for every relation $R,S$ that have certain traits $R\cup S$ have the same traits as well. Likewise for intersection. Determine if the following ...
0
votes
0answers
22 views

Is there a particular name for the set of all relations?

I know that a relation on a set $S$ is a subset $R \subseteq S \times S$ such that for all $(s,s') \in S \times S$, $(s,s') \in R$ iff $sRs'$, therefore the set $T$ of all relations on $S$ is the set ...
0
votes
0answers
33 views

Transitive, Reflexive, Symmetric

So i know what each of these properties are..but this question does not provide any information on a 3rd variable so i was wondering how i would do it? ...
0
votes
0answers
32 views

unifying latitude and longitude into single digit finding equation

I am trying to convert a latitude,longitude into a single point using the midpoint formula while still being able to do a radius search around that point. The midpoint formula is wrong for this ...
0
votes
0answers
80 views

Draw arrow diagram to show the following function.

Draw arrow diagram with two parallel lines to show the function $f:x \mapsto 3 - 2x^2$. Let the domain be the set of integers and draw six arrows for the function. How to draw it?