Tag Info

Hot answers tagged

16

The poset suggested by the hasse diagram below has only one minimal element.


9

A counterexample to the statement is $\Bbb Z \cup \{c\}$, where $c$ is not comparable to any integer. $c$ is then a minimal element, but there is no minimum because a minimum must be comparable to everything else.


5

To build a category, you need a class of objects for any two objects $A,B$ a set of morphisms $\operatorname{Mor}(A,B)$ for any three objects $A,B,C$ a composition $\circ\colon \operatorname{Mor}(B,C)\times \operatorname{Mor}(A,B)\to \operatorname{Mor}(A,C)$ for each object $A$ a specific morphism $\operatorname{Id}_A\in\operatorname{Mor}(A,A)$ (called ...


5

It is not true that any left-total and right-total relation is an isomorphism. Consider $$A=\{0\},B=\{0,1\},R=\{(0,0),(0,1)\}.$$This $R$ does not have an inverse. In fact, these $A,B$ are not isomorphic.


3

Generally, we could say: If there is a unique minimal element, and every non-empty subset has a minimal element, then there is a minimum (and it equals the unique minimal element). which is easily proven - suppose that in the poset $(S,\leq)$ our unique minimal element is $m$ and we consider $S'\subseteq S$ defined by $\{s\in S: m\not\leq s$} - so the ...


3

You can’t list them, but you can describe them, in the sense that for each $x\in\Bbb R$ you can write down a simple description of the equivalence class of $x$: it’s $x+\Bbb Q=\{x+q:q\in\Bbb Q\}$; in all likelihood this is the sort of answer that was intended, though one could wish that the question were worded better.


3

HINT: Think of a triangle whose vertices represent the points of the model, and whose edges represent the relation $R$.


3

By definition $aR^2b$ iff there exists a $c$ such that $aRc$ and $cRb$. So you can check all $3^2$ possibilities $aR^2b$: is $1R^21$? $1R^22$? $1R^23$? $2R^21$? ... For example, is $1R^21$? Well, there is no $(c,1)$ in $R$ so there can be no $c$ such that $(1,c)$ and $(c,1)$ are members of $R$. That is, there is no $c$ such that $1Rc$ and $cR1$. ...


3

The way to prove these things, in general, is to work on each of the three parts separately: show that the relation is reflexive, symmetric, and transitive. For each of these, write what you want to show explicitly, and then follow the general method for showing that kind of statement. For example, for symmetry in this relation, you want to prove that if ...


3

This is what you need to show: reflexive: $(x,x)\in S$; so $x-x \in \mathbb{Q}$, for all $x \in \mathbb{R}$. symmetric: if $(x,y)\in S$, then $(y,x)\in S$, so if $x-y \in \mathbb{Q}$, then $y-x \in \mathbb{Q}$, for all $x, y \in \mathbb{R}$. transitive if $(x,y), (y,z)\in S$, then $(x,z)\in S$; so if $x-y, y-z \in \mathbb{Q}$, then $x - z \in ...


2

Suppose $a=1$ then each of $(1,6)$ and $(1,11)$ are in $R$ so it isn't a function. Note we need to use negative $q$ values for these two pairs in the OP definition, which is OK according to phrasing of the OP's question. $1=5(-1)+6$ and $1=5(-2)+11$ give the two pairs, using respectively $q=-1,-2.$ Even if $q>0$ is required there would still be the ...


2

No, since $R$ should be a subset of $X$. Instead, from your answer we have that $(3,4) \in R$ but $(3,4) \notin X$. So to fix this, we should put $(3,4)$ in $X$. But then since $X$ must be symmetric, what else must also go in $X$? Note that $R$ is a proper subset of $X$ iff every element of $R$ is also in $X$ but $X$ contains an element that is not in $R$. ...


2

Well, you start with the relation defined by $R_1 = \{(6, 4), (4, 7), (3, 3), (5, 1)\}$. Then you need to add exactly those pairs to $R_1$, to become $R$, an equivalence relation, with the stipulation that you cannot add any ordered pair in the relation $\{(1, 2), (6, 1), (2, 4)\}$. Now, if we want our new relation $R$ to be an equivalence relation, it must ...


2

In this answer it is assumed that $\langle1,2\rangle\notin R$, $\langle6,1\rangle\notin R$ and $\langle2,4\rangle\notin R$. You might have meant that $\{\langle1,2\rangle,\langle6,1\rangle,\langle2,4\rangle\}\nsubseteq R$. Then things are different. Based on the date we conclude that each of the sets $\{4,6,7\}$ and $\{1,5\}$ must be a subset of an ...


2

Just play around with some numbers. Consider $3 \in \mathbb N$. What is it related ("equivalent") to? Well $(3, 5) \in R$, since $2 \mid 8$. But $(3,6) \notin R$, since $2 \not\mid 9$. Continuing, we notice that: $$ 2 \mid (a + b) \iff a + b \text{ is even} \iff a \text{ and } b \text{ have the same parity} $$ where by "parity", I mean whether a natural ...


2

You should prove two statements: 1) If $A$ has $m$ elements and $B$ has $n$ elements, then $A \times B$ has $mn$ elements. 2) If $C$ is a set of $k$ elements, then the power set $P(C)$ has $2^k$ elements. Regarding 2): Let $C = \{c_1,\ldots,c_k\}$ and consider the mapping $$f : P(C) \to \{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\}$$ defined in the ...


