New answers tagged

2

It seems to me that option (3) is correct. $\boxed{(p, m) \text{ is not minimal for }m \geq 3}$: Since $m \geq 3$, we know that $m - 1 \geq 2$, so $(p, m - 1) \in M \times M - \{(p, m)\}$. Since $p \mid p$ and $m - 1 \leq m$, we have that $(p, m - 1) \leq (p, m)$. $\boxed{\text{There is no maximal element}}$: Given any candidate maximal element $(p, q) \in ...


0

This is the integer sequence A001035: for n=18 the number you are looking for is 241939392597201176602897820148085023. The problem has been quite extensively studied: see a detailed discussion on the A001035 link above.


1

"$x$ and $y$ have the same number of prime factors" is easily seen to be transitive (in fact, it's an equivalence relation). "$|x - {100\over{3}}| \leq |y - {100\over{3}}|$" is clearly transitive since $\leq$ is transitive. Thus the intersection of these two relations is also transitive.


3

$S$ is an order relation if and only if: $S$ is reflexive, so $(a,a) \in S$ $S$ is anti-symmetric. This is not the same as not symmetric! Rather, you need to prove that if both $(a,b) \in S$ and $(b,a) \in S$ then $a=b$. $S$ is transitive, so if $(a,b) \in S$ and $(b,c) \in S$, then $(a,c) \in S$. Since $a$ and $a$ have the same number of prime factors ...


3

As pointed out by Zain Patel, divisibility is not an equivalence relation because it is not symmetric. However, since divisibility is reflexive, antisymmetric, and transitive, then it is a partial order.


3

It is not an equivalence relation because it isn't symmetric (despite the symmetric nature of the divisibility notation). This can be seen through a variety of counterexample, such as: $$2 \mid 4 \quad \text{but} \quad 4 \not\mid 2.$$ In fact, it is never symmetric (apart from when $a=b$) because $a \mid b$ requires $a \leq b$ whilst $b \mid a$ requires $b \...


0

If the relation is symmetric, then for all $(x,y) \in R$ that satisfy $x^2 - 4xy + 3y^2 = 0 \rightarrow (y,x) \in R$, so $y^2 - 4yx + 3x^2 = 0$. For $x^2 - 4xy + 3y^2 = (x - 3y)(x - y) = 0$, x must be equal to $3y$ or $y$, but does this ALWAYS imply that $y^2 - 4yx + 3x^2 = (y - 3x)(y - x) = 0$?


2

R is not symmetric because $(3,1)\in R$ but $(1,3)\not\in R$. Note that $x^2-4xy+3y^2=(x-y)(x-3y)$.


2

Let $V$ and $W$ be disjoint open nbhds of $A$ and $B$, respectively. Let $$U=V^2\cup W^2\cup\big(\mho\setminus(A\cup B)\big)^2\;;$$ $U$ is an open nbhd of the diagonal in $\mho^2$, so it’s easily seen to be an entourage of $\delta$. Suppose that $\langle a,b\rangle\in(A\times B)\cap(U\circ U^{-1})$; then there is a $z\in\mho$ such that $\langle a,z\...


0

Transitivity of $I_r$ is easy to check: you can verify it by just following the definition of $I_r$ and transitivity of $R$. (In fact, $I_r$ is an equivalence relation.) To prove that $P_r$ is transitive, examine how to derive the transitivity of strict order relation $<$ from that of the usual order $\le$. It goes as follows: if $x<y$ and $y<z$ ...


0

IF $X,Y$ are nonempty sets and $f:X\rightarrow Y$ is an onto function then $f^{-1}(y)$ defines an equivalence relation on $X$ and Can be used to define a quotient space over $X$. Topology gives you some nice tools of analyzing the space $X$ by its quotient space $Y$. But, set topology is very limited, it has no operation defined over the equivalence factors ...


0

I think that relation doesn't exist, cause $g\circ f\circ\overline{f^{-1}}\Leftrightarrow \{(a,d):\exists b,c:(a,b)\in \overline{f^{-1}} \wedge (b,c) \in f \wedge (c,d) \in g \} $ this means that, $dom(g) $ on right side is subset $dom(g) $ on left side. $g\circ f\circ\overline{f^{-1}} \subset g$ because $g"\{f\circ\overline{f^{-1}}\} \subset g$


2

Take both $f$ and $g$ to be equality on $U$; then $\langle x,y\rangle\in g\circ f\circ\overline{f^{-1}}$ iff there are $u,v\in U$ such that $x\ne u=v=y$, so $g\circ f\circ\overline{f^{-1}}=\overline g\nsubseteq g$.


1

$\require{AMScd}$I don't quite understand the question, but basically, I think you're trying to define a particular double category. Objects. Sets Arrows. Relations Proarrows. Relations Squares. We assume that each square has at most one filler, and that it has a filler iff the condition $$\quad(a,a')\in\alpha\wedge(b,b')\in\beta\implies\...


2

Such a characterisation of 'relations between relations' is not possible. As a counterexample, let $A,B,A',B',\alpha,\beta$ be whatever you want them to be, let $R = \varnothing$, let $R' = A' \times B'$. Then: $(a',b') \in R'$ for all $a' \in A'$ and $b' \in B'$, so the statement on the right-hand side of your $\Leftrightarrow$ symbol is true for all $a,...


0

$1\equiv5\pmod4$, yet $f(1)=3\not\equiv f(5)=11\pmod6$ That is, $f(x)=2x+1$ is not well defined as a function from $\mathbb{Z}_4$ to $\mathbb{Z}_6$; choosing a different representative for $x\bmod4$ gives a different residue class for $f(x)\bmod6$.


0

A relation on $A$ is as such defined to be a subset of $A\times A$. Defining a relation on $A$ is to explicitly enumerate which elements of $A\times A$ that is included in the relation or determine the relation implicitly as those elements in $A\times A$ which are related by some predicate $P(x,y)$. I think you mix up the definitions of the term relation ...


1

Assuming I interpreted your relation correctly, as I described in the comment... For transitivity to hold, we require $\forall S_1, S_2, S_3$, subsets of $A$, $S_1 \sim S_2$ and $S_2 \sim S_3 \implies S_1 \sim S_3$. (or, $(S_1, S_2) \in R$ and $(S_2, S_3) \in R \implies (S_1, S_3) \in R$) Let $S_1 = \{1, 2\}$ Let $S_2 = \{2, 3\}$ Let $S_3 = \{1, 2, 4\}$ ...


0

It is an onto relation from a set of lesser to a set of greater cardinality. Thus it is not a function by definition of cardinality.


1

I'm going to answer the question in the title: The function $f: \mathbb{Z} \to \mathbb{Z}/6$, $x \mapsto [2x+1]$ does not descend to a function on $\mathbb{Z}/4$ because $x_1 \cong x_2 (mod \,\, 4) \nRightarrow f(x_1) \cong f(x_2) (mod \,\, 6)$. You can check this explicitly for the choices $x_1=0$, $x_2=4$.


1

A function $f : \mathbb{Z}_3 \to X$ is just a function $\tilde f: \mathbb{Z} \to X$ making the following diagram commute: \begin{matrix} \mathbb{Z} & \xrightarrow{\tilde f} & X \\ \downarrow & & \parallel \\ \mathbb{Z}_3 & \xrightarrow{f} & X \end{matrix} where the left map is the projection $\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z} = \...


