Hot answers tagged

6

You could draw the relations on a piece of paper to make it clearer: R $$ 1\to 2\to 3\to 4\to 5 $$ and S $$ \begin{array}{cc} &&3\\ &\nearrow&\\ 2&&\downarrow\\ &\searrow&\\ &&4 \end{array} $$ and then squaring them means to form every relation that can be achieved by two consecutive arrows, so $$ ...


4

If you have an irreflexive relation $S$ on a set $X\neq\emptyset$ then $(x,x)\not\in S\ \forall x\in X $ If you have an reflexive relation $T$ on a set $X\neq\emptyset$ then $(x,x)\in T\ \forall x\in X $ We can't have two properties being applied to the same (non-trivial) set that simultaneously qualify $(x,x)$ being and not being in the relation. ...


3

$(2^n)(2^{\frac{n(n-1)}{2}})=2^{\frac{n(n+1)}{2}}$ (exponents add when you multiply) is the number of symmetric relations that are not necessarily reflexive. The $2^n$ factor disappears when we impose reflexivity because it counts the number of ways to choose a set of pairs of the form $(a,a)$, of which there are $n$.


3

Let's say $(a, b) \in \Bbb{N} \times \Bbb{N}$. We want to find the set of all $(c, d) \in \Bbb{N} \times \Bbb{N}$ such that $a-d=c-b$. This equation can be rearranged to say $a+b=c+d$. Thus, the equivalence class of $(a, b)$ is the following: $$\{(c, d) \in \Bbb{N} \times \Bbb{N} \mid a+b=c+d\}.$$ For any constant $n \in \mathbb N$, there are precisely $n$ ...


2

Consider: if $h$ is bijective, then it has an inverse, namely $h^{-1}$. How can you apply that to $f\circ h=g$? For transitivity, just remember what your proof should like: assume that you have some bijections $j$ and $k$ such that $f\circ j=g$, and $g\circ k=h$. You want some function $l$ such that $f\circ l=h$. Can you see how putting the previous two ...


2

Here, the inverse function exists : $$g(x)=2n$$ for $n>0$ and $$g(x)=-2n+1$$ for $n\le 0$ $f$ is actually a function from $\mathbb Z^+$ to $\mathbb Z$


2

$X\times Y$ is the set of ordered pairs $(x,y)$ where $x\in X$ and $y\in Y$. So in this case, $$A\times A=\{(a,b)\;\colon\;a\in A, b\in A\}.$$ In the example you gave, $A\times A=\{(1,1),(1,2),(2,1),(2,2)\}$. Notice that ordered pairs are distinct from unordered pairs, so while (as you say) the unordered pairs are equal $\{1,2\}=\{2,1\}$, the ordered pairs ...


2

Here's another way to think of it: A relation on a set $\{a_1,\dots,a_n\}$ can be represented by an $n\times n$ matrix of $0$s and $1$s, with a $1$ in the $ij$ position if $a_i$ is related to $a_j$. For a symmetric and reflexive relation, we can choose the entries above the main diagonal freely, and then this will determine the entries below the diagonal ...


1

$R\circ R$ is a relation such that if $R(x,y)$ and $R(y,z)$, then $R\circ R(x,z)$. In general, if $R_1$ and $R_2$ are relations on $A$, and $R_1(x,y)$ and $R_2(y,z)$, then $R_2R_1(x,z)$ (note the order of composition; we apply $R_1$ first, then $R_2$). So say $R$ is transitive, $R\circ R(x,y)$ and $R\circ R(y,z)$. You want to show that $R\circ R(x,z)$. To ...


1

Suppose that $R$ is transitive, and suppose that $(x,y),(y,z)\in R^2$. We want to show that $(x,z)\in R^2$. By definition, if $(x,y)\in R^2$ then there is an element $u$ "connecting $x$ with $y$, that is, such that $xRu$ and $uRy$. Since $R$ is transitive, this implies $xRy$. Using a similar argument we can show that $yRz$. So, since there is an element ...


1

It looks like you misread slightly: partial orders and equivalence relations are both reflexive and transitive, but only equivalence relations are symmetric, while partial orders are antisymmetric. A relation $R$ is symmetric if $aRb$ implies $bRa$, while a relation $R$ is antisymmetric if $aRb$ and $bRA$ implies $a=b$. For example, the relation "has the ...


1

R = {(a,c), (c,a), (a,d), (d,a), (d,c), (c,d), (a,a), (c,c), (d,d), (b,b)} Hope that helps. Note: The claim that R should be a subset of {a,b,c,d}x{0,1} is incorrect.


1

To answer Muno's question, $R$ on $S$ is not transitive: $x=z=1$ and $y=3$ is a counterexample (any $y$ other than $1$ will do). $x+y=y+z>3$ but $x+z<3$. silvascientist: $R$ satisfies Drittengleichheit if the implication is true; it is vacuously true if $xRz$ and $yRz$ is false. This does not mean that $xRy$ is true (similarly $xRy$ and $xRy$ false ...


1

Honestly, I think that the best way to approach this as a beginning math student is just to try to parse through a few examples. If you find a counterexample, you're done, otherwise, after a few tries, see if you can see why it would be true. Try it out with $R$: Reflexivity: $\forall X\in P(\mathbb{N}), R(X,X)$. Note that $A\cup A=A$, so $R(A,A)$ iff ...


1

Work it out by the definitions. Reflexivity: means x R x for all x. So: $ARB \iff |A\cup B| \ge 2$. Does $|A \cup A| \ge 2$ for all subsets of the natural numbers? Well... $|A \cup A| = |A|$. Do all subsets have cardinality $\ge 2$? Obviously not as, say {0} or {1} or {k} have cardinality of 1 (not to mention $|\emptyset| = 0$). So R is not ...


