Tag Info

New answers tagged

3

HINT: Think of a triangle whose vertices represent the points of the model, and whose edges represent the relation $R$.


0

Since any relation on a set $A$ to itself can be represented by a Boolean matrix. Thus each relation corresponds to a $n \times n$ matrix (call it $M$). For anti-symmetric relation you need the following: Let $i \neq j$ and let $m_{ij}$ be the $ij^{\text{th}}$ entry of $M$. Then If $m_{ij}=1$, then the entry $m_{ji}=0$. If $m_{ij}=0$, then $m_{ji}=1$ or ...


1

No -- $3^{(n^2-n)/2}$ counts the relations that are antisymmetric and irreflexive (it also counts the relations that are antisymmetric and reflexive, but that is unlikely to be what you had in mind). Instead: First let's count the antisymmetric relations. For each of the $\binom n2$ unordered pairs or elements we can either have $aRb$ or $bRa$ or neither, ...


1

A simple transfinite induction proof shows that $P_\alpha\subseteq P_\beta$ when $\alpha\le\beta$, and it is similarly obvious that $P_\alpha\subseteq P$. If it were true that $P_\alpha\subsetneq P_{\alpha+1}$ for every ordinal $\alpha$, then the function $f:{\sf On}\to {\cal P}(P):\alpha\mapsto P_{\alpha+1}\setminus P_\alpha$ would map each ordinal to one ...


1

Your definition is missing a crucial part. It should be $R$ is transitive iff for all $a,b,c\in\mathbb Z$ it holds that $$ (a,b)\in R \wedge (b,c) \in R\implies (a,c) \in R $$ When you want to prove that a "for all" statement is false, it suffices to give a single counterexample. For example, one counterexample would be $a=3, b=9, c=81$, because ...


0

Hint: Suppose that $b = a^2$ and $c = b^2$, where $a, b, c \in \mathbb{Z}$. Does this imply that $c = a^2$? Note that you cannot make the assumption that $a \neq b$.


2

You need to find two elements of the order which are incomparable. That what it means that the order is not total. In the case of a power set ordered by inclusion, this means $A$ and $B$ such that $A\nsubseteq B$ and $B\nsubseteq A$. Do note that this requires that $X$ has at least two elements.


0

Recall that $x\mid y$, the divides relation, says that there is an integer $n$ such that $y=nx$. Then if $x\mid y$ we have $y=nx$ and $-y=(-n)x$, and $-n$ is also an integer, so $x\mid-y$. More generally, if $k$ is an integer, then $x\mid y$ implies $x\mid ky$, and this is the special case when $k=-1$.


1

A relation on set $P$ is a subset of $P\times P$. In this case, $|P|=3$ so $|P\times P|=9$. Hence there are $2^9$ subsets of $P\times P$, and thus $2^9$ relations on $P$.


0

Given any $\mathcal A \subseteq \mathcal P(X)$, we claim that: $$ \sup\mathcal A = \bigcup_{A \in \mathcal A}A $$ To see this, first note that $\bigcup_{A \in \mathcal A}A \in \mathcal P(X)$ is an upper bound for $\mathcal A$. Indeed, given any $S \in \mathcal A$, we have from the properties of union that: $$ S \subseteq \bigcup_{A \in \mathcal A}A $$ It ...


3

You can’t list them, but you can describe them, in the sense that for each $x\in\Bbb R$ you can write down a simple description of the equivalence class of $x$: it’s $x+\Bbb Q=\{x+q:q\in\Bbb Q\}$; in all likelihood this is the sort of answer that was intended, though one could wish that the question were worded better.


2

No, since $R$ should be a subset of $X$. Instead, from your answer we have that $(3,4) \in R$ but $(3,4) \notin X$. So to fix this, we should put $(3,4)$ in $X$. But then since $X$ must be symmetric, what else must also go in $X$? Note that $R$ is a proper subset of $X$ iff every element of $R$ is also in $X$ but $X$ contains an element that is not in $R$. ...


1

