Tag Info

New answers tagged

0

To clarify, the relation the question is looking for is the following. Let $U$ be some set, and consider the relation $\subset$ on $U$. What does this relation do? It relates a subset $A\subseteq U$ to another subset $B\subseteq U$, if $A$ is a proper subset of $B$. So you need to check if this relation ($\subset$) is reflexive, symmetric etc. For ...


0

A relation $R$ on a set $A$ is a subset of $A\times A$, and in this case we have $A=\mathbb{Z}^2$ and so $R\subset\mathbb{Z}^2\times\mathbb{Z}^2$. Now we are told that a pair $\left((x,y),(x',y')\right)\in R$ iff the equations $x'=\left\lfloor\frac{|x|}{2}\right\rfloor$ and $y'=\left\lfloor\frac{|y|}{2}\right\rfloor$ are satisfied. So for example we know ...


0

There is no question there, and nothing that demands a solution. The text Define a relation $R$ on $\mathbb R$ as follows: For all real numbers $x$ and $y$, $mRn$ if and only if $3 \mid (m - n)$. is not an exercise, and it doesn't ask you to do anything. On the contrary, the quoted text is a definition of $R$. (Here I'm ignoring that it seems to ...


2

Try $R=\{(x,x) | x \in \mathbb{R}\}.$


0

This answer basically just confirms what it appears from the comments that you’ve already understood. Let $\langle P,\le\rangle$ be a partial order, and let $\preceq$ be a linear (total) order on $P$. The order $\preceq$ is compatible with the partial order $\le$ if the following condition is satisfied: for all $x,y\in P$, if $x\le y$, then $x\preceq ...


2

Your relation $R$ is already transitive, so it is its own transitive closure. It appears that what you’re misunderstanding is the notion of transitivity. A relation $R$ on a set $A$ is transitive if it satisfies the following condition: if $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$. It says absolutely ...


1

The transitive closure of a binary relation $R$ is the intersection of all transitive binary relations that extend $R$. To say that $S$ extends $R$ means that for all $x,y$ in the domain, if $aRb$ and $aSb$. The intersection $T$ of a set of binary relations is defined by saying that for all $x,y$ in the domain, $xTy$ if and only if for every binary ...


0

Hint: Start with something as: $\begin{array}{ccccccc} & a & b & c & d & e & f\\ a & \circ & \star & \circ & \circ & \circ & \circ\\ b & \circ & \circ & \star & \star & \circ & \circ\\ c & \circ & \circ & \circ & \circ & \star & \star\\ d & \circ & ...


0

Using DeMorgan's law on the conclusion, we see that it becomes $\neg q \lor \neg(p\to q)$. Since $\neg q \to \neg q$, then surely $\neg q \to (\neg q \lor A),$ where $A$ is any propositional statement. So your statement is a tautology, since it's always true.


0

Using $p\to q = \neg p \vee q $ and distributive laws, $$\neg{q} \to \neg(q\wedge(p\to \neg q))$$ $$=\neg q \to \neg (q\wedge(\neg p \vee \neg q))$$ $$=\neg q \to \neg ((q\wedge\neg p)\vee(q\wedge\neg q))$$ $$=\neg q \to \neg((q\wedge \neg p)\vee \mathrm{False})$$ $$=\neg q \to \neg(q\wedge\neg p)$$ $$=\neg q \to (\neg q \vee p)$$ $$=q\vee(\neg q \vee p)$$ ...


1

Reflexivity: Let $(a,b) \in R$. Then $(a,b) \leq (a,b)$ since a+b= a+b $\rightarrow$ a+b $\leq$ a+b and clearly $a\leq a$. Antisymmetry: Let $(a,b) \leq (c,d)$ and $(c,d) \leq (a,b)$. Then $a+b \leq c+d $ and $a\leq c$. Also, $c+d \leq a+b$ and $c\leq a$. Clearly, c < a and a < c is a contradiction unless a= c. By the same reasoning since a=c,a+b ...


1

