Tag Info

New answers tagged

2

Since nobody decided to give a formal answer, I will try to give mine according to your comments. There's no equinumerous function or bijective set. There are equinumerous sets and bijective functions. Equinumerous sets are sets for which at least a bijection (bijective function) exists. Set A and B are equinumerous, if there exists a one-to-one and onto ...


7

Reflexive means that for every $t$, $(t,t)$ is in the relation. The relation $x=1$ is not reflexive as $(2,2)$ is not in the relation.


2

If $\lvert A \rvert < \lvert B \rvert$, then you cannot have any surjective function $f\colon A\to B$ anyway, and the question is vacuous. (the image $f(A)$ of $A$ by any function $f$ must satisfy $\lvert f(A) \rvert \leq \lvert A \rvert$, with equality when $f$ is injective).


2

Hint: Think every relation as a binary square matrix of size 4 whose rows and columns are marked with characters $a,b,c,d$. If $a$-th row and $c$-th column is marked 1 then $(a,b) \in R$ otherwise not. Try to observe the properties of such a matrix if $R$ is reflexive, symmetric or antisymmetric .


1

A relation $R$ can be both symmetric and antisymmetric. For any such relation, suppose $a R b$. Then by symmetry, $bRa$. By antisymmetry, since $a R b$ and $b R a$, then $ a = b$. Hence, for any such relation, it must be that $ a R b \implies a = b$. You can check that any relation which satisfies $a R b \implies a = b$ is both symmetric and antisymmetric, ...


1

$R\subset A\times B$. Let $A=\{a_1,a_2,...,a_m\}$ and $B=\{b_1,b_2,...,b_n\}$. Recall that $A\times B=\{(a_i,b_j):1\leq i\leq m, 1\leq j\leq n\}$ so $|A\times B|=mn$. Also we have $|2^{A\times B}|=2^{mn}$ Since $R\in 2^{A\times B}$ then there are $2^{mn}$ relations.


0

If we are to define the Cartesian product of two sets $A$ and $S$ as $\{(a,s):a \in A$ and $s \in S\}$, then in general there is no set $A$ such that $A$ $\times$ $S = S$. If $A$ is empty, then $A$ $\times$ $S$ is empty: see here. If $A$ is non-empty then $A$ $\times$ $S$ cannot be equal to $S$ in general (which requires $A$ $\times$ $S$ $\subseteq$ $S$ and ...


1

To show that $ \mathcal{R}_1$ is a functional relation, we could proceed as follows. \begin{eqnarray*} x_1 \in X &\implies& (x_1, x_1) \in \Delta_X \\ &\implies& (x_1, x_1) \in \mathcal{R}_2 \circ \mathcal{R}_1 \end{eqnarray*} It follows from the earlier stated definition of $ \mathcal{R}_2 \circ \mathcal{R}_1$ and the ...


2

You should prove two statements: 1) If $A$ has $m$ elements and $B$ has $n$ elements, then $A \times B$ has $mn$ elements. 2) If $C$ is a set of $k$ elements, then the power set $P(C)$ has $2^k$ elements. Regarding 2): Let $C = \{c_1,\ldots,c_k\}$ and consider the mapping $$f : P(C) \to \{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\}$$ defined in the ...


0

In this case it's not $a=b, b=c$ then $a=c$. That is the statement of transitivity for $=$. But you need to show not that $=$, but that $\sim$ is transitive. So you need to show that if $(a_L, a_R)\sim (b_L, b_R)$ and $(b_L, b_R) \sim (c_L, c_R)$, then $(a_L, a_R)\sim(c_L, c_R)$. Using the definition of $\sim$, You can translate the conditions $(a_L, ...


1

$\leq %Lorem ipsum dolor sit amet$


0

Consider matrix which has ones on diagonal and zeros on other places. Symmetric property: $\forall a,b\in X$ $aRb\implies bRa$. Antisymmetric property: $\forall a,b\in X$ ($aRb \land bRa)\implies a=b$. So consider relation $R=\{(x_1,x_1),(x_2,x_2)...(x_n,x_n)\}$ s.t. $x_i\in X$ As you see both properties are hold, so we get matrix - $a_{ij}=1$ for $i=j$ and ...


0

