Tag Info

New answers tagged

0

If either $A$ or $B$ are empty, then $A\times B=\varnothing$. In that case there is only one relation between the two sets. The empty relation. And there are certainly no proper subsets to $A\times B$.


1

Recall that the definition of a relation $R$ between two sets $A$ and $B$ is a subset $R \subseteq A \times B$ so relations are not always a proper subset of $A \times B$. For example, given $A = \{a,b,c\}$ and $B = \{d,e,f\}$, we have $R = \{(a,d),(a,e),(a,f),(b,d),(b,e),(b,f),(c,d),(c,e),(c,f)\}$ which covers the entire set $A \times B$.


4

It is entirely valid to have a relation that relates every element of $A$ to every element of $B$. It can even have fancy properties -- for example if $B$ is a singleton set, the relation $A\times B$ will be a function!


2

For (b), the first recurrence implies $$ a_{n+2} = 3a_{n+1} + b_{n+1}. $$ Now substitute $a_{n+1} = 3a_n + b_n$ and $b_{n+1} = 5a_n - b_n$ into the right hand side of this equation and regroup to get $$ a_{n+2} = 3(3a_n + b_n) + 5a_n - b_n = 14a_n + 2b_n = 8a_n + 2(3a_n + b_n) = 8a_n + 2a_{n+1}. $$


0

Maybe try this: $$ a_{n+2} = 3a_{n+1}+b_{n+1}=9a_n+3b_n+4a_n-b_n=14a_n+2b_n \\ 2a_{n+1}+8a_n=6a_n+2b_n+8a_n=14a_n+2b_n $$ They are equal.


0

In order for a relation to be transitive, it must be the case that, whenever $(a,b)$ and $(b,c)$ are in the relation, then $(a,c)$ is also in the relation. So, either (1) this is the case for all $a,b,c \in \{1,2,3,4\}$ for your relation, or (2) there exist specific $a$, $b$, and $c$ such that $(a,b)$ and $(b,c)$ are in the relation, but $(a,c)$ is not. ...


3

$(4,1)$ and $(1,2)$ are both in the relation, but $(4,2)$ is not...


3

I assume the undirected edges are meant left-to-right ($\to$). Start with $s_0$ and repeat as many $a$ and $c$ as you want, then transition with $b$: [ac]*b. Then we need a $d$,$a$ and optionally any number of occurrences of $b$,$d$,$a$, i.e. [ac]*bda(bda)* Or shorter [ac]*(bda)+


5

Doesn't $(\mathbb R,<)$ have both of these properties?


1

There was just a question on Hall's theorem. Hall's theorem gives a necessary and sufficient condition for a relation from $A$ to $B$ to restrict to an injective function from $A$ to $B$. The condition is that for all $A' \subset A$, $|n(A')| \geq |A'|$ where $n(A')$ is the set of neighbours of $A'$ in $B$. Naively this would take $2^n$ time to check. This ...


1

The matrix representation of a relation $S$ from a set $X = \{x_1,x_2,\dots\}$ to a set $Y = \{y_1,y_2,\dots\}$ is given by the matrix $M$ where $$M_{i,j} = \begin{cases}1 & \text{if } (x_i,y_j) \in S\\ 0 & \text{if } (x_i,y_j) \notin S\end{cases}$$ Since you have six elements in your set, you will get a $6 \times 6$ matrix. From your diagram, we ...


0

Let $R \subset A \times B$ be our relation. Compute the two cardinalities $$n=\{ a \in A : \exists b \in B : a R b\}$$ $$m=\{ b \in B : \exists a \in A : a R b\}$$ If these two cardinalities are equal to the cardinality of $A$, then $R$ can be restricted to an injective function, otherwise no. EDIT: This is only a necessary condition. See comments below ...


1

