# Tag Info

2

The main thing to understand here is the logic. If you get that right you should find that everything else is pretty easy. Just a suggestion - others may disagree - but I find that writing these things in symbolic logic makes it harder, not easier. I would put them in words as far as possible. There are a lot of "if-then" statements to prove here. In ...

2

In many cases $a<b$ is defined as saying that $a\le b$ is true and $a\neq b$ is true. Thus if $a<b$ is true, so is $a\le b$.

2

Indeed it is !! If $a < b$, then surely $a ≤ b$, as $≤$ implies less than or equal to. If any one of the conditions, i.e. $<$ or $=$, is true then $a ≤ b$ is true. Therefore $a ≤ b$ will always be true, if $a<b$.

1

You seem a little confused about set builder notation. When we write $$T=\{x\in S: x \text{ satisfies some condition}\}$$ The symbol $x$ is a free variable. This, unpacked, roughly gives you instructions for how to build $T$: Take an $x$ in $S$. Check to see if $x$ satisfies the condition. If it does, put $x$ in $T$. If it doesn't, throw it out. Repeat ...

0

In the statement, you are only given that there is some $a,b,c$ that satisfies the requirement. From the definition of transitive, you need it to be true for any $a,b,c$. So let $A=\{1,2,3,4\}, R=\{(1,2),(2,3),(1,3),(2,4)\}$ We are missing $(1,4)$ in $R$ for transitivity, but the first three elements listed in $R$ meet the True/False statement.

2

The mere existence of elements three elements $a, b, c$ such that $(a, b) \in R, (b, c) \in R, \text{ and } (a, c)\in R$ does not guarantee that transitivity holds for all pairs of elements For example: Let's say our set is $\{a, b, c,\}$, and let $$R = \{(a, b), (b, c), (a, c) , (b, a)\}.$$ We have that $(b, a)\in R$ and $(a, b) \in R$, but $(b, b)\notin ... 0 Closure definition:$ R \circ R^{-1} $where$ R \subset A \times B $Reflexive means the following$ \forall a \in A  a (R \circ R^{-1}) a$. Transitive means the following$ \forall a,b,c \in A $,$ a(R \circ R^{-1})b \& b(R \circ R^{-1})c \rightarrow a(R \circ R^{-1})c$The closure in this specific case:$ (R \circ R^{-1}) := \{ (1,1), (2,2), ...

1

Reflexive and transitive are two different things. Transitive means: if $a \sim b$ and $b \sim c$ then $a \sim c$. While reflexive means that $a\sim a$ in your realtion. You have $R = \{(1,1), (2,3), (3,1)\}$ and you want it to be closed under transitivity . Since $2\sim 3$ and $3\sim 1$ you must have $2\sim 1$ so you add $(2,1)$. Edit: Suppose that ...

3

If $x$ is even and $y$ is odd, then $x=2k$ for some integer $k$ and $y=2l+1$ for some integer $l$, so $x+3y=2k+3(2l+1)=2(k+3l+1)+1$ is odd. If $x$ is odd and $y$ is even, then $x=2m+1$ for some integer $m$ and $y=2n$ for some integer $n$, so $x+3y=2m+1+3(2n)=2(m+3n)+1$ is odd.

2

There are exactly two equivalence classes: a. The set of integers divisible by 3, and b. The set of integers non-divisible by 3. Clearly, if $3\mid m$ and $3\mid n$, then $3\mid m^2$ and $3\mid n^2$, and hence $3\mid m^2-n^2$. If $3\not\mid m$ and $3\not\mid n$, then $m^2$ and $n^2$ leave remainder 1, when divided by 3, and hence $3\mid m^2-n^2$.

1