You can't get from $5$ to $1$ in any number of steps as it is now - adding $(5,1)$ doesn't actually help transitivity. If you wanted transitivity, you'd need $(x,5)$ for all $x$, since everything has a path to $5$, along with $(y,4)$ for $y=1,2,3$, since each of those has a path to $4$, and you'd also need $(2,1)$ and $(3,2)$, since there are paths between ...


-1

Yes, that is correct. Note that $f(n)=f(m)$ means $2n=2m$, hence $2\cdot(n-m)=0$. A product is zero only if one of the factors is zero, which implies $n=m$ here. We conclude that $f$ is injective. (Of course, $f$ is not onto as $2n\ne 1$ for all $n$).


1

You are correct! You should probably justify your claim, though, perhaps by showing that the relation $S$ (as you have defined it) contains and is contained by the transitive closure of $R.$


3

This is what you need to show: reflexive: $(x,x)\in S$; so $x-x \in \mathbb{Q}$, for all $x \in \mathbb{R}$. symmetric: if $(x,y)\in S$, then $(y,x)\in S$, so if $x-y \in \mathbb{Q}$, then $y-x \in \mathbb{Q}$, for all $x, y \in \mathbb{R}$. transitive if $(x,y), (y,z)\in S$, then $(x,z)\in S$; so if $x-y, y-z \in \mathbb{Q}$, then $x - z \in ...


3

The way to prove these things, in general, is to work on each of the three parts separately: show that the relation is reflexive, symmetric, and transitive. For each of these, write what you want to show explicitly, and then follow the general method for showing that kind of statement. For example, for symmetry in this relation, you want to prove that if ...


0

Taking the reflexive closure, we are only adding points (from the diagonal) that cannot be a counterexample to symmetry..


0

Consider $(x,y)\in S$. You need to show that $(y,x) \in S$. Case $x=y$. Trivial. Case $x \neq y$. Then we observe $(x,y) \in R$ and finish the proof based on the symmetry of $R$.


0

Here is another way, similar to Casteels' (so I copy his notation) but more clear in some ways: $$xRy \iff 3|(5x+7y) \iff 3|(-x+y) \iff 3|(x-y)$$ $$\iff 3|(7x+5y) \iff 3|(5y+7x) \iff yRx$$ And here is yet another way, even closer to Casteels'. $$xRy \iff 3|(5x+7y) \iff 3|2(5x+7y) \iff 3|(10x+14y)$$ $$\iff 3|(7x+5y) \iff 3|(5y+7x) \iff yRx$$


1

I'll leave it to you to justify this carefully: $3|(5x+7y) \iff 3|(2x+y) \iff 3|2(2x+y) \iff 3|(4x+2y) \iff 3|(x+2y)\iff 3|(7x+5y)$


0

Repetition does not matter. we cannot repeat if one relation is already present.in this example (1,2),(2,2),(1,1) is present so it is transitive relation.


1

If $R,S$ are relations, then define $RS$ (or $R \circ S$) as $R \circ S = \{ (x,z) | \exists y \ xRy \text{ and } y S z\}$. Let $R^k$ be the composition of $R$ with itself $k$ times. Then define $R^* = \cup_{k=1}^\infty R^k$. Since $R$ above is finite, then one can explicitly compute $R^*$ in a finite number of steps by a 'fixed point' computation starting ...


2

I think $R'$ is the transitive closure of $R$, to find the closure I recommend you draw the digraph of the relation, that is put point of the plane for each of the vertices and draw an arrow from $a$ to $b$ for each pair $(a,b)$ after this draw an arrow from $c$ to $d$ if you can get from $c$ to $d$ using the current arrows. Stop when you have done this for ...


1

You are misinterpreting the phrase "the number of elements that are in either $A$ or $B$, but not both is even." It does not mean, "one and only one of the sets $A,B$ has an even number of elements". Correctly understood, it means "the set of all elements belonging to one but not both of the sets $A,B$ has an even number of elements"; i.e., "$(A\cup ...


1

The set of elements that are in either $A$ or in $B$ but not both is the symmetric difference $A\setminus B \cup B\setminus A$. The symmetric difference of $A$ and $A$ is empty, and 0 is even!


1

You need to consider the number of elements in the set $(A \cup B) \setminus (A \cap B)$. If $A = B$ the number of elements is zero, which is even.


0

Note that $R^2$ is, at its most basic, a set. Therefore, for instance, $\{(1,1)\}$ is the same as $\{(1,1),(1,1)\}$. By convention, we usually only write elements in a set once, but it doesn't actually matter.


