Tag Info

Hot answers tagged

4

You're confused. Your statement 1 is incorrect; a correct version would say The empty set can be a set of ordered pairs, because 'Every element of the empty set is an ordered pair' is vacuously true. I mean, if I say "$S$ is a set all of whose elements are purple", then it follows that $S$ is a set of purple elements (perhaps vacuously, if $S$ is ...


2

Yes, you are confused between membership and subset. You have listed $A \times B$ in your third line. As $|A|=|B|=2$, it has $4$ elements. Are any of them $\emptyset$? No, so $\emptyset \not \in A \times B$. It is true that $\emptyset \subset A \times B$. Under $1$, it is not true that the empty set is an ordered pair. The line starting "So surely" ...


2

You want to show that if $\langle A,\le\rangle$ is a partial order that satisfies the law of trichotomy, then $\le$ is a total order on $A$. You need to focus on the goal of showing that $\le$ totally orders $A$: you need to show that for any $a,b\in A$, either $a\le b$, or $b<a$. You should therefore be starting with arbitrary $a,b\in A$, period: there’s ...


2

For each ordered pair of different tuples $\{(a,b),(b,c)\}$ we have to add at most one tuple, namely $(a,c)$. Since there are at most $n(n-1)=n^2-n$ of such pairs, then $|R^+|\le n+n^2-n$


2

If we imagine the set to have $n$ elements numbered $1, 2, \dots, n$, we can picture a relation via a binary $n \times n$ matrix $A$, where $A_{ij}$ is $1$ if $(i, j)$ is in the relation, and $0$ otherwise. Hence, we just have to count such matrices. Now, each relation must be reflexive, so the main diagonal is fixed with all $1$s. The other entries can ...


2

I agree with your solution. Good work supplying your working. (I don't have enough reputation to comment so I'm submitting this as an answer)


2

Suppose that $x\neq y$. Then $g(f(x))=g\circ f(x)\neq g\circ f(y)=g(f(y))$ since $g\circ f$ is injective. This implies $f(x)\neq f(y)$.


2

Your doubts are justified. For $R$ to be reflexive, you must have $(A,A)\in R$ for all propositions $A\in\Omega$. But you don't. Whenever $A$ is false, you have $A\land A = 0$. Therefore $A\not\in R$.


2

When we say, for example, "let $R$ be an equivalence relation on the set $X$", we mean: Suppose we have a subset $R\subseteq X\times X$ such that: 1) $\forall x\in X$ we have $(x,x)\in R$; 2) If $(x_1,x_2) \in R$, then $(x_2,x_1) \in R$; 3) If $(x_1,x_2),(x_2,x_3) \in R$, then $(x_1,x_3)\in R$. So your specific statement is saying you have two such ...


2

$R_1$ and $R_2$ are by definition subsets of $S \times S$ which are reflexive, antisymmetric, and transitive. Now we need to check that $R_1 \cap R_2$ is also reflexive, antisymmetric, and transitive. Reflexive: Since $(a,a)$ must be in both $R_1$ and $R_2$ for any $a \in S$, $(a,a)$ will also be in $R_1 \cap R_2$, so it is reflexive. Antisymmetric: Now, ...


1

reflexivity $\forall x \in S$, we have $(x, x) \in R_1$ and $(x, x) \in R_2$, thus $$ (x, x) \in R_1 \cap R_2 $$ antisymmetry if $(x,y) \in R_1 \cap R_2$ and $(y, x) \in R_1 \cap R_2$, then $$ (x,y) \in R_1 \text{ and } (y, x) \in R_1 $$ thus $x = y$. transitivity if $(x, y) \in R_1 \cap R_2$ and $(y, z) \in R_1 \cap R_2$, we have $$ (x,y)\in R_1, ...


1

A monad in $REL$ is a preorder on a set. To see this, note that we need a $1$-cell $R: A \to A$, a relation, such that we have $2$-cells: $$\eta: id_A \to R$$ $$\mu: R \circ R \to R$$ but these are just inclusions $id_A \subseteq R$ and $R \circ R \subseteq R$. $id_A \subseteq R$ means that if $x=y$ then $x R y$. $R \circ R \subseteq R$ means that if ...


1

If $f$ is not injective, then there exist $x, y \in S$, with $x \neq y$, such that $f(x) = f(y)$. Hence, $(g \circ f)(x) = g(f(x)) = g(f(y)) = (g \circ f)(y)$, so $g \circ f$ is not injective, contrary to hypothesis.


1

First and foremost, please note the corrections given by my colleagues. We discuss questions here...not just doing assignment for you. A matrix of the form $C_{ij}$ below whose entries are either 0 or 1 is called the adjacency matrix of the directed graph of relation $R$. $$B_{ij}=\begin{pmatrix} & 1 & 2 & 3 & 4 \\ \hline 1& - & - ...


1

Suppose that it's true for $n = 1...K-1$, then add a tuple to your $n = K-1$ tuples $R$. $(R \cup \{(a,b)\})^+ = R^+ \cup \{(a,x) : (b,x) \in R^+\} \cup \{(x,b): (x,a) \in R^+\} \cup \{(a,b)\} = R'^+$. So since by inductive assumption $|R^+| \leq (K-1)^2 = K^2 - 2K +1.$, we have that $|R'^+|$ is no greater than $3K^2 -2K + 2$. Okay, that's larger than ...


1

The problem is asking for an intepretation of when $(a,b)\in R^2$, and when $(a,b)\in R^n$, i.e. it is asking for an explanation in terms of people with doctorates and advisors. That $(a,b)\in R^2$ means that there exists some $c$, such that $(a,c)\in R$ and $(c,b)\in R$. This means that $a$ was the thesis advisor of someone who was the thesis advisor of ...


1

A partial order is (a) reflexive, (b) antisymmetric, and (c) transitive. We can make a non-reflexive relation reflexive by relating $a$ to itself, whenever it is not already related to itself. So: For a counterexample to 1., pick any transitive relation that is not antisymmetric. For a counterexample to 2., pick any antisymmetric relation that is not ...


1

There are many, many ways to encode ordered pairs into sets. But they all have one necessary key: you can "decode" the first element, and you can "decode" the second element. In the standard Kuratowski way, $(x,y)=\{\{x\},\{x,y\}\}$, and then $x$ is the unique element which is in both sets that appear in $(x,y)$; and $y$ is either equal to $x$, or it is the ...


1

The axiom of replacement! For the domain of a relation $R$, for instance: to each element $p$ of $R$ we may, definably, associate its left coordinate $p_0$. Then, using replacement, we get the set of all left coordinates, i.e. the domain. (I'm assuming by "domain" you mean $\{x: \exists y ((x, y)\in R)\}.$) Exercise: show that replacement is necessary. ...


1

A pair $\langle a,b\rangle$ belongs to $R^2=R\circ R$ if there is an $x\in A$ such that $\langle a,x\rangle\in R$ and $\langle x,b\rangle\in R$. If $G$ is the digraph for $R$, that means that there’s an edge from $a$ to $x$ and another from $x$ to $b$. In other words, $\langle a,b\rangle\in R^2$ if there is a path of length $2$ in $G$ from $a$ to $b$. For ...


1

(d) Every function on $S$ has a domain that is a subset of $S$: let's say a given domain has size $k$. Then for each member of the domain we choose another member of $S$ as its image under the function. That means $n^k$ possible choices for that domain. The number of domains of size $k$ is of course ${n \choose k}$. So the total number of functions is ...



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