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

1
vote
1answer
97 views

Question on 1-1 & onto function

While I was studying relations & functions I came across with this question which I can't figure out the meaning of it. Please help. Let $X$ be the set of all strings of finite length consisting ...
0
votes
1answer
88 views

Relation $R$: $R\circ R \subseteq R \implies R$ is transitive

Let $R$ be a relation on $X$, a set. If $R\circ R\subseteq R$, then is $R$ transitive?
5
votes
0answers
84 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?
0
votes
1answer
254 views

Related rates, where do I start?

A revolving searchlight, which is $100$ m from the nearest point on a straight highway, casts a horizontal beam along a highway. The beam leaves the spotlight at an angle of $\frac{π}{16}$ rad and ...
1
vote
1answer
30 views

Problem understanding domain of circular relation

I came across an exercise in a book which introduces the circular relation as: $C$ is a relation from $R \to R$ such that $(x,y) \in C$ means $x^2+y^2 = 1$. It then says that the domain of $C$ ...
-2
votes
2answers
50 views

Statements regarding relations in R

Suppose $\rho$ is a relation on $R$. I want to verify whether the following statements are true. Looks simple but proving them seems to be difficult for me. $\rho\circ\rho$ is a subset of $\rho$ ...
1
vote
1answer
51 views

About functions and relations

A pure threoretical question here. I have the relation $\pm\sqrt x$. As far as I understand it, that is not a function, as 1 input can map to 2 outputs. If I have a relation, which is not a function, ...
1
vote
1answer
95 views

Can someone help me finish this relations problem?

I have tried to work with this but this is all I have so far Are the following relations (integer sets) Reflexive, Symmetric, Asymmetric, or Transitive? $$R_1= \{(a, b) \mid a*b<1\}$$ Solution: ...
2
votes
1answer
75 views

Extension theorem on acyclic relations

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

Matrix of a relation on a set

If I have a Matrix $A=\begin{bmatrix} 0&0&0\\ 0 & 0 & 0 \\0&0&0\end{bmatrix}$ why is this both symmetric and anti-symmetric? If I had a Matrix $B=\begin{bmatrix} ...
2
votes
1answer
962 views

Relation Matrix

Is my set of related pairs correct for this problem? $$\{(2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)\}$$ Suppose that $\,A = \{1,2,3,4\}\,$ and $\,B = \{1, 2, 3\}.$ Let ...
2
votes
2answers
454 views

Set Relations Question

I understand these laws when applied to certain situations but can't seem to understand how to apply it to these problems. I know that if Jon is Mike's cousin, then Mike is Jon's cousin and that is a ...
2
votes
1answer
194 views

A problem on equivalent metrics and equivalence classes

Let $ X $ be a non empty set and $ \tau= \{d\mid d$ is a metric on $X\}$ Define the relation $\sim $ on $\tau$ by $ d \sim d' $ iff $ d $ and $ d'$ are equivalent metrics on $X$. Show that $\sim $ ...
1
vote
1answer
34 views

Set Relations Quick Question

Can someone please explain how this answer was reached? I know that relation of A is just A * A but wouldn't that just be $4^{2}? $ Let A = {1, 2, 3, 4}. How many relations are there on a set A? ...
1
vote
1answer
25 views

Growth of y with respect to time based on some given assumptions

I would be thankful if someone can help me with the following problem: Given: $\frac{\dot{N}(t)}{N(t)} = c_b - \frac{c_d}{y(t)}$ $\frac{\dot{A}(t)}{A(t)} = N(t)g - \delta $ $y(t) = ...
5
votes
1answer
287 views

Is this alternative definition of 'equivalence relation' well-known? useful? used?

I discovered that $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ The nice thing about ...
1
vote
2answers
232 views

Is this alternative definition of 'equivalence relation' correct?

I was puzzling over another question: Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$. And this made me discover that $$(0) \; \langle \forall a,b :: aRb ...
0
votes
2answers
449 views

Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$.

