# Tag Info

0

Sorry, that was my mistake. I haven't read my book carefully. There's small paragraph saying: for relations we define $R^1\equiv R$ and $R^{n+1} \equiv R^n\circ R$. Thanks for help. Next time I will read all the definitions carefully before I post a problem here :)

1

I think you got the definition of $R^2$ wrong. Here is the correct definition: Let $R$ be a relation on the set $A$. Then $R^2$ is defined by $$R^2 = \{(x,y)\ |\ \exists z\in A\text{ such that } (x,y)\in R\text{ and }(y,z)\in R\}.$$ So $R^2$ is not a set of ordered pairs of elements from $R$. It is a set of ordered pairs of elements from $A$, the same type ...

1

The problem makes more sense if we assume that the $\times$ that appear in it is not the Cartesian product, but an unusual notation for composition of relations, which is more commonly notated with $\circ$: $$R\circ S = \{ \langle a,c\rangle \mid \exists b: \langle a,b\rangle\in S \land \langle b,c\rangle\in R \}$$ In that case we can indeed have $R\circ ... 1 It is enought to prove that if a relation$R$is transitive and reflexive then$R^2=R.$By definition of transitive realtion we have that$R^2 \subseteq R.$Let us prove that$R \subseteq R^2.$Let$(a,b) \in R$. Since$R$is reflexive then$(b,b) \in R$. Then by definition of composition we get that$(a,b) \in R^2.$Thus$R^2=R.$0 If$\mathcal{R}$is a relation between$X$and$Y$and$x_1, ..., x_m$is an ordering of the elements of$X$and$y_1, ..., y_n$is an ordering of the elements of$Y$, then the matrix$M$of$\mathcal{R}$is a$m \times n$matrix such that$m_{i,j} = 1$if$x_i \mathcal{R} y_j$and$0$otherwise. In your example,$X = Y = \{1,2,3\}$and the ordering is$1, ...

2

For your first question, $f$ is not the least upper bound of $b$ and $c$: $b\le d$ and $c\le d$, so $d$ is an upper bound of $b$ and $c$, and $d<f$, so $f$ cannot be the least upper bound of $b$ and $c$. There is no upper bound of $b$ and $c$ that is smaller than $d$, but $d$ is still not the least upper bound, because we also have $b\le e$ and $c\le e$: ...

0

Your solutions to $(2)$ and $(3)$ are correct. $(1)$ is a bit tricky. You might think that the Hasse diagram below would do the trick, with $\{b,c\}$ as a subset with no infimum: a / \ b c However, the supremum of the empty set is the infimum of the whole partial order, so if every ...

3

$R:=\{(1,2),(2,1)\}$ is not transitive. $R\circ R=\{(1,1),(2,2)\}$ is transitive.

0

Let $R$ be the relation in $\mathbb{R} \times \mathbb{R}$ defined by $R=\{(x,y) : \vert x-y \vert =1\}$. It is easy to see that $R^2$ is reflexive and $R$ is not.

0

This relation is vacuously transitive as there is no case where $(a,b)\in R$ and $(b,c)\in R$ so the hypothesis for transitivity is never satisfied.

1

HINT: $S\times S$ is the set of all ordered pairs of sequences of real numbers; it is indeed infinite, since $S$ is. The relation $R$ has all but one of the properties of reflexivity, transitivity, antisymmetry, and symmetry, but this has nothing to do with pairing real numbers: members of $R$ are pairs of sequences of real numbers, not pairs of real ...

1

The three properties required for an equivalence relation are 1) reflexive: for any $x$ in the set $(x, x)$ is in the relation. That is obviously true here- the set is $\{1, 2, 3\}$ and we have $(1, 1), (2, 2), (3, 3)$ in the relation. 2) symmetric: if $(x, y)$ is in the relation then so is $(y,x)$. Again that is obvious. The only pairs in the relation ...

0

