New answers tagged

2

Apart from the fact that your proof could benefit from some better wording, it is perfectly correct. I would still suggest you try to reword it more clearly as that will help you later on. Make it more clear what you want to do. Something like: We wish to prove that $R$ is reflexive i.e. that for every $x$, $xRx$ is true: $$\forall x: xRx$$ Let $x_0\in ...


2

In practice you just check it by brute force. You can make it a bit faster to conduct by drawing a diagram with nodes indicating the elements 0, 1, 2, 3 and arrows between elements that are related (and such a diagram is good to do anyway in order to train your intuition). Then, instead of checking every combination of pairs for transitivity, you can just go ...


1

As your question suggests, you can indeed use a matrix to visualize the relation. In your example, the matrix is $$ A = \left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 \end{array}\right]. $$ Note that there is a $1$ in the $(i,j)$-th cell if and only if $(i,j)\in R$. ...


0

We say $a$ divides $b$, denoted by $a | b$, if $b$ is a multiple of $a$ (ie, $b$ is an integer multiple of $a$). Equivalently, $a |b$ iff $b=ka$ for some integer $k$. To remember what "$2$ divides $6$" means, perhaps you can remember the phrase "$2$ divides $6$ into $3$ parts". Hence, $2 | 6$. Note that $2 | 0$ because $0$ is an integer multiple of $...


1

Symmetric: $xRy \iff yRx$ Is it fair to say that the statements "$x$ lives in the same house as $y$" and "$y$ lives in the same house as $x$" are equivalent? If so, then the relation is symmetric. Reflexive: $xRx$ Is it always true that "$x$ lives in the same house as $x$"? If so, then the relation is reflexive. Transitive: $xRy \wedge yRz \implies xRz$ ...


1

Given two integers $a$ and $b$, we say $a$ divides $b$ if there is an integer $c$ such that $b=ac$. Source. This is what $a$ divides $b$ means. The shorthand notation is $$a|b$$. In your example, $$a|a^2\iff a\leq a^2$$ since by definition there exists $c$ such that $a^2 = ac$, namely $a = c$.


1

$a$ is said to divide $b$ if there is an integer $c$ such that $bc=a$


1

Let $R$ be a relation on set $A$ such that $R^{-1}\circ R=\left\{ \left\langle a,a\right\rangle \right\} $ for some $a\in A$ and $R\circ R^{-1}=\triangle_{A}$. Then $\left\langle x,b\right\rangle \in R\implies\left\langle x,x\right\rangle \in R^{-1}\circ R\implies x=a$ . So $R=\left\{ a\right\} \times S$ where $S$ is a non-empty subset of $A$. Based on ...


1

You appear in effect to be assuming that $\succsim$ is the same as ordinary $\ge$. This need not be the case. In fact, the whole point of the argument is that the lower contour sets for any continuous preorder on $X$ are closed, so that in this sense all continuous preorders on $X$ behave like the familiar natural order $\ge$. Of course the steps of 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, ...


1

I think you have not yet got a hold of the difference between minimum and minimal and maximum/maximal. A minimum of a partially ordered set is an element smaller than all other elements. An element is minimal if there is no element that is strictly smaller than it. For a totally ordered set, these are the same. But for a partially ordered set there can be ...


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

Symmetry should be obvious: just switch $m$ and $n$ in the definitions, and see what you get. As to transitivity, think $n = 1$, $m = 6$, $q = 8$. For one of the two relations (which one?), say $\gamma$, you have $n \gamma m$ and $m \gamma q$ but $n \not\gamma q$.


1

IMO your proof is incomplete: you only showed that for any $x\in Z$ you have $xR y$, so that $Z\subset \text{Seg}_R(X,y)$ and inclusion in the other way is not shown. In other words, how do you know (given your proof) $xRy$ implies $x\in Z$? For intuitive appreciation, I think it's probably better (well at least for me) to write $<$ for $R$ in this case, ...


0

Since $Z$ is an $R$-section of $X$, we know that $Z\subsetneq X$ since we additionally assumed $X\neq Z$. So then $X\setminus Z\neq\emptyset$ and $X\setminus Z\subseteq X$ so we know $X\setminus Z$ has a $R$-least element since $X$ is well ordered by $R$. $\require{cancel}$ So $\exists\ y\in X\setminus Z$ st. if $y\neq z \implies yRz \land\ y\cancel{R}z ...


0

I think you should specify the set on which you define the empty relation. Suppose A,B are two sets where A is empty and B is non-empty.Define the empty relation $ R_1$ (respectively $R_2$) on A (respectively on B). Since for every x∈A,(x,x)∈$R_1$, $R_1$ is reflexive. Since there exists x∈B (you can choose any x in B) such that (x,x)∉$R_2$, $R_2$ is not ...


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.


1

Continuity of this relation is defined to be that if it is preserved in limits: if for any pair of sequences $(x^n,y^n)$ converging to x and y respectively and $x^n\succsim y^n$ $\forall n$, then $x\succsim y$. This statement easily implies for any sequence of points $\{y^n\}$ with $x\succsim y^n$ $\forall n$ and $y^n$ converging to $y$, we have $x\...


0