2

In this answer it is assumed that $\langle1,2\rangle\notin R$, $\langle6,1\rangle\notin R$ and $\langle2,4\rangle\notin R$. You might have meant that $\{\langle1,2\rangle,\langle6,1\rangle,\langle2,4\rangle\}\nsubseteq R$. Then things are different. Based on the date we conclude that each of the sets $\{4,6,7\}$ and $\{1,5\}$ must be a subset of an ...


2

Well, you start with the relation defined by $R_1 = \{(6, 4), (4, 7), (3, 3), (5, 1)\}$. Then you need to add exactly those pairs to $R_1$, to become $R$, an equivalence relation, with the stipulation that you cannot add any ordered pair in the relation $\{(1, 2), (6, 1), (2, 4)\}$. Now, if we want our new relation $R$ to be an equivalence relation, it must ...


2

Just play around with some numbers. Consider $3 \in \mathbb N$. What is it related ("equivalent") to? Well $(3, 5) \in R$, since $2 \mid 8$. But $(3,6) \notin R$, since $2 \not\mid 9$. Continuing, we notice that: $$ 2 \mid (a + b) \iff a + b \text{ is even} \iff a \text{ and } b \text{ have the same parity} $$ where by "parity", I mean whether a natural ...


0

Hint:Take the number $1$ to be $a$, what kind numbers are related to $1$ in $R$? Then take $2$, and so on you will get the classes very fast.


0

Symmetric: Let $(x,y)\in R_1\cup R_2$. Then $(x,y)\in R_1$ or $(x,y)\in R_2$. WLOG, suppose $(x,y)\in R_1$. Now, $R_1$ is symmetric so $(y,x)\in R_1$. Therefore, $(y,x)\in R_1\cup R_2$, so $R_1\cup R_2$ is symmetric. Transitive: (disprove by counter-example) Let set $A=\{1,2,3\}$ and relations on $A$, \begin{eqnarray*} R_1 &=& ...


1

Some nice people have tried answering my question, and now I've totally understood the concept. However, I recently came across a wonderful explanation to this topic, which I think will help the new comers having the same question. This explanation is from the book "Discrete mathematics and its applications" by Kenneth H. Rosen, pg 597, 598: A computer ...


0

If you have a relation $R$, its transitive closure $R^+$ is the smallest transitive relation such that $R \subseteq R^+$. If $R$ is already transitive, then $R = R^+$. So a transitive closure is also a relation, and it is the relation that is obtained by expanding the original relation in such a way as to make it transitive. The same idea applies to ...


0

By definition, $R$ and $S$ are subsets of $A\times A$. Since both relations are reflexive, every pair $(x,x)\in A$ is also in $R$ and $S$. The subtraction of relations comes down to the subtraction of subsets of $A$: $$R\setminus S = \{(x,y)\in A\times A \mid (x,y)\in R , (x,y)\not\in S\}$$ This is also a subset of $A\times A$, and thus defines a relation ...


0

Hint: Since $R$ and $S$ are reflexive, we know that given any $a \in A$, we have that $(a,a) \in R$ and $(a,a) \in S$. The set difference $B - C$ is defined to be: $$ B - C = \{b \in B \mid b \notin C\} $$ So for example: $$ \{(1, 2), (3, 4), (2, 5)\} - \{(2, 3), (4, 3), (2, 5)\} = \{(1, 2), (3, 4)\} $$ To get things started, consider a proof by ...


0

Assume that the relations $R,S$ on a set $A$ are both reflexive, i.e. : for all $x \in A$, $(x,x) \in R$ and $(x,x) \in S$. The relation $R-S$ on $A$ is the set $\{ (x,y) | x,y \in A \land (x,y) \in R \land (x,y) \notin S \}$ i.e. we have to start from $R$ and "throw away" from it all couples belonging to $S$. Due to the fact that both $R,S$ are ...


0