$R^{-1}=\{(x,y)\in \mathbb{N}\times\mathbb{N}:(y,x)\in R\}$ =$\{(x,y)\in \mathbb{N}\times\mathbb{N}:(y,x)\in \{(a,b):a<b\}\}$ =$\{(x,y)\in \mathbb{N}\times\mathbb{N}:y<x\}$ and change the letters.

1

whatever the parity of $a$ and $b$ we have $a-b=(a+b)-2b$ this shows that $$2|(a+b) \Leftarrow\Rightarrow 2|(a-b) \tag{1}$$ keeping this in mind throughout, we notice that if $$a^2 \equiv b^2 \mod 4$$ then $$4|(a^2-b^2)=(a+b)(a-b)$$ from which $$2|(a-b)$$ or $$a \equiv b \mod 2$$ given (1), these steps are reversible

1

$A$ acts on the set of positive integers, so reflexivity requires that every positive integer relates to itself, or for $x \in A, R(x,x)$. Hopefully, you can find a counterexample. Similarly, symmetry requires that for all $x,y \in A, R(x,y) \to R(y,x)$, and transitivity is defined as usual, acting on all elements on $A$. From there, you should be able to ...

0

Observe that both the accounts and the people to whom they are assigned are distinguishable. Case 1: Teresa works only on the most expensive account. Joan must distribute six accounts to the other three administrative assistants. If there were no restrictions, Joan could assign each of the six accounts to one of three people. There are $3^6$ ways to ...

2

I think you have to assume you are distributing distinguishable objects into distinct containers. You need to use Stirling numbers of the second kind or something similar. The answer in the book seems to be $S_2(6,3)\times 3! + S_2(6,4)\times 4! = 90 \times 6 + 65 \times 24$. I might do it another way and say that you have to distribute $7$ accounts onto ...

1

It is reflexive! $xRx$ is: are you born less than one week apart... from yourself? But of course.

1

A relation is a set of ordered pairs, which maps from one set, called the domain, to another set, called the co-domain.   Here $A$ is the domain, and $B$ is the co-domain.   All the sets given in the OP are indeed relations of $A\to B$; but are they functions? A function is a relation where any element of the domain is mapped to at most one ...

0

A function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. So, according definition of function, given relations with domain $A = \{0, 2, 4, 6\}$, $(a) \{(6, 3), (2, 1), (0, 3), (4, 5)\} = \{ (0, 3),(2, 1), (4, 5),(6, 3)\}$ is function , since it defines for every ...

10

You don't need infinite sets at all - a set with two elements is enough. Suppose $a\not=b$. Then $a\not=b$ and $b\not=a$. But $a=a$! Indeed, "$\not=$" isn't transitive on any set with at least two elements.

9

For example $1\neq 2$ and $2\neq 1$, but is $1\neq 1$?

1

A relationship $R$ is reflexive if, for all $x$, it's true that $x R x$. $$\textsf{Is }\lvert x-x\rvert = 2 \textsf{ universally true?}$$ A relationship $R$ is reflexive if, for all $x,y$, it's true that $x R y\to y R x$ $$\textsf{Is }\lvert y-x\rvert = 2 \textsf{ true whenever }\lvert x-y\rvert = 2\textsf{ is true?}$$ A relationship $R$ is ...

2

Hint Go back to the definitions: $S$ is reflexive iff for every $x\in A$, we have $(x,x)\in S$. Since there are no pairs $(a,b)\in S$, what can you conclude? $S$ is symmetric iff whenever $(x,y)\in S$ then $(y,x)\in S$. Since there are no pairs $(x,y)\in S$, what can you conclude? $S$ is transitive iff ... . What can you conclude?

1