Let me divide it into two bits: (1) what are the upper bounds of $S$ and (2) is there a least one? First part: $u$ is an upper bound of $S$ if $s \propto u$ for all $s$ in $S$. Given $s$, the expression $s \propto u$ means that $u$ lies in $\{s, 4s, 4s+1, 4s+2, \ldots\}$. Call this set $U(s)$. For instance, $2 \propto u$ means that $u$ lies in $U(2) = \{2, ...


1

A maximal element of $S$ must be a member of $S$. An upper bound need not be, but it has to be comparable to all members of $S$. $10$ is maximal in $S$ because it is not $\propto$ any member of $S$. It is not an upper bound as $12 \not \propto 10$. Neither is $12$ an upper bound as $10 \not \propto 12$ The "in $\Bbb N$" part just means you should consider ...


0

G. Sassatelli has already sketched the solution in a comment. If the image is $S\subseteq[n]$ with $|S|=k$, the images of the elements in $S$ are fixed (they have to be mapped to themselves), and the remaining $n-k$ elements can independently be mapped to any of the $k$ elements in $|S|$. There are $\binom nk$ subsets with $k$ elements. Thus the number 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 ...


1

Let $A$ be a partially ordered set. For $B\subseteq A$ we say that $a=\sup B$ if for every $b\in B$, $b\leq a$, and for every $c\in A$, if every $b\in B$ satisfies that $b\leq c$, then $a\leq c$. Namely, amongst the set of upper bounds for $B$, $a$ is the minimum. The infimum is defined similarly, reversing the order and taking the maximum of lower bounds. ...


1

Your answer for the example in your last paragraph is correct. The "inclusion relation" on the set of subsets of a set defines just a partial order, not a total order. Many (most) pairs of sets aren't related. Hint for a): what is the largest set that's a subset of both $\{1\}$ and $\{2\}$? What is the smallest subset that has both as subsets? Similarly ...


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 ...


0

You know that the transitive closure is $<$. If a relation is reflexive then it must also contain $(x,x)$. Transitivity means it becomes $\le$. if a relation is symmetric then if it contains $(x,y)$ then it must contain $(y,x)$. Transitivity means it becomes $\neq$.


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 ...


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

For congruence or an equivalence relation, you need 3 properties: reflexive ($aRa$) symmetric ($aRb \Leftrightarrow bRa$) transitive ($aRb, bRc \Rightarrow aRc$) In your case, $a-a=0 \forall a \in \mathbb{R}$, so $R$ is reflexive. If $a,b \in \mathbb{R}$ and $a - b \in \mathbb{Z}$ then $b-a = -(a-b) \in \mathbb{Z}$, so $R$ is symmetric. Can you prove $...


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 ...


0

There is a category sometimes called $\mathbf{Rel}$ whose objects are sets, morphisms $r:A\to B$ are arbitrary subsets of $A\times B$, and composition is given by ordinary composition of relations. In categorist lingo, it's an example of what's called a power allegory. Just a few of its features: For all $A,B$, $\hom(A,B)$ comes with a Boolean algebra ...


0

I don't think you are thinking about it the right way, but maybe I am thinking about it a way that a person who is right wouldn't think. Anyway. The words domain and codomain are usually reserve for functions. A function is a relation, and so the answer could be that some relations have domains and codomains. So, no I wouldn't use domain and codomain if I ...


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 ...


0

Fix the pair $(a,b)$, and start with any $(c,d)$ it's equivalent to. It's clear that $(c+1,d+1)$ is also going to be equivalent, and distinct from $(c,d)$. So we can take the function $f$ with $f(n)=(c+n,d+n)$ and get a bijection between $\mathbb{N}$ and a subset of the equivalence class.


0

Hint: when is $(m,0)\mathrel{R}(n,0)$?


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)$


0

$$\lfloor x\rfloor\{x\}=1$$ $\lfloor x\rfloor\not =0$. Let $\lfloor x\rfloor=k, k\in Z$. Then $$\{x\}=\frac1k$$ $0\le\{x\}<1 \Rightarrow k>0$ T Then $$x=\lfloor x\rfloor+\{x\}=k+\frac1k, k\in \mathbb N$$


0

Notice that no matter what number is $x$ we have that $\lfloor x\rfloor\in\Bbb Z$. Equating then $\{x\}\in\{1/z:z\in\Bbb Z\setminus\{0\}\}$, and notice that we can write $$\{x\}=x-\lfloor x\rfloor$$ Then we can write the equation system $$x-\lfloor x\rfloor=\frac1z\quad\text{ and }\quad\lfloor x\rfloor=z$$ then we get that $$z=x-\frac1z\quad\to\quad x=z+...


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} $.


0

Onto means that $y = x^{2006} + x^{-2006}$ must hit every value in the range, i.e. $\mathbb{R}$. But $x^{2006} > 0, x^{-2006} > 0,$ so clearly $y > 5$, and the range is $\mathbb{R}_{>5}$.


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)


0

If for every $x\in X$ there is some $y\in X$ such that $xRy$, then $yRx$ because $R$ is symmetric. Then, $xRy$ and $yRx$, so $xRx$ since $R$· is transitive. But the condition "for every $x\in X$ there is some $y\in X$ such that $xRy$" is essential.


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 ...


0

$S$ is called the transitive closure of $R$, often written $R^+$. If we write $a\rightsquigarrow b$ for $(a,b)\in R$, then $(a,x)$ is in $S$ if there is a path $$ a \rightsquigarrow b \rightsquigarrow c \rightsquigarrow \cdots\rightsquigarrow v\rightsquigarrow w \rightsquigarrow x$$ For example, if $R$ is $\{(x,y)\in\mathbb R^2\mid x+x = y\}$ (never mind ...


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

\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 ...


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$ ...


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 ...


0

For any nonempty set $X$, the sets $$ \Delta_X=\{(x,x):x\in X\} $$ and $X\times X$ are both equivalence relations. They are the same only in a very special case.



Top 50 recent answers are included