If $R$ is an equivalence relation on the set $A$, the equivalence class of the element $a \in A$ is ${[a]}_{R} = \{s \, | \, a R s\}$. The set $A$ here is the set of all bit-strings of length $\geq 2$. We can take $00$, $01$, $10$, and $11$ as representatives (why?), giving us the following equivalence classes: $$ \begin{gather*} {[00]}_{R} = \text{the set ...


0

Each element $a \in A$ is in a unique part in $P$; let's call it $X_a$. So, if $x$ and $y$ are both in a part $X$, and $y$ and $z$ are both in a part $Z$, then $X$ and $Z$ are both equal to $X_y$. So, $x$ and $z$ are both in $X_y$, so $x \mathrel{R} z$. As far as $P$ being the set of equivalence classes: it's pretty much the definition. The equivalence ...


0

Suppose $3\mid 2x+y$ and $3\mid 2y+z$; then $$ 3\mid (2x+y)+(2y+z) $$ or $$ 3\mid (2x+z)+3y. $$ Since $3\mid 3y$, you conclude that $3\mid 2x+z$. Note that this is congruence modulo $3$ in disguise: saying $3\mid 2x+y$ is equivalent to saying that $3\mid 2x+y-3x$, that is, $3\mid y-x$.


0

If $3 \mod c = 0$ for some $c$, then $c$ must be a factor of 3. So, if $x$R$y$, then either $2x + y = 1$ or $2x + y = 3$. The only two cases are $x = y = 1$ and $x = 0, y = 1$. So if $x$R$y$ and $y$R$z$, then $x$R$z$, because it must be that $z = 1$ and we know $x = 0$ or $x = 1$.


1

$$ \begin{array}{c|c|c|c} R & 1 & 2 & 3 \\ \hline 1 & f & t\, & t \\ \hline 2 & f & f & t \\ \hline 3 & f & f & f \end{array} \circ \begin{array}{c|c|c|c} R & 1 & 2 & 3 \\ \hline 1 & f & t & t \\ \hline 2 & f & f & t \\ \hline 3 & f & f & f \end{array} = ...


2

If $R$ is a symmetric relation on a set $S$, then what you've shown so far is that $(a,a) \in R^2$ for all $a \in S$. What you have not yet shown is that if $(a,b) \in R^2$ then $(b,a) \in R^2$. Hint: if $(a,b) \in R^2$, then there is a $c \in S$ such that $(a,c)$ and $(c,b) \in R$.


3

By definition $aR^2b$ iff there exists a $c$ such that $aRc$ and $cRb$. So you can check all $3^2$ possibilities $aR^2b$: is $1R^21$? $1R^22$? $1R^23$? $2R^21$? ... For example, is $1R^21$? Well, there is no $(c,1)$ in $R$ so there can be no $c$ such that $(1,c)$ and $(c,1)$ are members of $R$. That is, there is no $c$ such that $1Rc$ and $cR1$. ...


1

Well, 0 is even so $(A,A)\in R$ - that's reflexivity. If $(A,B)$ and $(B,A)$ are in $R$, then $A\subseteq B\subseteq A$ implies $A = B$ - that's antisymmetry. And if $(A,B)$ and $(B,C)$ are in $R$, then $A\subseteq B\subseteq C$ implies $A\subseteq C$. Now, $|C|-|A| = |C|-|B|+|B|-|A|$ is a sum of two even numbers, hence even, so $(A,C) \in R$ - that's ...


1

You are correct that we need to add $(a, d), (b, c)$. And yes, for the reason you give, for the relation to be transitive requires that since $(c, d), (d, c) \in R$, we also need to add $(c, c)$ and $(d,d)$.


0

here are some hints. First of all think about an equivalence relationship as a way to do a partition in a set (call it $A$). For a partition you can think about a sequence $\{A_i\}_i$ such that $A_i\cap A_j=\emptyset$ and $\cup A_i=A$. Do you see how a partition is related with an equivalence relation? If you do: Now express a relation $a\equiv b$ as ...


0

I would guess $i_{A}$ is the identity function: $i : A \to A$ where $i(a) = a$ for every $a \in A$. So an equivalence relation partitions elements up into equivalence classes. That is $i, j$ are in the same equivalence class if and only if $iRj$. In order for $R$ to be a function, it has to map each $a \in A$ to a unique $b \in A$. So if an equivalence ...


0

No there is no such thing as anti-transitive. You might define it as xRy∧yRz⇒¬xRz, but it wouldn't be a very interesting property. The negation of transitive xRy∧yRz⇏xRz, which just says the relation is not transitive, would be even less interesting. Note that for instance anti-symmetric is not the negation of symmetric either (By Marc van Leeuwen)



Top 50 recent answers are included