Ask yourself these questions (and then answer them): Q. What is a partial ordering on a set? What properties do I have to establish? Q. What is the lex ordering on a cartesian product of two posets? You can do this. Unpack the definitions and check that the properties are satisfied.


1

A relation is any subset of $A \times A$. Given any set $X$, the number of subsets is $2^{\lvert X \rvert}$. So the number of relations on a 6-element set is $2^{36}$. Big number! For example one relation could be $\{(1,2)\}$. In other words 1R2 and that's the entire relation. You can see that there are a lot of possible relations. An equivalence relation ...


0

To prove it, we are wanted to suppose that $(a,b), (b,c) \in R$. Our goal is to show that $(a,c) \in R$. However, For any different element $a, b, c \in A$. So $(a,b), (b,c) \in R$ cannot hold, and this shows the transitive is true.


0

All you need for transitivity is $$(a,b)\in R, (b,c) \in R \Rightarrow (a,c)\in R$$ But $(a,b)\in R$ implies $a=b$ (why?), so $a=b=c$ and thus transitivity follows immediately from reflexivity.


1

Many symmetric relations are not transitive; for example: A lives within one mile of B. So your title would make more sense if instead of "Why is a symmetric relation transitive?" it said "Why is this symmetric relation transitive?". It is transitive because it lacks any opportunity not to be transitive: you would need to find $a, b, c$ such that $a\sim b$ ...


1

Suppose $x-y$ is rational and $y-z$ is rational, then its sum its rational, but this is $$x-y + y -z = x-z$$


2

Remember that a relation on $A$ is a subset of $A\times A$. Since $A$ has $6$ elements, $A\times A$ has $36$. This should help you calculate the number of relations in total. To count the reflexive relations, you need to recall the definition of reflexive and use it to limit the number of possible relations, similarly for symmetric relations.


1

In general, given a function $f$, we can define a relation $x R_f y$ iff $f(x) = f(y)$. It is easy to see that $x R_f x$, and that if $x R_f y$ then $y R_f x$. And if we have $x R_f y$ and $y R_f z$, then we have $x R_f z$ hence $R_f$ is an equivalence relation. Furthermore, the equivalence classes are given by $f^{-1}(r)$ for all values $r$ in the range of ...


2

Your Method 1 is wrong. They asked for a range not a quantity. Method 1 gives you the Fahrenheit value for $14^o \text{C},$ which is $57.2^o \text{F}$ $$14^o \text{C}=57.2^o \text{F}~~and~~42^o \text{C}=107.6^o \text{F}$$ $$\therefore~~\text{Difference}=50.4^o \text{ F}$$ You can also find the difference by $$F_1 - F_2=\frac{(C_1 - C_2)\times 9}{5}$$ ...


1

In your case $p(n)$ is the assumption that every total order on $n$ elements is isomorphic to $\{1,\ldots,n\}$ with the usual ordering. The proof then assumes that $p(k)$ holds, and then should proceed to prove that $p(k+1)$ holds as well. Usually this is done by removing the maximal (or minimal) element and using the induction hypothesis. This is one of ...


0