1

In your consideration of the equivalence classes of $0$, you looked at the classes in both $\mathbb{Z}_3$ and $\mathbb{Z}_6$, but for the rest you only looked at the classes in $\mathbb{Z}_6$. If you look at both, the answer will become clear: in $\mathbb{Z}_3$, $\overline{0}$ and $\overline{3}$ are both $\{\ldots, -6, -3, 0, 3, 6, \ldots\}$. So this single ...


1

$\mathbb Z_3 = \{\overline{0},\overline{1}, \overline{3}\}$ where $\overline{0} = \{....,0,3,6,9....\}$ $\overline{1} = \{.....,1,4,7,10.....\}$ $\overline{2} = \{......,2,5,8,11....\}$ $\overline{3} = \overline{0}; \overline{4} = \overline{1};\overline{5} = \overline{2}$. So if $f$ is well defined it'd have to be that $f(\overline {0}) = [0]$ and $f(\...


2

It is easy to show that $\mathbb Z_3=\left\{\begin{array}\{ \{...,-6,-3,0,3,6,...\},\\ \{...,-5,-2,1,4,7,...\},\\ \{...,-4,-1,2,5,8,...\}\end{array}\right\}$ and that $\mathbb Z_6=\left\{\begin{array}\{ \{...,-12,-6,0,6,12,...\},\\ \{...,-11,-5,1,7,13,...\},\\ \{...,-10,-4,2,8,14,...\},\\ \{...,-9,-3,3,9,15,...\},\\ \{...,-8,-2,4,10,16,...\},\\ \{...,-7,-...


-1

It is an onto relation from a set of lesser cardinality to a set of larger cardinality. Thus it cannot be a function (by the definition of cardinality).


1

I guess you want to ask why $f(\bar{x})=[2x]$ is a function but $f(\bar{x})=[x]$ is not, right? So in $\mathbb{Z}_3$, $\bar{0}=\bar{3}$, they are the same thing, so their image under the map should also be the same thing. While under $f(\bar{x})=[x]$, [0] does not equal [3] in $\mathbb{Z}_6$, but under $f(\bar{x})=[2x]$, the image is [0] and [6], they are ...


0

$k \mod 3 \equiv 3n + k\\ f(\bar k) = 6n + 2k \equiv 2k \mod 6$ For every $k$ in the domain everything in the equivalence class of $k$ maps to the same equivalence class in the co-domain. $f$ is a function.


1

In $\mathbb{Z}_3$, $\overline{0}=\{0,3,6,9,\ldots\}$. We have $f(\overline{0})=\{0,6,12,18,\ldots\}$, where we double each element of the set. This new set is exactly $\overline{0}$ in $\mathbb{Z}_6$. We have a choice of how we work in $\mathbb{Z}_n$. We can think of single numbers, with a bar. This is very familiar, but equality is not our usual sense ...


2

You have a rule that given an element of $\mathbb{Z}_3$, you can write down an element of $\mathbb{Z}_6$. The problem is that your rule is not well-defined. To be well-defined means that even if you have two different ways to describe the same input, you get the same output. To be more explicit, observe that in $\mathbb{Z}_3$, the elements $\overline{0}$...


8

If a function $f \colon \mathbb{Z}_3 \to \mathbb{Z}_6$ with $f(\overline{x}) = [x]$ for every $x \in \mathbb{Z}$ would exist, then $$ [0] = f(\overline{0}) = f(\overline{3}) = [3], $$ where we used for the second equality that $\overline{0} = \overline{3}$. By the definition of $\mathbb{Z}_6$ we have for all $x, y \in \mathbb{Z}$ that $[x] = [y]$ ...


2

Sure. The phrase “downward closedness” returns plenty of Google hits from math books. But your example feels clunky, because you’re essentially introducing the proof twice. Just eliminate the “regarding downward closedness” bit and you’re good to go! Some more alternatives: “$S$ is downward closed: …” “$S$ is downward closed. To show this, …” “To show that ...


0

Let's translate the problem into simpler terms. You are given a set $A$ and an equivalence relation $R$. You want a function f on A such that two conditions hold: If $x$ is equivalent to $y$, then $f$ takes on the same value for both. If $x$ is not equivalent to $y$, then $f$ must take distinct values for $x$ and $y$ In symbols, condition 1 is $(x,y)...


-1

We know that an empty set is a subset of all sets. If an empty set is infinite, how will it be subset of all sets. So, an empty set is must be finite.


0

Your intuition is correct, but it's not necessary to add another part to it since what you're suggesting is already implied by the definition of a Relation of a Set. A relation describes what elements in a Cartesian product are related to each other. Say we have set $A$ and set $B$, then $A \times B$ gives us all the possible ordered pairs resulting from ...


0

I think what you're trying to do could be illustrated in the following example, here's a way to define a relation: Let $ \sim $ be a relation over $\mathbb{Z}$ defined by $$ x \sim y \iff (x=y) \lor (x+y=3).$$ In this case, $\sim$ represents $R$ and, by giving the appropriate definition, you can specify which elements are in the relation. In my example ...


0

$R$ is a relation over the set $A$, if and only if, $R$ is a subset of the Cartesian square of $A$.   $$R\subseteq A{\times}A$$ That is unambiguous.   All possible subsets of $A^2$ are each a relation over $A$. Now we can describe some relations by set constructions when given some identified predicate, $P$. $$R=\{(a,b)\in A^2: P(a,b)\}$$ But ...


0

A relation is designed to be as generic a thing as possible, hence why it's just a set of pairs of elements. It's possible to create a rule, or identify a property, that defines the relation, but that's just a shorthand so you don't always have to write out all the pairs manually (which is particularly a pain when the relation isn't finite). It's like how a ...


1

Well I personally disagree with your sense of ambiguity that you feel. I think this definition perfectly encapsulates the intuitive notion of a relation. For example, for $a, b \in A$, the statement "$a$ is related to $b$" can be written in shorthand as $(a,b)$. A "relation" is then a specific way of grouping these related pairs together, so it seems ...


4

Yes. Without loss of generality, suppose that $z$ is the longest of the three numbers. Draw a line segment $AB$ having length $z$. Now draw circles with radii $x$ and $y$ centred at $A$ and $B$ respectively. These circles will intersect at points $P$ and $Q$. The triangles $PAB$ and $PAQ$ have side lengths $x,y,z$.


1

By defintion, $RS$ is the set of all tuples $(x,y)$ where there's some $(x,z)\in S$ and some $(z,y) \in R$. If $S$ and $R$ would be linear maps, this would translate to $S$ maps $x$ to $z(=Sx)$, and in turn $R$ maps $z$ to $y$ so that $RS$ maps $x$ to $y$. For your particular example, $E=\{(x,Ex), x\in \mathbb C^n\}$ and $A^{-1}=\{(Ay,y), y \in \mathbb C^n\...


2

You got it wrong. So, you're looking at a relation $<\,\, \in \mathbb{N}_0 \times \mathbb{N}_0$. By definition, $$<^n \,\,:= \{(a_0, a_n) \mid \exists a_0, a_1, \ldots, a_n \in \mathbb{N}_0 : a_0 < a_1 < \ldots < a_n \}$$ for positive $n$, but $$<^0 \,\,:= \{(a, a) \mid a \in \mathbb{N_0}\} = \,\,\,=$$ and $$<^{-1} \,\,:= \{(b, a) \...


1

If we want to get technical. $\overline 0 = \{a \in \mathbb Z|\exists n \in \mathbb Z: 0 - a = n*4 \}=\{...,-8,-4,0,4,8,12,....\}$ $0 \in \overline 0$ so $f(\overline 0) = [2*0 + 1] = [1] = \{a \in \mathbb Z|\exists n \in \mathbb Z: 1 - a = n*6 \}=\{..., -5,1,7,13,....\}$ But $0 - 4 = 0-1*4$ so $4 \in \overline 0$. So $f(\overline 0) = [2*4 + 1] = [9] = ...


2

$$ f(\overline{7}) = [15] = [3].$$ But $$ f(\overline{3}) = [7] = [1].$$ Since $\overline{7} = \overline{3}$, this is not well-defined.


0

If $P$ and $Q$ are ordered sets, then the product $P\times Q$ is an ordered set, with ordering: $(p,q) \leq (u,v)$ iff $p \leq u$ and $q \leq v$. If $P$ and $Q$ are both partially ordered sets, then $P\times Q$ is also a partially ordered set (Poset).


0

Of course $R$ is reflexive. For all $(a,b)\in\mathbb{R}\times\mathbb{R}$ it holds $(a,b)R(a,b)$ because $a\leq a$ and $b\leq b$; If $(a,b)R(x,y)$ and $(x,y)R(a,b)$, then both $a\leq x,b\leq y$ and $x\leq a,y\leq b$. It follows $a=x$ and $b=y$, so $(a,b)=(x,y)$ Let $(a,b)R(x,y)$ and $(x,y)R(c,d)$. Hence, $a\leq x$ and $x\leq c$, so $a\leq c$. The same for $b\...


1

Partition of a set $X$ is a collection of pairwise disjoint subsets of $X$ such that union of all these subsets gives $X$. Any partition naturally sets an equivalence relation and vise versa. The partition in your question can be set by equivalence relation that can be described in many ways. For example like this: we say that $x$ is equivalent to $y$ if $x$ ...


2

The two things you wanted to know: THE MISTAKE: $x \not= y \land y \not= z \not \implies x \not =z$ Take any counter-example, as in Parth Kohli's comment. $(x,y)$ is an ordered pair, so essentially $(x,y) \in \mathbb{N} \times \mathbb{N}$.


2

A simple counter example will suffice. Take $x=z=1$, $y=2$. Then $x \neq y$ and $y\neq z$, but $x = z$. As to your last question, we use $x,y \in \mathbb{N}$ to mean that both $x$ and $y$ are natural numbers. This differs from $(x, y) \in \mathbb{N^2}$ where $(x,y)$ is an ordered pair.


1

Symmetry follows from commutative of addition. However, it is easy to note that $xRx$ iff $3 | (x+x) \iff 3|2x \iff 3|x$. So the reflexive property fails for any $x$ not divisible by $3$. This equivalence also fails the transitive property, but you need only show one property is not satisfied to show it is not an equivalence. However, you may find it ...


1

The given relation is symmetric since for all $x$ and $y$, $(x+y) = (y+x)$. It isn't transitive since $1R2$ and $2R1$ but 1 is not related to 1.



Top 50 recent answers are included