Sets $R=\{(a,b)\}$ and $S=\{(a,c)\}$ are nonequal and have an empty intersection, so their set difference $R \setminus S$ is actually equal to the set $R$. This set is nonempty, so its projection is also nonempty. However tuples $(a,b)$ and $(a,c)$ have the same first element, so when we make projections at first, we get the same set in both cases: $P_1(R) ... 0 Suppose that$(x,y)\mathcal{R}(a,b)$and also that$(a,b)\mathcal{R}(u,v)$. We wish to show that this implies that$(x,y)\mathcal{R}(u,v)$. Since$(x,y)\mathcal{R}(a,b)$, by our definition of$\mathcal{R}$that means that$x+b=y+a$. Since$(a,b)\mathcal{R}(u,v)$, by our definition of$\mathcal{R}$that means that$a+v=b+u$. Now, try to combine those two ... 0 You can't just write the implication. If that was the case you could just right that and you would be done. You need to suppose that$(x,y) R (a,b)$and$(a,b)R(u,v)$then use the definitions of the relation to prove it.$(x,y) R (a,b) \implies x+b=y+a(a,b)R(u,v) \implies a+v=b+u$you want to show$x+v=y+u$now using the last two lines above can you ... 0 When answering the question, you only care about$x,y$such that$x=y$. Has anybody ever been born more at least a week before or after the day on which s/he was actually born? It's ridiculous, right? You can visualize this as a calendar, starting about 100,000 years ago and stretching, oh, let's hope far into the future. Each day of the calendar is filled ... 2 Divisibility is not antisymmetric on your$A$because$-2\mid 2$and$2\mid{-2}$. 0 If$xRy$iff$x$and$y$were born less than one week apart, we have that$xRx$, for all$x$, because$x$is born exactly the same day of$x$. See Reflexive relation : In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself. In other words, a relation$R$on a set$A$is reflexive when$xRx$holds ... 3 Let me see. Never heard of those, but try looking at this Wiki page; Absolutely correct; Correct when$X,Y$are finite, might extend to infinite sets with some transfinite arithmetic, I don't know; e.g.,$|\mathbb{Q}|^{|\mathbb{Q}|}$is not really clear; on the other hand,$2^{|\mathbb{Q}|}=|\mathbb{R}|$, if we want this relation in your 3) to continue ... 0 Maybe it's wise first to establish a definition of a partial function that we can all accept, and then address your question from there. This definition is motivated by a wikipedia article about "Partial Functions": A partial function$f$on$S$is a function whose domain is contained in$S$. From this, and, relative to your question, the only way to ... 1 You have to understand the various definitions. For example, to check associativity, ask yourself what needs to be verified. In case of the operation$\starwe need to check if $$(a \star b) \star c=a \star (b \star c)?$$ Start with left side: \begin{align*} (a \star b) \star c & = (a \star b)^2 + c^2\\ & = (a^2+b^2)^2+c^2. \end{align*} ... 1 Hint You have to recall that a (binary) mathematical "operation" is a relation, i.e. a set of pairs; thus, applying the set definition of relation to the newly defined "operation"⋆$, we have that :$(a,b) \in ⋆$iff$a^2 + b^2$. We say that a mathematical operation$\circ$is commutative when :$x \circ y = y \circ x\quad\text{for all }x,y$. ... 2 In general, I try to explain abstract algebra as the study of common operations. For example, we use the "+" operation in many contexts: we can add integers, real numbers, complex numbers, vectors, polynomials, matrices, continuous functions, hours in the day, and in many other contexts. All of these "+"'s have similar properties, they are commutative and ... 2 Reflexivity It means that$x \rho x$. That translates to $$\left(x^2 - x^2\right)\left(x^2x^2 - 1\right) = 0 \neq 1$$ So$\rho$is not an equivalence relation. We don't need to check the other properties. 0 You call it...$S$. There's no name for it in terms of$f$, because there's always a still larger set$T\supsetneq S$, and then what would that be called in terms of$f$? Typically,$S$is fixed in context -- it's, for example, the reals$\Bbb R$, or the positive reals$\Bbb R^+$, and so on.$f$simply doesn't carry information about possible supersets of ... 5 If$a \in [[x]]_R$, then$xRa$. We know that$xRy$and$R$is symmetric, hence$yRx$. By transitivity, we get$yRa$. Thus$a \in [[y]]_R$. Now just exchange the roles. 1 Let$b \in [[x]]_R = [[y]]_R$. Then$b R x$and$b R y$. By symmetry and transitivity$x R y$. 1 Equivalence relation is a subset of$A\times B$, not an element of it, so$R\notin A\times B$but$R\subset A\times B$. Equivalence relations are only defined in case$B = A$. An easy reminder is: any point must be equivalent to itself, so$(a,a)\in R$for all$a\in A$. Of course that implies$R\subset A\times A$(or at least$A\subset B$). Since$(a,a)\in ...