Let $$p(n)=\mbox{ for all total orders }P\mbox{ with }n\mbox{ elements, }P\simeq Q=(\{1,2,\ldots,n\},\leq')$$ If the base case is not specified, the proof is technically incomplete, but in this case we can take the base case to be either $0$ or $1$ and in either case the total order is trivial because there are fewer than two elements, so the base case is ...


0

Working straight from the definition on wikipedia, is suffices to show that if $a|b$ and $b|a$, then $a=b$. Just expand these hypotheses out as $a=mb$ and $b=na$ for some $n,m\in\mathbb{N}$ and notice that both $n=m=1$. Assuming you are working with $\mathbb{N}$. This shows your relation is anti-symmetric. Let's show it's not symmetric just because we can. ...


1

Since you have for the conversion from Celsius to Fahrenheit $$F=\frac95 C+32$$ you have $$\Delta F= F_2-F_1=(\frac95 C_2+32)-(\frac95 C_1+32)=\frac95 (C_2-C_1)=\frac95\Delta C$$


2

Basically, neother the function that takes Fahrenheit to degrees nor the other way around is a linear function (strictly-speaking, it is not an additive function, meaning $f(a+b) \neq f(a)+f(b)$). Let F be the function that takes temperature in Celsius to Fahrenheit. You just described a case of how $F(a-b)\neq F(a)-F(b)$. Actually, both F, and its inverse ...


-1

$$\frac C5=\frac{F-32}9\implies \frac{C_1-C_2}5=\frac{F_1-F_2}9$$


2

HINT: Since $A\neq B$, there is some $a\in A$ such that $a\notin B$, or there is some $b\in B$ such that $b\notin A$. Assume that the first case holds. Since $B$ is not empty, there is some $b\in B$. Now you have two elements from $A$ and $B$, use them to produce a witness for the inequality you are trying to prove.


3

Without loss of generality, assume that there is $x\in A$, $x\notin B$. $B$ is not empty, so there is $y\in B$. Then $(x,y)\in A\times B$ and $(x,y)\notin B\times A$.


1

The quotient set has only $5$ elements. Divide an integer $x$ by $5$. The remainder will say you in which class is $x$. If the number is negative and you find the division somewhat confusing (just like myself do), just add a big enough multiple of $5$ to it: $-8+10=2$, so $-8$ is in the same class as $2$. $1$ is in the same class as... well, as $1$. $10$ ...


1

Every equivalence class has a unique representant $r\in[0,1)$: $$[r]=\{x\in\mathbb R\mid x=\lfloor x\rfloor+r\}$$


1

You are saying that $aRb\wedge bRc\Rightarrow aRc$ has been fullfilled. That is not true: Here we have $1R2\wedge2R1$ but not $1R1$. On your second question: Can you find $a,b,c$ such that $aRb\wedge bRc$ and not $aRc$? No, you can't. Direct conclusion: $R$ is transitive.


0

In the first relation, we have $(1, 2) \in R $ and $(2, 1)\in R$, hence, if the relation were transitive, we would need $(1, 1) \in R$. In the second relation, it is trivially transitive, because transitivity fails only if there exist $a, b, c$ such that $(a, b) \in R$ and $(b, c) \in R$, and $(a, c) \notin R$. There is no such failure in relation $2$.


1

First question: $1R2$ and $2R1$. Transivity would imply that $1R1$. Notice that $a$ and $c$ in the definition of transitivity don't have to be different. Second question: $1R1$ and $1R1$, transivity implies that $1R1$. Ok. Same for $2$ and $3$. No counterexamples, so $R$ is transitive.


1

The first relation is not transitive as you have 1R2 and 2R1 (and 2R1 and 1R2). If it were transitive you would have 1R1 (and 2R2). But you do not. For the second relation. It is transitive, since the only relations are 1R1 and 2R2 and 3R3. So, the only couples xRy and yRZ are 1R1 and 1R1, which needs 1R1 to complete the transitivity condition. 2R2 and ...


2

You just need to use the Cartesian product. Then you can write: \begin{align*} [x,y]_{A\times B} &= \{(x',y') \in A\times B\ |\ (x',y')\sim_{A\times B} (x,y)\}\\ &= \{(x',y') \in A\times B\ |\ x' \in [x]_A \quad \text{and}\quad y'\in [y]_B\}\\ &= \{(x',y') \in [x]_A\times [y]_B\}\\ &= [x]_A\times [y]_B \end{align*} Now, say we have $n_A$ ...


1

Symmetry It follows that $\enspace a \sim b \implies b \sim a \enspace\enspace\forall \enspace a,b \in A $, since anything implies something true: formally, $Q \implies (P \implies Q) $. The same applies to transitivity.


0

If $a\sim b$ holds for all elements $a,b\in A$, then the claims needed for symmetry/transitivity are trivially true.


0

Here is an example that is going to show that the below relation is not anti-symmetric. Let R be a relation { (1,2), (1,3), (3,1), (1,1), (3,3), (3,2), (1,4), (4,2), (3,4)} First step is to find 2 members in the relation such that (a,b) ∈ R and (b,a) ∈ R If no such pair exist then your relation is anti -symmetric.If any such pair exist in your relation ...


0

For every $a\in A$ can you find a $B\in\wp A$ satisfying $aHB$? Is this $B$ unique in satisfying this condition? If (and only if) the answer on both questions is 'yes' then $H$ is a function.


0

A binary relation on a set $A$ is a collection of ordered pairs of elements of $A$. An element of $A$ can be related to many elements of $A$. A function is a relation between a set $A$ and a set $B$ with the property that each element of $A$ is related to exactly one element of $B$. Having said that, all functions are relations but not all relations are ...


1

There is a lecture series on Digital Signal Processing available on Youtube, in which a symbol appears which quite elegantly states "not necessarily equal to" by subscripting the "not equals" sign with the letter n. Screenshot source: Prof. S.C Dutta Roy, Department of Electrical Engineering, IIT Delhi


0

You are correct it is reflexive.Not symmetric as$(2,1)\in A$ but $(1,2) \notin A$. transitive is satisfied as there is only one pair in $A$ such that $(a,b)\in A$ and $(b,c) \in A$i.e.$(3,2)$ and $(2,1)$.for antisymmetric it is vacuosly true as there are no elements in $ A$ such that both $(a,b)$ and $(b,a) \in A$


1

Antisymmetry for (a): Suppose $a|b$ and $b|a.$ Then there are positive integers $s,t$ such that both $as=b$ and $bt=a.$ Substitution then gives $ast=a,$ so that $st=1.$ But since $s,t \ge 1$ this implies $s=t=1$ which then gives $a=b.$ For part (b) all you need to note is that, if $m$ is assumed to be maximal, it should be that every positive integer $x$ is ...


1

It's advisable to work carefully and make a good effort to find counterexamples in problems like these. From $a \leq b^2$ and $b \leq c^2,$ certainly you can conclude that $b^2 \leq c^4$ and therefore $a \leq c^4,$ but that was not what you needed to show. Consider $a=200,\ b=20,\ c=5.$ Observe that $$a = 200 \leq 20^2 = b^2,$$ $$b = 20 \leq 5^2 = c^2,$$ ...


0

Check out the transitivity parts of your proof. E.g. for a., we have $5\trianglelefteq 3$ and $3\trianglelefteq 2$ but not $5\trianglelefteq 2$. If you already find that the given relation is not reflexive (or not transitive), then you're done as it cannot be partial order. Finally, c. is indeed transitive, but we can have two different continuous ...


0

The first proof is not correct. $a\leq b^2$ and $b \leq c^2$ does not imply $a \leq c^2$. Consider $a=15, b=4, c=3$. The second proof is also incorrect because again transitivity fails. Consider $m=10,n=5,p=0$. Your problem is that you state, for example, that "if m ≤ n + 5, and n ≤ p + 5, then m ≤ p + 5" but do not give any justification. And the ...


0

Reflexivity is just a matter of noting every element in $S$ is related to itself, which you have. For transitivity I would just note 1 is only related to itself, so there are no nontrivial instances of transitivity to explore. Similarly, no elements are related to $3$ or $4$ except themselves. (When I say related to, I mean on the left hand side of the ...


0

I suggest you read https://archive.org/stream/PrincipiaMathematicaVolumeI/WhiteheadRussell-PrincipiaMathematicaVolumeI#page/n300/mode/1up, it contains all theory of composite relations exposed in a much more complete form than Zermelo's school, which your're using. In your case, you just have to prove $\breve{D}'(S|R)\subset \breve{D}'R$ for ...


1

Any subset of $\mathbb{N}$ containing $1$ are equivalent. So the equivalence class for $1$ is $$[1] = \{ \ \{ 1 \} \cup A \ \ | \ \ A \in \mathcal P(\{n \in \mathbb{N} \ | \ n > 1 \}) \ \}$$ Hence in general...



Top 50 recent answers are included