The equivalence class $[0]$ is the set of all elements related to $0$. We have $m \in \mathbb{N}$ is related to $0$ $\iff m^2 - 0 = m^2$ is a multiple of $3$. Since $3$ is prime, $m \sim 0 \iff m$ is a multiple of $3$. Hence, $[0] = \{3k : k \in \mathbb{N} \}$. Similarly, $m \sim 1 \iff m^2 - 1 = (m + 1)(m-1)$ is a multiple of $3$, in which case $m ... 1 (a)R in N will be reflexive iff (m,n) R (m,n). Now, m+n=n+m$\implies$(m,n) R (m,n)$\implies$R is reflexive (b)R in N will be symmetric if (m,n) R (l,k)$\implies$(l,k) R (m,n). Now, m+k=n+l$\implies$l+n=k+m$\implies$(m,n) R (l,k)$\implies$(l,k) R (m,n)$\implies$R is symmetric. (c)R in N will be transitive if (m,n) R (l,k) and (l,k) R ... 1 addendum: This answer is only useful if$\mathbb Z$(and subtraction) is allready at your disposal. It seems however that you are busy here with constructing$\mathbb Z$. If that is the case then have a look at the direct proof. Note that$(m,n)\sim(k,l)\iff f(m,n)=f(k,l)$where$f:\mathbb N\times\mathbb N\rightarrow\mathbb Z$is defined by$f(m,n)=m-n$. ... 1 In general if$f:X\rightarrow Y$is a function then$\sim$defined by$x\sim x'\iff f(x)=f(x')$is always an equivalence relation on$X$and this is not difficult to prove. Note that: 1)$f(x)=f(x)$reflexive 2)$f(x)=f(y)\Rightarrow f(y)=f(x)$symmetric 3)$f(x)=f(y)\wedge f(y)=f(z)\Rightarrow f(x)=f(z)$transitive In your case we deal with$f(n)=n^2$... 1 Hint $$m^2 = n^2 \iff m^2 - n^2 = 0 \iff (m - n)(m + n) = 0 \iff m = n \text{ or } m = -n$$ So$m$and$n$are equivalent if and only if either$m = n$or$m = -n$. 2 1.a. is not reflexive because it does not include$(1,1)$. It is symmetric. It is not transitive because, although it includes$(1,3)$and$(3,1)$, it does not include$(1,1)$1.b. Is reflexive and is not symmetric, for precisely the reasons you said. It is also transitive because there is no counterexample to it being transitive. There are only two that ... 2 Define$\phi(2n) = \phi_1(n)$,$\phi(2n-1) = \phi_2(n)$. 1 Let's look at a trivial example for a moment. Suppose$A = \{a,b,c\}$and$B = \{d,e\}$. One way of seeing that$A\cup B$is countable is to right a list containing all the elements. One such list is$a,b,c,d,e$. But this doesn't generalize nicely to countably infinite lists, since we'd never finish$A$. On the other hand, the list$a,d,b,e,c$, choosing an ... 0 If non-transitive means "never transitive for any triple", that is impossible for a complete tournament (irreflexive, never-symmetric relation) with$4$or more players. The question sounds like an exercise of rediscovering that fact. If partial tournaments are allowed then it can be done with any number of players, just partition them into 3 categories ... 0 Rerrange like this:$ $if$\,d\mid m\,$then$\, d\mid x\!\iff\! d\mid y,\,$since$\,d\mid m\mid x\!-\!y.\,$Hence$\,m,x\,$and$\,m,y\,$have the same set$\,S\,$of common divisors$\,d,\,$so the same greatest common divisor$(= {\rm max}\,S.)$2 Starting from what you had, let$x = km + y$. If$d|m$also divides x, then$d|km+y$. Since it already divides km then it divides x if and only if it divides y. Now let d be GCD(y,m). 9 Consider the ordered pair, such that$\{(x,y)\,|\,x,y\in\{a,b,c,d\}\}$. The following relation satisfies those conditions: $$\{(a,b) ,(b,c), (c,d), (d,a)\}$$ Clearly, this relation is not reflexive since there is no ordered pair with same members i.e.$(x,x)$. This relation is anti-symmetric since for instance, there is no ordered pair$(b,a)$. This ... 1 I think you meant "..., with$(x,y)\in R$and$(y',z)\in R$." but with that correction your reasoning seems fine to me. We have both that$R$is vacuously transitive (because there are no elements$\alpha$such that$(\alpha,\cdot)$and$(\cdot,\alpha)$are in$R$) and that$S$is not transitive for the reason you gave. 1 Consider$A = \{-1,0,1\}$and$R \subseteq A^2$defined as $$R = \{(0,1),(0,-1)\} \cup \Delta_A$$ that is, $$\stackrel{\curvearrowleft}{-1}\ \leftarrow\ \stackrel{\curvearrowleft}0 \ \rightarrow\ \stackrel{\curvearrowleft}1.$$ Of course,$R^\equiv = A^2$, but$R^k = R$and$R^{-k} = R^{-1}$for any$k \in \mathbb{N}$. The problem here is, that$R$and ... 0 The relation will necessarily be reflexive and symmetric (except it doesn't need to be reflexive on elements that are not related to anything). On the other hand, if$R\subseteq A\times A$is a reflexive symmetric relation, you can take$I=R$and$X_i=\{a,b\}$for all$i=(a,b)\in R$. 1 Neither of these is a property of a single object, but rather a relationship between different objects. The first thing is a construction: if you have any associative binary operation$*\colon X^2\to X$on a set$X$, it naturally extends to a$k$-ary operation$*^{(k)}\colon X^k\to X$for any natural$k\geq 1$. But this extension is formally a different ... 0 In the case of an operator, you're looking for associativity. Any binary operator "$*$" that satisfies the associativity law$a*(b*c)=(a*b)*c$, can be treated as a$k$-ary operator for all$k\in \mathbb{N}$and interpreted as applying$k-1$times the corresponding binary relation, keeping the given order of the terms. Matrix multiplication is such an ... 1 You did find$R$correctly, and each of the four lines beginning with$R$is correct. However, I'm not exactly sure what the question is that you are trying to answer; the title of your question made me think you just wanted to know whether or not it was an equivalence relation. If that were so, you only needed to show that it isn't transitive. 2 Hint for an easy way out: Does each ordered set have a greatest element? Edit: Sorry, I did misread part (c) of the definition. There's a related tactic that will work, though. The ordered set$(\mathbb Z, \prec)$has two elements without immediate predecessors:$0$and$-1$. The ordered set$(\mathbb N, \leq)$has only one such element. 0 Let$R$be a relation on$A$such that it's both symmetric and anti-symmetric. Let$(x,y)\in R$. Then by symmetry,$(y,x)\in R$and by anti-symmetry,$x=y$. 0 The curly braces denote sets, so the order does not matter, ie.$\{b,c\}=\{c,b\}$. There is a difference between an equivalence relation and the equivalence classes. The relation is an ordered pair$(a,b)$, which means that$a$and$b$are equivalent. The equivalence class is the set of all equivalent elements, so in your example, you have ... 1 For transitivity, we need to prove that$\;(aRb$and$bRc) \implies a R c$. Hint: $$\text{Let}\;\; a = 1, b = 3, c = 5$$ So$a R b$because$|a - b| \leq 2$, and$b R c$because$|b - c| \leq 2$. But what about$|a - c|$? If$|a-c| \not\leq 2$(i.e., if$|a - c| \gt 2),\;$then$\;\require{cancel} a \, \cancel{R}\, c$. 0 You can also think of it as a matrix of$nxn$, with the elements of the matrix being$(a_i,a_j)$with$ a_i,a_j \in A$. The elements of the main diagonal have to be included in R because R is reflexive. For the remaining$n^2-n$, picking a pair from the upper triangle say$(a_2,a_1)$implies that you are also picking$(a_1,a_2)$. So in reality you only have ... 0 Suppose that you've enumerated the elements of your finite set: $$A = \{a_1, \ldots, a_d\}.$$ Then, the zero-one matrix$M = (m_{ij})$, representing the relation$R$has entries $$m_{i,j} = \begin{cases} 1, &(a_i, a_j) \in R \\ 0, &(a_i, a_j) \notin R. \end{cases}$$ Now,$R$is transitive means that whenever$(a_i, a_j) \in R$and$(a_j, a_k) \in ...