0

A function, by definition, must be well defined and defined everywhere. Here the problem is with the later. Your relation is not defined everywhere. A relation $\sim$ is defined everywhere if every element in the domain set is related to at least one element in the codomain. i.e. $\forall x\in D \ \exists y\in C \ s.t. \ (x,y)\in R$ where $R$ is the ...

3

You specified a function as follows: $$f(2)=3, f(3)=3, f(4)=2, f(5)=1$$ This is not completely defined on the domain, as $1$ is not sent anywhere. If instead you misunderstood the usual way functions are defined, you might argue that you instead defined the function $$f(3)=2, f(3)=3, f(2)=4, f(1)=5$$ This would of course be wrong, but also still not be a ...

1

Let us take $r \in P(\mathbb{N}, \mathbb{N})$, and suppose that we have $s \in P(\mathbb{N}, \mathbb{N})$ such that $r = s^2$. Let us say there is some $(a,b) \in r$, then there must be $c \in \mathbb N$ such that $(a,c)$ and $(c,b)$ are in $s$. Let us then suppose that there is also $(a,c) \in r$, then there is $(a,c')$ and $(c', c)$ in $s$, for some ...

0

First, re 4. For a relation to be reflexive doesn't mean that the only things it relates are identical! (There would be little use for the word "reflexive" in that case, as the only such relation on a set is the identity relation.) For example, consider $n\sim m \iff$ integers $n,m$ are either both even or both odd. This is an equivalence relation on the ...

2

Let $U=\{a,b,c,d,e\}$. A reflexive relation on $U$ must contain each of the pairs $\langle a,a\rangle,\langle b,b\rangle,\langle c,c\rangle$, $\langle d,d\rangle$, and $\langle e,e\rangle$. That’s $5$ of the $25$ possible ordered pairs. Each of the other $20$ ordered pairs in $U\times U$ is optional: a reflexive relation on $U$ may contain it but need not. ...

1

You’re missing part of the definition of a wqo: it must be a quasi-order, meaning that it must be reflexive and transitive. Equivalently, $\preceq$ is a wqo on $A$ iff it is a well-founded quasi-order with no infinite antichain. This means that a partial order with an infinite antichain is not a wqo even if it’s well-founded. For example, the order $\preceq$ ...

0

There isn't really a general principle, because the general statement is false, although for some equivalence relations the composition is an equivalence relation (e.g. if both are the identity). What you need is a counterexample to show that the statement isn't always true. Consider two equivalence relations on $\{1,2,3\}$ given by their partitions as ...

3

Just a speculation. In case of partial ordering (for example, with respect to a cone) there are normally more situations than just $\ge$ and $>$. It may happen that a vector $a\ge 0$ (in the cone), $a\ne 0$ (not a vertex), but not yet $a>0$ (in the sense of the cone interior). It is where the demand for more notation symbols is most likely to come ...

2

Let $X$ be the set $\mathbb{N}$ of natural numbers, and let $R$ be $=$, the usual equality relation. Then $=$ is symmetric, because $x=y$ and $y=x$ mean the same thing. However it is not true that all natural numbers $x$ and $y$ fulfill $x=y$. For example $1=2$ is not satisfied. If $x$ equals $y$, then $y$ equals $x$. But not all pairs $x,y$ are like that. ...

3

Yes $<$ and $\lneq$ are the same relation. However, be careful about set inclusion: older texts, and some current mathematicians, use $\subset$ to mean $\subseteq$, and to indicate strict inclusion they might use $\subsetneq$ or $\subsetneqq$. Other authors who use both $\subset$ and $\subseteq$ will use $\subset$ to mean strict inclusion. These days, ...

Top 50 recent answers are included