Tag Info

Hot answers tagged

4

I will assume that by $<$ you mean the "less than" relation on some totally ordered set such as the real numbers. Is there ever a situation where you have $x<y$ AND $y<x$ at the same time? No. The statement then is an example of a Vacuous Truth since the premise is always false, there is no possible way that there is a contradiction. A statement ...


3

Yes; the statements are equivalent. Symmetry is the property that: $\forall x, y: \big((y,x)\in R\to (x,y)\in R\big)$ The contraposition of this is: $\forall x, y:\big( (x,y)\notin R\to (y,x)\notin R\big)$


3

Solution for part 1 Every edge in the Hasse diagram goes from a set $S$ to a set $S \cup \{x\}$ with exactly one more element. So we can count how many edges come from each set. A subset $S \subseteq \{1, 2, 3, \ldots, n\}$ of size $k$ is the initial point of exactly $(n-k)$ edges, because there are $n-k$ possible elements $x$ to add to get $S \cup \{x\}$. ...


3

Hint: symmetric relations on $\Bbb N$ are in bijection with subsets of $\{(a,b)\in\Bbb N^2:a\le b\}$. Alt route: any subset of $\{(c,c)\in\Bbb N^2:c\in\Bbb N\}$ is a symmetric relation.


3

$$R=\left \{ (1,1),(2,2),(3,3),...,(1,5),(5,1),(2,6),(6,2),(3,7),(7,3) \right \}$$ R is reflexive ${\color{Red} {(1,1),...(7,7)}} $ R is symmetric $(1,5)\Leftrightarrow (5,1)$ ,... R is transitive if you check so it is equivalence relation


3

A relation $R$ is transitive if any time we have pairs of the form $(a,b)$ and $(b,c)$ in $R$, it must also be the case that $(b,c) \in R$. As you have observed, $(1,2) \in S$ and $(2,3) \in S$, so these are two pairs of the form $(a,b)$ and $(b,c)$, but $(1,3) \notin S$, which is required by transitivity. So by definition, the relation is not transitive. ...


3

It's vacuously true! The point is that $(x,y) \in R$ and $(y,x) \in R$ can never happen, so whatever you say about it is true. For example the statement "If $(x,y) \in R$ and $(y,x) \in R$, then $5=7$" is true.


2

Hint: to decide whether the relation is transitive, you need to check whether $$(x,y), (y,z) \in R \overset{?}{\implies} (x,z)\in R$$ In your case, this translates to $$y=x+5 \text{ and } x<4, \; \; z=y+5 \text{ and } y<4 \overset{?}{\implies} z=x+5 \text{ and } x<4$$


2

.....................................................


2

You don't care anymore about 4 elements, so only 6 remaining. That's why the cardinality of your quotient should be $$2^6=64.$$ If you want to prove it formally show that $\overline{A}\mapsto A\setminus P$ is a bijection between the quotient $Q$ and $P(X\setminus P)$. Hence we have $$|Q|=|P(X\setminus P)|=2^{|X\setminus P|}=2^6=64.$$


2

A relation-as-part-of-formal-language isn't the same thing as a relation-as-type-of-set. In the former case it's a piece of syntax--e.g. the symbol '$\in$' along with the information that it takes two term symbols to make a formula out if it. In the latter case it is a subset of the Cartesian product. Note that you can sniff out that these are distinct ...


2

$\subseteq$ relation can be written with $\in $ relation as $$A \subseteq B \text{ is defined by } \forall x (x \in A \Rightarrow x \in B)$$


2

You can solve the problem directly without making use of the hint. Just 'define' relation $T$ on $A/S$ by stating: $$[x]T[y]\text{ if and only if }xRy$$ It must be checked now wether this relation is well-defined and at that point the compatibility of $R$ with $S$ comes in. Based on it we find that there is no dependence on the representatives $x$ and $y$, ...


2

No, because $4 \not \leq 6$ by the relation we are using, which is divisibility. $4$ does not divide into $6$ evenly. The $\inf$ of $4$ and $6$ is the largest number which divides them both, the $\gcd$, which is $2$


