Tag Info

Hot answers tagged

17

If Fred is Bob's brother, and vice versa, transitivity would imply that Fred is his own brother.


7

The best explanation is probably that the possibility of same-sex marriages were not on the author's mind when he/she came up with the exercise. If we suppose that marriages is always between a man and a woman (and genders are binary, bla bla bla), then the relation is indeed transitive, but vacuously so. The condition it has to satisfy is that if $x$ is ...


5

Most of the conditions are universal, so they must be true for all values. Note that the set where things are coming from does make a difference in how the properties behave. Let $R$ be a relation on $A$ (so $R\subseteq A\times A$). Reflexive: $$ \forall a\in A, (a,a)\in R $$ Irreflexive: $$ \forall a\in A, (a,a)\not\in R $$ Symmetric: $$ \forall ...


4

The relation you give is in fact not actually an asymmetric relation. The definition of an asymmetric relation is that if $(a,b)\in R$, then $(b,a)\not\in R$. This does not hold because $(a,a)\in R$. On the other hand, the given relation is an antisymmetric relation. The definition of antisymmetric is that if $(a,b)\in R$ and $(b,a)\in R$, then $a=b$. ...


3

Here is a different, but equivalent definition for antisymmetry: For a relation to be antisymmetric, we need that for any element $(x,y)$ in the relation where $x \neq y$, the element $(y,x)$ must not be in the relation. Now look at your example. Are there any $(x,y) \in R$ with $x \neq y$? Yes, all three, $(a,b), (b,c)$ and $(a,c)$. Do we have $(y,x) \in ...


3

Do you mean "irreflexive" instead of "not reflexive"? A relation is reflexive if $\forall x\in A, xRx$. It's irreflexive if $\forall x\in A, \neg (xRx)$. However, if it's not reflexive, you only know that $\exists x \in A, \neg(xRx)$. I ask, because the result you have to prove is wrong. Take a relation on the set $A=\{x,y,z\}$ with $\neg (xRx), ...


3

They're two different things, there isn't really a strong relationship between the two. Based on the definitions you're using, they both give two different criteria for concluding that $(x, x) \in R$. For any antisymmetric relation $R$, if we're given two pairs, $(x, y)$ and $(y, x)$ both belonging to $R$, then we can conclude that in fact $x = y$, so that ...


3

It is reflexive if this is a relation over the set $\{1,2,3,4\}$, and yes, the relation is symmetric. Yes, If we remove $(1,2)$ or $(2,1)$ then it is anti-symmetric. The relation is transitive, we do not need $(2,3)$ and $(3,4)$ to be in the set. Especially there is no pairs in the relation $(2,x)$ and $(x,3)$, which is what we would need in order to force ...


3

This is a question by bygone asker/user, who apparently was satisfied with answer it got, but for the sake of not leaving the question half-answered (from my perspective), I'll point out that a notion strictly on semigroups does appear in Howie's Fundamentals of Semigroup Theory in an exercise on p. 42. I'll reproduce it here with Howie's notation, who ...


2

If you mean a relation, then transitivity requires nothing out of $(a, b), (a, c)$. If you instead had $(a, b), (b, c)$, then $(a, c)$ would be needed. So the relation $$ R = \{(a, b), (a, c)\} $$ is vacuously transitive. Take $<$, for instance. If $a<b$ and $a<c$, you cannot compare $b$ and $c$ from this information, even though $<$ is ...


2

The name predicate calculus has an historical heritage ... Today we prefer to call it first-order logic. For the "founding fathers" : Frege, Russell, the distinction between propositional and predicate calculi were not relevant; see Principia Mathematica and The Notation in Principia Mathematica. In the first modern mathematical logic textbook : David ...


2

Try $R=\{(x,x) | x \in \mathbb{R}\}.$


2

You need to show two things: that $x$ is an upper bound for $B$, i.e., that $b\mathrel{R}x$ for each $b\in B$, and that $x$ is the least upper bound for $B$, i.e., that if $y\in A$ and $b\mathrel{R}y$ for all $b\in B$, then $x\mathrel{R}y$. You’ve tried to do the first, but your argument is a bit confused. For one thing, it starts in the wrong place: ...


2

Somehow its both: The ordered pairs in $L\setminus M$ are all pairs for which there exists an $x$ such that the pair is $(x,x)$. The "all" is dropped in the original formulation from "(all) pairs of the form" and the "exists" is contained in "for some $x$".


2