Symmetric: $$\forall \langle a,b\rangle \in \Bbb Z^2\; \forall \langle c,d\rangle \in\Bbb Z^2 \;\Big(\langle a,b\rangle \mathsf R\langle c,d\rangle \implies \langle c,d\rangle \mathsf R\langle a,b\rangle \Big)$$ So is it so?: $$\forall \langle a,b\rangle \in \Bbb Z^2\; \forall \langle c,d\rangle \in\Bbb Z^2 \;\Big((a<c\wedge b<d) \implies ...


1

Whatever the set you are provided. If relation on the set is transitive then it must satisfy the condition i.e. if $(a,b)\in R$ and $(b,c) \in R$ then $(a,c)$ does $\forall a,b,c \in S$ You can use definition to prove or disprove a statement given for a Relation. Nothing changes in your reasoning but the elements. Well, it may take enough time to check ...


4

Since $R$ is small, you can actually consider all possibilities for $a,b$, and $c$. However, this is easier if you have a systematic arrangement of the ordered pairs. One way is to represent them by a matrix: $$\begin{array}{c|ccc} &t&u&v&w&x&y&z\\ \hline t&1&&1&&&&1\\ ...


1

Yes, you are right. You need to find three specific elements (we'll call them $a$, $b$, and $c$) such that $(a,b)$ and $(b,c)$ belong to $R$, but $(a,c)$ does not. Here's a hint: suppose $u$ is our $a$, and $x$ is our $b$. $(u,x$) belongs to $R$. Now see if there is some $c$ such that $(x,c)$ belongs to $R$, but $(u,c)$ doesn't.


1

Here $[3,6]$ means the class of $[3,6]$ under the equivalence relation. $$[3,6] = \{(a,b) \in A \times A \mid (a,b)\sim (3,6) \} = \{(a,b) \in A \times A \mid a+6 = b+3 \}.$$ Meaning you have to find all pairs of numbers $(a,b)$ between $1$ and $9$ satisfying $a+6=b+3$. For example, for $a = 1$ we get $b = 4$. If $a = 2$, you get $b = 5$, you get the ...


0

Say we have some equivalence relation $\sim_n$ on a set $Z$. Then if two elements $a,b \in Z$ are related through the relation $\sim_n$, we write $a \sim_n b$. From this, we can talk about the equivalence class of an element $a \in Z$ with respect to the relation $\sim_n$ and we denote this $[a]_n$. An equivalence class is simply all the elements that are ...


0

In general if $(E,\mathcal{R})$ is a set with an equivalence relation the collection of sets $E_x=\{y\in E, x\mathcal{R}y\}$ form a partition of $E$. More specifically $E_x\neq \phi$ and for $x\neq y$ $E_x=E_y$ if $x\mathcal{R} y$ or $E_x\cap E_y=\phi$ otherwise


2

Relations are subsets of products $A\times B$ where $A$ is the domain and $B$ the codomain of the relation. A function $f$ is a relation with a special property: for each $a\in A$ there is a unique $b\in B$ s.t. $\langle a,b\rangle\in f$. This unique $b$ is denoted as $f(a)$ and the 'range' of function $f$ is the set $\{f(a)\mid a\in A\}\subseteq B$. You ...


0

There is no difference. Note, that each function can be seen as a special relation. So $f:A \rightarrow B$ can be seen as a relation $R_f \subseteq A\times B$ such as $$\forall x \in A: \exists ! y \in B: xR_fy$$ The domain and the range is so defined, such that the relation $R_f$ has the same domain and the range as $f$. Note: Here I mean with "range" ...


1

'Well-defined' is a rather foggy concept, and you'll find it used in lots of different ways throughout mathematics. Typically, one makes a definition, and then one sometimes has to check various things hat show that the definition makes sense. For example, it's not unheard of to use well-defined in the following sense: We define a function $f\colon ...


0

Normally well-defined means that if you have choices to make during the evaluation of some function or quantity, it doesn't matter what choices you make you'll end up with the same result. When dealing with equivalence classes this means you have to get the same function value for whatever representative you choose from the equivalence class. For what ...


1

The words "ordered n-tuple" and "n-tuple" are synonym: See the wikipedia article „tuple“ or Wolfram's article.


3

I hope no one minds if I assemble the various comments by Cloudscape and coffeemath (and myself) into an answer. For reflexivity, you want to show that $xSx$, or $x=|x|$ for all $x\in\mathbb{R}$. Clearly this is not true for any negative values of $x$, so $S$ is not reflexive. For symmetry, you want to show that $xSy$ implies $ySx$, or that whenever ...


5

We would like to know how many functions from $\{ 1, 2, 3\}$ to $\{1,2,3\}$ there are for which $f(1)+f(3)\equiv 0 \mod 2$. In other words, we would like to know how many ways we can match the parity of $f(1)$ with $f(3)$. If $f(1) = 1$ then $f(3) = 1$ or $f(3)=3$. If $f(1) = 2$ then $f(3) = 2$. If $f(1) = 3$ then $f(3) = 1$ or $f(3)= 3$. In each of ...


-1

Is this relation transitive?. I don't think so. We have (a,b) and (a,c). To be transitive, (b,c) must be a part of relation too. So, this is not a total order relation because is not transitive.


0

For a relation $R$ to be symmetric, we have to have for all elements in $R$ that if $(x,y) \in R$, then also $(y,x) \in R$. You have found some elements in $R_1$ such that both $(x,y) \in R_1$ and $(y,x) \in R_1$, but for example $(2,4) \in R_1$ but $(4,2) \notin R_1$, hence it it not symmetric because it doesn't satisfy the criterion for every element. ...


1

I preassume that you are dealing with relations on set $\{1,2,3,4\}$. That is not mentioned in your question but is essential information. If it lacks then it can e.g. not be checked wether the relations are reflexive. 1) $R_1$ is not symmetric: $(2,4)\in R_1\wedge (4,2)\notin R_1$ 5) $R_5$ is (also) antisymmetric. What makes you think it is not? Can you ...


