Tag Info

Hot answers tagged

5

This relation is transitive. 3 doesn't play any role here since you don't require a transitive relation to be full. Observe that the transitivity here means: $$(1,2)\wedge(2,1)\in R\Rightarrow(1,1)\in R \\(2,1)\wedge(1,2)\in R\Rightarrow(2,2)\in R$$ and these are found in the relation so it's transitive. In fact that's equivalence relation on $\{1,2\}$ ...


5

The definition of antisymmetry does cover relations like $<$. If you examine that definition carefully, you’ll see that in order for a relation $R$ to violate it, there must be elements $a,b\in S$ such that $R(a,b)$, $R(b,a)$, and $a\ne b$. If you can’t even find elements $a,b\in S$ such that $R(a,b)$ and $R(b,a)$, then you certainly can’t find elements ...


4

It is not surjective. For example $(1,0)$ dont have a source. Assume that $$(x+y,x-y)=(1,0).$$ Then $x=y$ and then $2x=1$ which have no solutions over $\mathbb{Z}$. By the way over $\mathbb{R}$ it is surjective since the corresponding matrix is invertible.


4

The relation $S$ is characterized by 1 and 2 and being "the smallest relation" with these properties 1 and 2. It is not quite correct to say that $R$ is a subset of $A$, it is rather a subset of $A^2$ [added: meanwhile corrected]. The set $i_A$ is, in all likelihood, the diagonal of $A^2$, that is $\{(a,a) \colon a \in A \}$. Presumably, the notation $i_A$ ...


4

We have $(b,c)\in R$ and $(c, b)\in R,\;$ so for transitive closure, we need $\,(b, b)\in T_R.$ Similarly, for transitive closure, $(c, b)\in R$ and $(b, c)\in R\,$ require that $(c, c) \in T_R$.


3

This is often a source of confusion among beginners, so I'll try to explain where the problem is. Everybody knows intuitively what a relation among elements of a set is; examples from the real world are “being a parent of”, “being siblings”, “being taller” and so on. However, defining what a relation is becomes circular, so in mathematics a more pragmatic ...


3

You seem to have some misunderstanding on how proofs work. To show that a relation is reflexive, you must show that $(x, x) \in R$ for ALL $x$, not just one. To show it is not reflexive, you simply demonstrate some $x$ for which it is not reflexive. Your second proof is invalid because it does not show that it always true, it only gives an example. Consider ...


2

Yes, you are correct. Well, the third is correct if the statement is $\exists x \Big(\forall y R(x, y) \land \forall z R(z, x)\Big)$, and you have chosen $a$ as the existent example of $x$.   (You could have chosen $a$, $b$, $c$, or any combination of at least one of the three).


2

It is not transitive as $(2,4)$ and $(4,1)$ belongs to $R$ but $(2,1)$ does not belong to $R$. Remember for transitivity you need $(a,b)\in R$ and $(b,c)\in R \implies (a,c) \in R$ for all $a,b,c \in R$. Also the second relation is transitive as the above condition holds. For a relation to be transitive we do not need $(a,a) \in R$ for all $a$.


2

Consider $\mathbb{N}$ with its usual ordering. Does the chain $\mathbb{N}\subseteq\mathbb{N}$ have a supremum?


2

For 1. : consider $a,b,c \in A$ such that $aRc$ and $cRb$. This means that $aR^2b$ and we have that $R_2 ⊆ R$, and this means that : : $(a,b) \in R^2 \subseteq R$ and thus $(a,b) \in R$. Thus we have that, from $aRc, cRb$, follows : $aRb$, and this is transitivity. For 2. : we have $R^2 \subseteq R$ form 1. (transitivity); thus we have to check that ...


2

You need to distinguish very clearly between existential and universal quantification, and you should not use "let" when you actually want to say something about "any arbitrary given" something. Your first part of the first question should therefore be more precisely the following: If $R$ is transitive on $A$:   For any $a,b \in A$ such that $a R^2 ...


2

Well, $\mathbf{Rel}$ is a full subcategory of $\mathbf{CJS}$, the category of complete join-semilattices (and join-preserving maps). The embedding sends a set $X$ to the powerset $\mathscr{P} X$ and a relation $R : X \not\to Y$ to the unique join-preserving map $r : \mathscr{P} X \to \mathscr{P} Y$ where $r \{ x \} = \{ y \in Y : x \mathrel{R} y \}$. Thus ...


2

The OP clarified that $(x,y),(y,z),(x,z)\in R \wedge S$ is an abbreviation of $(x,y),(y,z),(x,z)\in R\land (x,y),(y,z),(x,z)\in S$. Let $x,y,z\in A$. While $(x,y),(y,z),(x,z)\in R \wedge S\Rightarrow (x,y),(y,z),(x,z)\in R \cap S$ is actually true, it doesn't prove that $R\cap S$ is transitive. Recall that, by definition, a relation $T$ on $A$ is ...