Remember that the implication: $$p \rightarrow q$$ Is always true when $p$ is false, regardless of the truth value of $q$. Thus, consider your first relation $R = \{(1,6),(2,7),(3,8)\}$. Note that: $$(x,y)\in R \wedge (y,z)\in R$$ is always false, hence the implication: $$(x,y)\in R \wedge (y,z)\in R \rightarrow (x,z)\in R$$ is always true, and hence ...


2

Here are a few relations on subsets of $\Bbb R$, represented as subsets of $\Bbb R^2$. The dotted line represents $\{(x,y)\in\Bbb R^2\mid y = x\}$. Symmetric, reflexive: Symmetric, not reflexive Antisymmetric, not reflexive Neither antisymmetric, nor symmetric, but reflexive Neither antisymmetric, nor symmetric, nor reflexive


2

You have defined two relations on ${\mathbb R}^2$. Both are defined by a certain function on ${\mathbb R}^2$ taking equal values on equivalent points and different values on unequal points. For $R_1$ this function is $f_1(x,y):=x+y$, and for $R_2$ this function is $f(x,y):=\min\{x,y\}$. A "canonical representation" of the quotient set for $R_1$ would be ...


2

It is not reflexive because $(0,0)\notin Z$; Is is not symmetric because of the reasons you stated. For instance, $(0,2)\in Z$ but $(2,0)\notin Z$. It is not transitive; for example, $(0,2)\in Z$ and $(2,3)\in Z$ but $(0,3)\notin Z$


2

You are correct about symmetry and reflexivity. For transitivity, we need that every time there are two pairs of the form $(a,b)$ and $(b,c)$ in the relation, it must also be the case that $(a,c)$ is in the relation. The relation you have given is not transitive, can you find two pairs $(a,b)$ and $(b,c)$ in your relation such that $(a,c)$ is not in the ...


2

Your relation $R$ is already transitive, so it is its own transitive closure. It appears that what you’re misunderstanding is the notion of transitivity. A relation $R$ on a set $A$ is transitive if it satisfies the following condition: if $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$. It says absolutely ...


1

It is not transitive because it has (2,3) and (3,4) but doesn't have (2,4). Correct, it's not symmetric for the reason you noted. Also correct, it's not reflexive. To be reflexive all (a,a) must be part of the relation (for any a). That doesn't hold here apparently.


1

The transitive closure of a binary relation $R$ is the intersection of all transitive binary relations that extend $R$. To say that $S$ extends $R$ means that for all $x,y$ in the domain, if $aRb$ and $aSb$. The intersection $T$ of a set of binary relations is defined by saying that for all $x,y$ in the domain, $xTy$ if and only if for every binary ...


1

This set is not transitive because $(2,3),(3,4) \in Z $ but $ (2,4)\notin Z$. The reason you provided for not-symmetric is right.


1

Transitivity says: $aRb$ and $bRc$ imply $aRc$ $x$ is a brother of $y$, $y$ is a brother of $x$, but $x$ is not a brother of $x$. Therefore, it's not a transitive relation.


1

If X is the brother of Y and Y is the brother of X, then X is his own brother, if it were transitive.


1

Are you familiar with the definitions of reflexive, symmetric and transitive relations? A reflexive relation is a binary relation on a set for which every element is related to itself. As you can clearly see $(0,0),(1,1)$ etc. are not contained in your relation, so it is not reflexive. A relation is symmetric if $aRb \implies bRa$. Once again, ...


1

The "antisymmetry" statement looks like $$\text{If } xRy \text{ and } yRx, \text{ then } x = y,$$ or, using the ordered pair notation, $$\text{If } (x, y) \in R \text{ and } (y, x) \in R, \text{ then } x = y.$$ So, in your example, you just need to check if you have any ordered pairs $(x, y)$ and $(y, x)$ both in $R$: The only 'pair' of pairs allowed is ...


1

An equivalence relation is always partition. In general you want to put it in the form of a set. Here, you can say, $$A_{r}= \{(x,y) | y = \frac{x}{3^k}\}$$ Where $A_r$ denotes the equivalent partition corresponding to your relation. Also, $k$ is assumed to be an integer.


1

(apple, apple) and (apple,atom) are each in both $R_1$ and $R_2$, but (atom, apple) is only in $R_2$. In the dictionary, "apple" comes before "atom". This explains $R_1$. In the alphabet, "a" comes at the same place as "a". This explains $R_2$.



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