Tag Info

New answers tagged

0

The three equivalence relations have just one very important quantifier and it's for reflexivity. It is that FOR ALL X IN THE RELATION R, X IS RELATED TO X. Well, while 1 is in the set, (1,1) is not in the set lof ordered pairs that define whatever the relation is. Don't feel bad(ly), I was stumped by this when using the Herstein text and even asked a group ...


2

By "almost equal", you mean "almost everywhere equal". Which means that the two functions agree except possibly on a set of measure zero. You can kind of visualize the measure of a subset of the real line as being its "length". And in fact, this is exactly what the measure is for intervals: that is, the measure of $(a,b)$ is $b-a.$ Now, what we call ...


1

There seems to be one step missing: ordered pairs (the elements of the cartesian products) can be reduced to sets Following Kuratowski we can define $$ (x,y):=\{\{x\},\{x,y\}\}$$ which may look somewhat arbitrary, but conveys the essetnial notion of ordered pair: $(x,y)=(u,v)\iff x=u\land y=v$.


0

A sequence is a function $f:\mathbb Z^+ \to \mathbf S$. $f:\mathbb Z^+ \to \mathbf S$ is a special case of a relation $f \subset \mathbb Z^+ \times \mathbf S.$ The cartesian product $\mathbb Z^+ \times \mathbf S$ is the set $\{(x,y): x \in \mathbb Z^+$ and $y \in \mathbf S \}$ I'm not sure what you mean by "basic". It seems that you are trying to use the ...


0

Therefore relations makes use of the cartesian product operator, which also makes use of sequences. What.   Ah... Yes, that is a just wee bit recursive, isn't it now? The Cartesian product of sets $\rm A, B$ is defined as: $\mathrm A{\times}\mathrm B = \{\langle a,b\rangle \mid a\in\mathrm A \,\wedge\, b\in\mathrm B\}$ That is, it is the set of ...


2

Yes, it is vacuously antisymmetric. However, note that in your formulation "$(x>y)\land(y>x)\to \exists(x,y)\mid x=y$" the symbols $\exists(x,y)$ make no sense and should not be there. If you want quantifiers in that statement (which is not a bad idea), it should be as $$ \forall x\;\forall y\;\bigl[ (x>y)\land(y>x)\to x=y \bigr]$$


0

No it is not transitive consider $(-1, 1/2)$ and $(1/2,100)$.


0

Hint: Let $a=0.1$, $b=2$, and $c=-3$.


0

It's not reflexive. $0\times 0\not\gt 0$. It IS transitive. If $ab \gt 0$ then $a,b$ have the same sign. If $bc\gt 0$ then $b,c$ have the same sign and thus $a,c$ have the same sign and $ac\gt0$.


0

The relation will be transitive if $xRy$ and $yRz$ imply $xRz$ for all $x,y,z \in A$. In the language of your relation, the implication you would need to prove is $y=3x$ and $z=3y \overset{?}{\implies} z=3x$ (If you wanted to prove this, you could try substituting equations.) Now, to prove that it is not transitive, you just need to find some $x,y,z$ in ...


0

Take $A=\{a\}$, $B=\{b_1, b_2\}$ and $C=\{c\}$ for the sets. And $R=\{(a,b_1),(a,b_2)\}$, $S=\{(b_1,c)\}$ and $T=\{(b_2,c)\}$ for the relations. Then $S \circ R=\{(a,c)\}$, $T \circ R=\{(a,c)\}$ and $S \setminus T=S$. Hence $(S◦R) \setminus (T◦R)= \emptyset$ while $(S \setminus T)◦R=\{(a,c)\}$.


0

Let $R$ be the full relation (that relates every element of $A$ to every element of $B$), and let $S$ and $T$ be two different bijections between $B$ and $C$. Then both $S\circ R$ and $T\circ R$ are the full relation from $A$ to $C$, so their difference is the empty relation, whereas the left-hand side is not the empty relation since $S\neq T$.


0

There are various conventions regarding the nomenclature for relations. Unfortunately, they are often conflicting. On the one hand, we have the "axiomatic-set-theoretic" names: $A, B$ have no name $\{1,3\} = \{x \mid \exists y: (x,y)\in R\}$ is called the domain of $R$ $\{20,40\} = \{y \mid \exists x: (x,y)\in R\}$ is called the codomain of $R$ On the ...


3