0

The book is right. Consider $(2,4)$; what would have to be true if the relation $R_1$ were symmetric? Likewise with $(1,4)$ for $R_6$.


1

Let $a^m = b^n$ and $b^x = c^y$. Then $(a^m)^x = (b^n)^x$ and $(b^x)^n = (c^y)^n$. We have $a^{mx} = b^{nx} = c^{yn} \implies a^{mx} = c^{yn}$


2

In your notation, try $m'' = mm'$ and $n'' = nn'$.


1

An equivalence relation on $A$ starts life as a subset of $A \times A$. If I hand you a subset $S$ from $A \times A$ and tell you it is an equivalence relation, then the symmetric property says that for any $x \in A$ and for any $y \in A$, if $(x,y) \in S$ then $(y,x) \in S$. This does not hold for arbitrary subsets of $A \times A$, but any subset of $A ...


0

Equivalence relation on a subset of the $A\times A$ does not mean it is an element on the set $A \times A$. It is a binary relation between the elements of $A \times A$ satisfying the 3 conditions. For example, if you say "$(x,y) = (y,x)$ for all $(x,y)\in A \times A$" then the relation '$=$' is symmetric.


-1

We want a function that takes us from $(x+3y, 3x+y)$ to $(x,y)$. Let us assume that we can write this as $g(x,y) = (ax+by, cx+dy)$, then $$a(x+3y) + b(3x+y) = x+0y$$ and $$c(x+3y)+d(3x+y) = 0x+y$$ Hence the first equation gives us: $$a+3b = 1 \text{ and } 3a+b = 0$$ The second gives $$c+3d = 0 \text{ and } 3c+d =1.$$ Hence $-b = 3a$ and $a-9a = 1$ which ...


3

One thing that might be useful is to observe that this is a linear function. We can write $f(x,y) = (x + 3y, 3x + y)$ also in the matrix form $$ f(x,y) \;\; \to \;\; \left [ \begin{array}{cc} 1 & 3 \\ 3 & 1 \\ \end{array} \right ] \left [\begin{array}{c} x \\ y \\ \end{array} \right ] \\ $$ Finding the inverse of $f$ should then be equivalent to ...


2

You need to solve $(u,v) = (x+3y, 3x+y)$ for $x,y$. In this case we get $3u-v = 8y$, hence $y = \frac{1}{8}(3u-v)$ and the same way we get $x = \frac{1}{8}(3v-u)$. So $f^{-1}(u,v) = \frac{1}{8}(3v-u, 3u-v)$. You can check that this is true by computing $f\circ f^{-1}$ and $f^{-1}\circ f$.


0

For symmetric I am confused. If you have triangle ABC that is congruent with triangle DEF , then DEF is congruent with ABC . But is this true if they are not equal? Like, to prove antisymmetry you must show that xRy and yRx to where x=y . ABC isCongruentTo DEF so then DEF isCongruentTo ABC , but ABC=DEF so therefore antisymmetric? Can something be ...


1

