Tag Info

New answers tagged

0

Your textbook is correct. Linearly ordered set and totally ordered set are the same thing. If a linearly ordered set has $n$ elements, its Hasse diagram is a vertical path with $n$ nodes and $n-1$ edges. For $n=5$, for instance, it looks like this: * | * | ...


1

To extend mrp's answer: $|\mathcal P (A)\times\mathcal P (A)|=2^{2^3}=256.$ We take the $8$ pairs we are interested in, and put them into a bag. This bag is a relation. Now, we can add any other element of $\mathcal P (A) \times \mathcal P (A)$ and add it to our bag to create a new relation. This can be achieved in ...


1

$$P(A) = \{\emptyset,1,2,3,\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$$ Now, a relation $R$ on a set $X$ is reflexive if for all $x \in X$, we have that $(x,x) \in R$. This means that any reflexive relation on $P(A)$ must at least contain the pairs ...


0

Your counts for groups 1 and 2 are correct, but your strategy gets the wrong answer, because some of the relations are symmetric and also do not contain $(1,4)$, and if you simply add groups 1 and 2 you will have counted these twice. To get this right, you need to count a third group: the set of permutations that are symmetric and also do not contain ...


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\}$ ...


1

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 ...


0

Let’s look at the example in your comment: $$R=\left\{\langle x,y\rangle\in\Bbb R^2:x^2>x\land y^2>y\right\}\;.$$ The defining condition involves the relationship $x^2>x$ for real numbers $x$, so a good place to begin is by figuring which $x\in\Bbb R$ have this property. In other words, solve the inequality $x^2>x$. You may know the solution ...


0

Well you could check if S is an equivalence relation or if there is some "partial order relation" on S, because this would then imply that S is reflexive by definition.


0

Correct. Easy check is to view the pairs as two things that have to connect to each other Put them in the order of the relations in the compositions, i.e $S$ pair before $R$ pair: $(x,z)(z,y)$ Are the two "inner elements" equal? Yes as $z=z$. Then the outer elements $x,y$ form a pair $(x,y)$ in the composition $S \circ R$


0

There is atleast one case where it does not hold. Consider $S = \{(a,b),(b,a)\}$ Then $S \circ S = \{(a,a),(b,b)\}$ i.e reflexive even though $S$ is not


1

If $\sim$ is a transitive relation on $A$ then if $(a,b)\in R$ and $(b,c)\in R$ then $(a,c)\in R$. You have $0\sim 0$ and $0\sim 1$ which implies $0\sim 1$. Therefore $(0,1)\in R$, which is something that's true. Recall that$\{a,a,a,a,a\}=\{a\}$ so you don't need $(0,1)$ to be repeated in A, you already have it.


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

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

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

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?


0

You are given that $A=B$, $A=C$ an $B=D$. From the first two you get that $C=B$, and from that and the third one, that $C=D$. If you want, you've used the transitive propery of equality twice.


0

Yes, although somewhat trivially. A relation $R$ is asymmetric iff, for any $x,y$ in the domain, $xRy\Rightarrow \neg yRx$. It is antisymmetric iff $xRy \wedge yRx \Longrightarrow y=x$. However, for an asymmetric relation $R$, the condition $xRy\wedge yRx$ is always false, which means the condition for being an antisymmetric relation is (vacuously) true. ...


0

There is a simple solution to the problem. It comes in two parts. And it says that what you're looking for cannot be done, in general. The first part, is to see the larger picture, that we may want to extend the notion of tuple to infinite index sets, and iterated ordered pairs is not the way to go. Instead we define what an ordered pair is, and what is a ...


0

You can define things differently. Nothing wrong with that. Just realize that you get different theorems. And some definitions are less equal than others.


0

This is what I ended-up writing... (by Josh Thomson) Mathematical Relations in Computing Computing is reliant upon countless mathematical operations, among which are core numeric systems such as ‘Unary’, ‘Binary’ and ‘Ternary’. These different numeric systems have their own uses in computing, but each share a common difference. The Unary number system has ...


