# Tag Info

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

Only top voted, non community-wiki answers of a minimum length are eligible