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

6
votes
0answers
86 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
97 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
124 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
108 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
86 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 Y....
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
36 views

Restriction to equivalence relation is equivalence relation

Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $. $\mathbf{...
3
votes
0answers
69 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
62 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 $y=(y_1,...
3
votes
0answers
70 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
55 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
42 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
84 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
40 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
51 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
70 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
33 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
100 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
72 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
138 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
2k 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 defined ...
2
votes
0answers
103 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
29 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 $a$...
2
votes
0answers
925 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
111 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
150 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
334 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
22 views

A few questions about relations over finite sets.

I am trying to describe some property of relations and to figure out, whther it was studied before. I know, that a set with functions is called an algebra. Is there a name for a set with relations (...
1
vote
0answers
45 views

I am confused about this notation for matrix representation.

I am confused about this notation from the image below. How can you represent something like (1,2),1 as a 2D matrix? For S1 = (0,1,2) and S2 = (0,1) I would expect two matrices like: [(1,0),(1,0),...
1
vote
0answers
16 views

Are there established names and/or symbols for these orderings?

Consider the following orderings on $\mathbb{Z}^2$. Say $(a, b) \leq_1 (c, d)$ if $a \leq c$ or if $a = c$ and $b \geq d$. So for instance $$(1,3) <_1 (1,2) <_1 (1,1) <_1 (2, 3) <_1 (2,...
1
vote
0answers
17 views

Determine whether or not the poset $(\mathbb{N}, \propto$) has a least element

"Define a relation $\propto$ on the natural numbers $\mathbb{N}$ by declaring that for $x, y \in \mathbb{N}$, $x \propto y \iff (x=y)$ or $(3x \leq y)$ a) Show that $\propto$ is a partial order on $\...
1
vote
0answers
25 views

Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup A_2$.

Suppose $R_1$ is a partial order on $A_1$, $R_2$ is a partial order on $A_2$, and $A_1 \cap A_2 = \emptyset$. Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup ...
1
vote
0answers
17 views

Let A be a set with $\lvert A \rvert$ = $4$. What is the max number of elements tht a relation R on A can contain so tht $R \cap R^{-1}$ = $\emptyset$

Let A be a set with $\lvert A \rvert$ = $4$. What is the maximum number of elements that a relation R on A can contain so that $R \cap R^{-1}$ = $\emptyset$? I am not sure at all how to start this ...
1
vote
0answers
13 views

Symmetric and reflexive closure on positive integers

Finding the symmetric and reflexive closure of the relation $R = \{(a, b) | a > b\}$ on the set of positive integers. For symmetric closure I have: $R = \{(a, b) | a > b\} U \{(b, a) | a > b\...
1
vote
0answers
45 views

LEN-Model equivalency

Starting position is a principal-agent-model with incomplete information (moral hazard) and the following properties: Agent utility: $u(z)=-e^{(-r_az)}$ Principal utility: $B(z)=-e^{(-r_pz)}$ Effort ...
1
vote
0answers
20 views

equivalence class of kernel relation of floor function

By taking particular values of $k$, I found that equivalence class of $k$, $[k]=\{k,k+1,k+2,...,2k-1\}$, equivalence class of $2k$, $[2k]=\{2k,2k+1,2k+2,...,3k-1\}$ and so on, but how to present it ...
1
vote
0answers
35 views

Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” relations, respectively. Find $R_1\cap R_2$ and $R_1 \cup R_2$.

I have this question and would need help on how to find $R_1 \cup R_2$. My working for $R_1 \cap R_2$ is shown below: Let $R_1$ and $R_2$ be the “congruent modulo 3” and the “congruent modulo 4” ...
1
vote
0answers
9 views

Number of symmetric relations

Let set $A=\{1,2,3\}$ Find number of symmetric relations that can be defined on $A$ containing ordered pairs $(1,2)$ and $(2,1)$ is? Can someone give me some hint for this question?
1
vote
0answers
33 views

How Galois connections between powersets correspond to binary relations?

How to show the well-known bijective correspondence between Galois connections (or rather polarities) between two powersets on some (fixed) sets with binary relations between these sets? You can also ...
1
vote
0answers
20 views

Ensure exact partitioning when performing masked equality comparison

This question arose from an informatics problem, but I do believe Math SE is the right stack to ask because I am not asking for a algorithm in a specific language but for properties to check using ...
1
vote
0answers
59 views

Is this relation $\mathscr R$ on the set of relations, reflexive?

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R = \{(\mathscr P, \mathscr Q) \mid \...
1
vote
0answers
42 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
34 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, ...