Hello I need help with the proof strategy for this problem. Let $R$ be an equivalence relation on a set $A$ and let $a,b \in A$. Prove that $[a] = [b]$ if and only if $aRb$.
2
votes
1answer
147 views

Is there any binary relation operator that has these properties in any objects?

Consider binary relation operators d b q p (with a direct correspondence by generalization of: < > ≮ ≯ these are a ...
0
votes
1answer
93 views

Question concerning satisfiability in a certain Kripke model

My question concerns the exercise on p.77 of Boolos, Logic of Provability: True or false: if $A$ is satisfiable in some finite transitive and irreflexive [FIT] model and contains at most one ...
0
votes
2answers
178 views

Minimum Equivalence Relation

Let $X= \{1,2,3,4\}$, and $R = \{(1,2),(3,4)\}$. Show the minimum equivalence relation on $X$ that extends $R$. How many elements does the quotient set $X/R$ have ? Can somebody give hints to solve it ...
0
votes
1answer
192 views

Union of two partial orderings

Suppose S and R are partial orderings. Does is necessarily mean that $R \cup S$ (union) is a partial ordering? If not what conditions would have to be met for it to be a partial ordering?
2
votes
3answers
93 views

Composition $R \circ R$ of a partial ordering $R$ with itself is again a partial ordering

If $R$ is a partial ordering then $R\circ R$ is a partial ordering. I cannot seem to prove this can anyone help ?
1
vote
0answers
46 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| = ...
2
votes
0answers
96 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
1answer
50 views

Identifying the constants and variables in statements

Please help me to identify the constants and variables in these statements. Thanks in advance. Ratio of the circumference of any circle to its diameter. Height of a boy on a given day. Height ...
2
votes
1answer
68 views

Is there a name for this type of relation?

Let $S$ be a set. Let $\sim$ be a binary relation on $S$. Suppose $\sim$ follows these three rules. $x\sim x$ for all $x\in S$ (reflexivity). If $x\sim y$, then $y\sim x$ for all $x, y \in S$ ...
13
votes
5answers
228 views

Does “=” have to be interpreted as equality?

To put it briefly: In model theory, we are allowed to interpret any relation symbol in any way we like. So why do people seem to require that "$=$" is interpreted as the actual equality? Let me ...
4
votes
4answers
680 views

$5 \mid n^2 - m^2$ is an equivalence relation

How can I show this is an equivalence relation: $$ n \operatorname{R} m \Longleftrightarrow n^2 - m^2 \textrm{ is divisible by } 5 $$ I know equivalence relations are symmetric, reflexive and ...
0
votes
1answer
50 views

A simple proof about finite subsets of a set

What is the simplest proof that for every cartesian square $A\times A$, which is a subset of $\Gamma$, the set $A$ is finite? $$\Gamma = \left\{ ( x ; x) \hspace{.5em} | \hspace{.5em} x \in [ 0 ; 1] ...
5
votes
3answers
1k views

Why is the empty set finite?

On page 25 of Principles of Mathematical Analysis (ed. 3) by Rudin, there is the definition (excluding the irrelevant parts for this question): Definition 2.4: For any positive integer $n$, let ...
2
votes
0answers
43 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 ...
1
vote
1answer
337 views

Is My understanding of complete relations correct?

I am using "Foundations of Mathematical Economics" by Michael Carter. The problem 1.16 of the book: Consider the relations $<$, $\le$ and $=$ on $\mathbb R$. Which of the above properties ...
0
votes
2answers
240 views

Composite of relation and its opposite

I have a relation set $R = \{(a, b), (a, c), (b, c), (b, d), (c, d), (c, a)\}$ included in set $\{a, b, c, d\}\times\{a, b, c, d\}$. Its opposite of relation is $R^{−1} = \{(b, a), (c, a), (c, b), ...
4
votes
1answer
181 views

Why is this relation $R=\{(a,b), (b,c), (c,a)\}$ transitive?

I have a set of relations, shown below: $R=\{(a,b), (b,c), (c,a)\}$ for $A= \{a,b,c\}$ According to my professor, this relation is transitive but I don't understand why. I was under the impression ...
3
votes
2answers
1k views

Determine whether this relation is reflexive, symmetric…

Determine whether this relation $R$ on the set of all integers is reflexive, symmetric, anti-symmetric and/or transitive where $x\,R\,y$ iff $x = y + 1$ or $x = y-1$ It is not reflexive: Let $x = ...
0
votes
1answer
46 views

A property of uniform spaces

Is it true that $E\circ E\subseteq E$ for every entourage $E$ of every uniform space?
1
vote
1answer
312 views

Transitivity of a square of a relation [duplicate]

Transitivity $\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is ...
0
votes
1answer
78 views

Suppose $(A, \le)$ is a partially ordered set. Define a relation $\preceq$ on $A\times A$ by $(a,b)\preceq (c,d)$ if

if and only if 1) $a\le c$ and $a \ne c$ 2) $a = c$ and $b\le d$ Prove that $(A\times A,\preceq)$ is also a partially ordered set. So to prove this I would start with trying to find 1) ...
0
votes
1answer
59 views