2

$R\subseteq A\times A$, and $S\subseteq B\times B$, so $$R\cup S\subseteq (A\times A)\cup(B\times B)\subseteq(A\cup B)\times(A\cup B)\;;$$ $R\cup S$ is a relation on $A\cup B$.


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


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


2

Some examples include: The set $\mathbb Q$ of rational numbers with the usual ordering, which is interesting in that it has the same cardinality as your $A$ but a very different kind of order (a dense order). The long line, which is interesting in that it has the same cardinality as the set $\mathbb R$ of real numbers but a substantially different kind of ...


2

The second part should rather start "Now, suppose that $R\circ R\subseteq R$. Let $(x,y)\in R$ and $(y,z)\in R$." Then you want to show that $ (x,z)\in R$.


2

You know that $<$ is transitive and antisymmetric. Now you define the reflexive extension of $<$ to be $\le$ with $a\le b$ iff $a<b$ or $a=b$. You need to prove that $\forall a\in A: a\le a$ (reflexivity), and this is obvious since $a=a$ (and therefore $a\le a$ by definition of $\le$). As for inequality, it is symmetric. You can show that the ...


2

Hint: Here is a directed graph representing the relation $\mathcal{R}$ with a directed edge from $x$ to $y$ iff $x\mathcal{R}y$. Is it currently transitive? What is the necessary edge(s) you need to make it transitive? Is there a natural way to partition these elements so that in the image they are "grouped" how the edges appear?


2

This is not reflexive, as $(0,0) \not\in R$. This is not symmetric, as $(1,0) \in R$ but $(0,1) \not\in R$. This is transitive as if $(x,y) \in R$ and $(y, z) \in R$ then $x=1$ and thus $(x,z)\in R$. This is antisymmetric because if $(x,y) \in R$ and $(y,x) \in R$ then $x=1$ and $y=1$.


1

It is transitive and antisymmetric, as you claim. However It is not reflexive, since $(0,0) \not \in R$ for instance. For reflexivity, you need $(x,x) \in R$ for all $x \in \mathbb{R}$. It is not symmetric, since $(1,0) \in R$ but $(0,1) \not\in R$. However, if it was both symmetric and antisymmetric, there would be interesting things to say. Relations ...


1

The usual ordering on $\Bbb{R}$ can be uniquely defined as the total order $\lt$ on $\Bbb{R}$ that satisfies the following two properties: (Let $a,b,c \in \Bbb{R}$) 1) $c \gt 0 \iff c$ is positive. 2) $a \lt b, \ \ 0 \lt c \implies ac \lt bc$ Proof that this defines uniquely $\lt$: Suppose that $\lt'$ also satisfies these properties and is a total ...


1

The "usual order relation" is a creation of laziness. It's the order relation that your intuition comes up with first when you have to define an order relation on the space it's attached to. So for $\Bbb R$, it's the ordering of numbers, for $\{1,2\}$ it's the only "sensible" ordering "up to renaming of the elements" (i.e., $1 < 2$). I hope that clears ...


1

You should look again at what "reflexive" means. It is stated as: $$\forall a\in A [a\leq a].$$ Notice that we are only choosing one object - so you've gone wrong if you've already taken two objects $a$ and $b$. In doing it with one object, you won't need to take $a=b$ for granted, you'll just need to take $a=a$ (which is clearly okay to do). Also, it ...


1

I would assume you meant a binarry relation on $A \times A$. binary relation is a subset of the cartesian product of ordered pairs $A \times A$. if the two elements in $A$ are $x$ and $y$ then four possible ordered pairs are:$(x,x),(y,y),(x,y)$ and $(y,x)$. The number of possible subsets of this cartesian product are $2^4$ ($16$ as desired) from elementary ...


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


1

is reflexive as (a,a);a=1(1)4 exist,is symmetric as (1,2) nd (2,1) exist and transitive as corrosponding term of (2,1),(1,2)- (1,1) exist in this relation.



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