Strictly speaking, the universal quantification should be there in all three cases. It's often just left out as a shorthand. Edit: strictly speaking, all statements are implicitly universally quantified. This is true even if the statement is written as an implication e.g. $$\text{ if } a \in A \text{ then } (a,a) \in R$$ is really just $$\forall a \in ...


1

Reflexive means EACH $a\in A$ is in relation with itself. Symmetric means AS LONG AS $aRb$, then $bRa$. Transitive means IF $aRb$, $bRc$, then $aRc$. A relation that is reflexive, symmetric and transitive is called an equivalence relation. I would like to think "friendship" as an example of equivalent relation (in a perfect world in which 1) you are ...


0

If I understand what you mean by "picture": To represent a general relation on a set $X$ with a diagram, you'd normally draw a subset $R$ of the Cartesian product $X \times X$. In your example, $X$ is the set of ordered pairs of positive integers, while your diagram only depicts $X$ itself. To picture the relation $R$ in this sense, you'd need to start with ...


0

Such binary relations $p$ and $q$ exist. The proof: $Y \cap \alpha X \neq \emptyset \Leftrightarrow X \cap \beta Y \neq \emptyset$; $y \in \alpha X \Leftrightarrow X \cap \beta \{ y \} \neq \emptyset$; $y \in \alpha X \Leftrightarrow \exists x \in X : x \in \beta \{ y \}$; $y \in \alpha X \Leftrightarrow \exists x \in X : (x, y) \in p \Leftrightarrow y ...


1

The symbol for denoting similar triangles is ($\color{blue}{\sim}$) Notice, suppose $\triangle ABC$ & $\triangle PQR$ are similar then in LaTex it is written as $\text{"\triangle ABC \sim \triangle PQR"}$ surrounded in-between by 2 or 4 dollar signs which appears as follows $$\color{blue}{\triangle ABC \sim \triangle PQR}$$


1

Reflexive: Does $xD_nx \forall x\in S$? Yes, because $x|x \implies x|x$. Anti-symmetric: Does $xD_ny \land yD_nx \implies x=y$? Your proof here is correct, you might want to add $jk=1 \implies j=1,k=1$. Transitive: Does $xD_ny \land yD_nz \implies xD_nz$? We have $jx=y$ and $ky=z$ so $z=ky=kjx \implies jkx=z \implies xD_nz$. For the Hasse diagrams, I ...


1

You are done though! $$xm=y, yn=z \implies xmn= z \implies x|z \implies x D_n z$$ Substitution, you were doing so well.


4

$\triangle ABC \sim \triangle DEF$.


1

You are not completely missing the point, but you're a bit off the mark. Firstly, let go of the fact that you know nothing about the elements of the set $A$. It really is not important. (Incidentally, the claim remains true even if $A$ is empty.) What you have to do is construct the function $f$. To construct a function you must specify its domain and ...


0

x+y is even if and only if x-y is even because x-y=(x+y)-2y. So the even integers form one equivalence class, and the odd integers form the other.


1

In fewer symbols, the relation you are trying to show is an equivalence relation is that two functions $f$ and $g$ are equivalent if their derivatives are the same. The definition of an equivalence relation is a relation which is symmetric, reflexive, and transitive, so all you need to do is to prove the relation is each of these three things. Again in ...


1

Your intuition is correct. To describe the equivalence classes explicitly, it often helps to find the equivalence classes of numbers that are easy to work with. Let's find, for example, the equivalence classes $[0]$ and $[1]$. $0+a$ is even for which integers $a$? All these will form $[0]$. $1+b$ is even for which integers $b$? All these will form $[1]$. ...


0

Suppose $x+y$ is even. What does that tell you about $x$ and $y$? HINT: Write down some examples . . .


0

Assuming the "is even" is a typo, and M is defined by $$(x_1,y_1)M(x_2,y_2) \Leftrightarrow x_1|x_2 \ \text{and}\ y_1|y_2$$ You can see that $M$ is reflexive : $x|x$ and $y|y$ so $(x,y) M(x,y)$ You can see that $M$ is transitive : if $x_1|x_2$ and $x_2|x_3$ , then $x_1|x_3$ You can see that $M$ is not symetric : You have $(1,1)M(2,3)$ but not ...


2

Thanks for uploading the screen shot! Now it's clear that the author of the problem made a mistake somewhere. You could try to guess what they meant, but if possible, it would be better to notify them of the mistake and ask them to fix it.