2

I think $R'$ is the transitive closure of $R$, to find the closure I recommend you draw the digraph of the relation, that is put point of the plane for each of the vertices and draw an arrow from $a$ to $b$ for each pair $(a,b)$ after this draw an arrow from $c$ to $d$ if you can get from $c$ to $d$ using the current arrows. Stop when you have done this for ...


2

If $R$ is a symmetric relation on a set $S$, then what you've shown so far is that $(a,a) \in R^2$ for all $a \in S$. What you have not yet shown is that if $(a,b) \in R^2$ then $(b,a) \in R^2$. Hint: if $(a,b) \in R^2$, then there is a $c \in S$ such that $(a,c)$ and $(c,b) \in R$.


2

You need to find two elements of the order which are incomparable. That what it means that the order is not total. In the case of a power set ordered by inclusion, this means $A$ and $B$ such that $A\nsubseteq B$ and $B\nsubseteq A$. Do note that this requires that $X$ has at least two elements.


2

So far so good. Regarding the last question, the composition of relations works as follows: if $R$ and $Q$ are two relations over the same set, then $x(Q\circ R)z$ iff there exists $y$ such that $xRy$ and $yQz$, that is in loose terms, you can go from $x$ to $z$ via $Q\circ R$ iff you can go from $x$ to some $y$ (via $R$) from which you can go to $z$ (via ...


2

It's not true unless we also know that $B \subseteq X$. Otherwise, for a counterexample, consider $A = \{1, 2\}$ and $B = \{3, 4\}$ and $X = \{1, 2, 3\}$. Then: $$ A = \{1, 2\} = X - B $$ yet on the other hand: $$ A \cup B = \{1,2,3,4\} \neq \{1,2,3\} = X $$


2

A relation is a set of ordered pairs, i.e.a subset of $A^2$. So both $R$ an $S$ are subsets of $A^2$ and one could be a subset of the other. Take any $a\in A$. Since $S$ is reflexive we have that $aSa$, that is $\langle a,a \rangle\in S$. But $S\subseteq R$, so $\langle a,a \rangle\in R$, that is $aRa$. Since this holds for every $a\in A$, the relation $R$ ...


1

Hint: $$(x,x) \in S \subset R $$


1

Saying that a relation $X$ on the set $A$ is reflexive means that $\Delta_A\subseteq X$, where $$ \Delta_A=\{(x,x):x\in A\} $$ Then $$ \Delta_A\subseteq S $$ and, since $S\subseteq R$, …


1

$\begin{align}A \cup B & = (X-B)\cup B \\[1ex] & = \{x: (x\in X \wedge x\notin B)\vee x\in B\} \\[1ex] & =\{x: x\in X \vee x\in B\} \\[1ex] & = X \cup B \\[3ex] A \cap B & = (X-B)\cap B \\[1ex] & = \{x: (x\in X \wedge x\notin B)\wedge x\in B\} \\[1ex] & =\{x: x\in B\wedge x\notin B\} \\[1ex] & = \varnothing\end{align}$


1

By finding counterexamples, i.e. cases where $xRx$ is true for some $x\in\mathbb Z$ (then $R$ is not irreflexive). Or by proving that there are no counterexamples (then $R$ is irreflexive). addendum: Note that $xRx$ in the mentioned relations actually stands for: $x^2\geq1$ $x=x+1$ $x=x-1$ Can you find an $x\in\mathbb Z$ s.t. $x^2\geq1$? Then you ...


1

$$ A = X \setminus B $$ ist the same as $A\cap B= \emptyset$ and $A\cup B = X$ You only have to partition $\{1,2,3\}$ into two disjoints sets: let $B$ run through all subsets and take $A=X\setminus B$


1

Well, 0 is even so $(A,A)\in R$ - that's reflexivity. If $(A,B)$ and $(B,A)$ are in $R$, then $A\subseteq B\subseteq A$ implies $A = B$ - that's antisymmetry. And if $(A,B)$ and $(B,C)$ are in $R$, then $A\subseteq B\subseteq C$ implies $A\subseteq C$. Now, $|C|-|A| = |C|-|B|+|B|-|A|$ is a sum of two even numbers, hence even, so $(A,C) \in R$ - that's ...


1

The answer to your first question "What is the domain of T?" is $\{5, 6\}$ because the definition of a domain of a relation that is frequently used is quite clear: The domain of a relation is the set of the first coordinates from the ordered pairs. Since 4 has no pair, it is not part of the domain. And the answer to your second question "Are there ...


1

You are correct that we need to add $(a, d), (b, c)$. And yes, for the reason you give, for the relation to be transitive requires that since $(c, d), (d, c) \in R$, we also need to add $(c, c)$ and $(d,d)$.



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