2

Relation composition is defined so that $$a\,(S\circ R)\,b\iff\exists c:(a\,R\,c\wedge c\,S\,b).$$ And converse is defined so that $a\,R^{-1}\,b\iff b\,R\,a$. Applying this to your example, we have: $$p\,S\circ S^{-1}\,q\iff\exists n:(p\,S^{-1}\,n\wedge n\,S\,q)\iff\exists n:(n\,S\,p\wedge n\,S\,q).$$ Applying the interpretation that $p\,S\,q$ means that ...


2

Calculating the first few values: $0,5,20,65,200$ , dividing by $5$ this is $0,1,4,13,40$ , multiplying by $2$ we get $0,2,8,26,80$ adding $1$ we get $1,3,9,27,81$. Otherwise you can use generating functions: Let $A=\sum\limits_{n=0}^\infty t(n)x^n$. Then $A=3xA+5\sum\limits_{n=1}^\infty x^n$ (since $f(0)=0$). Then $(1-3x)A=\frac{5}{1-x}-5$ so ...


2

Hint: $(A\times B)\cap (B\times B)=(A\cap B)\times B$


2

Not really. For example the empty relation is anti-symmetric, but is not reflexive unless the underlying set is empty as well. I hope this helps $\ddot\smile$.


2

Your definition is wrong. The relation $R$ is antisymmetric if, whenever $x\mathrel{R}y$ and $y\mathrel R x$ it holds that $x=y$. An example of a relation that is antisymmetric but not reflexive is $>$ on the set of integers.


2

Which elements are related to which elements? That is, $a R b$ if and only if there exists a cell (subset) X in the partition such that $a\in X$ and $b \in X$. You will see this is indeed and equivalence relation. Looking at the cell of the partition given by $\{d, e\}$, we know that $(d, d) \in R, (e, e) \in R, (d, e) \in R, (e, d)\in R$. But we also ...


1

Your proof of anti-symmetry of $R^{-1}$ is good. Concerning transitivity, assume that $(x,y)\in R^{-1}$ and that $(y,z)\in R^{-1}$. Then by definition of $R^{-1}$, you also have $(y,x)\in R$ and $(z,y)\in R$. Since R is transitive, we also have $(z,x)\in R$, and then $(x,z)\in R^{-1}$, proving that $R^{-1}$ is transitive.


1

There are two types of solutions here: the homogeneous and the particular. Rewrite the equation as $$T_n - 3 T_{n-1} = 5$$ The homogeneous solution is simply the solution assuming the RHS is zero. Thus $T_n^{(H)} = A \cdot 3^n$. The particular solution is a simple solution that satisfies the equation and boundary conditions. In this case, $T_n^{(P)} = ...


1

HINT: How many permutations does $\Bbb N$ has? This alone gives you a lower bound, with a set of distinct linear orders, all isomorphic to the usual ordering of $\Bbb N$.


1

Hint: Prove the following reasonably easy If a set $\;A\;\;$ is partioned by $\;\left\{\;\;A_i\;:\;\;i\in I\;\right\}\;$ , then the equivalence relation determined by this partition is $$x\sim y\iff \exists\;i\in I\;\;s.t.\;\;x,y\in A_i$$ Namely: prove the above indeed is an equivalence relation whose equivalence classes are exactly the sets $\;A_i\;$ .


1

If $\mathcal P\subseteq \wp(A)$ denotes a partition of set $A$ then the corresponding equivalence relation on $A$ is determined by: $$xRy\iff x\text{ and }y\text{ belong to the same element of }\mathcal P$$ If you must find all equivalence relations on a set $A$ then I advice you to start always by finding all partitions (as you did here). Example: ...


1

The number of $n$-element symmetric relations is $$2^{\binom{n}{2}+n}$$ as answered here. Essentially, for each pair of distinct elements $a$ and $b$ we choose whether or not to include both $(a,b)$ and $(b,a)$, giving $\binom{n}{2}$ binary choices, and for each element $a$ we choose whether or not to include $(a,a)$, giving $n$ binary choices. For ...


1

Take for a simplest example $$R_1=\{(a,x),(a,y)\},\\ R_2=\{(x,z)\},\quad R_3=\{(y,z)\}\,.$$ Note also that we have equality with union instead of intersection.


1

Reflexivity: $\mathfrak{R}$ is reflexive if $\forall r\in P,\,r\,\mathfrak{R}\,r$ which isn't what you did. In fact, if you take $r\in\mathfrak{R}$, $r=r$ so $r\,\mathfrak{R}\,r $ according to the definition. Antisymetry: Yes that's right, even if in fact seems to me that you're using antisymetry of numbers. I think it's better to say "$r$ is ancestor of ...


1

Yes there is, check Bell number. It gives you a Recurrence relation for calculating number of equivalence relations on a set having $n$ elements.



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