# Tag Info

4

It's in order to maintain consistency with function composition and application. For functions $g=S, f=R$, the notation for composition of relations $S, R$ should be the same as that of composition of $g,f$: $(g\circ f)(x) = g(f(x))$. If composition were defined so that the first function $f$ applied (or relation $R$) appears "leftmost", then we would want ...

4

Because of $R$, we must have $1=2=4=5=6$, $7=8$, and $3=3$. So there are at most three equivalence classes. You can also combine them in various ways, e.g. $1=2=4=5=6$ and $3=7=8$.

3

Note that if $x=0$ then, as we're given $y=7x$, so we get $$y=7\times 0=0$$ Therefore we have an initial point on the plane: $A=(0,0)$. The same story can be done for $x=15$ to find another point which is $B=(15,7\times 15)=(15,105)$. Now draw the line $y=7x$ first and then bold the line between $A$ and $B$.

3

No, the number of equivalence classes is finite, because there are only finitely many propositional variables, namely $p,q,r$. Any propositional formula in $P$ represents (or induces) a truth function — a function from $n$ tuples of truth values to truth values. The truth table of a formula defines this truth function. The formulas of $P$ define 3-ary truth ...

2

Hint: in this example, you can test to see if two propositions are equivalent by computing their truth tables. If the final answers are identical (intermediate working being irrelevant), then they are equivalent; if the final answers are different, they are not. So the question is in effect the same as asking: how many possible final answers are there for ...

2

Let $d(n)$ be the number of digits of a positive integer $n$. Then $$d(n)= 1+ \lfloor \log_{10}(n) \rfloor$$ This uses the floor function and the base 10 logarithm. The slow growth rate you mentioned is because of the fact that logarithms, which are the inverse of exponents, grow very slowly. You should read that article on logarithms - they are extremely ...

2

It is only a preorder. If $u$ is any non-trivial unit, and $x$ is any non-zero element, then $x|ux|x$, but $x \neq ux$.

2

A relation $R$ is said to be transitive if for all $a,b,c$ in its domain, $aRb$ and $bRc \Rightarrow aRc$ In your case, the relation would be transitive if, for all $x,y,z \in \mathbb N$, $x+y=10$ and $y+z=10$ implied $x+z=10$, which is clearly not the case.

2

Learn by playing with it. Take a piece of paper and start drawing! Put a $1$ at the bottom and just start drawing arrows. You put an arrow whenever one number evenly divides into another, for example$$1\rightarrow 2\rightarrow 4 \rightarrow 8 \rightarrow 16$$ should be in your drawing. If you manage to draw all the possible arrows you have completely ...

1

Why would, for example $(1,3)$ need to be in the relation? The definition is: $R$ is symmetric if (and only if) it holds for all $a$ and $b$ that if $(a,b)\in R$ then $(b,a)\in R$ which we can unfold to $R$ is symmetric if (and only if) all of the following are true: If $(1,1)\in R$ then $(1,1)\in R$ If $(1,2)\in R$ then $(2,1)\in R$ ...

1

Let us consider induction on $n$ of a slightly stronger statement. If $R$ is a transitive binary relation that contains a cycle of length $n$, then $xRy$ for any $x$ and $y$ in the cycle. In this case we will say $R$ is full with respect to the cycle. Base case $n=1$ and $n=2$ are trivial. Inductive step. Assume that whenever there is a cycle of length ...

1

Your proofs for reflexivity and stymmetry are somewhat correct. I say "somewhat" because you mean to say the right thing, but I'm inclined to say you natation is incorrect. More on the notation at the end of this answer. To prove transitivity need to do something like this: $$(x,y)\in \rho\wedge(y,z)\in\rho\implies x-y=3k_1\wedge y-z=3k_2\implies ... 1 In general, let a and b be integers and m a positive integer. Then,$$R:=\big\{(x,y)\in\mathbb{Z}\times\mathbb{Z}\,|\,ax+by\text{ is divisible by }m\big\} is an equivalence relation on $\mathbb{Z}$ if and only if $m$ divides $a+b$. Furthermore, if $m$ divides $a+b$, then the set of equivalence classes of $\mathbb{Z}$ under $R$ is precisely ...

1

$x\cap B$ is a subset of $B$ and $B$ has $8$ subsets. For each of these subsets there is one equivalence class. So the required number is $8$.

1

If $f:\{2,3\}\to \{2,3\}$ is a function then $f(2)$ can equal $2$ or $3.$ For each choice of $f(2)$ there are $2$ choices for $f(3).$ Thus $2x2=4$ functions.There are $16$ subsets of $A=\{2,3\}\times \{2,3\}.$ Subsets of $A$ are what binary relations on $\{2,3\}$ are.

1

A relation is simply any declaration that $a R b$. A relationship is a collection of possible relations. They can be as "small" as "no term is related to anything else" or as large as "everything is related to everything else", which is the same as "$2 R 2, 2R3, 3R2, 3R3$. As claiming $a R b$ is really just another way of stating an ordered pair $(a,b)$ ...

1

Your resolution is unclear and incorrect in some places. For reflexivity, that's not what you have to prove (which is also wrong! as, if $x=0.5$ then $x^3\not\ge x$), you have to show that $x^3-x\ge x^3 -x$ which is obviously true (as the expressions are equal). Also, saying "$xRy$ does not equal $yRx$" doesn't make much sense, you should use a word like ...

1

Towards showing that $S/\sigma^*$ is a group: can you show that (the equivalence class corresponding to) $aa^{-1}$ is an identity in $S/\sigma^*$? More precisely: that $baa^{-1}\sigma b$ for any $b$? Towards showing that $\sigma^*$ is the least group congruence: suppose $S/\rho$ is a group. Then show that if $a\sigma b$, the equivalence class corresponding ...

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