Tag Info

New answers tagged

0

Transitive closure can be found using the above graph.Include all the pair of vertices for which the path exist in the graph


0

So if $y \in \bigcup_{a \in A} R_a \Rightarrow y \in R_x$ for some $x \in A$, then $(x, y) \in R$, hence $y \in \operatorname{Rng}(R)$. Conversely $y \in \operatorname{Rng}(R)$ implies that there exists $x \in A$, such that $(x, y) \in R \Rightarrow y \in R_x \subseteq \bigcup_{a\in A} R_a$.


0

1) Correct. 2) $\neq$ is not antisymmetric (and not transitive, so it can be used for 4). For that $[x\neq y\wedge y\neq x]\Rightarrow x=y$ must be true, and that is not the case. 3) $<$ is antisymmetric. This because $\neg[x<y\wedge y<x]$ is true and consequently $\neg[x<y\wedge y<x]\vee x=y$ (equivalent with: $[x<y\wedge ...


4

The only glitch is that you should say Let $x,y,z\in A$, with $x,y,z$ pairwise distinct instead of $A=\{x,y,z\}$ because you don't know that $A$ has exactly three elements. The rest of the arguments are good.


2

These both look perfectly good to me. For the counterexample, you may want to specify that $x$, $y$, and $z$ are all distinct (I suspect you had that in mind anyway). For example, you could use $\{1,2,3\}$ instead of $\{x,y,z\}$.


1

That last property isn’t antisymmetry. Antisymmetry says that if $\langle a,b\rangle$ and $\langle b,a\rangle$ are both in $R$, then $a=b$; that last property implies that $R$ doesn’t contain both $\langle a,b\rangle$ and $\langle b,a\rangle$ in the first place i.e., that $R$ is asymmetric. Note that a reflexive relation cannot be asymmetric unless the ...


0

Since $x \sim y$ and $y \sim x$, we have (as you said) $x = ym$ and $y = xn$ for $n,m \in \Bbb N$. Therefore we have, $$xy = xynm \implies 1 = nm \iff n = m = 1.$$ The result now follows.


1

You want your relation $R$ to not be transitive, so there should be $a,b,c$ with $aRb$, $bRc$ but not $aRc$. Well, suppose the underlying set has only those three elements $a,b,c$. What else besides $aRb$ and $bRc$ has to be in the relation? Just $aRa$, $bRb$, $cRc$ to make it reflexive. Check that the relation consisting of $aRb$, $bRc$, $aRa$, $bRb$, ...


0

Sit four people at a table and let $xRy$ if $x=y$ or $x$ is seated to the left of $y$.


1

Consider the relation $\sim$ on the real numbers $\mathbb{R}$ given by $$a\sim b\iff a\leq b\leq a+1$$ See if you can prove for yourself that it has the properties listed - if you need help I can say more.


0

A relation on a singleton set is always confluent. If $M=\{a\}$ all we need to check is that $$(a\mathrel R a \land a\mathrel R a) \to \exists z \in M : (a\mathrel R z\land a \mathrel R z)$$ which is obviously true -- if the left-hand side is true, then $a$ itself works as $z$. If $R$ is the identity relation, the left-hand side is $x=w_1\land x=w_2$, so ...


0

Go back to definitions,what does it mean to be reflexive,antisymetric and transitive? For reflexivity consider any element $a$ of set $X$,then there is natural number k(namely number 1) such that $a=a^k$ thus it is reflexive For antisymmetry consider and $aRb$ and $bRa$,they imply that $b=a^{k_0}$ and that $a=b^{k_1}$ then $b=(b^{k_1})^{k_0} = ...


1

Hints: For $x\in M$, let $[x]$ be the equivalence class of $x$ with respect to $\sim$. $x\sim y \Leftrightarrow [x]=[y]$ Also $M/\sim=\{[x]:x\in M\}$ Now think about what it means for two elements of $M$ to be related with respect to $∼_{M/∼}$


1

The smallest equivalence relation must always contain the diagonal $\{(x,x) : x \in s \}$, because every element must be equivalent to itself. And the diagonal is an equivalence relation (equality) and has size $n$.


0

Confluence is a property that a relation on a set may or may not have (as Willie Wong commented, what you wrote is a definition, not a statement about some specific relation where you can check if the property holds or not). Intuitively, as paw88789 comments, a relation is confluent if every time it branches off at some element $x$ to some elements $w_1$ ...


0

As Zhen Lin noted in his comment, subobject classifiers have nothing to do with the matter at hand. Having said that: being a subobjet is not logically equivalent to being a subset. Not even in the category of sets and functions. More exactly, in Set, $A \subseteq B$ implies that $A$ is a subobject of $B$ (the mono in question being the injection), but not ...


2

This is all well and good. There are a couple of possibilities for $g$ which might be even simpler to work with, though. For instance $g(x,y) =x/4$ or $g(x,y)=-y$, but it matters little. As for the surjectivity, you just have to point out that for any $c\in\Bbb R$ there is an $x$ such that $$ c=g\circ f(x) =5x $$ and that $x$ is, for your $g$, given by ...


1

Hint: $R$ is a relation on the set $\mathbb{Z}\times\mathbb{Z}$. In order to show that $R$ is reflexive, you must show that if $q\in \mathbb{Z}\times\mathbb{Z}$ then $q\sim q$; that is, that for every $(a,b)\in\mathbb{Z}\times\mathbb{Z}$ that $(a,b)\sim (a,b)$. The other properties of an equivalence relation are similar. Does that help?


0

Well, you have a set with 16 elements, so you need to draw 16 points on the plane and join some of them with arcs. The trick is not to draw too many arcs - for example, you'll need to draw an arc between (1, 1) and (1, 2) and another arc between (1, 2) and (2, 2), but you shouldn't draw an arc between (1, 1) and (2, 2) because of transitivity (which I think ...


0

Well it's not too hard, I mean, it's easy to think that: If $(a,b) \textbf{R} (c,d) and (c,d) \textbf{R} (e,f) \implies a \lvert c , b \lvert d , c \lvert e \wedge d \lvert f$ so if $c$ divides $e$ and $a$ divides $c$ then $a$ divides $e$, because the relation "divides" is transitive, the same with $b$. Therefore $(a,b) \textbf{R} (e,f)$ so it is ...


1

Integers that add up to an odd number.


0

We can prove that it is reflexive, for example, as follows: $R$ is reflexive if for every element $(a,b) \in A \times A$, we have $((a,b),(a,b)) \in R$. That is, $R$ is reflexive if for every pair $(a,b)$ of numbers from $1$ to $4$, $a$ divides $a$ and $b$ divides $b$. Is it always true that $a$ divides $a$? That $b$ divides $b$? If so, then $R$ is ...


3

I would start by making sure that it’s not transitive. Let $R$ be the relation, and suppose that $a\,R\,b$, where $a\ne b$. Symmetry will require that $b\,R\,a$, so you’ll have to have $a\,R\,b\,R\,a$; transitivity would tell you that $a\,R\,a$, so if you make sure that $a\,\not R\,a$, you’ll kill two birds with one stone by ensuring both that $R$ is not ...


0

Your wording is slightly off. You say: for any $a,b\in A$ in the binary relation $R$ is a subset of $A\times A$, it is anti-symmetric if $(a,b)\in R$ and $(b,a)\in R$ then $a = b$. Which makes it sound like $R$ could be anti-symmetric for one pair $a,b$ and not so for another. What you should write is A binary relation $R$ is anti-symmetric if for ...


1

If $R$ is anti-symmetric then any subset of $R$ is anti-symmetric, also $R\cap S$. I think the normal way of doing such things is: If $(a,b),(b,a)\in R\cap S\implies (a,b),(b,a)\in R\implies a=b$.


0

If your new equivalence relation $\underset{S}{\sim}$ is a constriction from the whole set $E$, then the answer is yes. Equivalence relation have to satisfy 3 axioms: Reflexivity. $a \underset{S}{\sim} a$. It is true for new relation because of the fact that we can look at the element $a$ like an element of the whole $E$ and use fact that $a ...


1

No, in this case, the entry corresponding to $(2, 3)$ (the $(3, 4)$ entry of the matrix) is zero, so $(2, 3) \not\in R$. Since $(3, 2) \in R$, however, the new relation $R' := R \cup \{(2, 3)\}$ formed by adding $(2, 3)$ to $R$ is not antisymmetric.


1

Clarification on the number of $S_{ij}$'s: There are $n^2-n$ total elements in $A_2$. To count the number of subsets of $A_2$ of the form: $$ S_{ij}=\{(a_i,a_j), (a_j, a_i)\} $$ with $j\ne i$, there are $n^2-n$ ways to choose $(a_i,a_j)$, and once we've chosen $(a_i,a_j)$, the two element subset is determined. However, this means we have counted each ...


2

I am learning about relations right now and I have a question about some terms. I am told a relation on $A$ is a subset of $A\times A$. Then I am told a relation $R$ on $A$ is reflexive if for all (and this is where I have a problem) $a∈R$, we have $a∼a$. No, it's for all $a\in A$ that $a\sim a$. Which means that $(a,a)\in R$ Take, for example, ...


2

Drawing a picture might help here. There are $n^2$ total elements of $A \times A$. Of these, $n$ of them lie on the diagonal, and the remaining $n^2 - n$ are not. Of the elements not on the diagonal, half of them are above the diagonal and half of them are below, so $\frac{n^2 - n}{2}$ are below. To make a relation reflexive, we must choose all of the ...


2

HINT: I think you misunderstood the relation. The relation statement is this: \begin{equation} aPb\Longleftrightarrow5|(2a+3b) \end{equation} $a$ and $b$ are just placeholders. You can think of $P$ like a relation between two objects, lke so: \begin{equation} \heartsuit P\diamondsuit\Longleftrightarrow5|(2\heartsuit+3\diamondsuit) \end{equation} Read it ...


0

Given the definition: $\forall x,y: (x\rho^2 y \iff \exists w\, (x\rho w\land w\rho y))$ If $\rho$ is Reflective then $\forall x\, (x\rho x)$ so clearly $\rho^2$ is too as it follows by $\underline\qquad$ that : $\forall x\, (x\rho^2 x)$. If $\rho$ is Symmetric then $\forall x,y\, (x\rho y\iff y\rho x)$ so clearly $\rho^2$ is too as it follows by ...


2

It is true, and what remains to be checked is: If $a\rho^2b$, and $b\rho^2c$, then $a\rho^2c$. Since $a\rho^2b$, there is $c$ such that: $a\rho c$, and $c\rho b$, and also there is $d$ such that $b\rho d$, and $d\rho c$. Thus by transitivity, $a\rho d$. So $a\rho d$, and $d\rho c$ ,hence $a\rho^2 c$. Hence $\rho^2$ is transitive.


1

Hints: reflexive, $a p a$ since $\sin a=\sin a$. symmetric, If $a p b$, then $\sin a=\sin b$, and hence $\sin b=\sin a$, which shows that $b p a$ . transitive, If $apb$ and $bpc$, then $\sin a=\sin b$ and $\sin b=\sin c$, and hence $\sin a=\sin c$. So $apc$. $[a]=\{b\in \Bbb R: \sin a=\sin b\}$.


2

Observe that you also have (1,3) and (3,1). However you don't have (1,1).


1

Two remarks: (1) Equality is an equivalence relation which is also a partial order ($\leq$). (2) An equivalence relation is never a strict partial order ($<$).


0

Yes, but it must be exactly like the one you propoes, that is all the equivalence classes must be of size one. For if we had an equivalence class with at least two elements a,b we would $(a,b),(b,a)\in R$ so it would not satisfy anti-transitivity


1

Your answer to (1) seems almost correct to me. My method: think of what property all the elements of one class would have: they all have the same first letter in their string, and also they have the same third letter. So a class is described by (first letter, third letter), such as “A_B_”. My only objection is that ordinarily, a “string from the alphabet ...


1

As was noted in the comments, you have far too much in your second level. For instance, $2\mid 4$ and $1\mid 1$, so $\langle 2,1\rangle$ must be below $\langle 4,1\rangle$. On the other hand, we know that there’s nothing between them, because there is no integer $n\{1,2,3,4\}$ such that $2\mid n$, $n\mid 4$, and $n$ is neither $2$ nor $4$. Here are the ...


0

If function $f:\mathbb Z\times\mathbb Z\rightarrow\mathbb Z$ is prescribed by $(a,b)\mapsto a+b$ then $$((a,b),(c,d))\in\mathcal R\iff f(a,b)=f(c,d)$$ This makes it easy to prove that the relation is reflexive, symmetric and transitive: $f(a,b)=f(a,b)$ $f(a,b)=f(a',b')\Rightarrow f(a',b')=f(a,b)$ $f(a,b)=f(a',b')\wedge f(a',b')=f(a'',b'')\Rightarrow ...


0

$(k,a)R(l,b)\Leftrightarrow kb=la$, where a,b,... >0 and $k,l,...\in\mathbb Z$. Reflexive: $ka=ka\Rightarrow (k,a)R(k,a)$. Symmetric: $(k,a)R(l,b)\Rightarrow kb=la\Rightarrow la=kb\Rightarrow (l,b)R(k,a)$. Transitive: $(k,a)R(l,b)\wedge (l,b)R(m,c)\Rightarrow kb=la \wedge lc=mb\Rightarrow$ $kbc=lac \wedge lac=mba\Rightarrow$$ kbc=mba\Rightarrow $ ...


2

In order for a relation to fail to be transitive, there must exist pairs $(x,y)$ and $(y,z)$ in the relation such that $(x,z)$ is not in the relation.


1

The premise $aRbRc$ is never met so transitivity is satisfied vacuously. (Here, we have used: the statement $A\implies B$ is true if $A$ can never be satisfied.)


0

Let (a,b)=x, (b,c)=y and (c,d)=z; Now to prove that R on A is equivalence. We'll have prove that it is also reflexive(xRx), symmetric[(xRy)=(yRx)] and transitive[(xRy) and (yRz) implies (xRz)]. And the condition is: (a,b)R(c,d) implies a+d=b+c xRx=(a,b)R(a,b) implies a+b=b+a which is true; therefore it is reflexive. xRy=(a,b)R(b,c) implies a+c=b+b….1 & ...


0

Let (a,b)=x, (b,c)=y and (c,d)=z; Now to prove that R on A is equivalence. We'll have prove that it is also reflexive(xRx), symmetric[(xRy)=(yRx)] and transitive[(xRy) and (yRz) implies (xRz)]. And the condition is: (a,b)R(c,d) implies a+d=b+c 1. xRx=(a,b)R(a,b) implies a+b=b+a which is true; therefore it is reflexive. 2. xRy=(a,b)R(b,c) implies a+c=b+b….1 ...


-1

It may or may not be transitive. It depends on the set and the relation. eg 1: Let S={} then R={} and it is trivially transitive. eg 2: Let S={a} then there are two relations R1={}, R2={(a,a)} and both are transitive trivially. eg 3: Let S={a,b} then there are 16 relations R1={} --> Transitive R2={(a,a)} --> ...


2

In the argument for symmetry, you've shown that if $f = g$ then $f \sim g$ and $g \sim f$. But this does not guarantee symmetry, which requires that if $f \sim g$ then $g \sim f$. To do this, $f \sim g$ shows that there is a constant $k$ such that $f(x) = g(x)$ for all $x \geq k$, and you need to show that there is a constant $l$ such that $g(x) = f(x)$ for ...


1

To prove that two sets $A$ and $B$ are equal it is enough to show that $x\in A$ implies $x\in B$ and conversely that $x\in B$ implies $x\in A$ (as you did). If $A=\emptyset$ then $x\in B$ implies that $x\in A$ wich cannot be true. So it is okay to conclude that $B=\emptyset$.


1

I think this is not a partial order. Indeed the antisymmetry does not work. Consider $$a=2, \quad b=4$$ Then you have $aRb,$ since $2-4 = -2 \le 4$, and $bRa$, since $4-2 =2\le 4$.


0

Okay, let's adopt the definitions: $(x) = x$ $(a,b) = \{\{a\},\{a,b\}\}$ Then we can check that $(\varnothing)\neq (\varnothing,\varnothing)$. By definition, $(\varnothing) = \varnothing$ $(\varnothing,\varnothing) = \{\{\varnothing\},\{\varnothing,\varnothing\}\}$ (This can be simplified further, but there's no need.) We have ...



Top 50 recent answers are included