Tag Info

New answers tagged

0

I believe the above by mathcounterexamples.net takes care of the second question you ask about quite nicely. As for the first question, I think this is where you are misunderstanding transitivity. Transitive is $(a,b)$ AND $(b,c)$ implies $(a,c)$. The relation need not be symmetric, so the order matters. It is the second coordinate of the first and the ...


1

Regarding your first point. To evaluate transitivity you have to look at two couples $(a,b),(b,c)$ in your relation set and verify that $(a,c)$ also belongs to it. Hence, you don't need to evaluate $(2,4),(3,4)$. Regarding your second point. Name $R=\{(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)\}$. You have $(0,2) \in R$ and $(2,3) \in R$. If ...


0

Let $R_1$ be a relation on a set $A$ and if we are required to show that it is not transitive relation then we have to show that there exists $a,b,c\in A$ such that $(a,b),(b,c)\in R_1 \not \Rightarrow (a,c)\in R_1$ $R=\{(x,y):x\text{ is wife of }y\}$ In case of $R$ if $(x,y)\in R$ then there is no $z$ such that $(y,z)\in R$. Since we are unable to show ...


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


0

Here's an illustrative example to get you going. We take the relation $$R=\{\color{red}{(1,2)},\color{blue}{(2,1)},\color{green}{(3,3)}\}$$ on the set $A=\{1,2,3\}$. For the matrix representation, we write $1$ in cell $(i,j)$ whenever $(i,j) \in R$, and $0$ otherwise. In this case: $$ \begin{bmatrix} 0 & \color{red}{1} & 0 \\ \color{blue}{1} & ...


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


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

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


0

In short, you've got the right ideas. The matrix representation for $p$ is $$\begin{array}{c|ccc} &a&b&c&d&e\\ \hline a&0&0&1&0&1\\ b&1&0&0&0&0\\ c&0&0&0&0&0\\ d&0&0&0&0&0\\ e&0&0&0&1&0 \end{array}$$ You are also correct that $p$ is not ...


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

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$


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


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)


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


0

The statement you made between 1 and 2. Shows that the empty set is a subset of $A\times B$ not an element of it.


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


0

I think not. If $f=\varnothing$ (the empty relation), then $f$ is not a function as long as the underlying set is non-empty, but for any other binary relation $g$, one has $g\circ f=\varnothing$.


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


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


0

Yes, there can be many relations which are neither symmetric nor antisymmetric . For example; Consider a set $S={a,b,c,d}$ and the relation on $S$ given by $$R=\{(a,b), (b,a), (c,d)\}.$$


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



Top 50 recent answers are included