0

2

Whether the empty relation is reflexive or not depends on the set on which you are defining this relation -- you can define the empty relation on any set $X$. The statement "$R$ is reflexive" says: for each $x\in X$, we have $(x,x)\in R$. This is vacuously true if $X=\emptyset$, and it is false if $X$ is nonempty. The statement "$R$ is symmetric" says: if ...

0

The basic fact here is that an implication "if $P$ then $Q$" is false in one case only: that where $P$ is true and $Q$ is false. For example, to show that the statement $$\hbox{"if x is a bird then x can fly"}$$ is not always true, you have to give an example of something which is a bird but cannot fly. The statement that $R$ is transitive is that for ...

-1

A relation, $R$, is symmetric when for all $x,y$, if $(x,y)\in R$ then $(y,x)\in R$. But here, since $R$ is empty, it has no elements $(x,y)$, so the hypothesis is empty. But the conclusion of an implication is true even with an empty hypothesis. So, $R$ is symmetric. Same goes for transitivity. But it is not reflexive, because $(x,x)\notin R, \forall x$, ...

0

For a particular j, Aj is just the projection of f(ij x J) back on I. Every element of I must appear in some Aj because f is a bijection: if ik is not in any Aj then ik x J cannot appear in the mapping by f from I x J to I x J. So you can choose (without AofC because the sets are finite) a sequence of elements from I such that each belongs to the ...