Suppose $R$ is a relation, and let $X$ be the domain of $R.$ I claim that $R$ is the equality relation on $X$--that is, $$R=[=]_X:=\bigl\{\langle x,x\rangle:x\in X\bigr\}.$$ On the one hand, if $\langle x,y\rangle\in R$--that is, $x\:R\:y$--then $x\in X$ by definition. By symmetry, $y\:R\:x,$ and by antisymmetry, $x=y.$ Hence, $R\subseteq [=]_X.$ On the ...


1

A relation $R$ on a set $A$ is by definition a subset of the set $A \times A$. So to find the numbers of relations on a set $A$, we can simply find the number of subsets $A \times A$. We know that if $A$ has $n$ elements, then $A \times A$ has $n^2$ elements, and the set of subsets of $A$, also known as the power set $\mathcal{P}(A)$, has $2^n$ elements. ...


1

Firstly, to avoid misunderstandings: the number of relations on A is asserted to be the number of subsets of A x A (and not of A !). Secondly: this is indicated by the first sentence of the solution: "A relation on A is a subset of A x A" - I hope it is clear that if a relation is a subset (and different subsets are thus different relations), then the ...


0

xTy iff x > y + 1 , is clearly non symmetric and not reflexive. Suppose y > z + 1; we deduced x > y + 1 > z + 2 > z + 1, hence T is transitive.


1

Hint: Since we need to break symmetry, there has to be some $(a,b) \in T$ with $a \ne b$. Let us pick $(1,2) \in T$. Now we need to add some extra things to $T$ to satisfy the requirement that it have three or more elements. (Recall that $T$ is transitive iff $(x,y), (y,z) \in T \implies (x,z) \in T$.) Suppose that we add $(2,3)$ to $T$. What is missing ...


1

This is not an algebra problem about roots. Calculate the difference in the value of $f$ at consecutive positive integers: $$f(a+1)-f(a) = (a+1)^3-a^3 +3(a+1-a) = 3a^2 +3a+4 \ge10.$$ This shows the function is increasing and jumps by a quantity of 10 or more. Obviously it cannot cover all even integers. So this function not onlly misses 0 in its image, it ...


1

To show that $f$ is not onto, you have to show that there exists some element $x \in 2\mathbb{Z}$ such that $f(a) \neq x$ for every $a \in \mathbb{Z}$. Therefore, let $x = 0$ and suppose there exists $a \in \mathbb{Z}$ such that $f(a) = 0$. Then $a^3 + 3a + 2 = 0$. It's easy to see that $f$ is a strictly increasing function. Since our domain is the integers, ...


2

I'm no expert, but a relation can be treated as a function that maps to propositions. The book is written under the propositions = types paradigm, so a binary relation over types $A$ and $B$ is any element of the type $A \times B \rightarrow \mathfrak{U}$ where $\mathfrak{U}$ is the universe.


1

In order for $f$ to be a function, it must satisfy two things: It's defined on every point $(a,b)\in \Bbb Z^*\times \Bbb Z^*$ For every point $(a,b)\in \Bbb Z^*\times \Bbb Z^*$, the value of $f(a,b)$ is not ambiguous, meaning with this that $((a,b),q)\in (\Bbb Z^*\times \Bbb Z^*)\times \Bbb Q$ lies in the relation for at most one $q$. The problem here is ...


3

You'd need to prove that if $\frac{a}{b}=\frac{c}{d}$ then $$\frac{\max(a,b)}{\min(a,b)}=\frac{\max(c,d)}{\min(c,d)}$$ Then it depends on what $a,b$ are allowed. We know that $a,b\neq 0$, but can they have a common divisor? Can $b$ be negative? Or are we taking some "usual" representation for each rational - for example, $a,b$ relatively prime with ...


2

firstly, I am not understanding the function of R,I think that, this is only a relation (according to me) how can it be an equivalence it's not a set. A relation $R$ is a set of pairs, $R\subseteq A\times A$. $aRb$ is just a short form to write $(a,b)\in R$. Now if we define $R=R_1\cap R_2$, we have $$\begin{align} aRb &\iff (a,b)\in R ...


2

The word "equivalent" is built from "equal" and "value" — well, actually from the Latin words aequus (equal) and valere (to be worth). So two elements are equivalent if they are in a sense equal-valued, or interchangeable. Often this is indeed used literally, by defining some quantities as equivalence classes; for example, the fraction $\frac42$ has the same ...



Top 50 recent answers are included