1

We find $M^{[n]}$ in the same way we would find $M^n$, only we replace addition with $\vee$ and multiplication with $\wedge$. So, for example: we have $$ M_R = \pmatrix{ 1&0&\color{blue}1\\ \color{red} 0& \color{red} 1& \color{purple}0\\ 1&1&\color{blue}0 } $$ So, the entry of $M_R^{[2]}$ in the $\color{red}2$nd row and ...


1

Probably the best-known example is the collinearity relation among three points $C(x,y,z)$, which is an equivalence relation in that it satisfies the axioms of... Symmetry: $C(x,y,z)$ is invariant under permutations of $x, y, z$ Reflexivity: $C(x,y,y)$ Transitivity: $C(a,x,y)\land C(a,y,z)\to C(a,x,z)$ And there doesn't seem to be a reasonable way to ...


1

I'm not sure if "$\rho \circ \phi$" means we do $\rho$ first or not, but it won't matter. Let $(x,y) \in \rho \circ \phi$. Case 1: We do $\rho$ first. Then there exists $z \in A$ such that $(x,z) \in \rho$ and $(z,y) \in \phi$. But then $(x,z) \in \sigma$, and so $(x,y) \in \sigma \circ \phi$. Case 2: We do $\phi$ first. Then there exists $z \in A$ such ...


2

If the set has finite cardinality, yes. If not, then see the counterexamples in the other answers/comments.


4

Consider the multiply-by-$2$ map on the integers.


0

$S$ is a set of $n$ elements. $S$ is non-empty and we know, every non-empty set always contains the identity relation. So , It can't be empty relation , I suppose since empty relation is invalidated , that explains why smallest equivalence relation on set $S$ is $n$. i.e Empty relation is transitive and symmetric on every set but not equivalence.


1

Suppose $R$ is reflexive and transitive. Then the relation defined by $$ x\mathrel{R_s}y \qquad\text{if and only if}\qquad x\mathrel{R}y\text{ and }y\mathrel{R} x $$ is an equivalence relation. The proof is easy. Consider $B=A/R_s$ and define, for $[x],[y]\in B$ ($[a]$ denotes the equivalence class with respect to $R_s$ of $a\in A$), $$ [x]\mathrel{S}[y] ...


4

It's not. Take $j=k=1$ and $l=m=2$. Then $\delta_{jk}\delta_{lm}=1$, but $$\sum_{i=1}^N \delta_{ij}\delta_{ik}\delta_{il}\delta_{im}=\delta_{11}\delta_{11}\delta_{12}\delta_{12}+\delta_{21}\delta_{21}\delta_{22}\delta_{22}=0+0=0.$$ What is true is that $$\sum_{i=1}^N \delta_{ij}\delta_{ik}\delta_{il}\delta_{im}=\delta_{jklm},$$ i.e. the function that is ...


0

In my opinion your misunderstanding is in the logic, not in the set theory. If $p$ is false, then the conditional statement “if $p$ then $q$” is vacuously true. This does not mean that $q$ is true, it means the entire statement is true. As @Doug Chatham says, For example, consider the implication, "If 2+2=5, then you will pass the course." Since 2+2 is ...


0

I believe the above by mathcounterexamples.net takes care of the second question you ask about quite nicely. As for the first question, I think this is where you are misunderstanding transitivity. Transitive is $(a,b)$ AND $(b,c)$ implies $(a,c)$. The relation need not be symmetric, so the order matters. It is the second coordinate of the first and the ...


2

Regarding your first point. To evaluate transitivity you have to look at two couples $(a,b),(b,c)$ in your relation set and verify that $(a,c)$ also belongs to it. Hence, you don't need to evaluate $(2,4),(3,4)$. Regarding your second point. Name $R=\{(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)\}$. You have $(0,2) \in R$ and $(2,3) \in R$. If ...


0

Let $R_1$ be a relation on a set $A$ and if we are required to show that it is not transitive relation then we have to show that there exists $a,b,c\in A$ such that $(a,b),(b,c)\in R_1 \not \Rightarrow (a,c)\in R_1$ $R=\{(x,y):x\text{ is wife of }y\}$ In case of $R$ if $(x,y)\in R$ then there is no $z$ such that $(y,z)\in R$. Since we are unable to show ...



Top 50 recent answers are included