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
87 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
113 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
72 views

How to Prove It, Exercise 6.5.9

Suppose $R$ is a relation on $A$ and $S$ is the transitive closure of $R$. If $(a, b) \in S$, then there is some positive integer $n$ such that $(a, b) \in R^n$, and therefore by the well-ordering ...
4
votes
0answers
77 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
51 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
57 views

Why is this not a proof of Schroeder-Bernstein?

We can show that if $f: A \rightarrow B$ is injective then $|A| \leq |B|$ and if $g: B \rightarrow A$ is injective then $|B| \leq |A|$ so $|A| = |B|$. By the definition of having equal cardinality, ...
3
votes
0answers
39 views

A reflexive relation?

Suppose I have a set $\mathrm{A}=\{1,2,3,4,5\}$ and a reflexive relation $\mathrm R$ defined on $\mathrm A$, i.e., $$R\colon A\mapsto A\quad\textrm{and}\quad \mathrm R\textrm{ is reflexive.}$$ Is ...
3
votes
0answers
35 views

Proving Equivalence Relation $xPy$ iff $ y = x + n\pi$ on The Reals

I am trying to prove that the relation P on $\mathbb{R}$ by the rule $\forall x, y \in \mathbb{R}, xPy \text{ if and only if } \exists n \in \mathbb{Z} \text{ such that }y = x+ n\pi$ From what I can ...
3
votes
0answers
53 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
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
29 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
2
votes
0answers
34 views

Reflexive, Symmetric, Transitive

Let $X = \{0, 1, 2, ... , 10\}$, Define the relation $R$ on $X$ by: for all $a, b \in X, aRb$ if and only if $a + b = 10$ Is R reflexive? symmetric, transitive? Give reasons. Here are my answers, ...
2
votes
0answers
22 views

composition of relations and multiset relations

As is well known, composition of relations is defined as $$R\circ S = \{(a,b):\exists x: (a,x)\in S \land (x,b)\in R\} \tag 1$$ This is formally the very same definition as for function composition. ...
2
votes
0answers
28 views

What is the irreflexive closure of an irreflexive relation?

I am working on a problem that states the following: When is it possible to define the irreflexive closure of a relation R, that is, a relation that contains R, is irreflexive, and is contained in ...
2
votes
0answers
26 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
2
votes
0answers
59 views

Relations in a finitely complete category with images

I can't use tikz inside MathStackExchange; so my question is on an image below.
2
votes
0answers
49 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
718 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 ...
2
votes
0answers
43 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
84 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
26 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
346 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
103 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
44 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
838 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
140 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
291 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
147 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
24 views

How to prove partial ordering formally?

The question is: The set $S$ is defined as $\varnothing \in S$, If $x \in S$, then also $\{x\} \cup x \in S$. Prove or disprove it is partial ordering. So the set $S$ looks ...
1
vote
0answers
14 views

Is there a term for irreflexive relations whose reflexive closures are equivalence relations?

Consider a relation $\sim$ which is irreflexive, that is: $$ \forall A \:A\nsim A $$ Further suppose the reflexive closure of $\sim$ is an equivalence relation. The reflexive closure of $\sim$, ...
1
vote
0answers
14 views

Book on theory of relations

Could someone recommend an introductory book on Theory of Relations for undergraduate level mathematician? Something gentle and intuitive.
1
vote
0answers
64 views

How to construct a transitive relation?

Given a binary relation $\mathcal{R}$ on a set $A$, you can be assured that the relation $\mathcal{R} \cup \mathcal{R}^{-1}$ is symmetric. (I can give a proof of this, if you would like.) I wanted to ...
1
vote
0answers
86 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
1
vote
0answers
22 views

Can someone verify my work for finding the following relations?

I am working on this problem Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs {(1,1), (1, 2), (1,3), (2,3), (2,4), (3,1), (3,4), (3,5), (4,2), (4,5), (5,1), (5,2), ...
1
vote
0answers
50 views

Is my answer for the composite relation correct and not the textbook's?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 5 pg 593] Here is how my textbook's way of representing a relation with a matrix And the definition of a ...
1
vote
0answers
59 views

Equivalence Relations with equivalence classes

Consider the following relation on $\mathbb{Z} \times \mathbb{Z}$: $(x, y)\sim (x', y')$ iff $xy' = x'y$. (a) Prove that it is an equivalence relation. (b) Consider the set of equivalence classes ...
1
vote
0answers
43 views

xor of three relations using Relation Algebra operations

Suppose I have three relations R1, R2, and R3. How can I specify xor of these three relations using relation algebra operations. How this scales up (for example, for four relations)? Thanks I add ...
1
vote
0answers
30 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
103 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
119 views

Real life example of relations with various combination of properties

Attempted a set of questions as below: ...
1
vote
0answers
40 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
56 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
60 views

Finding Equivalence Classes for Infinite Sets

Let $R$ be the relation on the set of rational numbers $\Bbb Q$ defined as follows: for all $q, r \in \Bbb Q$, $qRr$ iff $q − r \in \Bbb Z$. Then $R$ is an equivalence relation on $\Bbb Q$. What is ...
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
36 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
30 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
40 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
35 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
109 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
75 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 ...