0

A relation that is antisymmetric but not reflexive is said to be "strongly antisymmetric" or "asymmetric". This implies : $$(xRy) \implies (\neg(yRx))$$ As if $(xRy)$ and $(yRx)$, then $x=y$ but $x\not R x$ because $R$ is not reflexive (which mean you actually can't apply antisymetry to deduce equality). $>$ and $<$ are the most common examples.


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

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

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 ...


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

You might try this with a few examples of $R_1$ and $R_2$. For instance, consider the set of all line segments in the plane. If $A$ and $B$ are two line segments, let $A\mathrel{R_1}B$ if $A$ and $B$ have the same length, and $A \mathrel{R_2} B$ if $A$ and $B$ have the same slope (or are both vertical). Clearly $R_1$ and $R_2$ are symmetric and transitive ...


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).


1

Yes, your reasoning is perfect. In fact, it's not too hard to show that this function is also injective (one-to-one) and surjective (onto). Since the domain is equal to the codomain, we say that $R$ is a special type of bijection known as a permutation.


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 ...


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

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\;$ .


0

I don't know if this will help, but let's try it out. For every $x\in R$ and $y\in R$, there are only four possibilities: $(x,y)\in R$ and $(y,x)\in R$ $(x,y)\notin R$ but $(y,x)\in R$ $(x,y)\in R$ but $(y,x)\notin R$, or $(x,y)\notin R$ and $(y,x)\notin R$. A reflection is asymmetric if only the last three ever occur. The proof shows that it is ...


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$.


0

Note: based on some more readings and new things I have learnt, I will also try to give my answer. Feel free to modify it in order to improve it. I found the complete theorem, which by itself answers also to my question: Let $S = R \cup i_A$, where as usual $i_A$ is the identity relation on $A$. We will show that S is the reflexive closure of A. Thus, we ...


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$.


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$ ...


0

I'm not sure what you personally mean by "binary". Maybe the binary numeral system for the natural numbers?... In any case, here, a binary relation between two sets of objects, say $A$ and $B$, is a collection of pairs $(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m), \ldots$ (finite or infinite), where every $a_i$ belongs to $A$ and every $b_i$ to $B$. Note that ...


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 ...


0

This is an example of that the axioms of a theory doesn't say much of the intentions with the theory. The purpose of relation has never been to study universal properties, for example.


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 ...


-2

Technically, Russell's paradox points to a rather interesting proof-technique to show that a certain mathematical object does not exists: To prove that it doesn't exist a surjection $p:A\to\mathcal P(A)$, define the set $B=\{x\in A|x\notin p(x)\}$. Obviously, $B\notin\mathrm{Im}\; p$. Historically, Russell's paradox shows that the traditional ...


3

If it is of interest to you, you can translate Russell's paradox into lambda calculus logic to avoid sets completely: $$P = \{Q ~\mid~ Q \not \in Q\}$$ becomes $$\text{define } P \text{ as } \bigg(\lambda ~ Q .\lnot Q(Q)\bigg)$$ or more easily read as $P(Q) = \lnot Q(Q)$. To follow the logic, set $P$ as the argument to get $P(P) = \lnot P(P)$, which ...


24

The interesting thing about Russell's paradox is not that it involves an object that can't exist, but that that object is embedded in a theory that seemed sound until Russell pointed out the contradictory object. Certainly one can invent all sorts of false principles about nonexistent objects. For example, let $V$ be a village in which there live two men, ...


5

Your graph theory version is not paradoxical, because there was never any reason in the first place to believe that such a graph exists. By contrast, Frege's set theory did imply that a set with the Russell property exists, hence the paradox.


1

Your argument for 1 is almost correct. In fact "no element is related to itself" would also hold for $A=\emptyset$, but in that case the empty relation would be reflexive. To make the argument more precise, write something like this: As $A$ is not empty, there exists some element $a\in A$. As $R$ is empty, $a R a$ does not hold, hence $R$ is not reflexive. ...



Top 50 recent answers are included