I need help with relations

Let $S$ be the power set $P({1,2,...,10})$; that is, $S$ is the set of all subsets of $\{1,2,\dots,10\}$. define the relation $\mathcal R$ on $S$ by: For all subsets $A,B$ of $\{1,2,\dots,10\}$, ...
0
votes
1answer
75 views

is this symmetric

A is the set of all functions $\mathbb{R}$ $\to$ $\mathbb{R}$ f is related to g if and only if f(x) $\le$ g(x) for all x $\in$ $\mathbb{R}$ I said its reflexive since it is less than OR equal, so ...
0
votes
3answers
193 views

I dont understand equivalence classes with relations

I am not quite understanding equivalence classes. For example I have this problem: Let $A$ be the set of integers and $\quad a\;R\;b\quad$ if and only if $\quad |a| = |b|$. I have proved that this ...
0
votes
1answer
169 views

Reflexivity, Transitivity, Symmertry of the square of an relation

$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is reflexive/symmetric/transitive ...
1
vote
1answer
2k views

Symmetric, transitive and reflexive properties of a matrix

Say I had a relation \begin{align} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{align} where $a,b,c,d \in \mathbb{R}$, where $X$ is related to $Y$ if and only if $\det(X) = \det(Y)$ ...
0
votes
1answer
93 views

is a relation R total/linear/well-order

Let $\mathcal{R}$ be a relation on $\mathbb{N}\times \mathbb{N}$ i.e $\mathcal{R}\subseteq(\mathbb{N}\times \mathbb{N})\times (\mathbb{N}\times \mathbb{N})$ s.t $(x,y)\mathcal{R}(z,w)$ iff $x<z$ or ...
2
votes
4answers
1k views

Transitivity of union of two transitive relations

I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union ...
7
votes
2answers
165 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
3
votes
1answer
49 views

Suppose $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq B_2$, then $x_1 Rx_2$

I'm having trouble with the following proof: Suppose $\mathcal{R}$ is a partial order on A, $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq ...
4
votes
3answers
126 views

Why is Transitivity necessary in the definition in the definition of an order on a set?

In Rudin, Principles of Mathematical Analysis (ed. 3), he provides the following definition (pp. 3) Definition: Let $S$ be a set. An order on $S$ is a relation, denoted by $<$, with the ...
2
votes
2answers
144 views

Let $A$ be a set, $R$ an empty relation on $A$, what is $A/R$?

Let $A=\{0,1,2\}$ be a set and $R=\{\}$. I know that $R$ is not an equivalence relation, but does it have to be? What is $A/R$ if $R$ is empty? Examples: $R_1=\{(0,0),(1,1),(2,2)\}$, $A/R_1=\{[0], ...