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
75 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 for all $x$, the number of $y$ such that $xRy$ is finite. Is there ...
5
votes
0answers
93 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
118 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
102 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
83 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
53 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
61 views

Principia Mathematica Part VI “Quantity” vs Part IV “Relation Arithmetic”

In "My Philosophical Development", of Principia Mathematica Part IV "Relation Arithmetic", Bertrand Russell laments: "I think relation-arithmetic important, not only as an interesting ...
3
votes
0answers
46 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 ...
3
votes
0answers
67 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
51 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
41 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
58 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
45 views

Identification Topology (Mendelson's 'Introduction to Topology', page 103)

Let $f: (X, \sigma) \rightarrow (Y, \tau)$ be continuous and let $a \sim b$ if $f(a) = f(b)$. Noting $\sim$ is an equivalence relation, let $\pi(x)$ map $x$ to its equivalence class. Noting $\pi: X ...
2
votes
0answers
58 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
31 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
77 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
48 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
62 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
86 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
1k 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
44 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
95 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
28 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
582 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
109 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
46 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
1k 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
149 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
320 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
148 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
39 views

Topology given by a relation

I have a problem with creating an equivalence relation ~ in a set : $ S^{1}\times S^{2}$ so that $ (S^{1}\times S^{2})/$~ (a quotient space of the given relation) is homeomorphic to 3-dimensional ...
1
vote
0answers
24 views

Problem with understanding natural number difference

Proofwiki says the following about difference in natural numbers: In the context of the natural numbers, the difference is defined as: $n−m=p⟺m+p=n$ from which it can be seen that the ...
1
vote
0answers
29 views

Relation by induction

Suppose we have the element $a$ and $b$ in some algebra $A$ and $0<q<1$ subject to the relations: $$a^2b-(q+q^{-1})aba+ba^2=0$$ $$b^2a-(q+q^{-1})bab+ab^2=0$$ I want to deduce from this a ...
1
vote
0answers
31 views

equivalence relations example

determine if the relation on $\mathbb{Z} \times \mathbb{Z}$ is an equivalence relation. $$R=\{((a,b),(c,d)) \in A \times A: a+3b=c+3d\}$$ What I have thus far I need to show that R is reflexive, ...
1
vote
0answers
24 views

Symmetry of a relation

There is a professor in our University who each year posts some homework for his students (1st years at computer studies) and I am trying to solve it for fun. However, now I got stuck on something ...
1
vote
0answers
21 views

Interesting relation on element of matrices, is it an equivalence relation?

Let $A\in \Bbb F^{n\times m}$. Let $\operatorname{neighborhood}(x)$ denote the elements surrounding $x$ ($x$ included). Let $a,b,c\in A$, $k\in \Bbb F$. I've come across the following relation: ...
1
vote
0answers
28 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
22 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
17 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
68 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
290 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
32 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
131 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
82 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
52 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
31 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
290 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
313 views

Real life example of relations with various combination of properties

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