To show that $\leq$ is a partial order, we need to show three things: $(a,b) \leq (a,b)$ for all $(a,b)$. $(a,b) \leq (c,d)$ and $(c,d)\leq (a,b)$ implies $(a,b) = (c,d)$. $(a,b)\leq (c,d)$ and $(c,d) \leq (e,f)$ then $(a,b) \leq (e,f)$. The first definitely holds, as $a \leq a$ and $a + b \leq a + b$. The second holds: Assume $(a,b) \leq (c,d)$ and ...


3

This is a question by bygone asker/user, who apparently was satisfied with answer it got, but for the sake of not leaving the question half-answered (from my perspective), I'll point out that a notion strictly on semigroups does appear in Howie's Fundamentals of Semigroup Theory in an exercise on p. 42. I'll reproduce it here with Howie's notation, who ...


0

This looks correct to me. Another way to approach this is to try to partition people based on the relation. So for part A, you can partition people into distinct sets: First set is all people aged 0 Second set is all people aged 1 Third set is all people aged 2 Etc. For part B, you can part consider all pairs of people in the population: First set ...


0

Suppose $(n,m)\mathrel{R}(r,s)$ and $(r,s)\mathrel{R}(n,m)$ Can we have $n>r$? No: this would contradict $(r,s)\mathrel{R}(n,m)$, because both $r>n $ and $r=n$ are false. Therefore $n=r$. Now we know $m\ge s$ and $s\ge m$, so also $m=s$. For transitivity it's similar. Suppose $(n,m)\mathrel{R}(r,s)$ and $(r,s)\mathrel{R}(x,y)$. If $n>r$, then it ...


0

The "mess of logical operators" is more or less inevitable, since you're trying to prove an if-then statement containing phrases each of which has an "or" in it. You're trying to prove: if $(n,m)R(r,s)$ and $(r,s)R(n,m)$, then $(n,m)=(r,s)$ (which is to say, $n=r$ and $m=s$). Try proving this directly by splitting into two cases: $n\ne r$ and $n=r$. In one ...


0

First of all, $vRv$ where $v$ and $v$ has the same number of zero's, hence $R$ is reflexive, Now Moreover if $uRv$ $\equiv$ ($u$ and $v$ have the same number of zero's) $\equiv$ ($v$ and $u$ have the same number of zero's) $\equiv$ ($vRu$ and so $R$ is symmatric)! Now suppose that ($uRv$ and $vRm$) $\equiv$ ($u$ and $v$ have the same number of zero's) ...


0

Reflexive: $u \sim u$ is clear that $u$ has the same amount of zeros as itself. Symmetry: if $u \sim v$ which means $u$ has the same amount of zeros as v then of course $v \sim u$ which means v has the same amount of zeros as $u$. Transitive: if $u \sim v $ and $v \sim w$ then $u \sim w$. Because $u$ and $v$ have the same amount of zeros and $v$ has the ...


2

The name predicate calculus has an historical heritage ... Today we prefer to call it first-order logic. For the "founding fathers" : Frege, Russell, the distinction between propositional and predicate calculi were not relevant; see Principia Mathematica and The Notation in Principia Mathematica. In the first modern mathematical logic textbook : David ...


0

A partition of a set $A$ is a collection of $a_i \subset A$ such that each $a_i$ is disjoint from the others and $\bigcup a_i = A$. An equivalence relation always partitions a set. Given a set $A$ and some relation $R$, the set of equivalence classes $A/R$ is a partition of $A$. Each member of $A/R$ is a subset of $A$ such that each member is $R$ related. ...


1

An equivalence relation is always partition. In general you want to put it in the form of a set. Here, you can say, $$A_{r}= \{(x,y) | y = \frac{x}{3^k}\}$$ Where $A_r$ denotes the equivalent partition corresponding to your relation. Also, $k$ is assumed to be an integer.


0

OK see here, we call a relation R transitive if $(a,b)\in R$ and $(b,c)\in R$ then $(a,c)\in R$. That is if a related to $b$, we will search whether $b$ transit any other element $c$ then only we are going to check whether $a$ related to $c$ if $b$ won't transit we by default consider it as transitive. Now in your example $1$ related to $1$ only and $1$ ...


1

