Tag Info

New answers tagged

0

a and b are asymmetrically equivalent. Note: I think this question was misinterpreted in the other answers. GitGud posted "asymmetric" in the comments but not as an answer. After leaving it up for a week I settled on "asymmetrically_equivalent" as a function name. I'd like to credit GitGud instead of myself but it seems this question has gone stale, so I'm ...


2

To show $R[A \cup B] = R[A] \cup R[B]$ for a relation $R \subset X \times Y$, $A,B \subset X$, we have to show two inclusions. So take any $y \in R[A \cup B]$; this means that there exists $x \in A \cup B$ such that $(x,y) \in R$. Then either $x \in A$, and then $y \in R[A]$, or $x \in B$ and then $y \in R[B]$. In either case $y \in R[A] \cup R[B]$, as ...


3

$$\frac{x^2}{y^2}+\frac{y^2}{z^2}+\frac{z^2}{x^2}=\frac{1}{2}\bigg(\frac{x^2}{y^2}+\frac{y^2}{z^2}\bigg)+\frac{1}{2}\bigg(\frac{x^2}{y^2}+\frac{z^2}{x^2}\bigg)+\frac{1}{2}\bigg(\frac{y^2}{z^2}+\frac{z^2}{x^2}\bigg)\geq \frac{x}{z}+\frac{z}{y}+\frac{y}{x}$$ and "=" holds iff $x=y=z$.


-2

Setting $x=y=z$ we get: $$\frac{x^2}{x^2} + \frac{x^2}{x^2} + \frac{x^2}{x^2} = \frac{x}{x} + \frac{x}{x} + \frac{x}{x}$$ $$\Leftrightarrow$$ $$1+1+1=1+1+1$$ which is true $\forall x,y,z\in\mathbb{R}$.


0

a) There is a difference between antisymmetrical and asymmetrical. If '$a$ taller than $b$' implies here that $a$ and $b$ have not the same length then the relation is not antisymmetrical but asymmetrical. In fact if: $$\left(a,b\right)\in R\wedge\left(b,a\right)\in R\Rightarrow a=b$$ then $R$ is antisymmetrical. If: $$\left(a,b\right)\in ...


1