0

$x$ can only assume the values 5, 4, 3, 2, 1, and 0 (if you consider 0 to be a natural number). Thus $\def\p#1{\langle {#1},{#1}\rangle}\alpha = \{ \p5, \p4, \p3, \p2, \p1, \p0\}$. This is an equivalence relation.

-1

TYPES OF RELATION In mathematics we have three types of relation those are: Reflexive This is the relation type by which an elements of a set are mapped to itself, that is $aEa$ then $aRa$. Symmetric This is the relation whereby $(a,b)Ea$ that is $aRb$ implies $bRa$. Transitive This is the relation whereby $aRb$ and $bRc$ which implies ...

1

In terms of recurrence relations, homogenous relates to linear recurrences. In the Fibonacci example, $F_{n+2}=F_{n+1}+F_n$ is homogeneous since it is linear in the sequence elements without further constants. Scaling the sequence gives another solution. Homogenous linear recurrences with constant coefficients can be solved with an exponential or geometric ...

0

That equation could be made to have homogeneous ("the same") degree by introducing a new variable, say $r^2 - rs - s^2 = 0$. This sort of thing is typical in studying curves in projective geometry.

2

Not only an equivalence relation on a non-empty set $A$ defines a partition of $A$ in equivalence classes, the reverse is also true: every partition of $A$ corresponds to an equivalence relation. Hence the partition which arises from the singletons of $A$ corresponds to an equivalence relation $R_{\text{singleton}}$. The usual name for ...

0

There's no trick here, the $=$ is literal identity. Note that the antecedent of the antisymmetry condition does not say that $a,b$ are distinct. For any element reflexively related by $R$, e.g. $aRa$, that element is trivially related symmetrically to itself. Antisymmetry says that the reflexively related elements are the only symmetrically related elements. ...

0

Perhaps it will make more sense to you if we replace $a = b$ with "it is not the case that $a$ and $b$ are distinct." Afterall, we define two elements as being distinct by asserting $a \neq b$. The negation of $a\neq b$ is the negation of "a and b are distinct" which is thus $\lnot (a \neq b), \text{ i.e., } a = b$. In short, you can think of asymmetry as ...

1

In the language of mathematics, $=$ is the "equality" relation. Two things are equal if and only if they are the same thing, in which case we write it as $a=b$. How can two things be the same? Well, one can perhaps define something in two ways, and then we argue that the two definitions give rise to the same object. For example $A$ is $1+1$ and $B$ is ...

2

Transitivity means if $x R y$ and $y R z$, then $x R z$. Since $\text{dom}(R) \cap \text{rang}(R) = \emptyset$, there are no $x,y,z$ such that $x R y$ and $y R z$ since otherwise $y \in \text{dom}(R) \cap \text{rang}(R)$. So the statement of transitivity is vacuously true.

1

It is equivalent to asking in how many ways can you partition the set! The answer is just the 4th Bell number: $$B_4=15$$ Calulated pretty easily from the case of a $0,1,2,3$ element sets (Which you can solve in your head to be $1,1,2,5$) using the recurrence relation: B_4 = \sum_{k=0}^3 \binom{3}{k} B_k = \binom{3}{0} \cdot 1 + \binom{3}{1} \cdot 1 + ...

8

An equivalence relation divides the underlying set into equivalence classes. The equivalence classes determine the relation, and the relation determines the equivalence classes. It will probably be easier to count in how many ways we can divide our set into equivalence classes. We can do it by cases: (1) Everybody is in the same equivalence class. (2) ...

Top 50 recent answers are included