# Tag Info

## Hot answers tagged relations

18

I’m going to guess that the actual context was more like the smallest equivalence relation on $A$ satisfying such-and-so conditions. If that’s the case, what is intended is the intersection of all equivalence relations on $A$ satisfying the given conditions: the intersection of equivalence relations on $A$ is an equivalence relation on $A$, and this ...

8

An equivalence relation is a set of ordered pairs, and one set can be a subset of another. For any set $S$ the smallest equivalence relation is the one that contains all the pairs $(s,s)$ for $s \in S$. It has to have those to be reflexive, and any other equivalence relation must have those. The largest equivalence relation is the set of all pairs $(s,t)$. ...

6

Suppose $[x]\{x\}=1$. $x$ can not be an integer, or else $\{x\}=0$. Also, $x>0$ or else $[x] < 0$ and $\{x\} > 0$. Therefore, let $[x] = a$ and $\{x\} = b$, where $0 < b < 1$. Then $ab = 1$, so $b = \dfrac1{a}$, so $x = a+b =a+\dfrac1{a}$.

6

You are correct about $R$ being reflexive and not symmetric. However, you have not proved that it is antisymmetric. You have only given a case that is antisymmetric, namely $(1,1)$, but you would need to show that it is true for all cases. You would need to prove the following statement: For all $(a,b)\in \mathbb{Z}\times \mathbb{Z}$ the following ...

5

Equivalence relations are (partially) ordered by implication; $\Theta \leq \Phi$ if and only if $$x \Theta y \implies x \Phi y$$ is an identity. In fact, this partial ordering is a complete lattice; the meet operation (a.k.a. the greatest lower bound) is given by logical and. That is, the equivalence relation $\Theta = \bigwedge_{i \in I} \Theta_i$ is the ...

3

if $\alpha>0$ then $\alpha+\frac{1}{\alpha}\ge\,2\,\,$. We know $x^{2006}\ge 0$ then $x^{2006}+\frac{1}{x^{2006}}\ge\,2\,\,$ as aresult $$y=x^{2006}+\frac{1}{x^{2006}}+5\ge\,2\,\,+5\ge7$$ i.e $R_f=[7,\infty)$

3

Hint: $x^{2006}$ is always non-negative. (Why?) Furthermore, $\frac{1}{x^{2006}}$ is always positive when $x\neq 0$ (Technically, your proposed "function" is not a function at all since it is undefined for $x=0$. Regardless, looking at the domain instead as $\Bbb R\setminus\{0\}$ it will still have problems with being onto)

3

The equality relation is also an equivalence relation.

3

Let $(a,b) \in \mathbb{Z}^2$. If $(a,b) \in R$, then $a = m b$ for some $m \in \mathbb{Z}$. If $(b,a) \in R$, then $b = n a$ for some $m \in \mathbb{Z}$. So if $(a,b), (b, a) \in R$ then $$a = m b = m (n a) = (m n) a \iff m n = 1 \iff m = n = 1 \vee m = n = -1$$ The first case means $a = b$ and the second means $a = -b$. The second case gives us ...

3

For a relation $R$ to be transitive, if you have $aRb$ and $bRc$, you also need to have $aRc$ In this case, we have $1R1$ and $1R2$. Hence, we need to have $1R2$, which we do have. Also, we have $1R1$ and $1R1$, hence we need to have $1R1$, which he have as well. thus, we have exhausted all combinations of $aRb$ and $bRc$ and we have checked that the ...

3