From part (a), you know all the elements of $M$ are square matrices. You just need to show that the relation is therefore symmetric and transitive. Adding more detail: We know all elements of $M$ are square matrices. Symmetry: If $(m_1, m_2) \in R$, then the matrix multiplication $m_1 m_2$ is defined. Therefore both matrices must be the same size ($n ...


0

To understand your specific example, we have to refer to Lamport'book, which I'm not able to browse. In general, a relation is not defined as "the smallest" something ... See order relation : A partial order on a set $X$ is a relation $R ⊆ X^2$ such that (i) $(x, y) ∈ R$ and $(y, z) ∈ R$ implies $(x, z) ∈ R$ (ii) $(x, x) ∈ R$ for all $x, ...


1

In the example you mentioned in the comments, the author is defining a relation something like this: $R$ is the smallest relation satisfying: If $a$ and $b$ are ... then $aRb$. If $a$ and $b$ are ... then $aRb$. ... In this case, the use of "smallest" is just like the use of "if and only if" rather than "if". Let's say I define a ...


0

Your proof is a bit jumbled. In its principle it is the same proof as sketched by William, but your proof is harder to read for two reasons. You are using $f$ for the a choice function and $h$ is in fact the function you prove to exist. That's fine, but it is confusing to the reader. The way you find the choice function is a bit cumbersome. You are correct ...


1

Here is a sketch of a proof using the axiom of choice: Let $R$ be a relation on $A$. For each $a \in A$, let $X_a = \{b \in A : b R a\}$. By the assumption on the relation $R$, $X_a \neq \emptyset$. Let $\mathcal{X} = \{X_a : a \in A\}$ ($\mathcal{A}$ is a set by the axiom of replacement). Since $\mathcal{X}$ is a family of nonempty sets, the axiom choice ...


1

Just don't call it a pullback. Yes this is ok.


13

$ m \mid n$ means that $m$ divides $n$. We could also say that $n$ is divisible by $m$ AND we could also say that $n$ is a multiple of $m$,so $n= a \cdot m, a \in \mathbb{Z}$.


1

The first thing you need to do is to get the definitions absolutely clear. A (binary) relation $R$ on a set $A$ is not a subset of $A$, it is a subset of $A\times A$. In other words, $R$ does not consist of elements of $A$, it consists of pairs of elements of $A$. A relation $R$ on a set $A$ is transitive means: for all $a,b,c\in A$, if $(a,b)\in R$ and ...


2

You are very close. For brevity, denote $R$ composed with $R$ by $R\circ R$. By the definition of composition, the pair $(a,c)$ is in $R\circ R$ if and only if there exists a $b$ such that $(a,b)$ and $(b,c)$ are both in $R$. But if there is such a $b$, then by transitivity $(a,c)$ is in $R$. Thus if $(a,c)$ is in $R\circ R$, then $(a,c)$ is in $R$. ...


3

It means that $\leq$ is a total relation: any two elements can be compared. To see this, look at the contrapositive: $$a \neq b \implies (a < b) \lor (b < a)$$ Equivalently, the statement is: $$(a = b) \lor (a < b) \lor (b < a)$$


0

As far as I know this is just simplifying the expressions: $\begin{align} \neg (a<b) \text{ and } \neg(b<a) \iff a \geq b \text{ and } b\geq a \iff a = b\end{align}$ This is under the assumption that $a,b$ are real numbers, which I assumed since the notation of the OP indicates use in programming languages.


1

Call $R^+$ the relation coming from the intersection. Define $R^*$ the relation coming from the chains. It is easy to show that $R^*$ is a transitive relation containing $R$. So $R^+ \subseteq R^*$. Now suppose $R'$ is an arbitrary transitive relation containing $R$. Note that $R^* \subseteq R'$. This implies $R^* \subseteq R^+$.


4

An $n$-ary (or $n$-place) function symbol is an expression which combines with $n$ terms to form another term. (If you like, think of the symbol coming with $n$ slots to be filled in; and when the slots are filled, we then get a complete term.) For example, in arithmetic the function symbol '$+(\ldots,\ldots)$' combines with the two numerals '$2$' and '$4$' ...


4

$\varnothing$. It's transitive and symmetric by vacuous arguments. But it is not reflexive since $(n,n)\notin\varnothing$ for all $n\in\Bbb N$!


1

We consider the set $\mathbb N$ of all natural numbers.Then the relation: $a$ ~ $b$ $\iff a=b\neq1$ is transitive, symmetric, but not reflexive


5

Define $$R = \{(m, n)\mid m, n\in \mathbb N \;\text{ and }\;m, n \text{ are both even}\}$$ Then, for every odd integer $t\in \mathbb N$, $(t, t)\notin R$, hence reflexivity fails. Recall that for reflexivity to hold, it must be the case that for every $n\in \mathbb N$, $(n, n) \in \mathbb N$. No exceptions. However, it is easy to verify that $R$ is both ...


1

The name is the distance formula. Distance travelled = rate $\times$ time travelled The formula Distance = Rate x Time expresses one of the most frequently used relations in algebra Note the chart


1

You could say distance is jointly proportional to speed and time (the constant of proportionality is 1). Or you could say speed is proportional to distance and inversely proportional to time.


2

A relation on $A$ is a subset of $A\times A$. A reflexive relation, in this case, is any relation $R$ such that $(1, 1) \in R$ and $(b, b)\in R$ and $(\varnothing, \varnothing) \in R$. Any subset of $A\times A$ containing those three ordered pairs is reflexive. One such relation is given by $R_1 = \{(1, 1), (b, b), (\varnothing, \varnothing)\}$. Another ...


1

Let $S = A \cup B$, let $\mathcal{R} \subseteq A \times B$, and let $(x,y) \in \mathcal{R}$. Then $x \in A \subseteq S$ and $y \in B \subseteq S$, so $(x,y) \in S \times S$. Therefore $\mathcal{R} \subseteq S \times S$. (At least, I think that's what's being asked...)


3

$f(x)=x^2\sin x$ and $g(x)=x.$


1

The identity function $1_X \colon X \to X$ on a set $X$ induces an equivalence relation on $X$ since it partitions $X$ into its singleton sets. A function $f \colon X \to X$ is symmetric if and only if $f(f(x))=x$ for all $x \in X$, so $f$ must be an involution, which is to say $f^2 = 1_X$. If $\lvert X \rvert > 2$, then $f \colon X \to X$ cannot be ...


2

Let $$f(x)= \begin{cases} x^2 & 2n\le x<2n+1 \\ 1 & 2n+1\le x < 2n+2\end{cases}$$ and $g(x) = x$.


3

I would prefer to speak about a "functional relation" here rather than a "function", because the latter wording implies that the only thing you're planning to do with it is to apply it to inputs, and here you're doing something quite different. That being said, here are some comments on your observations: $f(x)=−x$ is total and symmetric, In general a ...


1

Here are some ideas that can help: For $f:\mathbb{R} \longrightarrow \mathbb{R}$ to be symmetric you need $f(f(x))=x$ (because we need if $(x,y) \in f$, then $(y,x) \in f$. Now functions of the form $f(x)=x$ and $f(x)=-x+c$ will satisfy this condition.


0

Suppose $S$ has $n$ elements. Then $S \times S$ has $n^2$ many elements. But to be reflexive, it should contain all diagonal elements $(s,s)$, for $s \in S$, so there are $n^2 - n$ many elements of $S \times S$ that we can either put in a reflexive relation or not. So we have $2^{n^2 - n}$ many such relations, because every subset of $S \times S \setminus ...


1

Consider the set $A \times A$ which has $n^2$ elements. The requirement that your relation $R$ be reflexive says that $(a,a) \in R$ for all $a$. So out of the $n^2$ elements of $A \times A$, $n$ of them are required to be in $R$. What remains is $n^2-n$ elements of $A \times A$, each of which may or may not be in the relation. The subsets of these $n^2-n$ ...


2

There are $2^{n^2}$ subsets of $S\times S$ if $|S|=n$. You're looking for subsets which contain the diagonal, $\Delta(S) = \{(s,s): s\in S\}\subseteq S\times S$. So this is just a matter of choosing which other sets are a part of your relation, i.e. any other collection of sets can be thrown in, off-diagonal, which is to say: subsets of $$S\times ...


1

It's somewhat of a logical subtlety. A relation $R$ is transitive iff: $\forall x,y,z : (xRy \wedge yRz) \Rightarrow xRz$. A relation $R$ is symmetric iff: $\forall x,y : xRy \Rightarrow yRx$. Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P \Rightarrow Q$ is true whenever ...


1

The relation $\sim$ is reflexive if whenever $x \sim y$, it is also true that $y \sim x$. In other words, if there is no pair $x, y$ with $x \sim y$ and $y \not\sim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the ...


0

I'll hazard an answer. What to do would depend on the network and what you want to look for. Generally it's better to start with a hypothesis and test for it, rather than diving in trying to "find something interesting". I suggest you play around with it manually, e.g. try drawing the data (or parts of it) in different ways, until you find something you ...


1

Part of the reason is "historical". Function is a typical mathematical concept and has its origin in the idea of "recipe" or "procedure" which, taking an input $x$ "produce" an output $y$. Paradigmatic examples are the simple mathematical functions like : "double of __" (i.e. $y = 2 \times x$), "square of __" (i.e. $y = x^2$). The concept of relation is ...


2

The general way to construct a matrix for a relation between to finite sets $\{a_1,a_2\dots a_m\}$ amd $\{b_1,b_2\dotsb_n\}$ is to create an $m\times n$ matrix X where $x_{i,j}=1$ if $a_i$ is related to $b_i$ and $0$ if they are not related. In this case the matrix would look like this: $$ \begin{matrix} 0 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 ...


2

$(a,b)\in R$ if $a<b$ this means, that $(1,3),(1,5),(2,3),(2,5),(3,5),(4,5)\in R$


0

put $n$ instead of 12. the sum of the integers is bounded by $6n-15$, whilst there are $2^6-1$ non-empty subsets


3

As $|A| = 6$, $|\mathcal P(A)| = 2^6 = 64$, so there are at most 64 distinct sums. Now, note that $12 + 11 + 10 + 9 + 8 + 7 = 57$, and so no subset of $A$ can sum to more than $57$, by distinctness of the elements of $A$. Further, as each element of $A$ is positive, no subset of $A$ can sum to less than $0$. Therefore, the possible sums for subsets of $A$ ...


2

There are $2^6=64$ possible subsets of $A$, the sums of all of them is less than $12+11+10+9+8+7=57$. There is not enough room for the sums to be all distinct.


0

What you've written is fine, for those values, but it tells us nothing about the truth value of $(1, 2)$ with respect to $S\circ R$. So I would add that for $x \in S$, you expand your answer (words will do). E.g., Putting $U = \{1, 2, 3, \ldots, 11, 12\}$: Then for all $x \in U, \;x \notin \{3, 6, 9\}$, for all $y \in U$, $(x, y)\notin S\circ R$, i.e., ...


2

We have $\def\R{\mathrel R}\def\S{\mathrel S}$ $$ R \circ S = \{(x,z) \mid \exists y. \, x\S y\land y \R z\} $$ hence $$ R \circ S = \{(3,6), (6,3), (9,2)\} $$


1

Congruence relations on $\mathfrak{A} = (A, F)$ can be also viewed as the equivalence relations on $A$ which are the subalgebras of $\mathfrak{A} \times \mathfrak{A}$. Consider $\mathfrak{B} = (A \times A, F, t, (\cdot)^{-1}, \triangle_{A})$, where $\triangle_{A} = \{(a, a)\ |\ a \in A\}$ is the set of nullary operations. $(a, b)^{-1} = (b, a)$ is the ...


2

Given a number $x$, we have $yRx \iff y=x+n$ for some integer $n$. So the equivalence class of $x$ is $x+\mathbb{Z}$, that is, {$...,x-2,x-1,x,x+1,x+2,...$}. The set of all such equivalence classes is the partition formed on $\mathbb{R}$. Now, $xRy$ iff $x$ and $y$ have the same decimal part. For example, $1.23R5.23$. So the distinct equivalence ...


0

For those interested in the thing here it is. Let $w\in X$. This means that w is actually one the equivalent classes of mod for example congruence modulo 5 will have 0,1,2,3,4 as it cases. $x\equiv 1 \mod 5$ is what x subtract by 1 is divisible by 5. So then you do $x\equiv w\mod (m)$. By the symetry $y\equiv x \mod(m)$ then by the transitivity $y=w ...


0

You want the equivalence relation $R$ such that $(a,b) \in R$ iff $a, b \in A_i$ for some $i$. In general, partition $\left\{A_i\right\}_{i \in I}$ corresponds to the equivalence relation $$R = \bigcup_{i\in I} A_i \times A_i$$i.e. the union of Cartesian squares of each set in the partition.


3

The partitioning of $A$ into subsets/cells induces (and is induced by) the following relation $$R = \{(1, 1), (2, 2), (3,3), (4, 4), (5, 5), (6, 6), (1, 3), (3, 1), (1, 5), (5, 1), \\ (3, 5), (5, 3), (4, 6), (6, 4) \}$$ such that for any $a, b\in A$, $(a, b) \in R$ if and only if $a$ and $b$ are in the same subset/cell of the partition. N.B. ...


0

$$a,b\in A\;,\;\;\;aRb\iff a,b\in A_1\;\;or\;\;a,b\in A_2\;\;or\;\;a,b\in A_3\iff$$ $$R=\left\{(1,1),(2,2),...,(6,6), (1,3),(3,1),(1,5),(5,1), (3,5), (5,3) (4,6),(6,4)\right\}$$



Top 50 recent answers are included