I believe there is one equivalence class for each rational $r\in\mathbb Q$. That's because $a+b\sqrt{2}$ is equivalent to $r+\sqrt{2}$ where $r=a/b$. Now just show $r+\sqrt{2}$ is equivalent to $s+\sqrt{2}$ iff $r=s$.


0

Hint: Equivalence class of an element $a \in A$ for an equivalence relation $R: A \longrightarrow A$ is defined as the set of those elements in $A$ which are ''equivalent'' to $a$ via relation $R$. In your case the set $A=\mathbb{R}^2=\{(x,y) \, | \, x,y \in \mathbb{R}\}$. For the relation in part (1). Consider the equivalence class of the element ...


1

First one is an equivalence relation, and you can easily prove it. For the first one, equivalence classes are the set of points where the function takes the same value. For example, roots of the polynomial, {2,3} will form an equivalence class ([2]=[3]). For the second one, it is not reflexive or transitive, but symmetric as you inferred.


0

The notation you see here can be expanded to $$R = \{(x,y) : |x-y| = 2\}$$ Now you should see that this relation is symmetric but neither reflexive nor transitive. Generally the notations $xRy: P(x,y)$ and $R = \{(x,y) : P(x,y)\}$, where $P$ is a predicate, are equivalent. Sometimes you also see $xRy :\Leftrightarrow P(x,y)$ (read the $:\Leftrightarrow$ as ...


2

You need to show two things: that $x$ is an upper bound for $B$, i.e., that $b\mathrel{R}x$ for each $b\in B$, and that $x$ is the least upper bound for $B$, i.e., that if $y\in A$ and $b\mathrel{R}y$ for all $b\in B$, then $x\mathrel{R}y$. You’ve tried to do the first, but your argument is a bit confused. For one thing, it starts in the wrong place: ...


1

The "antisymmetry" statement looks like $$\text{If } xRy \text{ and } yRx, \text{ then } x = y,$$ or, using the ordered pair notation, $$\text{If } (x, y) \in R \text{ and } (y, x) \in R, \text{ then } x = y.$$ So, in your example, you just need to check if you have any ordered pairs $(x, y)$ and $(y, x)$ both in $R$: The only 'pair' of pairs allowed is ...


3

Here is a different, but equivalent definition for antisymmetry: For a relation to be antisymmetric, we need that for any element $(x,y)$ in the relation where $x \neq y$, the element $(y,x)$ must not be in the relation. Now look at your example. Are there any $(x,y) \in R$ with $x \neq y$? Yes, all three, $(a,b), (b,c)$ and $(a,c)$. Do we have $(y,x) \in ...


0

For the second one, if $R$ is asymmetric, then $aRa\ \Rightarrow\ \neg aRa$, so that $aRa$ does not hold for any $a$. This implies that $aR^ca$ for all $a$, so that $R^c$ is reflexive.


0

You are generally on the right track. The easiest set to count is the relation $R_2$ of part (b.). How many $a\in A$ allow for $b\in A$ such that $a+b=1000$? Since zero is not in $A$, only $999$ of the elements $a\in A$ allow this, and there is clearly exactly one $b = 1000-a$ for each such $a$. Similar to what you found for the simple case with ten ...


2

Somehow its both: The ordered pairs in $L\setminus M$ are all pairs for which there exists an $x$ such that the pair is $(x,x)$. The "all" is dropped in the original formulation from "(all) pairs of the form" and the "exists" is contained in "for some $x$".


1

You are correct in saying that it concerns all $x\in R$. The author is using "for some" in the context of "are of the form $(x,x)$...".


2

You are correct about symmetry and reflexivity. For transitivity, we need that every time there are two pairs of the form $(a,b)$ and $(b,c)$ in the relation, it must also be the case that $(a,c)$ is in the relation. The relation you have given is not transitive, can you find two pairs $(a,b)$ and $(b,c)$ in your relation such that $(a,c)$ is not in the ...


1

This set is not transitive because $(2,3),(3,4) \in Z $ but $ (2,4)\notin Z$. The reason you provided for not-symmetric is right.


2

It is not reflexive because $(0,0)\notin Z$; Is is not symmetric because of the reasons you stated. For instance, $(0,2)\in Z$ but $(2,0)\notin Z$. It is not transitive; for example, $(0,2)\in Z$ and $(2,3)\in Z$ but $(0,3)\notin Z$


1

It is not transitive because it has (2,3) and (3,4) but doesn't have (2,4). Correct, it's not symmetric for the reason you noted. Also correct, it's not reflexive. To be reflexive all (a,a) must be part of the relation (for any a). That doesn't hold here apparently.


0

The relation $R$ is transitive if For all $x,y,z$, if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$. In order to prove a relation is transitive, you need to prove the previous definition holds for all $x,y,z$ in the set where the relation is defined. However, if you want to prove $R$ is not transitive, it suffices to exhibit some elements ...


1

Suppose that $P : \mathsf{Rel} \times \mathsf{Rel} \to \mathsf{Rel}$ is a functor equipped with natural isomorphisms $$\hom(P(X,Y),Z) \cong \hom(X,P(Y,Z))$$ and $$P(X,1) \cong X \cong P(X,1).$$ Then $P(-,Y)$ is left adjoint to $P(Y,-)$, so that it preserves colimits, in particular coproducts. This implies $$P(X,Y) \cong P(\coprod_{x \in X} 1,Y) \cong ...


1

Write $f\sim g$ if $(f,g)\in R$. For reflexivity of $R$, you need to check whether $f\sim f$ for all $f\in F$. For symmetry of $R$, you need to check whether, for all $f,g\in F$, it holds that $f\sim g$ implies $g\sim f$. For transitivity of $R$, you need to check whether $f\sim g$ and $g\sim h$ implies $f\sim h$ for arbitrary $f,g,h\in F$. Since this ...


-1

What if Y is female. So X is a brother of Y, but Y is a sister of X.


0

HINT: Let $\mathscr{C}$ be the given family of subsets of $\Bbb R$, and suppose that $M\in\mathscr{C}$ is minimal. $M\in\mathscr{C}$, so $M\ne\varnothing$, and we may choose $x\in M$. Now consider the set $$[x+1,\to)=\{y\in\Bbb R:y\ge x+1\}\;.$$


0

Relation $R\subseteq X\times Y$ is a map if and only for every $x\in X$ there is exactly one $y\in Y$ such that $\langle x,y\rangle\in R$. Here $X=\{a,b\}$ and $Y=\{c,d\}$ with $a\neq b$ and $c\neq d$. So in this context $R$ is a map if it is of the form $\{\langle a,y\rangle,\langle b,z\rangle\}$ with $y,z\in\{c,d\}$. It is not empty (relation 1 is not ...


1

If X is the brother of Y and Y is the brother of X, then X is his own brother, if it were transitive.


1

Transitivity says: $aRb$ and $bRc$ imply $aRc$ $x$ is a brother of $y$, $y$ is a brother of $x$, but $x$ is not a brother of $x$. Therefore, it's not a transitive relation.


15

If Fred is Bob's brother, and vice versa, transitivity would imply that Fred is his own brother.


0

Well, it really depends on the quantity of set-theoretic details you require, but I'd try the following. Let $\Gamma:=\{X\subseteq\mathbb{R}\ |\ X\neq\emptyset\wedge\forall x\forall y((x\in X\wedge y<x)\rightarrow y\in X)\}$ and $M\in\Gamma$ minimal, i.e. $\forall Y\in\Gamma(Y\subseteq M\rightarrow Y=M)$ Let's recall notations $$ ...


1

(apple, apple) and (apple,atom) are each in both $R_1$ and $R_2$, but (atom, apple) is only in $R_2$. In the dictionary, "apple" comes before "atom". This explains $R_1$. In the alphabet, "a" comes at the same place as "a". This explains $R_2$.


0

If you mean "If a relation contains (a,b) and (c,a)", then for transitivity only (b,c) is needed. (c,b) is needed when you need to prove symmetry. If not, I think symmetry, i.e. (a,c) $\Leftrightarrow$ (c,a) is needed to imply (b,c) with transitivity.



Top 50 recent answers are included