New answers tagged

0

Hint: Start by plugging the expression for $f$ into the expression for $g$. That is, simplify the expression $g(ax+b)=1-(ax+b)+(ax+b)^2$. Then set this equal to $16x^2-12x +3$.


0

If $x\sim y$, then by symmetry $y\sim x$ so by transitivity $x\sim x$. Thus an element related to any other element is also related to itself. The set therefore decomposes into two subsets; on one the partial equivalence relation is empty and on the other it is an equivalence relation. Thus the partial equivalence relations on $[n]$ are in bijection with ...


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


0

Assuming that the second f is supposed to be g, notice that functions are also relations. So, f is related to g iff the square $$ \begin{array}{ccc} X & \stackrel{R}{\to} & X' \\ f \downarrow & & \downarrow g \\ Y & \stackrel{S}{\to} & Y' \end{array} $$ commutes.


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

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


0

Your method is fine. You can shorten it by noticing that $$ 2a+2b=4k, $$ for some integer $k$, if and only if $a+b=2k$. This should put you on the track that your relation $R$ is just congruence modulo $2$, so $a\mathrel{R}b$ if and only if $a$ and $b$ are both even or both odd.


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


0

For first part as Noble Mushtak said $R_1 \cap R_2$ is reflexive. Now for second part $R_1 \cup R_2=R_1 or R_2 - (R_1 \cap R_2)$ i.e. that part of $R_1$ and $R_2$ which are only one time in $R_1 \cap R_2$ which are also reflexive as we have seen . That's it


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


0

No, your relation $R$ is not reflexive since $(1, 1)$ and $(2, 2)$ are not included. It is antisymmetric since it has $(1, 2)$ but does not have $(2, 1)$. Any equivalence relation (a relation that is reflexive, symmetric and transitive) will fit the bill. One example is the $=$ relation over, say, $\mathbb{R}$. Let $x, y, z \in \mathbb{R}$. reflexive: ...


1

The relation $R$ is not reflexive: take $A=\{1\}$; then $|A\cap A|=1<2$. The relation $T$ is indeed a partial order, but is not a well-ordering, because, for instance, $\{(1,2),(2,1)\}$ has no minimum. The relation $S$ is indeed an equivalence relation and it is not antisymmetric (the only equivalence relation that is also a partial ordering is the ...


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

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

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


0

From Wikipedia: In mathematics, a well-order (or well-ordering or well-order relation) on a set $S$ is a total order on $S$ with the property that every non-empty subset of $S$ has a least element in this ordering. In particular, a well-order is a total order (which itself is a partial order). But the other implication is not true: for instance, take ...


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.


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


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

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


0

It is equivalent to speak about an equivalence relation $R$ on a set $A$ and a partition of $A$ into its classes of equivalence. Hence there is a natural partition by the preimages $f^{-1}(b)$ for all $b \in B$ (which are either disjoint or identical), in other terms: $$aRa' \Leftrightarrow f(a)=f(a') \Leftrightarrow a \ \text{and} \ a' \ \text{belong to ...


0

$f(a) = f(a) \implies R$ is reflexive, and if $aRb \implies f(a) = f(b) \implies f(b) = f(a) \implies bRa$, hence $R$ is symmetric. And if $aRb, bRc \implies f(a) = f(b), f(b) = f(c) \implies f(a) = f(c) \implies aRc$. Thus $R$ is equivalence relation on $A$. The equivalent classes consist of the $f^{-1}(x)'s $ whereas $x \in $ the range of $f$.


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


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


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

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

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


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


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


0

If you want to find out whether a relation $R$ on a set $A$ is an equivalence relation then it is a handsome strategy to look for a function $f:A\to Y$ such that $aRb\iff f(a)=f(b)$. If you can find one then you are indeed dealing with an equivalence relation. Note that e.g. reflexivity of $R$ follows directly from the evident fact that $f(a)=f(a)$ for ...


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


0

We're "subtracting" as part of the definition of $R_1 \oplus R_2$; the solution is showing how to find $R_1 \oplus R_2$ proceeding from the definition. In this case, $R_1 \cap R_2 = \emptyset$, but that's not true in general. Also, your work is somewhat incorrect: $R_1 \cap R_2 = \{(x, y) \mid x = y\}$, so \begin{align*} R_1 \oplus R_2 &= R_1 \cup R_2 ...


0

You have a most unfortunate typo. Your alleged solution $$ R_1 ⊕ R_2 = R_1 ∪ R_2 − R_1 ∩ R_2 = \{(x, y) \mid x = y\} $$ should, instead, read $$ R_1 ⊕ R_2 = R_1 ∪ R_2 − R_1 ∩ R_2 = \{(x, y) \mid x \neq y\}. $$ The reason is fairly simple: $(x,y)\in R_1\cup R_2$ iff $(x,y)\in R_1$ or $(x,y)\in R_2$; thus, $(x,y)\in R_1\cup R_2$ iff $x<y$ or $x>y$. Note ...


0

Let $B_1 = \{w,x,y\}$ and $B_2 =\{x,y,z\}$. Let $C(B_1)=\{x\}$ and $C(B_2)=\{y\}$. This example satisfies your property (it holds vacuously), but fails WARP.


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


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$


0

1) Observe that $R$ is demanded to be an equivalence relation. That means that it induces a partition on $S$. Working in opposite direction you can also start with some partition on humans (lots of choices) and then define $R$ by stating that $aRb$ if and only if $a$ and $b$ belong to the same component of the partition. Then automatically $R$ is an ...


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


0

A relation $S$ on a set $A$ is a set of ordered pairs. So if $A=\{1,2\}$ then if we define $S$ as a relation on $A$ we have that $S$ is actually a set. So $S$ is any subset of $A\times A=\{(1,2),(2,1),(1,1),(2,2)\}$. As any subset of this set will define a relation then the total number of relations is just the number of elements in the power set, which in ...


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


0

2 and 3 are coprime, i.e. neither 2 divides 3 nor 3 divides 2. Hence with the relation given (x | y) the two numbers are not comparable; therefore the relation can only be a partial order and not a total order, since the necessary condition for a total order does not hold for all possible natural numbers. Note: this answer is an explanation of @almagest's ...


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


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


0

It is transitive, but in a trivial way. One way to think about this is that there is no triplet that contradicts transitivity! Then by the excluded middle property ($P\land\neg P=True$) the relation is transitive. You can also reason like this: Let $aRb$ and $bRc$. The. $a=b=c$, because of the properties of the relation. Then $aRc$.


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


0

HINT: Suppose that $S,R$, and $R\circ S$ are all equivalence relations. By definition $$R\circ S=\left\{\langle x,y\rangle\in X\times X:\exists z\in X\,\big(\langle x,z\rangle\in S\text{ and }\langle z,y\rangle\in R\big)\right\}\;.$$ The first thing that you need to show is that if $E$ is an equivalence relation on $X$ such that $S\subseteq E$ and ...


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


1

First let me correct your terminology: for $n=2$, for instance, what you mean is that there are $6$ ordered pairs that are in the relation $S$ to $(2,2)$. The objects $(1,1),(1,2),(2,1),(2,2),(1,3)$, and $(3,1)$ that you found are ordered pairs, not relations. HINT: For a given $n$ you’re counting the pairs $(a,b)$ such that $a+b\le 2n$. One way to do that ...



Top 50 recent answers are included