The pre-order being complete has no topological meaning, but purely set-theoretic. It means that for any two points $x,y$ in the domain of the pre-order, we must have $x \succsim y$ or $y \succsim x$ (or possibly both here, because we have a pre-order, so we can have both at the same time (invariant goods (?), or some such thing, economics is not my field, ...

2

I don't know what you want it for, but it is possible to define the smallest equivalence relation on a set $S$ containing a given relation $R$. Here's the formula: $$R^e = \bigcup_{n=1}^\infty [R\cup R^{-1} \cup 1_S]^n$$ We know that when $n=1$, we'll have $1_S$, satisfying reflexivity. Symmetry follows by induction; the base case is clear because we ...

2

Transitivity of a relation $R$ is the statement that $(a,b) \in R \wedge (b,c) \in R \implies (a,c) \in R$, where $\wedge$ is the "and" symbol and $\implies$ is the "implies" symbol, in terms of logical representation. This is sometimes simplified to the notation $aRb \wedge bRc \implies aRc.$ In words, this essentially means that given element $a$ and $b$ ...

2

Hint: Work through some examples. Fix one integer and figure out everything it's related to. For example, consider $7$. We know that $(7, 8) \in t(R)$. But since $(8, 9) \in t(R)$, we know by transitivity that $(7, 9) \in t(R)$. But we can repeat this argument with $(9, 10) \in t(R)$ to get that $(7, 10) \in t(R)$. A simple induction argument would show that ...

2

Absolutely it makes sense. The domain of the relation R is the set of arguments i.e. first members of each ordered pair and the codomain is the set of which the values i.e. second members of all the ordered pairs is a subset of. In other words, the range of the relation is a subset of the codomain. Set-theorists distinguish between the range and codomain of ...

2

The relationships amongst the elements of $B$ don’t actually matter. For the infimum you’re looking for the largest subset of $U$ that is a subset of every member of $B$, and for the supremum you’re looking for the smallest subset of $U$ that contains each member of $B$ as a subset. (Here largest and smallest refer to the subset relation: $X$ is smaller than ...

2

Your proof is correct. For reflexivity, note the following: If $R$ and $S$ are reflexive relations on a set $X$ and $x\in X$. Then, $(x,x)\in R$ and $(x,x)\in S$ so that $(x,x)\in R\cap S$. I.e., $R\cap S$ is reflexive.

2

Clearly the first is not transitive: $1+6=7$ and $\operatorname{rest}(6,7)+\operatorname{rest}(8,7)=7$ but neither $1=8$ nor $\operatorname{rest}(1,7)+\operatorname{rest}(8,7)=7$ is true. Now consider the second relation: in fact we can write $$n\ \beta\ m\iff n^2\equiv m^2\pmod7.$$ Then can you start from this definition and prove that it is both symmetric ...

1

Any relation $R$ generates an equivalence relation $E$ wich is by definition the intersection of all equivalence relations that contain $R$ as a subset. Any equivalence relation $E$ on a set $X$ corresponds with a partition $P$ on $X$ that has the equivalence classes of $E$ as its elements. Denoting the equivalence class represented by $x\in X$ as $[x]$ we ...

1

In general: if $R$ is a relation then $S:=\bigcup_{n=1}^{\infty}R^n$ is its transitive closure. If $T$ is a transitive relation with $R\subseteq T$ then with induction it can be shown that $R^n\subseteq T$ for each $n\in\{1,2,\dots\}$, so that $S\subseteq T$. Conversely it can be shown that $S$ is a transitive relation with $R\subseteq S$.

1

An equivalence relation is just a relation which is reflexive, transitive, and symmetric. A congruence relation, however, is a bit more: it's a relation which respects some structure. Note that this means the phrase "congruence relation" by itself is vague: I have to tell you what structure I want it to respect. Here's the right picture: I have some ...

1

Think of $R$ as defining a graph. $x$ and $y$ are related by $S$ if $x$ and $y$ if there is a path between $x$ and $y$, i.e. if $x$ and $y$ are in the same connected component. You just need to apply the definition of equivalence relation to $S$. (i) Show that there is a path between $x$ and $x$ via $R$. (ii) Show that if there is a path from $x$ to $y$ ...

1

That the product has period $\pi$ is easily seen, once we prove $$\cos x\cos2x\cos3x =\frac{1}{4}\left(\cos6x+\cos4x+\cos2x+1\right).$$There are at least two quick ways to do this. One uses $\cos nx =\tfrac{1}{2}\left(z^n+z^{-n}\right)$ with $z:=e^{ix}$; the other uses $\cos A\cos B=\tfrac{1}{2}\left(\cos\left(A+B\right)+\cos\left(A-B\right)\right)$. Edited ...

1

\begin{align} \cos(3x - x) &= \cos 3x \cos x + \sin 3x \sin x \\ \cos(3x + x) &= \cos 3x \cos x - \sin 3x \sin x \\ \hline \cos x \cos 3x &= \dfrac 12 \cos 2x + \dfrac 12 \cos 4x \\ \cos x \cos 3x &= \dfrac 12 \cos 2x + \dfrac 12 (2 \cos^2 2x - 1) \\ \cos x \cos 3x &= \dfrac 12 \cos 2x + \cos^2 2x - \dfrac 12 ...

1

R is a transitive relation if for every $a,b,c\in A$, $$(a,b),(b,c)\in R$$then $$(a,c)\in R$$ When $A=\{1, 2, 3\}$ and $R=\{(1, 1),(2, 2), (1, 2), (2, 1), (1, 3)\}$ You have $(2,1),(1,3)\in R$, but $(2,3)\notin R$, so R is not transitive.

1

"Onto" is essentially a representation of surjectivity. A function $f : A \rightarrow B$ is surjective if and only if $$\forall y \in B. \exists x \in A. f(x) = y.$$ In words, it means that every element of $y$ can be mapped to by $f$ using some element in the domain of $f$, $A$. The way one can prove that a function is surjective is by taking an arbitrary ...

1

It is certainly possible that the two are equal, however several counter examples exist. Some basic examples of equivalence relations that you should be aware of are the "trivial" equivalence relations. The first of which where every element is related only to itself. The second of which is where every element is related to every other element. Take for ...

1

The relation $S$ is not reflexive because $(\{b\};\{b\})$ is not in $S$, it is symmetric because $B\cap A=A\cap B$, it is not transitive because if $A=\{a,b\}$ and $B=\{a,c\}$ then $(A,B)\in S$ and $(B,A)\in S$ but $(A,A)$ is not in $S$, it is not antisymmetric as shown in the above example we get not $A=B$ .

1

That's almost right, except it should say $(A,B)$ instead of $(a,b)$.

1

A relation is usually implemented as a set of ordered pairs. Equality on $\mathbb{N}^{\geq 1}$, for instance, is implemented as $E = \{ (1,1), (2,2), (3,3), \dots \}$. So the complement would be $$\{ \text{ordered pairs} \} \setminus E$$ That is, $$\{(1,2), (1,3), \dots, (2,1),(2,3), \dots\}$$ Suppose $R^C$ were not symmetric. Then there would be $(a,b)$ ...

Only top voted, non community-wiki answers of a minimum length are eligible