New answers tagged

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


1

You're making a really common mistake, a mistake you probably even know about in abstract terms, but it's hard to recognize it when it shows up in real life. (Especially when the wording is as convoluted as in MW; that's really shoddy work on their part imo). Trying to keep as many words from the original definition as possible, I'll rewrite it so the logic ...


0

The diagrams are describing the steps in some sorting algorithm (couldn't tell you which) and giving the resulting partial order at each step in the form of a Hasse diagram. It appears that each case starts with an antichain and ends in a chain.


2

The reflexive closure of some relation $R$ over $A$ is the smallest subset of $A\times A$ that (a) contains $R$ and (b) is reflexive. In this case $R$ is the empty set, so every subset of $A\times A$ satisfies condition (a). We're left with looking for the smallest subset of $A\times A$ that is a reflexive relation on $A$. This smallest subset is evidently ...


3

I am not quite sure about this notation but suppose that $R$ is the relation such that if $(x,y)\in R$ then $x\leq ay: a,x,y \in \mathbb{R}$. Let's think about $y\geq \dfrac{x}{a}$. Geometrically, this is interpreted as the region including and above the line $y=x/a$. So suppose $(x,y) \in R$ and $(y,z)\in R$. We want to show that $(x,z)\in R$, hence the ...


1

Hints: (a) Try solutions of the form $u_n=a \lambda^n$. (b) Try solutions of the form $u_n = a 3^n + b n^2 + c n + d$ (c) Try solutions of the form $u_n = a 3^n + b 4^n$ The main principle is to combine solutions of the homogenous equation with a particular solution. (a) is a homogenous equation and you can just try $u_n=a \lambda^n$ and see which ...


0

Can you find two pairs $\langle a,b\rangle,\langle b,c\rangle\in S$ such that $\langle a,c\rangle\notin S$? If not then you can conclude that the relation is transitive.


0

Check that $\;(a,b)\in S,\,(b,c)\in S\implies (a,c)\in S\;$ for all the possible instances. For example $$(1,2)\in S,\,(2,1)\in S\implies (1,1)\in S\;\;\color{green}\checkmark$$ There is only one more instance to check...


0

The relation $R$ is in fact antisymmetric. Antisymmetry says that whenever $(x,y) \in R$ and $(y,x) \in R$, we must have $x = y$. However, there is no pair $(x,y) \in R$ such that $(y,x) \in R$, so it is vacuously antisymmetric. It is also irreflexive, because no element is related to itself, meaning that there is no element $x$ such that $(x,x) \in R$.


3

Your proof does indeed show that $R$ is not a non-strict partial order. Perhaps what you read elsewhere claimed that $R' = \{(x,y) ~|~ \text{the first letter of }x\text{ occurs later than the first letter of }y\}$ is a strict partial order, which is of course true.


0

There are $B_n$ equivalence relations on $[n]$. As shown in the two threads linked to in the comments, there are $B_{n+1}$ relations on $[n]$ that are symmetric and transitive. Thus there are $B_{n+1}-B_n$ relations that are symmetric and transitive but not reflexive.


1

Because no matter how you select elements $x,y,z \in \{a, b, c\}$ such that $xRy$ and $yRz$ (hint: there's only one way), you have $xRz$, which is what it means to be transitive.


2

You only have two pairs of the form $\;(a,b),\,\,(b,c)\in R\;$ , and also $\;(a,c)\in R\;$ , so it is true that whenever $\;(x,y),\,(y,z)\in R\;$ , also $\;(x,z)\in R\;$, and that's transitivity


0

$xRy \iff x^n = y^m$ and $yRz \iff y^s = z^t$ for natural $s,t,n,m$. Thus take $$ (y^s)^m = (y^m)^s = (x^n)^s = x^{ns}\: \text{and} \: (y^s)^m = (z^t)^m = z^{tm} $$ which gives $x^a = z^b$ for natural $a=ns, b = tm$, so $xRz$.


0

Suppose $x \sim y $ such that $x^a = y^b$ and $y \sim z$ such that $y^c = z^d$. Then $(y^c)^b = y^{cb} = (z^d)^b = z^{db} \rightarrow (x^a)^c = x^{ac} = z^{db}$. This proves that $x \sim z$. Edit: This relation can be seen after doing a few examples like on $3 \sim 9$ and $9 \sim 81$: $3^2 = 9^1$ and $9^2 = 81^1$ such that $3^4 = (3^2)^2 = 9^2 = 81^2$ ...


0

If $(x,y),(y,z)\in R$ implies: $$x^n=y^m\quad and \quad y^\hat{n}=z^\hat{m}$$ This will lead to: $$x^{n*\hat{n}} = y^{m * \hat{n}}=x^{m* \hat{m}}$$ Just a sketch, but I bet you can proof everything neccessary.


1

Apparently, the formula tries to express the existence of a supreme and it's unicity (hence the $y=z$ consequent). Since that kind of number does not exist neither in $\mathbb{N}$ nor in $\mathbb{Q}$, then you can be sure that neither $S_1$ nor $S_2$ model the formula.


1

Let $R$ be a relation in $A \times B$. If you want $R^{-1}$ to be function on $B$, then you need $R$ to be injective and surjective. Indeed, if $R$ is injective, then $R^{-1}$ is a function on the range of $R$. If $R$ is surjective, then its range is $B$. (A relation is injective iff $(a_1,b) \in R$ and $(a_2,b) \in R$ imply $a_1=a_2$. A relation is ...


0

You can use the identity function. This clearly satisfies the definition of a reduction.


2

HINT:Denote by $[x], [y]$ the equivalence classes. To test that the addition is well defined you must see that $[x+y]=[x'+y']$, for all $x'\in[x],y'\in[y]$. In other words: $$x+y\sim x'+y'.$$


1

If I understand your picture correctly, you want to know, given the value of the blue curve at some $x$-value between -8 and 0, the value of the corresponding red curve. So the input to your function will be a number $s$ between $200$ and perhaps $300$, and the output will be between about $0$ and $60$. Here goes. Suppose we call the blue value $t$. Then ...


3

HINT: Show that the relation has only finitely many equivalence classes, say $C_1,\ldots,C_m$, and use the subscripts on the equivalence classes to define your function $f$.


2

This answer starts where you stopped. We focus on the $4$ sets $[1],[0],[4],[9]$. Any equivalence relation with the mentioned properties will induce a partition such that each of its elements is a non-empty union of these sets. We have $[1]\cup[0]\cup[4]\cup[9]=\mathbb N$, but what can be said about mutually disjointness? On this the third property applies ...


0

Hint: Start by plugging the expression for $f$ into the expression for $g$. That is, simplify the expression $g(ax+b)=1-(ax+b)+(ax+b)^2$. Then set this equal to $16x^2-12x +3$.


0

If $x\sim y$, then by symmetry $y\sim x$ so by transitivity $x\sim x$. Thus an element related to any other element is also related to itself. The set therefore decomposes into two subsets; on one the partial equivalence relation is empty and on the other it is an equivalence relation. Thus the partial equivalence relations on $[n]$ are in bijection with ...


1

You have done most of the work, you just need to prove transitivity. If $a R b$ and $b R c$, $\frac{a}{b}=2^{m_1}$ and $\frac{b}{c}=2^{m_2}$, multiply them together, you have $$\frac{a}{c}=2^{m_1+m_2}$$ Since $m_1+m_2 \in \mathbb{Z}$, $\frac{a}{c} \in H$, i.e. $a Rc$.


1

It depends on the context. If there is no ambiguity, "less than or equal to" works. In a lecture, you might pronounce it "curly less than" to help people who are taking notes. If you want a short way to pronounce it, you might vocally label it "r" or "rel" (short for "relation"), as in "Suppose that rel is a partial order", but this is less standard and I ...


1

Your proof is right. I would clarify the steps in the transitivity part by saying something like this: Assume $aRb$ and $bRc$. Now $2a+2b\equiv 0 \mod 4$ and $2b+2c\equiv 0 \mod 4$, which means $2a+2b=4m$ and $2b+2c=4n$ for some integers $m$ and $n$. Now by adding the two equations together we have $2a+2b+2b+2c=4m+4n$, i.e. $2a+2c=4(m+n-b)$, and thus ...


0

Your method is fine. You can shorten it by noticing that $$ 2a+2b=4k, $$ for some integer $k$, if and only if $a+b=2k$. This should put you on the track that your relation $R$ is just congruence modulo $2$, so $a\mathrel{R}b$ if and only if $a$ and $b$ are both even or both odd.


1

You seem to be fundamentally misunderstanding something here. Given a set $S$, a relation $R$ is simply defined as some subset of $S^2$, that is, where $$R=\{\langle s_1, s_2\rangle\in R: s_1\in S, s_2\in S\}$$ $R$ is by definition a relation. The domain of $R$ (admittedly this isn't a term I haven't heard or seen before, but from intuition and Google this ...


0

For first part as Noble Mushtak said $R_1 \cap R_2$ is reflexive. Now for second part $R_1 \cup R_2=R_1 or R_2 - (R_1 \cap R_2)$ i.e. that part of $R_1$ and $R_2$ which are only one time in $R_1 \cap R_2$ which are also reflexive as we have seen . That's it


1

Basically, to prove a relation $R$ is reflexive on a set $S$, we need to prove $(s, s) \in R$ for all $s \in S$. Since we already know this is true for $R_1$ and $R_2$, it becomes very easy to prove this for their intersection and union. Given an element $s \in S$, we know that $(s, s) \in R_1$ and $(s, s) \in R_2$ because $R_1, R_2$ are reflexive. Since ...



Top 50 recent answers are included