1

Assume that $B\subseteq C$. You want to prove that $A\times B\subseteq A\times C$, so take an element $(a,b)\in A\times B$. Since $B\subseteq C$, and since $b\in B$, we have $b\in C$. Thus $(a,b)\in A\times C$, which proves that whenever $(a,b)\in A\times B$, then also $(a,b)\in A\times C$.


1

You seem to be fundamentally misunderstanding something here. Given a set $S$, a relation $R$ is simply defined as some subset of $S^2$, that is, where $$R=\{\langle s_1, s_2\rangle\in R: s_1\in S, s_2\in S\}$$ $R$ is by definition a relation. The domain of $R$ (admittedly this isn't a term I haven't heard or seen before, but from intuition and Google this ...


1

You have done most of the work, you just need to prove transitivity. If $a R b$ and $b R c$, $\frac{a}{b}=2^{m_1}$ and $\frac{b}{c}=2^{m_2}$, multiply them together, you have $$\frac{a}{c}=2^{m_1+m_2}$$ Since $m_1+m_2 \in \mathbb{Z}$, $\frac{a}{c} \in H$, i.e. $a Rc$.


1

Basically, to prove a relation $R$ is reflexive on a set $S$, we need to prove $(s, s) \in R$ for all $s \in S$. Since we already know this is true for $R_1$ and $R_2$, it becomes very easy to prove this for their intersection and union. Given an element $s \in S$, we know that $(s, s) \in R_1$ and $(s, s) \in R_2$ because $R_1, R_2$ are reflexive. Since ...


1

Your proof is right. I would clarify the steps in the transitivity part by saying something like this: Assume $aRb$ and $bRc$. Now $2a+2b\equiv 0 \mod 4$ and $2b+2c\equiv 0 \mod 4$, which means $2a+2b=4m$ and $2b+2c=4n$ for some integers $m$ and $n$. Now by adding the two equations together we have $2a+2b+2b+2c=4m+4n$, i.e. $2a+2c=4(m+n-b)$, and thus ...


1

It depends on the context. If there is no ambiguity, "less than or equal to" works. In a lecture, you might pronounce it "curly less than" to help people who are taking notes. If you want a short way to pronounce it, you might vocally label it "r" or "rel" (short for "relation"), as in "Suppose that rel is a partial order", but this is less standard and I ...


1

It’s straightforward to show that any pair $\langle A,B\rangle$ that satisfies your condition belongs to $R^+$, since it must belong to any reflexive, transitive relation containing $R$. On the other hand, it’s also easy to check that that the set of all pairs satisfying your condition is a reflexive, transitive relation containing $R$ and hence contains ...


1

Are you sure your not mixing together a signature and a structure? A signature doesn't specify the domain. The whole point of a mathematical theory is that you can interpret it in any domain that can provide the structures and satisfy the constraints specified in the signature. As such, no, you can't use elements of the "domain", because you don't know ...


1

The relation is not reflexive because $(1,1)$ is not in $R$ because $3$ is not a divisor of $2$. It would have been a reflexive relation if $\forall a,(a,a) \in R$, so you counter examples are false. Your counter example for transitivity is true. Note: To prove something is false you only need one counter example. It is indeed symetric. A more formal way ...


1

$f$ acts on $\mathbb{N}\setminus\{0\}$ as follows: $$ f(n) = \left\{\begin{array}{rcl}\frac{n}{2} &\text{if}& n\equiv 0\pmod{2}\\-\frac{n-1}{2}&\text{if}&n\equiv 1\pmod{2} \end{array}\right.$$ hence $f^{-1}$ maps positive integers into even numbers and non-positive integers into odd numbers: $$ f^{-1}(m) = \left\{\begin{array}{rcl}2m ...


1

You’re not looking for subsets of $S$ at all: you’re looking for elements of $S\times S$, the set being ordered lexicographically. I’ll do (a) completely; then you can use that as a model to try (b). I’ll write $\prec$ for the lexicographic order on $S\times S$: if $\langle a,b\rangle,\langle c,d\rangle\in S\times S$, $\langle a,b\rangle\prec\langle ...


1

The notation of $f(S)$, where $f:X \rightarrow Y$ is a function and $S \subset X$ is a set, means "the set of elements you get when you apply the function $f$ to the elements of $S$". For example, if $f:\mathbb{R} \rightarrow \mathbb{R}^+$ where $f(x) = x^2$, and if $S = (-2, 2)$, then $f(S) = [0, 4)$ because if you apply $f$ to all the elements of $S$ ...


1

This answer starts where you stopped. We focus on the $4$ sets $[1],[0],[4],[9]$. Any equivalence relation with the mentioned properties will induce a partition such that each of its elements is a non-empty union of these sets. We have $[1]\cup[0]\cup[4]\cup[9]=\mathbb N$, but what can be said about mutually disjointness? On this the third property applies ...


1

I don't know how to give a hint to number 1 without giving it away. I'd suggest just trying natural language relationships. Example a R b if b is the mother of a, but is it reflexive? Is a R a? Is a always the mother of a? Of course not. How about if a R b if a and b have the same parents. Is it reflexive? Does a have the same parents as him/herself. ...


1

Maybe a straightforward proof may help you with this. $b)$ Reflexive: Let $x \in \mathbb{R}$. Then $x-x=0 \in \mathbb{Q}$ Transitive: Let $x,y,z \in \mathbb{R}$ with $x-y \in \mathbb{Q}$ and $y-z \in \mathbb{Q}$. Then $x-z = (x-y) + (y-z) \in \mathbb{Q}$. Symmetric: Let $x,y \in \mathbb{R}$ with $x-y \in \mathbb{Q}$. Then $y-x = -(x-y) \in \mathbb{Q}$ ...



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