Why are Noetherian Rings important? I know they are important in abstract algebra, but why do people study them? Why are they so important to study? Do they make certain things easier to understand?

The answer to this question (which I have also asked myself at various times) might also be a "No". Maybe Noetherian rings aren't that important after all, and their perceived ubiquity is a meme in commutative-algebraic literature?

Let me quote a paragraph from the Foreword of the (so far unfinished) translation of Commutative algebra -- Constructive methods by Henri Lombardi and Claude Quitté (the French version, Algèbre Commutative, Méthodes constructives, is available from Calvage & Mounet, and some additions can be found on http://hlombardi.free.fr/publis/LivresBrochures.html ). I hope the authors don't mind this.

  Finally, let us mention two striking traits of this work compared to classical
   works on commutative algebra.

  The first is to have left Noetherianity on the backburner. Experience
   shows that indeed Noetherianity is often too strong an assumption, which
   hides the true algorithmic nature of things. For example, such a theorem
   usually stated for Noetherian rings and finitely generated modules, when
   its proof is examined to extract an algorithm, turns out to be a theorem on
   coherent rings and finitely presented modules. The usual theorem is but
   a corollary of the right theorem, but with two nonconstructive arguments
   allowing to deduce coherence and finite presentation from Noetherianity and
   finite generation in classical mathematics. A proof in the more satisfying
   framework of coherence and finitely presented modules is often already
   published in research articles, although rarely in an entirely constructive
   form, but “the right statement” is generally missing in the reference works.

I certainly endorse such a position as a constructivist, as a noncommutative algebraist and as a combinatorialist. (Most advantages of the concept of Noetherianity crumble into dust when one crosses the boundaries of commutative algebra into either direction.)

I'm adding this as an answer because StackExchange won't let me comment.

@Martin Brandenburg, $dim(R[t]) = dim(R) + 1$ is a bad example of a property that requires Noetherian-ness. The class of rings  which satisfy this are called Jaffard rings and include (not necessarily Noetherian) Prüfer domains such as the ring of (all) algebraic integers.

As pointed out in @darij grinberg's answer, while there are many theorems for which Noetherian-ness is a sufficient condition, there aren't many theorems for which Noetherian-ness is a necessary condition.

I would say rather that the class of Noetherian rings has a nice balance of (1) being easy to define, (2) containing many of the rings that come up in practice cf. @rschwieb's answer, and (3) satisfying many important theorems that are used often in practice.

We are in the situation where large swathes of the literature are stated for Noetherian rings even when its not necessary (for example, this is a common criticism of Hartshorne's book Algebraic Geometry). So in practice it's often much easier to just make the blanket assumption that all rings are Noetherian instead of having potentially complicated lists of more general conditions at the beginning of each statement, and trying to chase down (or add) non-Noetherian references to the literature.

So basically, what Jim said here.


Proving $\sum_{k=0}^n \binom{n}{k} = 2^n$ combinatorially? I am trying to prove the basic fact that

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$

I can use the binomial theorem, simply setting $x = y = 1$, but how can I prove this combinatorially?

Thanks.

Okay. So you have a collection of $n$ objects and you want to count the number of ways to select a subset of them. First off note that for each of the $n$ objects, either it is in the set or it isn't. Hence, this way of counting gives $2^n$. The other way is to count the number of ways to select a subset of size $k$ for each $0\leq k\leq n$, and then add them up. This gives the left hand expression.

You are given a set $S$ of $n$ objects and you are tasked with finding the number of subsets in the set.

There are two ways of counting the number of subsets. The first one is the evident one of $|S|=2^n$ (if you don't know the proof, I can show it to you).

The second method of computing is finding the number of subsets of a fixed cardinality $0\leq k\leq n$, and then summing them all up from $k=0$ to $k=n$. By the definition of the binomial coefficients, there are $\binom{n}{k}$ ways of choosing $k$ objects in our set, and hence $\displaystyle |S|=\sum_{k=0}^n \binom{n}{k}$.

And so, we get: $\displaystyle 2^n=|S|=\sum_{k=0}^n \binom{n}{k}$


The 68-95-99.7% rule gives approximate probabilities of a Normal r.v. being within 1, 2, and 3 standard deviations of its mean ... The 68-95-99.7% rule gives approximate probabilities of a Normal r.v. being within 1, 2, and 3 standard deviations of its mean. Derive analogous rules for the following distributions.
a) Unif(0, 1).
b) Expo(1).

For part A, I got $σ = \frac{1}{sqrt(12)}$, $μ = \frac{1}{2}$, X ~ Uni(0, 1)

$P(|U - μ|≤ nσ) = P(|U - \frac{1}{2}|≤ \frac{n}{srt(12)}) = P(\frac{1}{2} - \frac{n}{srt(12)}≤U≤ \frac{1}{2} + \frac{n}{srt(12)})$
$P(|U - μ|≤ nσ) = F_U (\frac{1}{2} + \frac{n}{srt(12)}) - F_U (\frac{1}{2} - \frac{n}{srt(12)})$
Then I plugged in, 1, 2, and 3 and got 57.73%, 100%, and 100%

For part B, I got $σ = \frac{1}{ λ}$, $μ = \frac{1}{ λ} = 1$

$P(|E_1 - μ|≤nσ) = P(|E_1 - 1|≤n) = P(1 - n≤E_1≤1 + n)$
$P(|E_1 - μ|≤nσ) = F_{E_{1}}(1 + n) - F_{E_{1}}(1 - n)$
Then I plugged in, 1, 2, and 3 and got 86.47%, 95.02%, and 98.17%

However I feel like my answers are off I'm just not exactly where my work is off. Please any help would be very much appreciated!

Your answers are correct.
The precise values are as follows.  For the uniform distribution, the probability of being within $1$ standard deviation of the mean is $1/\sqrt{3}$.  The probability of being within $2$ standard deviations is $1$, because $2/\sqrt{3} > 1$.  The same is true of $3$ standard deviations.
For the exponential distribution with mean $1$, the standard deviation is also $1$, therefore being within $1$ standard deviation of the mean implies that $0 \le E_1 \le 2$.  This is simply $1 - e^{-2}$.  To be within two standard deviations, we must have $0 \le E_1 \le 3$, or $1 - e^{-3}$.  And to be within three standard deviations, the probability is $1 - e^{-4}$.
Note that in both cases, we encounter situations where one or more of the endpoints of the interval are truncated due to the support of the random variable not being infinite.


Reduce $39^{13} \text{ (mod 55)}$ I am trying to reduce $39^{13} \text{ (mod 55)}$. I first tried taking successive powers of 39 to find some pattern:

$39^2\equiv36\text{ (mod 55)}$
$39^3\equiv29\text{ (mod 55)}$
$39^4\equiv31\text{ (mod 55)}$
$39^5\equiv54\text{ (mod 55)}$
$39^6\equiv16\text{ (mod 55)}$
$39^7\equiv59\text{ (mod 55)}$
$39^8\equiv46\text{ (mod 55)}$

but it seems that it is not very helpful.

Also, 55 is composite, so we cannot make use of any theorem like Euler's Theorem.

I also tried factoring $39^{13}=3^{13}\times13^{13}$, but this way will make the calculation even longer.

Is there any better approach?

Many thanks for the help!

You missed a trick there. Note that,

$$39^5\equiv54 \equiv -1\pmod {55}$$

More generally, you can

Factor the 55 into 11 and 5 and apply CRT. This is what Euler88 did.
Factor 39 into 3 and 13 and calculate $13^{13},\    3^{13} \pmod{55}$

Note that $55=5\cdot11$, so we can use Euler's theorem mod 5 and mod 11, and then use the Chinese Remainder Theorem:
$$39^{13}\equiv39^1{\pmod 5}\equiv4{\pmod5}$$
$$39^{13}\equiv39^3{\pmod {11}}\equiv7{\pmod {11}}$$
Now the Chinese Remainder Theorem says there is a unique integer(mod 5*11) that is equivalent to $4{\pmod 5}$ and to $7{\pmod {11}}$.  In this case, that integer is $29$, so $39^{13}\equiv29{\pmod {55}}$


What is meant by a natural morphism $T(X\times Y)\to T(X)\times T(Y)$? Suppose $\mathcal{A}$ and $\mathcal{B}$ are categories with products, and $T$ a functor between them. If $X$ and $Y$ are objects in $\mathcal{A}$, what does it mean when we say there is a natural morphism $f\colon T(X\times Y)\to T(X)\times T(Y)$?

In $\mathcal{A}$, we have the product $X\times Y$, with corresponding morphisms $\pi_1:X\times Y\to X$ and $\pi_2:X\times Y\to Y$. Under $T$, we get a diagram of objects in $\mathcal{B}$ of morphisms $T(\pi_1):T(X\times Y)\to T(X)$ and $T(\pi_2):T(X\times Y)\to T(Y)$.

Since products exist in $\mathcal{B}$, we have a product $(T(X)\times T(Y),p_1,p_2)$ such that there is a unique morphism $f\colon T(X\times Y)\to T(X)\times T(Y)$ such that $p_1f=T(\pi_1)$ and $p_2f=T(\pi_2)$.

My guess is that this $f$ is the so called natural morphism, but I don't know how to verify that because I don't know what it means. I've only heard of natural transformations/isomorphisms between functors, but not natural morphisms between objects. Can anyone clarify?

Consider the categories $\mathcal B^2$ and $\mathcal C^2$ of pairs of objects in $\mathcal B$ and $\mathcal C$, respectively.  The Cartesian product on $\mathcal B$ is a functor $\times_\mathcal B$ from $\mathcal B^2$ to $\mathcal B$ and similarly for $\mathcal C$.  There is also the functor $T^2:\mathcal B^2\to\mathcal C^2$ which applies $T$ to each object in a pair.  The "natural morphism" you describe is a natural transformation from the functor $T\circ\times_\mathcal B$ to $\times_\mathcal C\circ T^2$.

In (modern) mathematics those morphisms which arise from the definitions or the universal properties are called the $\mathbf{canonical}$ morphisms. The functorial morphisms are called the $\mathbf{natural}$ morphisms; for instance if $\phi:F\rightarrow G$ is a natural transformation between the two functors $F,G:\mathscr{C}\rightarrow\mathscr{D}$ then for each object $C$ of $\mathscr{C}$ the morphism $\phi_{C}:F(C)\rightarrow G(C)$ is called a natural morphism. In Grothendieck's style of mathematics, all of the morphisms (which appear in practice) are either canonical or natural.


Terence Tao, Analysis 1. Exercise 5.3.2. Real Numbers and Cauchy Sequences. Let $ x = \lim_{n\rightarrow\infty}a_n, y = \lim_{n\rightarrow\infty}b_n$, and $ x' = \lim_{n\rightarrow\infty}a'_n$ be real numbers. Then $xy$ is also a real number. Furthermore, is $x=x'$, then $xy = x'y$.

Here is my attempt.

We need to show that $xy = \lim_{n\rightarrow\infty}a_n b_n$ is a real number.

from the hypothesis we know that $a_n$ and $b_n$. are eventually $\delta$ -steady sequences for every $\delta> 0 $. so we can choose $a_n$ and $b_n$ to be eventually $\sqrt{\epsilon}$-steady sequences.

since $(a_n)_{n=1}$ is eventually $\sqrt{\epsilon}$-steady, we know there is an $N \geq 1$ such that $d(a_n,a_m) < \sqrt{\epsilon}$  for every $n,m > N$. By a similar argument we can say the same for $(b_n)_{n=1}$.

by proposition 4.3.7 (h).

$d(a_nb_n,a_mb_m) < \sqrt{\epsilon}|b_n| + \sqrt{\epsilon}|a_n| + \epsilon $

From here i am not sure where to go, I am pretty sure i am going the right way, as this sort of resembles the definition of a cauchy sequence that is eventually $\sqrt{\epsilon}|b_n| + \sqrt{\epsilon}|a_n| + \epsilon $-close. I think I require something that just involves epsilon.

The second part of the question I havent attempted yet, but I thought I'd include it just in case anyone would like to lend a helping hand.

by the way propostion 4.3.7 (h). states that if x and y are $\epsilon$-close and z and w and $\delta$ close then xz and yw are $(\epsilon|z| + \delta|x| + \epsilon \delta$)-close.

EDIT.

A real number is defined to be an object of the form $ x = \lim_{n\rightarrow\infty}a_n$, where $a_n$ is a cauchy sequence of rational numbers.

${\bf 1.}$ Let $a.$ and $b.$ be two Cauchy sequences of rational numbers. Then
$$a_mb_m-a_nb_n=a_m(b_m-b_n)+b_n(a_m-a_n)$$
and therefore
$$|a_mb_m-a_nb_n|\leq |a_m|\>|b_m-b_n|+|b_m|\>|a_m-a_n|\ .\tag{1}$$

Since Cauchy sequences are bounded there is a common bound $C>0$ for the $|a_n|$ and the $|b_n|$. Let an $\epsilon>0$ be given. Then there is an $N\in{\mathbb N}$ such that the two sequences are ${\epsilon\over 2C}$-steady for $n\geq N$. On account of $(1)$ this implies that

$$|a_mb_m-a_nb_n|\leq C{\epsilon\over 2C}+C{\epsilon\over2C}=\epsilon\qquad(m, \>n\geq N)\ ,$$
which proves that the sequence $c_n:=a_nb_n$ $\>(n\geq1)$ is Cauchy, whence defines a real number.

${\bf 2.}$ A similar argument, using the inequality
$$|a_n'b_n-a_n b_n|\leq C\>|a_n'-a_n|\ ,$$
proves that $x'y\sim xy$ when $x'\sim x$.

Multiplication of Cauchy Sequences

Real numbers are being defined as Cauchy sequences rational numbers.  We can multiply two sequences of numbers to get another sequence.  Will it also be Cauchy?

  Lemma: If $a_n$ and $b_n$ are Cauchy, then $a_n b_n$ is also Cauchy

In the case of the real numbers, Cauchy sequences are not just close, they are guaranteed to have a limit. I don't quite remember how the proof goes.

  Lemma: If $a_n$ and $b_n$ are Cauchy with limits $x$ and $y$, then $a_n b_n$ is Cauchy with limit $xy$

Finally there is a question of whether two different sequences can represent the same number?  What about:

$$  1- \frac{1}{n} \hspace{0.25in}\text{ vs }\hspace{0.25in} 1 + \frac{1}{n} $$

In your case you just want to subtract the Cauchy sequences, and get $$xy - x'y = (x - x')y = 0\cdot y = 0$$

However $\mathbf{0}$ here means "a Cauchy sequence converging to $0 \in \mathbb{Q}$".  So all the steps here need to be checked carefully.  Can you do that?

Comment In real life sequences are definitely not Cauchy, e.g. $(-1)^n$.  Or in reality $(-1)^{f(n)}$ where $f(n)$ is something totally random and may chance over time.

Think about it for a little bit, for very large $n > M$, then $a_M - \epsilon < a_n < a_M + \epsilon$ and a similar statement for $b_n$.  Then:

$$
(a_m - \epsilon)(b_m - \delta) < a_n b_n < (a_m + \epsilon)(b_m + \delta)  $$

The error term is like $(\epsilon b_m + \delta a_m) + \delta \epsilon$ which is Tao's proposition.  How big is this error?

$$ (\epsilon (b_N + \delta) + \delta (a_M + \epsilon)) + \delta \epsilon
= (\delta a_M  + \epsilon b_N) + 3\delta \epsilon$$

This is getting rather expensive I suspect $\epsilon^\ast = \delta a_M  + \epsilon b_N$.

Summary: to multiply two Cauchy sequences $a_nb_n$ and get to be $\epsilon$-close to $xy$, we must truncate much further than to get $a_n$ to be $\epsilon$-close to $x$ or
$b_n$ to be $\epsilon$-close to $y$.


Basic Algebra Question about speed Hi I just want to check this.  It's from a recent test I took and the answer I got didn't match any of the choices.  If a car travels $x$ miles at $Y$ miles per hour, and then another $x$ miles at $Z$ miles per hour, what is the average speed during the trip?  It should just be the total miles divided by the total time right?  That's $$\frac{2x}{\frac{x}{Y} + \frac{x}{Z}}$$

Be careful about average velocity and average speed. If you want to calculate average speed, then your calculation is ok. But average velocity is   $ \frac{displacement}{time}$. So if the car moves x miles to the east and then x miles to the west, then the average velocity is $0$.


What's the difference between $\sum_{r=1}^n(ar+b)$ and $\sum_{r=1}^nar+b$ Does
$$\sum_{r=1}^n(ar+b)=\sum_{r=1}^nar+b$$
or does
$$\sum_{r=1}^n(ar+b)=\sum_{r=1}^nar+\sum_{r=1}^nb$$
If I'm given $u_r=ar+b$ how would I substitute that into
$$\sum_{r=1}^nu_r$$
Does that mean $$\sum_{r=1}^nu_r=\sum_{r=1}^n(u_r)=\sum_{r=1}^n(ar+b)$$
or
$$\sum_{r=1}^nu_r=\sum_{r=1}^nar+b$$
Also $u_r$ means $f(r)$, right?

You can see the correct answer by writing the sums explicitly:
$$\begin{align}
\sum_{r=1}^n(ar+b) &= (a1+b) + (a2+b) + \dots + (an+b)\\
&=(a1 + a2 + \dots + an) + (b + b + \dots + b)\\
&=\sum_{r=1}^nar+\sum_{r=1}^nb
\end{align}$$

There is an ambiguity in the notation

$$\sum_{k=1}^n ak+b $$

does it means

$$\left(\sum_{k=1}^n ak\right)+b $$

or

$$\sum_{k=1}^n \left( ak+b \right)$$


Bayes' Theorem Help? Problem 2.10 from Introduction to Probability by Blitzstein and Hwang asks the following:

Fred is working on a major project. In planning the project, two milestones
are set up, with dates by which they should be accomplished. This serves as a way to track Fred’s progress.

Let $A_1$ be the event that Fred completes the first milestone on time, $A_2$ be the event that he completes the second milestone on time, and $A_3$ be the
event that he completes the project on time.

Suppose that $\mathsf P(A_{j+1}\mid A_j) = 0.8$ but $\mathsf P(A_{j+1}\mid A_j^\complement) = 0.3$ for $j \in\{ 1, 2\}$, since if Fred falls behind on his schedule it will be hard for him to get caught up.

Also, assume that the second milestone supersedes the first, in the sense that once we know whether he is on time in completing the second milestone, it no longer matters what happened with the first milestone. We can express this by saying that $A_1$ and $A_3$ are conditionally independent given $A_2$ and they’re also conditionally independent given $A_2^\complement$.

(a) Find the probability that Fred will finish the project on time, given that he completes the first milestone on time. Also find the probability that Fred will finish the project on time, given that he is late for the first milestone.

(b) Suppose that $\mathsf P(A_1) = 0.75$. Find the probability that Fred will finish the project on time.

My thinking is that you can obviously start with $\mathsf P(A_3 \mid A_1)$, but then you can try conditioning on $A_2$ as well. This leads me to a roadblock. Thoughts?

Yes, you do seek $\mathsf P(A_3\mid A_1)$, as well as $\mathsf P(A_3\mid A_1^\complement)$ and the next step is to use partitioning on $A_2$, with the Law of Total Probability.

$$\mathsf P(A_3\mid A_1) ~=~ \mathsf P(A_3\mid A_1,A_2)\;\mathsf P(A_2\mid A_1)+\mathsf P(A_3\mid A_1,A_2^\complement)\;\mathsf P(A_2^\complement\mid A_1)$$

$$\mathsf P(A_3\mid A_1^\complement) ~=~ \mathsf P(A_3\mid A_1^\complement,A_2)\;\mathsf P(A_2\mid A_1^\complement)+\mathsf P(A_3\mid A_1^\complement,A_2^\complement)\;\mathsf P(A_2^\complement\mid A_1^\complement)$$

So, moving onwards.   The assumption of conditional independence, between $A_1,A_3$ when given $A_2$, would mean that:

$$\mathsf P(A_3\mid A_1,A_2)=\mathsf P(A_3\mid A_2)\\\mathsf P(A_3\mid A_1,A_2^\complement)=\mathsf P(A_3\mid A_2^\complement)\\\mathsf P(A_3\mid A_1^\complement,A_2)=\mathsf P(A_3\mid A_2)\\\mathsf P(A_3\mid A_1^\complement,A_2^\complement)=\mathsf P(A_3\mid A_2^\complement)$$

Put it together.

Of course, for the second part we likewise use that: $$\mathsf P(A_3)~=~\mathsf P(A_3\mid A_1)\;\mathsf P(A_1)+\mathsf P(A_3\mid A_1^\complement)\;\mathsf P(A_1^\complement)$$


Integration of a function with respect to another function. What is the intuition/idea behind integration of a function with respect to another function? Say $$\int f(x)d(g(x)) \;\;\;\;\;?$$
or may be a more particular example $$\int x^2d(x^3)$$

My concern is not at the level of problem solving. To solve we could simply substitute $u=x^3$ and then $x^2=u^{2/3}$. My concern is rather about what meaning physical/geometrical does this impart?

ADDED if you ask what kind of meaning I seek, integration of a function w.r.t a variable gives the area under the curve and above x-axis.

There's no geometric interpretation of $\int f(x) \mbox{d}(g(x))$ as far as I'm concern. However, it does have a meaning. Say, you want to take the differentiation of $\sin(x)$ w.r.t x, and $\sin (x)$, they give 2 different results:

$\frac{\mbox{d} \sin x}{\mbox{d}x} = \cos x$
$\frac{\mbox{d} \sin x}{\mbox{d} \sin x} = 1$

Another example is to take the derivatives of $x^4$ w.r.t x, and $x^2$ respectively.

$\frac{\mbox{d} x^4}{\mbox{d}x} = 4x^3$
$\frac{\mbox{d} x^4}{\mbox{d} x^2} = \frac{\mbox{d} (x^2)^2}{\mbox{d} x^2} = 2x^2$

An antiderivative of $f$ w.r.t $x$ is some function $F$, such that $\dfrac{\mbox{d}F}{\mbox{d}x} = f$

So:

$\int \mbox{d}(x^2)$ is some function, such that its derivative w.r.t $x^2$ is 1, this family of function is, of course, $x^2 + C$.
$\int x^5\mbox{d}(x^5)$ is some function, such that its derivative w.r.t $x^5$ is $x^5$, this family of function is, of course, $\dfrac{x^{10}}{2} + C$, since: $\frac{1}{2}\dfrac{\mbox{d}(x^{10} + C)}{\mbox{d}(x^5)} = \frac{1}{2}\dfrac{\mbox{d}((x^5)^2)}{\mbox{d}(x^5)} + 0 = x^5$

When solving problems, you just need to remember that $\int f(x)\mbox{d}(g(x)) = \int f(x).g'(x) \mbox{d}x$, e.g, when you take some function out of d, you have to differentiate it, and vice versa, when you put some function into d, you'll have to integrate it, like this:

$\int x^5 \mbox{d}(x^2) = \int 2x^6 \mbox{d}(x) = \dfrac{2x^7}{7} + C$. (Take $x^2$ out of d, we differentiate it, and have $2x$)
$\int \sin^2 x \cos x \mbox{d}x = \int \sin^2 x \mbox{d}(\sin x) = \frac{\sin ^ 3 x}{3} + C$ (Put $\cos x$ into d, we have to integrate it to get $\sin x$).

This is an old question with a marked answer, but there is a better one.

This is how you find the area under the curve for a function with respect to another function given some hidden parameter. One such application is the receiver operating charateristic (ROC)
Receiver Operating Characteristic

In the ROC, we are interested in how the dependent variables $f(t)$ and $g(t)$ vary with $t$. We have the probability of false detection on the $x$-axis and the probability of detection on the $y$-axis. So, the integral of $f(t)$ with respect to $g(t)$ is an excellent measure of how likely we are to correctly identify the presence of some signal. There are likely other similar interpretations, but this is one I'm familiar with.


trouble solving this sequence problem I'm having some trouble solving this problem about sequences:

$$a(n): a(1) = 2;$$  $$   a(n+1) = (a(n) + 1)/2, n\in N$$

1)Prove that this sequence is monotonically decreasing

2)Prove that$$ 1 < a(n) ≤ 2, \forall n\in N$$

3)Prove that this sequence is convergent and calculate its limit

The first one, after calculating some terms, I saw that it was decreasing to 1, but how do I prove it theoretically?

I should start with 2) using induction.

2) If $1<a_n\leq 2$ then: $$a_{n+1}=\frac{a_n+1}{2}>\frac{1+1}{2}=1$$ and $$a_{n+1}=\frac{a_n+1}{2}\leq\frac{2+1}{2}\leq 2$$

1) From $a_n>1$ it follows directly that: $$a_{n+1}=\frac{a_n+1}{2}<a_n$$

A bounded monotone sequence is convergent and we can find its limit $a$ on base of the relation $a_{n+1}=\dfrac{a_n+1}{2}$. Both sides converges and this leads to $a=\dfrac{a+1}{2}$ hence $a=1$


Mixing solutions of specified strength While reading one aptitude book, I came across this question:

  $35\%$ alcohol mixed with $60\%$ alcohol to get a $50\%$ alcohol. In what ratio were they mixed?

I spent 20 minutes on this question, but I couldn't even figure out what it means! Could anyone explain this to me?

Call the ratio you want to find r=(volume of 35% alcohol):(volume of 60% alcohol).  Suppose that there are r liters of the 35% alcohol (so there are 0.35 L of alcohol and 0.65 L of water), 1 liter of the 60% alcohol (so the ratio is r), and 1+r liters of the 50% alcohol.  From there, you can construct an equation about the alcohol (or about the water) and solve for r.

Given a liters of 35% alcohol solution, and b liters of 60% alcohol solution, what would be the alcohol ratio after we'll mix this two solutions?

The a liters are actually a*35/100 alcohol, and a*(1-(35/100)) water. Likewise the b liters contains b*60/100 alcohol and b*(1-(60/100)) water.

Mixing them together would give us a*35/100+b*60/100 alcohol and a*(1-(35/100))+b*(1-(60/100)) water. The question is for which a,b we have the ratio

((a*35+b*60)/100)/((a*65+b*40)/100) = 50% = 1/2

or

(a*35+b*60)/(a*65+b*40) = 1/2

I believe you can take it from here...


Proof with inequalities and a function I need help approaching a proof which deals with inequalities:

If p and r are the precision and recall of a test, then the F1 measure of the test is
defined to be
$$F(p, r) = \frac{2pr}{p+r}$$

Prove that, for all positive reals p, r, and t, if t ≥ r then F(p, t) ≥ F(p, r)

What's the first step to approaching this problem? Do I need to look at this with different cases?

A standard way is to look at $F(p,t)-F(p,r)$, which is
$$\frac{2pt}{p+t}-\frac{2pr}{p+r}.$$
Bring to a common denominator and simplify. We get
$$\frac{2pt(p+r)-2pr(p+t)}{(p+t)(p+r)},$$
which simplifies to
$$\frac{2p^2(t-r)}{(p+t)(p+r)}.$$
This is clearly $\ge 0$.


Countability of the zero set of a real polynomial This is the question from my calculus homework: Is it possible for a polynomial $f\colon\, \mathbb{R}^{n}\to \mathbb{R}$ to have a countable zero-set $f^{-1}(\{0\})$?
(By countable I mean countably infinite).

Of course, I claim that it's impossible.

Surely, if the zero $z$ isn't shared with at least one of the partial derivatives, say $\frac{\partial f}{\partial x_{1} }(z)\neq 0$, by Implicit Function Theorem we get (locally) a smooth curve $\{f(x_{1},t)=0\}=\{(x_{1},\gamma(x_{1}) )\}$, so it's surely uncountable. However, it may be the case that all of the real zeros are shared with all the derivatives.
My thought is to proceed somehow inductively, but I have no idea how to do it.

Our proffesor gave me a "hint" - to show that locally, the roots of a polynomial (in one variable) vary analytically as a function of coefficents. Is it true? Is there any elementary proof of that fact? I know that they vary continously (as discussed here), but those multiple roots are driving me crazy...

If you were so kind and help me, I would be very grateful.
Also, it's my first question, so please forgive any mistakes made.

Thanks in advance.

The only proof I could find so far does not use analycity.  Say $f$ is a polynomial in the variables $x_1,x_2, \ldots ,x_n$. Denote by $Z(f)$ the set of zeroes of $f$, let $p_i$ be the projection on the $i$-th coordinate axis :

$$
p_i(x_1,x_2, \ldots ,x_n)=x_i
$$

and let $Z_i=p(Z(f))$. By the  Tarski-Seideberg theorem, each $Z_i$ can be defined by a set of univariate polynomial equalities or inequalities. So each $Z_i$ is a finite union of intervals or points of $\mathbb R$. If $Z_i$ contains an interval of positive length, $Z_i$ is uncountable ; otherwise $Z_i$ is finite.

If some $Z_i$ is uncountable, so is $Z(f)$. If all the $Z_i$ are finite, so is $Z(f)$. QED

Here are some examples of how this works : for a univariate polynomial $f$,

-When $f$ has degree $1$, $f$ always has a unique simple root.

-When $f$ has degree $2$, $f$ has  two simple roots if ${\sf disc}(f)>0$, one double root if ${\sf disc}(f)=0$, and no root at all if ${\sf disc}(f)<0$.

-When $f$ has degree $3$, $f=a_3x^3+a_2x^2+a_1x+a_0$,

$$
\begin{array}{|l|l|l|}
\hline
\text{Case} & & \text{Roots  of } \ f \\
\hline
{\sf disc}(f') < 0 & & \text{one  simple  root}\\
\hline
{\sf disc}(f')= 0 & {\sf disc}(f) =0 & \text{one  triple  root} \\
\hline
{\sf disc}(f')= 0 & {\sf disc}(f) \lt 0 & \text{one simple  root} \\
\hline
{\sf disc}(f')\gt 0 & G(f)\lt 0 & \text{three  simple  roots}\\
\hline
{\sf disc}(f')\gt 0 & G(f)= 0 & \text{one  simple  root, one  double root} \\
\hline
{\sf disc}(f')\gt 0 & G(f)\gt 0 & \text{one  simple  root} \\
\hline
\end{array}
$$

where $G(f)=4a_3a_1^3 - a_2^2a_1^2 - 18a_0a_3a_2a_1 + 4a_0a_2^3 + 27a_0^2a_3^2
$

Assume $p(x)$ is a polynomial of degree $n\geq 1$ (with leading coefficient not zero, that is, $p$ is not also a polynomial of degree $n-1$) and assume that the zero set of $p$ is not finite (possibly even uncountable).

First: it is obvious that $p'(x)$ has degree $n-1$, $p''(x)$ has degree $n-2$ and so on.

Second: take a countable subset of the zero set of $p$ and label its elements as $z_0,z_1,z_2,\ldots$ such that $z_i\leq z_{i+1}$. Then, by Rolle's thm, it follows that in each of the intervals $(z_i,z_{i+1})$ there is at least one zero of $p'(x)$. Hence also $p'(x)$ has a not finite zero set.

Third (and last): iterating the previous step $n-1$ times, we obtain that $p^{(n-1)}(x)$ also has a not-finite zero set. However, $p^{(n-1)}(x)$ is a linear function, with exactly one zero (notice that $p^{(n-1)}(x)$ can't be the null function, cause we assumed that the leading coefficient is not zero). Contradiction.


Estimate standard deviation of sample You have a random sample of 25 objects with mean weight of 24 grams, estimate the standard deviation of the sample.

In addition, you know it's supposed to be 25 grams with a deviation of 1 gram, but this has no relevance to the above question, right?

How is this done? Looking in my formula reference this is not enough information to give an estimate.

A sample mean of $24$ is unlikely from a sample of twenty-five items with a population mean of $25$ and population standard deviation of $1$.  So the sample casts doubt on the population parameters.

But conditioned on the data given and ignoring issues such as finite populations, a good estimate of the variance of the sample conditioned on the population mean and sample mean is the same as the population mean. $1$ in this case.

Here is an illustration of ten thousands trials in R from a normal distribution, suggesting no relationship between the sample standard deviation and the difference between the population mean and the sample mean

library(matrixStats)
samplesize <- 25
cases      <- 10000
popmean    <- 25
popsd      <- 1
set.seed(1)
matdat <- matrix(rnorm(ss*cases, mean=popmean, sd=popsd), ncol=ss)
samplemeans <- rowMeans(matdat)
samplesds <- rowSds(matdat)
plot(samplesds ~ samplemeans)

Standard deviation is $0$ because all the samples are completely random.


Limit of a function involving infinity What would be the limit of $\frac{1}{\alpha} \left(x+\frac{\alpha}{2}\right)$ as $\alpha$ approaches 0, where $-\frac{\alpha}{2} \leq x \leq \frac{\alpha}{2},\  $  and $\alpha > 0$?

I have tried the following, but i think it may not be correct.

$$\lim\limits_{\alpha \to 0}  \frac{x}{\alpha} +\frac{1}{2}$$

Taking the limit

$$=\frac{x}{0} + \frac{1}{2}
 = (\infty + \frac{1}{2})
 \to\infty$$

If $x=0$, the limit is $1/2$. Suppose $x>0$; then
$$
\lim_{x\to0^-}\frac{x}{\alpha}=-\infty,
\qquad
\lim_{x\to0^+}\frac{x}{\alpha}=\infty
$$
Similarly (with signs swapped) if $x<0$. Adding $1/2$ doesn't change the limits.

Break the problem down into cases:

Case 1: $x=-\frac{a}{2}$

$$\lim_{a\to0}\frac{1}{a}\left(\frac{a}{2}-\frac{a}{2}\right)=\lim_{a\to0}\frac{1}{a}(0)=0$$

This follows from $\forall a>0.\frac{1}{a}0=0$ for arbitrarily small $a$

Case 2: $x=\frac{a}{2}$

$$\lim_{a\to0}\frac{1}{a}\frac{2a}{2}=\lim_{a\to0}\frac{1}{a}a=1$$

This follows from $\forall a>0.\frac{1}{a}a=1$ for arbitrarily small $a$

This shows that the limit is not independent of choice of $x$, and therefore does not exist (this can be shown more explicitly by considering the function $f(x,y)=\frac{1}{y}\left(x+\frac{y}{2}\right)$. Different limits are obtained for $(x,y)\to(0,0)$ depending on the path you take to get to $(0,0)$.

While this shows that the limit does not exist, for the sake of completion, you may consider the final case.

Case 3: $x\in\left(-\frac{a}{2},\frac{a}{2}\right)\setminus\left\{0\right\}$

$$\lim_{a\to0}\frac{1}{a}\left(x+\frac{a}{2}\right)=\lim_{a\to0}\frac{x}{a}+\frac{1}{2}=\infty$$

Correction: As per Eevee Trainer's comment, $\infty$ is not a [real] number, so it is an abuse of notation to write $\lim_{a\to0}\frac{x}{a}+\frac{1}{2}=\infty$ assuming that $x$ and $a$ are real. However, this is exactly the case given a one-point compactification of the real number line.

In the absence of a point at infinity, if it is decided that the expression must have a limit, then that limit must be infinite. This can be proven using nonstandard techniques

$$\lim_{a\to0}\frac{1}{a}\left(x+\frac{a}{2}\right)\approx\lim_{a\to\epsilon}\frac{1}{a}\left(x+\frac{a}{2}\right)=\epsilon^{-1}\left(x+\frac{\epsilon}{2}\right)$$

Where $\epsilon$ is infinitesimal. It follows that $x+\frac{\epsilon}{2}\in\text{monad}(x)$, thus $x\approx x+\frac{\epsilon}{2}$. Since the reciprocal of an infinitesimal is nonfinite and $x$ is finite by the previous, the product of $\epsilon^{-1}$ and any $y$ s.t. $y\in\text{monad}(x)$ must be infinite. Therefore the limit, evaluated this way, is infinite.

STILL the limit does not exist due to the contradictions in cases 1 and 2.

You can also look at a graph of the function $f(x,y)$.

Edit: as per J.G.'s comment, the limit does exist for fixed $x=0$. This is, in fact, the only fixed value of $x$ for which the limit exists. However, whether or not this is "the" limit depends closely on how you evaluate the expression.

Edit: In response to KaviRamaMurthy's comment, it is worth noting that if $x$ is evaluated according to:

$$x=\lim_{a\to0}\left\{y\in\mathbb{R}\mid\frac{a}{2}\leq y\leq\frac{a}{2}\right\}$$

Then the result is indeterminate, whereas if $x$ is evaluated as a [single-valued] function of $a$ as in cases 1 and 2 the result is either 0, 1, or infinite.

If $x$ is evaluated as a constant, then the limit is either $\infty$ (using one-point compactification of the real-number line), $\pm\infty$ depending on whether $x$ is greater than or less than zero, or $\frac{1}{2}$ if $x$ is equal to zero.

Hopefully this covers every possible interpretation of the expression.

Yet another correction

From jnxd:

  My question was transpired by the need to verify a statement $u(x)=\lim_{\alpha\to0}u_\alpha(x)$ mentioned in an
  article here. The statement is marked 4.9.

This is a different question. The statement given is
$$\hspace{50pt} \delta_{\alpha}(x)=\frac{d}{dx} u_{\alpha}(x), \hspace{15pt}  u(x)=\lim_{\alpha \rightarrow 0} u_{\alpha}(x) \hspace{50pt} (4.9)$$
Where
$$u_\alpha(x)=\begin{cases}1&x>\frac{\alpha}{2}\\\frac{1}{\alpha}\left(x+\frac{\alpha}{2}\right)&-\frac{\alpha}{2}\leq x\leq\frac{\alpha}{2}\\0&x<\frac{\alpha}{2}\end{cases}$$
In this context, the limit refers to the function $u(x)$, not its value at 0.
$$u(x)=\begin{cases}1&x>0\\0&x<0\end{cases}\quad\text{or}\quad u(x)=\begin{cases}1&x\geq0\\0&x<0\end{cases}$$
You will notice that smaller values of $\alpha$ lead to larger values of the derivative of $u_\alpha(x)$ in the region $[-\frac{\alpha}{2},\frac{\alpha}{2}]$. Because this piece of $u_\alpha(x)$ is linear for all $\alpha\neq0$, its derivative is a constant. When $\alpha=0$, $u_\alpha(x)$ becomes discontinuous at $0$ - it jumps from a value of $0$ to a value of $1$. The derivative of $u(x)\vert_{x=0}$ is thus "infinite". Ergo,

$$\delta(x)=\begin{cases}\infty&x=0\\0&\text{otherwise}\end{cases}$$

This is not the formal definition of the Dirac Delta, but it is the right idea. I think the confusion arises from the fact that the value of the Dirac Delta at $0$ is not well defined in terms of real numbers. The key takeaway is that the Dirac Delta can be approximated to arbitrary precision as the derivative of $u(x)$ - I would not consider the value of $u(0)$ itself.

If it is absolutely necessary to evaluate the function $u(x)$ at zero, then I would say $u(0)=1/2$. This can be determined either by evaluating the limit whilst fixing $x=0$ or by considering:

$$\int \delta(x)\ dx=\frac{\text{sgn}(x)+1}{2}$$

It is possible to justify this analytically (I definitely wouldn't say prove), but not without going far off topic. I would be very careful when using this, as it could easily lead to errors. Actually, if the application is probability, I would not use this at all.


How to integrate $\int_{0}^{2} \sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}\,dx$? I want to integrate this $$\int_{0}^{2} \sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}\,dx$$

I tried making the substitution $u^2=x+u$ and  my integral turns into

$$\int_{0}^{2}u(2u-1)\,du = \frac{10}{3}$$

However the answer is supposed to be $\dfrac{19}{6}$, I would like to know where I am making a mistake or another way

Let $L(x)=\sqrt{x+\sqrt{x+\cdots}}$.

$L(x)^2=x+L(x)$, hence, $L(x)^2-L(x)-x=0$ and $L(x)=\frac{1\pm\sqrt{1+4x}}{2}$.

Because $L(x)\ge0$, $L(x)=\frac{1+\sqrt{1+4x}}{2}$ and then the intergal is straightforward.

Hint:
solve the two equations to find the new limits of integration( use the $u^2-u=x$)
$$u^2-u=0$$
and
$$u^2-u=2$$


If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors. I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese)

  A plane is divided by many lines. Show that it is possible to color
  the regions formed with only two colors so that no two adjacent
  regions share the same color.

First of all, I was not able to solve it. Then I did I search on Google, and I've find the following here.

4.Show that if n lines are drawn on the plane so that none of them are parallel, and so that no three
lines intersect at a point, then the plane is divided by those lines into $\dfrac{n^{2} + n + 2}{2}$ regions.

The next exercise is:

Show that if the same lines as in problem $4$ are drawn on a plane that it is possible to color the regions formed with only two colors so that no two adjacent regions share the same color.

Proof: With zero lines, you can obviously do it; in fact, one color would be sufficient. If you can
successfully $2$-color the plane with $k$ lines, when you add the $(k + 1)$st line, swap the colors of all the regions on one side of the line. This will provide a $2$-coloring of the configuration with $k + 1$ lines. (In fact, for this problem, there is no real need to have the lines in general position: some can be parallel, and multiple lines can pass through a point, and the proof will continue to work.)

I did a drawn, and I got convinced, but  I did not understand it. I am feeling stupid, but I was not able to understand the proof without drawing.

I would appreciate your help.

I will try to explain the proof you have found instead of giving another one.

The proof is, in fact, by induction. You start with one line and two regions: one black and one white. We want to show that if we have already drawn $k$ lines and painted all regions such that no two adjacent regions share the same color, then we can add any new $(k+1)$th line and repaint some regions (newly created and old ones) such that the property holds: no two adjacent regions share the same color.

Draw a new line, and do NOT change any colors for now. Consider both sides of the new line. No two regions on the same side of the new line are painted same color! This is because you did not change any colors, and any two regions on the same side may share only a part of a line which they shared before you drew a new line. Moreover, if you invert the colors of all regions on same side of the new line, then this property will still hold for them (blacks become white, and whites become black).

When you draw a new line, you create new regions by dividing some regions in two parts. These and only these newly created adjacent regions will share same color. But once you invert the colors of all regions on one side, you get what you need. All adjacent regions on either side are still painted in different colors, and now newly created adjacent regions (which share the same side which is a part of the new line) are opposite colors as well, because one of them got inverted.

This is easy if you solve it by induction.
First proving when $1$ line divides a plane into $2$ regions then we can fill the second region with  green and red without having adjacent regions having same colour.
Then assuming it is true for $m$ lines then the number of regions will be $m+1$ and we have assumed that we can fill these $m+1$ regions with two colours without having same adjacent sides.
Then we have to prove for $m+1$ lines this $m+1$ will divide the plane into $m+2$ regions and since we have assume that $m+1$ regions can be filled with $2$ colours without having same adjacent sides then the next region can be fill of the opposite colour used in the $(m+1)$th region therefore $m+2$ region can also be fill $2$ colours without having same adjacent sides.
Since it is true for $1$ line and we have prove if it is true for $m$ lines then it's going to be true for $m+1$ lines hence proved.


Integral of arcsin(x)/(x^2) I did the integration by parts and got this expression, but then I am stuck on how to take it further. I tried substituting u=1-x^2, but then I had to do a partial fraction decomposition (which I did not take). Any hints or help would be very appreciated!

Take $x = \sin u$ initially to get simple integral.
$$\int u \csc( u )\cot( u) du= -u\csc( u) + \int \csc (u) du\\
= -u \csc (u) +\ln|\cot( u )-\csc (u)| + c.$$

I wrote my answer for this question, click
here  to see the image.


Factorizing $x^4-13x^3+56x^2-19$ I have been trying to factor the following quartic equation for two days now and I cannot find any way to factor it:

$$x^4-13x^3+56x^2-19.$$

I just can't seem to factor it at all. Is this equation able to be factored at all? Thanks in advanced guys!

.By factoring the quartic, I assume you want me to express the given polynomial as a product of two or more irreducible integer coefficient polynomials. I shall do more : I shall try to provide the roots of this polynomial as well.

We claim that this polynomial cannot be written as a product of integer polynomials of strictly smaller degree! We make use of a nice criteria, which you may ignore if you do not know : a polynomial with integer polynomials is irreducible if there is a prime $p$ such that when we reduce the coefficients of our polynomial modulo $p$, the new polynomial is irreducible in the finite field $\mathbb F_p$.

If we do this with $p=2$, we get the polynomial $x^4+x^3+1$. This is much easier to check for irreducibility ,actually : you can check it has no linear factors by substituting $0$ and $1$ in, and the only irreducible polynomial in degree $2$ is $x^2+x+1$, which can be seen by the division algorithm to not divide this.

Hence, if you are seeking to factorize your polynomial as a product of integer polynomials, you cannot do this!

But, you can still go in for "root finding" i.e. locating suitable regions where the (complex) roots of this polynomial are contained.

To do this, we make use first, of the Descartes' rule of signs. You may read this up in the link below[1].

Using the rule of signs of coefficients, there are three sign changes, and therefore either three or one positive root(s). Furthermore, there is exactly one negative root, by applying the rule to the negative of the above polynomial.

However,  there is an improvement of the Descartes' rule : instead of taking the sign changes of coefficients, you take the partial sums in the reverse order of coefficients : i.e. here you'd get $-19,-19,37,24,25$. There's precisely one change of sign, and therefore exactly one positive root.

Now, there's exactly one positive and one negative root, so where are these? Clearly, $f(-1) >0 ,f(0)<0,f(1)>0$ by substitution, so by the intermediate value theorem we get that both have modulus less than $1$ and one is positive, the other negative.

Finally, as to the complex roots, we have the wonderful Rouche's theorem, which (I'll be brief) uses the fact that $56$ is greater than the sum of absolute values of all other coefficients, to conclude that two roots of $f$ lie inside the complex unit circle, and  two outside. Therefore both complex roots lie outside the unit circle.

I believe that there should be easily derivable upper bounds for the moduli of the complex roots as well, but at the moment this is all I am able to say, so I'd be happy if somebody can make this tighter.

[1] :
 https://pdfs.semanticscholar.org/bc6c/59cbf7e5f76719e85afa669ce238ab56b80d.pdf

You find all possible roots of your expression.

To do this, you can use the rational root theorem and plug values of the possible rational roots in, which are $\pm19, \pm1$.

Another way you can do this is with graphing, most of the time, a graph with decimals to the third place is approximated and cannot be expressed as a fraction.

Therefore, there is no way to factor this, as its factors cannot be expressed in the form $x-\cfrac pq$,

where $\cfrac pq$ is some rational number.

Another quartic term which cannot be factored is $x^4-3$, but you know the roots from looking at the expression. Such is not the case in your expression.


Euler Lagrange equation in variational calculus for a sum of integrals Let $F, G: \mathbb{R}^3\rightarrow{}\mathbb{R}$ be two continuously differentiable functions and let $a\leq b \leq c$. I want to know if there exists some known method to find a function that maximizes the functional $J(P):=\int_a^b F(q,P(q),P'(q))dq+ \int_b^c G(q,P(q),P'(q))dq$ between all the continuously differentiable functions $P: \mathbb{R}\rightarrow{}\mathbb{R}$ satisfying $P(a)=0$.

This is known as a multiphase optimal control problem, and there is software available online for this kind of problems. Examples are DIDO (matlab, proprietary), GPOPS-II (matlab, proprietary), PROPT(matlab, proprietary - i think), ICLOCS2 (matlab, free) and PSOPT (C++, free).
They all use pseudospectral methods, which are great to feed a computer, but not very practical to solve by hand. I don't know any method to solve analytically. However, I am certain that if $F$ and $G$ are not identical, then the Hamiltonian will (most likely) have a jump discontinuity at q = b.


Probability in a knock-out tournament Maths newbie so please go gently. Imagine if you would:

4 teams in the semi-final of a soccer tournament A,B,C,D.

A,B and C all have 20% chance of winning the tournament. D however, is the favourite with a 40% chance of winning.

The lunch time game is between A and B where A wins.

So...the question is how do I calculate the new probabilities of B,C or D now winning before the evening semi between C and D

Second question if I can? what the probabilities after D wins the evenings semi match?

Thanks in advance.

With a nod to @TonyK that this real world problem is impossible, I will treat it as a pure mathematical question.

Before the game was played:
$$P(A)=P(B)=P(C)=0.2$$
and
$$P(D)=0.4$$

It was a given that in order to win, Team D must win its semi and would play either A or B in the final. Assuming that its chances against either are the same, what has changed by now knowing that Team A won the semi?

Nothing

Team D still has $P(D)=0.4$.

By similar reasoning Team C still has $P(C)=0.2$.

Which means $P(A)=0.4$

Shame on those who downvoted @Raja!

Team D is still twice as likely to win as A and C, even though B is now out of the running. A and C have equal odds still. Letting $P_{X}$ denoting the probably that team X wins, then we can set up the equation $P_{D}+P_{A}+P_{C}=1$. But again we already know $P_{D}=2P_{A}=2P_{C}$, so we can replace $P_{A}$ and $P_{C}$ in the first equation with $\frac{1}{2}P_{D}$. Now we have $P_{D}+\frac{1}{2}P_{D}+\frac{1}{2}P_{D}=1$ and solving for $P_{D}$ yields $P_{D}=\frac{1}{2}$, or 50%. Now that we know $P_{D}$ we can solve for $P_{C}$ and $P_{A}$, and we'll find that $P_{A}$=$25$% = $P_{C}$. You can repeat this process to figure out the remaining part of your question.


None exact first order ODE i have to solve the following $1^{st}$ order differential equation

$(xy+1)dx+(2y-x)dy=0$

i am in the elementary differential class,and have not learned multivariate functions,
the equation below is none exact,since
$M_y=x\ne N_x=-1$
so i am looking for a substitution that can make it exact because the intergration factor has both $x$ and $y$ ...

$\large \frac{dy}{dx}=\frac{xy+1}{x-2y}$

Approach $1$:

$(xy+1)~dx+(2y-x)~dy=0$

$(xy+1)~dx=(x-2y)~dy$

$(x-2y)\dfrac{dy}{dx}=xy+1$

Let $u=\dfrac{x}{2}-y$ ,

Then $y=\dfrac{x}{2}-u$

$\dfrac{dy}{dx}=\dfrac{1}{2}-\dfrac{du}{dx}$

$\therefore2u\left(\dfrac{1}{2}-\dfrac{du}{dx}\right)=x\left(\dfrac{x}{2}-u\right)+1$

$u-2u\dfrac{du}{dx}=\dfrac{x^2}{2}-xu+1$

$2u\dfrac{du}{dx}=(x+1)u-\dfrac{x^2}{2}-1$

$u\dfrac{du}{dx}=\dfrac{(x+1)u}{2}-\dfrac{x^2+2}{4}$

This belongs to an Abel equation of the second kind.

Let $s=x+1$ ,

Then $\dfrac{du}{dx}=\dfrac{du}{ds}\dfrac{ds}{dx}=\dfrac{du}{ds}$

$\therefore u\dfrac{du}{ds}=\dfrac{su}{2}-\dfrac{(s-1)^2+2}{4}$

Let $t=\dfrac{s^2}{4}$ ,

Then $s=\pm2\sqrt t$

$\dfrac{du}{ds}=\dfrac{du}{dt}\dfrac{dt}{ds}=\dfrac{s}{2}\dfrac{du}{dt}$

$\therefore\dfrac{su}{2}\dfrac{du}{dt}=\dfrac{su}{2}-\dfrac{(s-1)^2+2}{4}$

$u\dfrac{du}{dt}=u-\dfrac{(s-1)^2+2}{2s}$

$u\dfrac{du}{dt}-u=\dfrac{(\pm2\sqrt t-1)^2+2}{\pm4\sqrt t}$

$u\dfrac{du}{dt}-u=\pm\sqrt t+1\pm\dfrac{3}{4\sqrt t}$

This belongs to an Abel equation of the second kind in the canonical form.

Please follow the method in https://arxiv.org/ftp/arxiv/papers/1503/1503.05929.pdf

Approach $2$:

$(xy+1)~dx+(2y-x)~dy=0$

$(xy+1)~dx=(x-2y)~dy$

$(yx+1)\dfrac{dx}{dy}=x-2y$

Let $u=x+\dfrac{1}{y}$ ,

Then $x=u-\dfrac{1}{y}$

$\dfrac{dx}{dy}=\dfrac{du}{dy}+\dfrac{1}{y^2}$

$\therefore yu\left(\dfrac{du}{dy}+\dfrac{1}{y^2}\right)=u-\dfrac{1}{y}-2y$

$yu\dfrac{du}{dy}+\dfrac{u}{y}=u-\dfrac{2y^2+1}{y}$

$yu\dfrac{du}{dy}=\dfrac{(y-1)u}{y}-\dfrac{2y^2+1}{y}$

$u\dfrac{du}{dy}=\dfrac{(y-1)u}{y^2}-\dfrac{2y^2+1}{y^2}$

This belongs to an Abel equation of the second kind.

In fact all Abel equation of the second kind can be transformed into Abel equation of the first kind.

Let $u=\dfrac{1}{v}$ ,

Then $\dfrac{du}{dy}=-\dfrac{1}{v^2}\dfrac{dv}{dy}$

$\therefore-\dfrac{1}{v^3}\dfrac{dv}{dy}=\dfrac{y-1}{y^2v}-\dfrac{2y^2+1}{y^2}$

$\dfrac{dv}{dy}=\dfrac{(2y^2+1)v^3}{y^2}-\dfrac{(y-1)v^2}{y^2}$

Please follow the method in http://www.hindawi.com/journals/ijmms/2011/387429/#sec2

setting
$y=vx$ we get

$dy=vdx+xdv$ and substituting we get

$(vx^2+1)dx+(2y-1)(vdx+xdv)=0$

$(vx^2+2yv-vx+1)dx+(2yx-x^2)dv=0$

$(vx^2+2v^2x-vx+1)dx+x^2(2v-1)dv=0$

$(vx(x+2v-1)+1)dx+x^2(2v-1)dv=0$

this should be seperable but i cannot seperate it easily...


Does it make sense to ask this about taking a derivative? If $g(x) = f(h(x))$, does it make sense to ask:  what is $(dg/df)(x)$?

I think it makes sense. But I think that expression also needs to equal $1$ for all $x$ since infinitesimal changes on both sides of the equation produced by an infinitesimal changes in $x$ need to be the same.


How to "Repeat" A Function In an Interval Periodically? Given a function $f(x)$, how can you use sine (and not mod), to make $f(x)$ in an interval of $[a,b]$ to repeat every interval of $b-a$? In answers, use $f(x)=x$ as an example. I also do not expect it to be continuous.

How about
$$f\left(\frac{a+b}2+\frac {b-a}\pi \arctan \left  ( \tan \left ( -\frac \pi 2 +\pi\frac {x-a} {b-a} \right)\right)\right)$$

You want the period to be $b-a=T,$ so compose the function with a sinusoid with this period.


Peano Induction confusion In a beginning Analysis book, I found this basic representation of induction:

  Let $A$ be any set or collection of natural numbers $\mathbb{N}$ with
  the properties (1) $1 \in A$ and (2) $k + 1 \in A$ wherever $k \in A$,
  then $A = \mathbb{N}$.

Yes, this is informal, but I can only understand this (and any other Peano Axioms) to mean that when you get to the "last" member of $A$, say, $k_\omega$ and $k_\omega + 1$ is, by definition, also in $A$, we must conclude that $A$ can "go on indefinitely" until it too is actually all of $\mathbb{N}$. It's as if any set of natural numbers that has a proper successor function included in its definition had the ability to instantly blow itself up to be the entire set of natural numbers. How can I understand this any other way? It seems a paradox to even speak of "subset $A$" when you say it has a "machine," i.e., a successor function, that implies it never was a subset. Is this a sort of contradiction trick?

First of all, there's nothing here about "never was a subset"; remember that $\mathbb N$ is a subset of itself --- indeed, every set is a subset of itself.

Now for your real question, here's one way to understand induction, which some people have found useful; I hope it helps you, but if it doesn't then just wait for more people to answer.  Think about a set $A$ of natural numbers  which happens to contain the number $1$, but suppose it's not the whole set $\mathbb N$ of all natural numbers, so some natural number, say $z$, is not in $A$.  Now imagine counting from $1$ to $z$ and checking whether the numbers you name are in $A$ or not. So you ask the questions "Is $1$ in $A$?", "Is $2$ in $A$?", "Is $3$ in $A$?", $\dots$, "Is $z-1$ in $A$?", and "Is $z$ in $A$?"  The answers to these questions start with "yes" for the first question (because $1\in A$) and end with "No" for the last question (because $z$ was chosen to be outside $A$). So, at some step during the counting, the answers must have switched from "Yes" to "No".  (It might have gone back and forth between yes and no several times, but that doesn't matter. All  I care about is that, in  order to go from "yes" at the beginning to "no" at the end, you need to switch from "yes" to "no" at least once.) Now think about that switching moment. You got a "yes" answer to some question and "no" to the next question. Those questions were about two consecutive natural numbers, say $k$ and $k+1$.  So $k\in A$ but $k+1\notin A$.  In other words, we have a counterexample to the implication "whenever $k\in A$ then $k+1\in A$."

Summary: If $1\in A$ but some $z\notin A$, then we cannot have the implication "whenever $k\in A$ then $k+1\in A$."

The induction principle is just this same result in contrapositive form. Assuming that "whenever $k\in A$ then $k+1\in A$." we cannot have "$1\in A$ but some $z\notin A$." So, if we also assume $1\in A$ then there cannot be any natural number $z\notin A$.   That is, $A$ must contain all of the natural numbers.

There is nothing mysterious about induction. The principle of induction may hold on sets other than the natural numbers, even on finite sets. It can be shown to hold on any singleton for example. If we have $n=\{ 1 \}$ and $s(1)=1$, then it is easy to prove that:

  $\forall a\subset n: [1 \in a \land \forall k\in a: [s(k)\in a] \implies \forall k\in n: k\in a]$

Likewise for $n=\{ 1, 2\}$, $s(1)=2$ and $s(2)=1$. Induction would not hold, however, if $s(1)=1$ and $s(2)=2$. (Hint: The subset $a=\{1 \}$ would be a counter-example.)

If we have the function $s: n\to n$ for any non-empty, possibly finite set $n$, (say $1 \in n$), then induction would hold on subset $m\subset n$ such that:

  $m=\{1, s(1), s(s(1)), s(s(s(1))), \cdots \}$

(Hint: Suppose $a\subset m$, $1 \in a$ and $\forall k\in a:[s(k)\in a]$. Suppose further that $x\in m$. Prove $x\in a$.)


how to apply implicit function in derivatives I find this question rather akwardly put.... have a look

The tangent to the curve: $y^2 - x^3$ passes point $P(1,1)$ and cuts the axes at points $Q$ and $R$ for $x$- and $y$-axis respectively. Find the ration $\overline{PR} : \overline{RQ}$.

I am unable to interprete this implicitly,

can we interprete as $f(x, y) = y^2 - x ^3$  of $y^2 - x^3 = 0?$

$y^2 -x^3 = 0 \Leftrightarrow \frac{d}{dx}(y^2) = \frac{d}{dx}(x^3) \Leftrightarrow 2y\frac{dy}{dx} = 3x^2 \Leftrightarrow \frac{dy}{dx} = \frac{3x^2}{2y}$
This is how implicit differentiation is done, however it's not needed for your case. You may explicitly find $y(x) = x^{3/2}$ and solve the problem using formula for tangent line.


Probability with Markov chains I need some hint about Markov chains. So here is my homework.

  Let $\{ X_t : t = 0,1, 2, 3, \ldots, n\}? $ be a Markov chain. What is $P(X_0 =i\mid X_n=j)$?

So I need to calculate if it's $j$ in the time of $n$ what is the probability of being $i$ at the start?

Is it :

Since if we start from state 0, then the probability to go to next state 1 is $1/2$, and to state 2 is $1/4$, etc.

$$ P_i = \left(\frac {1} {2}\right)^n \cdot \frac {1} {2}$$

Is that right ?

Hint:
$P(X_0=i\mid X_n=j)=\frac{P(X_n=j\mid X_0=i)\times P(X_0=i)}{P(X_n=j)}=p_{ij}^{(n)}\times\frac{\pi_i}{\pi_j} $

Note: The Markov chain must be stationary, i.e., the chain must be in steady state.

Use Bayes theorem and decomposition matrix or probability generate function to solve it:
$$ P(X_0=i∣X_n=j) = \frac{P_{ij}^n\times P(X_0=i)}{\sum P_{ij}^n\times P(X_0=i)}$$


Proving commutativity of addition for vector spaces I'm trying to prove commutativity of addition for vector spaces, using the axioms for vector spaces. Apparently commutativity can be proven! Im having trouble getting a good feel for what is allowed and what is not. Here's my work so far:

$u+v+u+v = 2(u+v) = 2u + 2v = u+u+v+v = u+(u+v)+v$

Here I just wanna claim that $u+(v+u)+v = u+(u+v)+v$

$\Rightarrow -u+u+(v+u)+v+(-v) = -u+u+(u+v)+v+(-v)$ : here im just adding -u to the right, and -v to the left. Question: is this "adding to both sides" really legit in this context? Why?

Quick help proof: $-v+v = (-1)v+(1)v = (-1+1)v = 0v = 0 = v-v$

And another: $ 0+v = v+(-v) + v = (1)v + (-1)v + v = (1-1)v + v = v = v+0$

We have $0 + (u+v) + 0 = 0+(v+u)+0 \Rightarrow u+v = v+u$

This feels ugly and not at all elegant, especially the great leap "add -u to both sides" feels completely out of place. Do I need more lemmas? Is there a more elegant way?

//not homework or anything, just for my own pleasure, feel free to provide theory, as it is more insightful than solutions. :)
Thanks!

EDIT: corrected notation a little.

Normally commutativity is taken as an axiom, but you can deduce it from associativity, distributivity and from the existence of inverses as follows:

$(u + v) - (v + u) = (u + v) - v - u$ (by distributivity)
$ = u + (v - v) - u$ (by associativity)
$ = u + 0 - u = (u + 0) - u = u - u = 0$

So $u + v = v + u$

I agree that commutativity is an axiom for Vector Spaces, so what you might need to show is that the ordinary vector spaces you know about satisfy the axioms of Vector Spaces.  Then you can forget about my capital letters.

You know numbers commute.  Use that to show vectors commute.

$\begin{align}u+v&=&(u_1,u_2,...,v_n)+(v_1,v_2,...,v_n)\\
&=&(u_1+v_1,u_2+v_2,...,u_n+v_n)\\
&=&(v_1+u_1,v_2+u_2,...,v_n+u_n)\\
&=&v+u
\end{align}$


Order of study? Rudin, Spivak, Munkres? I'm currently taking an analysis course at a top 10 four year university in which we use Baby Rudin as our primary text.

I was curious to know the order in which I should continue my studies. That is, should I study Rudin then Spivak's Calculus on Manifolds then Munkres Topology? Or, should I study Rudin and Spivak concurrently and then Munkres? Or some variation? I already have exposure to topology, just never in a formal course.

I'm trying to broaden my mathematical foundation as much as possible in the next year and a half before I leave high school, so I'd like to know the different analysis/topology paths to consider, and why.

As someone who studied Baby Rudin in high school, I suggest studying the first 4 chapters of Baby Rudin before moving on to Munkres. When you start studying Munkres, you can go straight into the second chapter (Topological spaces).


Formula to calculate the number of possible positions for $x$ numbers What formula do I use to calculate the number of possible positions for $x$ numbers?

Let's say I have $3$ people in a race. What are all the possible combinations of the order they can finish in? Let's assume ties are not possible. I heard I use factorial but its been a while since I have used factorials. So I want to verify.

It is easy to enumerate for three people. Lets call the people $x_1,x_2,x_3$. The possible orderings are shown below.

$x_1,x_2,x_3$
$x_1,x_3,x_2$
$x_2,x_1,x_3$
$x_2,x_3,x_1$
$x_3,x_1,x_2$
$x_3,x_2,x_1$

In general, in a $n$ people race, lets denote the people by $x_1,x_2,\ldots,x_n$. The first position can be taken by any one of the $n$ individuals. Hence, there are $n$ options for the first place. Now given that the first position is taken by $1$ individual, for each of the $n$ options for the first position, the second position can be taken by any one of the remaining $n-1$ individuals. Proceeding like this, in general the $k^{th}$ position can be taken by any one of the remaining $n-k+1$ individuals. Hence, the total number of ordering is given by $$n \times (n-1) \times \cdots \times (n-k+1) \times \cdots 2 \times 1$$which is nothing but $n!$.

In you case, $n=3$ gives us $3! = 6$ which matches with our enumeration.

Decent answers. However, with no duplicates, the solution may be more simply explained.

Since no ties are involved (duplicates) each position can have one less than the next highest finisher and thus we get:

3 * 2 * 1 = 6

If there were 5 people in the race, the solution would then be 5 * 4 * 3


Evaluating $\lim\limits_{n\to\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$ I'm supposed to calculate:
$$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$
By using WolframAlpha, I might guess that the limit is $\frac{1}{2}$, which is a pretty interesting and nice result. I wonder in which ways we may approach it.

The probabilistic way:

This is $P[N_n\leqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+\cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.

By the central limit theorem, $Y_n=\frac1{\sqrt{n}}(X_1+\cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_n\leqslant 0]\to P[Z\leqslant0]$.

Finally, $P[Z\leqslant0]=\frac12$ and $[N_n\leqslant n]=[Y_n\leqslant 0]$ hence $P[N_n\leqslant n]\to\frac12$, QED.

The analytical way, completing your try:

  Hence, I know that what I need to do is to find $\lim\limits_{n\to\infty}I_n$, where
  $$
I_n=\frac{e^{-n}}{n!}\int_{0}^n (n-t)^ne^tdt.$$

To begin with, let $u(t)=(1-t)e^t$, then $I_n=\dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$
J_n=\int_{0}^1 u(t)^n\mathrm dt.
$$
Now, $u(t)\leqslant\mathrm e^{-t^2/2}$ hence
$$
J_n\leqslant\int_0^1\mathrm e^{-nt^2/2}\mathrm dt\leqslant\int_0^\infty\mathrm e^{-nt^2/2}\mathrm dt=\sqrt{\frac{\pi}{2n}}.
$$
Likewise, the function $t\mapsto u(t)\mathrm e^{t^2/2}$ is decreasing on $t\geqslant0$ hence $u(t)\geqslant c_n\mathrm e^{-t^2/2}$ on $t\leqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})\mathrm e^{-1/(2\sqrt{n})}$, hence
$$
J_n\geqslant c_n\int_0^{1/n^{1/4}}\mathrm e^{-nt^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\int_0^{n^{1/4}}\mathrm e^{-t^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\sqrt{\frac{\pi}{2}}(1+o(1)).
$$
Since $c_n\to1$, all this proves that $\sqrt{n}J_n\to\sqrt{\frac\pi2}$. Stirling formula shows that the prefactor $\frac{e^{-n}n^n}{n!}$ is equivalent to $\frac1{\sqrt{2\pi n}}$. Regrouping everything, one sees that $I_n\sim\frac1{\sqrt{2\pi n}}n\sqrt{\frac\pi{2n}}=\frac12$.

  Moral:
  The probabilistic way is shorter, easier, more illuminating, and more fun.

  Caveat:
  My advice in these matters is, clearly, horribly biased.

On this page there is a nice collection of evidence.

I add another proof which also uses the Stirling formula.

$\displaystyle e^{-n}\sum\limits_{k=0}^n\frac{n^k}{k!} = e^{-n}\sum\limits_{k=0}^n\frac{k^k (n-k)^{n-k}}{k!(n-k)!} \hspace{4cm}$ e.g. here

$\displaystyle \lim\limits_{n\to\infty} e^{-n}\sum\limits_{k=1}^{n-1}\frac{e^k e^{n-k}}{\sqrt{2\pi k (1+\mathcal{O}(1/k))}\sqrt{2\pi (n-k)(1+\mathcal{O}(1/(n-k)))}} $

$\displaystyle = \lim\limits_{n\to\infty} \frac{1}{2\pi}\frac{1}{n}\sum\limits_{k=1}^{n-1}\frac{1}{\sqrt{\frac{k}{n}\left(1-\frac{k}{n}\right)}} =\frac{1}{2\pi} \int\limits_0^1\frac{dx}{\sqrt{x(1-x)}}=\frac{\Gamma(\frac{1}{2})^2}{2\pi~\Gamma(1)} = \frac{1}{2}$


Recommendations for books on complex analysis and on measure theory? I'm looking for a book on complex analysis that has a similar writing style to either Terry Tao's Analysis II or Nathan Jacobson's Basic Algebra series. I have found both of these extremely easy to read and follow the proofs given quite easily, or at least I have so far. Preferably the level would be for an advanced undergraduate course or a book used in a first year graduate class on complex analysis.

For the measure theory book, I was wondering what a good book would be for a study of the subject starting from almost the ground level (like why Riemann's criteria for integrability is not entirely sufficient), but would be accessible to an advanced undergraduate.

For complex analysis, I would recommend Marsden and Hoffman's Basic Complex Analysis.  Very detailed and shows every step, and it's a good introduction for those not ready for Rudin (Real and Complex anaylsis).  As for measure theory, baby Rudin (Principles of Mathematical Analysis) is undoubtedly the standard to which all others should be held.  The text starts by proving most of the theorems used in calculus and culminates with great chapters on measure theory and the Lebesgue theory of integration.

For complex analysis I would suggest either Stein's Princeton Lectures on Analysis Volume 2- Complex Analysis or Freitag's Complex Analysis.
As for measure theory there is this great book by Folland: Real Analysis Modern Techniques and Their Applications.
It was the book that I used when I took the course, and I really liked it. I found, especially after Chapter 1, that was a delightful experience to read it, and learn from it.
Hopefully you'll like these books just as I did.


Help with prove of inf. I need to prove that:

$$\inf\{\frac{1}{3}+\frac{3n+1}{6n^2} \Big| n\in\mathbb N\}=\frac{1}{3}$$

I get stuck with my proof, I'll write it down.

$$n\geq1$$
$$3n\geq3$$
$$3n+1\geq4$$
$$\frac{1}{3}+3n+1\geq4+\frac{1}{3}$$

Now, I'm having a problem with $6n^2$ if I multiply by $6n^2$, I'll get variable in the express of $4+\frac{1}{3}$.

Any ideas?, Thanks!

Let:
$$
S =
\left\{\frac{1}{3} + \frac{3n + 1}{6n^2} ~\middle|~ n \in \mathbb N\right\}
$$
Notice that since $3n + 1 > 0$ and $6n^2 > 0$, we know that $\frac{3n + 1}{6n^2} > 0$ so that $\frac{1}{3}$ is a lower bound for $S$. It remains to show that $\frac{1}{3}$ is the greatest lower bound.

To this end, choose any $\epsilon > 0$. Now recall that, by the Archimedean property, there is some $N \in \mathbb N$ such that $N > \frac{2}{3\epsilon}$. But then since $\frac{1}{3} + \frac{3N + 1}{6N^2} \in S$ and:
\begin{align*}
\frac{1}{3} + \frac{3N + 1}{6N^2}
&< \frac{1}{3} + \frac{3N + N}{6N^2} &\text{since }N > 1 \\
&= \frac{1}{3} + \frac{2}{3N} \\
&< \frac{1}{3} + \epsilon &\text{since }N > \frac{2}{3\epsilon} \iff \epsilon > \frac{2}{3N} \\
\end{align*}
it follows that $\frac{1}{3} = \inf S$, as desired. $~~\blacksquare$

Obviously $\frac{1}{3}+\frac{3n+1}{n^2}\geq\frac{1}{3}.$ The sequence $a_n=\frac{1}{3}+\frac{3n+1}{n^2}$ converges to $\frac{1}{3}$ since $\frac{3n+1}{n^2}$ behaves like $\frac{1}{n}.$ Thus $a_n\rightarrow \frac{1}{3}.$ whcih is to say $\inf=\frac{1}{3}$


How to derive the solutions of a linear constant-coefficient differential equation One thing I've hated about differential equations is how I need to guess the form of the solution.
e.g. it's easy to show that solutions to a linear constant-coefficient differential equation such as

$$y''' + 2 y'' + 3 y' + 4 y = 0$$

have the form of (some linear combination of) exponentials:
You can just plug in $y = e^{a x + b}$ and show that the equation is satisfiable.

But I feel there is something wrong if I must find the solutions through guess-and-check.
Yet what I was never told, and what I seem to never be able to find from looking online, is how to derive this fact rigorously, when I don't already have the intuition necessary to guess the form of the solution?

Sitting down and working through some math, I've come up with some nonsense that works quite beautifully:

Place the homogeneous equation into the following matrix form:
$$\vec{y}\,' = A \vec{y}$$ where, for example, we have $\vec{y} = \begin{bmatrix} y & y' & \ldots \end{bmatrix}^T$
Drop the arrows and pretend everything is a scalar:
$$y' = Ay$$
Separate the, uh, variables:
$$\frac{dy}{dx} = A y$$
$$\frac{dy}{y} = A\,dx$$
Integrate:
$$\int \frac{dy}{y} = \int A\,dx$$

$$\ln y = A x + b$$

$$y = e^{A x + b}$$

Profit!

That was fun while it lasted... but how do I derive it properly?

So, most of the math you've seen up to now is very simple, by mathematical standards.  The sorts of problems that come up in algebra, trig, and calculus courses can often be solved just by starting from an equation, applying a set of transformations to both sides of the equation, and arriving at an answer.

Most of math doesn't work that way at all.  I mean, consider Euclid's proof that there are infinitely many prime numbers, for instance.  Would you ask something like

"Why did I have to guess that looking at $p_1 p_2 \cdots p_n + 1$ and its factorization was the right thing to do?  Isn't there some way to just derive this automatically?"

No, of course not.  There's nothing nonrigorous about Euclid's proof, and there's nothing nonrigorous about observing that the $k$-th derivative of $e^{ax+b}$ is $a^k e^{ax+b}$, and that taking that together with the fundamental theorem of algebra will give us all the solutions we seek.


Why does creating a model show consistency? As per the title, why does the ability to generate a model from axioms prove they are consistent?

I would just like to mention that one generally does not construct a model of a theory $T$ from the axioms of $T$ itself.  Instead, one uses external means to produce a structure that one can show is a model of $T$.

Here is where Ben's answer comes into play, although in my opinion it obfuscates matters: if you construct a model of $T$ using some other theory $T^\prime$, then what you have really done is shown that the consistency of $T^\prime$ implies the consistency of $T$.  There are times where this distinction is important.  For example, from the axioms ZFC of set theory one can construct a model of Peano Arithmetic, PA.  It is unknown whether ZFC is actually consistent, though widely believed, and therefore we cannot immediately conclude that PA is consistent, though this is also widely believed.

But let's assume that we have constructed a model $M$ of $T$ using methods that are above reproach.  For example, $M$ might be a finite $\mathcal{L}$-structure of specific size $n$.  The claim that $T$ is consistent then comes down to two facts about the underlying logic.

Fact 1: If $M$ is a structure in some language $\mathcal{L}$, then $M \models \varphi$ and $M \models \neg \varphi$ cannot both be true for every $\mathcal{L}$-sentence $\varphi$.  (In fact, exactly one of $M \models \varphi$ or $M \models \neg \varphi$ holds.)

Fact 2: If $T$ is a theory in a language $\mathcal{L}$ and $\varphi$ is a $\mathcal{L}$-sentence such that $T \vdash \varphi$, then $M \models \varphi$ for all models $M$ of $T$.

Now, if $\varphi$ were an $\mathcal{L}$-sentence such that $T \vdash \varphi$ and $T \vdash \neg \varphi$, then by Fact 2 we conclude that $M \models \varphi$ and $M \models \neg \varphi$, but this contradicts Fact 1!

Creating a model doesn't show that a theory is consistent. What it shows is that, if we can create a model of theory A within theory B, then we know that if A is inconsistent, B must be inconsistent as well.

For example, say A is elliptic geometry. At one time, people thought that A was inconsistent, and they tried really really hard to prove that it was inconsistent. But let B be Euclidean geometry. We can construct a model of A in B, by taking A's points to be points on a sphere, identifying points that lie at each other's antipodes, and taking lines to be great circles. This shows that if A was inconsistent, then B would as well.

In most cases, there is no hope of proving B's consistency, due to Godel's theorem. However, it often happens that B is a theory that people don't think is likely to be inconsistent, e.g., ZFC set theory or Peano arithmetic. Therefore A has a model in B, everybody realizes that it's a waste of time to worry about inconsistencies in A.


Find the area enclosed by the curve $x=t-\sin t $, $y=1-\cos t$ from $0$ to $2\pi$ Find the area enclosed by the curve $x=t-\sin t $, $y=1-\cos t$ from $0$ to $2\pi$ and the x-axis

Not sure how to execute. is it just that $.5\int_{0}^{2\pi}x^2+y^2$ ?

and not sure how to account for the x-axis limitation on the area

So, not knowing your level and what you've tried, I'm going to offer this

HINT: You want the area under the curve and above the $x$-axis, so you want $\displaystyle\int_{x=0}^{2\pi} y\,dx$. Rewrite everything in terms of $t$, putting in $y=y(t)$, $dx = \dfrac{dx}{dt}dt$, and you should get a reasonably simple $t$ integral from $t=0$ to $t=2\pi$.

Reparametrize on $x'$ and $y'$ with $x' = \frac{x}{\pi} - 1$ and $y' = \frac{y}{2}$. You'll get a much clearer drawing, and probably much better formulae. After that, multiply your result by $2\pi$ to account for the initial (linear) transformation.


Brute-force bifurcation diagram I know there is unaccepted answer in this question on this problem. But let’s make it clear, really. I believe it can serve as great reference starting point.
Suppose that I have autonomous system $\mathcal{D(\dot{y},y,\mu)}$  given by ODE/DAE and some parameter $\mu$. Using implicit an integration scheme, I can obtain a bunch of solutions for different (consistent) initial conditions $y_0(t_0)$ for some parameter value $\mu$.
Now, I know there are solutions which are stable (not oscillatory), limit cycles (harmonic oscillatory solution with period $T$ with possible harmonics), damped oscillatory solutions, quasiperiodic solutions and probably some chaotic behaviour. I am interested in creating a bifurcation diagram.
In terms of pseudocode, how can I achieve this?
In particular, I am confused about picking points of the time series.  How do I choose them (sampling period $T$)? What is the rule in such cases?
For illustration, the time series below are for some fixed parameter value $\mu_1$ and three different initial conditions. They clearly exhibit chaotic behaviour:

For same set of initial conditions but a different $\mu_2$, $\mu_2\neq\mu_1$, I obtain these time series:

We can see, that depending on initial condition, only a phase difference occurs, but all trajectories tends to be same.
Can you provide a commented procedure for this?
In papers, there are no explicit descriptions on how they derived their diagrams.

In particular, I am confused about picking points of time series.  How do I choose them (sampling period $T$)? What is the rule in such cases?

To make a bifurcation diagram for a continuous-time system, you first need to make a Poincaré map. Specifically, you obtain a sequence of values of a reasonable observable at a somewhat systematically determined points of your oscillation. The most common choice would be the sequence of local minima or maxima of one dynamical variable, but you can also go for observables like the slope at zero crossings or similar. Usually, you choose some aspect of the dynamics that is relevant to your research.
Note that you cannot just sample at a fixed time interval, since there is no fixed period length between different parameters and not even within one parameter in case of chaotic dynamics.
Except for using the Poincaré map instead of the actual map, the method is the same as for discrete-time systems:

Choose a reasonably fine sampling of the parameter interval you are interested in, say $μ_i = μ_\text{min} + \frac{i}{N} (μ_\text{max}-μ_\text{min})$ with $i \in {1, …, N}$.
For each $μ_i$:

Evolve the system (using that $μ_i$) long enough to get rid of transients.
Further evolve the system for a sufficient amount of time and extract the values of the Poincaré map (let them be $a_1, a_2, …$).
Make dots at $(μ_i,a_1), (μ_i,a_2), …$ in your bifurcation diagram.

You only need to consider multiple initial conditions if your system is multistable, which you should also notice as interrupted lines on a good bifurcation diagram (unless you have two or more competing chaotic or quasiperiodic attractors).

To answer your first question, to select the timestep you need to satisfy the following

Your timestep is small enough that you can resolve your features. You may attempt to bound how fast your function can change (e.g. via Lipshitz continuity). If you find such a bound, you can directly figure out a timestep small enough to capture all local fluctuations. Note however, that some evil functions (e.g. $\sin \frac{1}{x}$) don't have such a bound, in which case you are screwed :D
Your timestep has to be such that the error of your numerical integration scheme (e.g. Runge-Kutta) on the sampling timescale is smaller than the changes you observe due to your parameter. One way to approximate the error is to use two different numerical integration procedures (e.g. order 2 and 4) and approximate the error via difference between the results.


A coin is tossed 7 times. The probability that at least 4 consecutive heads appear is? A coin is tossed 7 times. The probability that at least 4
  consecutive heads appear is?

I have checked and double checked but I can't figure out which cases I am missing.

Here are the cases:

4 consecutive heads appear:

$n_1 = \dfrac{4!}{3!}= 4$

5 heads appear

Subcase 1: 4 consecutive heads appear and the other head is separated.

For example: HTTHHHH or THTHHHH

Subcase 1 has $4$ possibilities.

Subcase 2: 5 consecutive heads:

$\dfrac{3!}{2!} = 3$

$n_2 = 4+ 3 = 7$

6 heads appear

There are 6 gaps (including the ends) where we can place the $T$

Let me show those places by G:

GHGHGHHGHGHG

$n_3 = 6$

All heads appear

$n_4 = 1$

$P(\text{4 consecutive heads}) = \dfrac{n_1+ n_2+ n_3 + n_4}{2^7}  = \dfrac{18}{2^7} = \dfrac{9}{64}$

Please let me know my mistake.

The component of $n_2$ counting the ways that five heads appear, one of which is separated from the other four, should be 6 rather than 4:
$$\text{HTTHHHH THTHHHH}\\
\text{HTHHHHT THHHHTH}\\
\text{HHHHTTH HHHHTHT}$$
Thus the probability is $\frac{20}{2^7}=\frac5{32}$.

I would split cases in the following way:

1) Exactly 4 consecutive heads: HHHHTxy, THHHHTx, xyTHHHH, => ten possibilites

2) Exactly 5 consecutive heads: HHHHHTx, THHHHT, xTHHHH => five possibilities

3) Exactly 6 consecutive heads: two possibilities, as the 7th flip must be T

4) Exactly 7 consecutive heads: one possibility

In total 18 possibilities.


Prove that function $f(n) = \cos(1/n)$ is monotonically decreasing? Ho can we prove that this function

$$f(n) = \cos(1/n)$$

is monotonically decreasing? I computed derivative of this function and got:

$$f'(n) = \frac{\sin(1/n)}{n^2}$$

and it is positive, but should be negative, because function $f(n) = \cos(1/n)$ is monotonically decreasing.

Is $n$ supposed to be a positive integer? If so you should probably call $f$ a sequence instead of a function, to prevent confusion.

Assuming that yes you are talking about the sequence $\cos(1/n)$: That sequence is not decreasing, it's increasing.

In detail: The sequence $1/n$ is decreasing. And $0<1/n<\pi$, which means that $\cos$ is also decreasing on the relevant range. A decreasing function of a decreasing sequence is increasing.

Remember that the derivative of $1/n^2$ is negative.


Is there at least one irrational number with the property that it cannot be defined by a finite string of information? Ok, so maybe that wasn't the best way of phrasing the question, but I think it's specific enough. Let me explain myself a bit more below in case I am wrong.

So I'm assuming (although I've never checked) that the irrational numbers are defined as simply all reals that are not rational.

I'm asking about the existence, then, of an irrational number that has no finite description. I.e, not only does it not have a finite-number or recurring decimal description, but no other description could be made (counting things such as "The ratio of the circumference and diameter of any circle in a Euclidean plane" as finite).

Clearly, there would have to be infinitely many of these and they would have to form continuous connected regions of the real line, otherwise they would afford descriptions such as "The otherwise-non-finitely-describable number lying between x & y" where x & y bound the "otherwise-non-finitely-describable z, and z can be shown to be the only such number between x & y.

If so, then this would have implications for Laplace's Demon and other similar philosophical arguments since it would be mathematically impossible to have knowledge of all of the universe so long as at least one parameter lay within one of these non-finitely-describable regions.

Yes, there are such numbers.  Chaitin discusses them extensively, he has a popular book on the subject, Meta Math: The Quest for Omega.  They do not form continuous connected segments of the real line, because for example, the rationals are dense (that is, between any two real numbers there is at least one rational -- and in fact there are an infinite number of rationals).

However, these non-computable numbers are also dense in the real line.

You might want to take a look at the "computability theory", "definable number", and "analytical hierarchy" articles in Wikipedia.

Note that this doesn't pose as big a problem for the philosophy of physics as you might think:  This doesn't say that you cannot measure a physical constant to whatever precision you might wish.

I don't think the set of all such numbers is well-defined. Using particular words to mean one thing makes defining other things more difficult. Is the set of irrationals that can be defined in English the same as the set that can be defined in French or Chinese?


A closed ball in a metric space is closed Prove that any closed ball in a metric space is closed.

(Note that this is not a duplicate as this is a proof verification question and have a different proof, in my opinion, as compared to other proofs on this site)

My Attempted Proof:   Let $(X, d)$ be a metric space. Pick a closed ball $\Phi = \overline{B(x, r)} = \{y \in X \ | \ d(x, y) \leq r\}$. Note that at this moment in time $\overline{B(x, r)}$ is just a notation, we don't know if $\Phi$ is actually closed.

We now show that $\Phi$ is closed. To do this we show that $X \setminus \Phi$ is open. Observe that $X \setminus \Phi = \{y \in X \ | \ d(x, y) > r\}$. Pick $y \in X \setminus \Phi$. For this $y$ we have $d(x, y) > r$ which implies that $d(x, y) = r + \epsilon$ for some $\epsilon > 0$.

We claim that $B(y, \epsilon) \subseteq X \setminus \Phi$. To prove this claim, pick $z \in B(y, \epsilon)$. We now show that $z \in X \setminus \Phi$ by showing that $d(x, z) > r$. To that end observe that the triangle inequality gives us

\begin{align*}
  & d(x, y) \leq d(x, z) + d(z, y) \\
  & \implies \epsilon + r \leq d(x, z) + d(y, z) \\
  & \implies \epsilon + r < d(x, z) + \epsilon \ \ \ \ \ \  \ \ \  \text{since $d(y, z) < \epsilon$} \\
  & \implies r < d(x, z)
  \end{align*}

as desired. Hence $z \in X \setminus \Phi$ and we have $B(y, \epsilon) \subseteq X \setminus \Phi$, and since $y$ was arbitrary we have that $X \setminus \Phi$ is an open set in $(X, d)$ and thus $\Phi$ is a closed set. $\square$

Is this a rigorous and satisfactory proof? Can it be improved in any way?

Your proof is flawless.

The only recommendation that I have is to change the notation on your closed ball.

$\overline{B(x, r)}$ is used for the closure of the open ball B(x, r) not the closed ball.

$\overline{B}(x,r)$ is a better notation for a closed ball.

The closure of an open ball is not necessarily the closed ball depending on the topology.

We know that a closed ball in a metric space is closed. If we replace
the triangular inequality of the metric d by:
d1
(x, y) ≤ s[d1
(x, z) + d1
(z, y)],
where s > 1. Then check if still the closed ball in a metric space with
the metric d1 is closed?explain


The global section of direct sum of twisted sheaves I am working with the Exercise 5.14 in Hartshorne's GTM52. And its problem (a) is stated roughly as follows.

Let $X$ be a closed subscheme of $\mathbb{P}^r_k$, a projective $r$-space over an algebraically closed field $k$, let $S$ be the homogeneous coordinate ring of $X$, i.e. $S=k[x_0,\dots,x_r]/I$, where $I=\Gamma_*(\mathscr{I}_X)$, and let $S'=\bigoplus_{n\ge0}\Gamma(X,\mathscr{O}_X(n))$.
Show that $S$ is a domain and that $S'$ is its integral closure.

Here my questions don't involve the $S$. I just want to ask something about the $S'$.
The hint of the problem (a) tells that one can regard the ring $S'$ as the global sections of such a sheaf of rings $\mathscr{S}=\bigoplus_{n\ge0}\mathscr{O}_X(n)$ on $X$, a direct sum of infinitely many sheaves. That is, there is an equation about them:
$$\Gamma(X,\mathscr{S})=\Gamma(X,\bigoplus_{n\ge0}\mathscr{O}_X(n))=\bigoplus_{n\ge0}\Gamma(X,\mathscr{O}_X(n)).$$
Does it true? I know that the arbitrary direct sum of sheaves $\{\mathscr{F}_i\}$ is defined to be the associated sheaf of the presheaf $U\mapsto\bigoplus_{i}\mathscr{F}_i(U)$. In the finite case, such a presheaf is just a sheaf. And else, it may be not, because we can give a counter-example (see here: Direct and inverse limits of sheaves). So I want to query if the global sections of $\mathscr{S}$ is just $\bigoplus_{n\ge0}\Gamma(X,\mathscr{O}_X(n))$, and if the process of sheafification doesn't change the global sections (up to an isomorphism).
Thanks in advance.

The presheaf direct sum of sheaves should be a sheaf as long as $X$ is Noetherian. Clearly it is a separated presheaf, so all we need to show is the gluability axiom. If I have an infinite collection $s_i \in \bigoplus_{j} \mathcal{F}_j(U_i)$ that agree on overlaps, then they have a natural gluing $s \in \prod_j \mathcal{F}_j(\bigcup_i U_i)$. By Noetherianness, the union of the $U_i$ is quasicompact, so in fact this section $s$ can be viewed as gluing together FINITELY many $s_i$, hence is nonzero in only finitely many entries and lives in the subgroup $\bigoplus_j \mathcal{F}_j(\bigcup_i U_i)$.
In particular, in your case above this holds and so the direct sum commutes with global sections.

If $\{F_i\}_{i\in I}$ is a set of quasi coherent sheaves on a scheme $X$ of finite type over a field, it follows the direct sum $F:=\oplus_{i \in I} F_i$ is a quasi coherent sheaf, and there is an isomorphism of global sections
$$F1.\text{   }\Gamma(X, F) \cong \oplus_{i \in I} \Gamma(X, F_i):$$
I believe taking global sections commutes with arbitrary direct sums of qc sheaves.
Question: "So I want to query if the global sections of $\mathcal{S}$ is just $\oplus_{n \geq 0} \Gamma(X,\mathcal{O}_X(n))$, and if the process of sheafification doesn't change the global sections (up to an isomorphism)?"
In your example $X$ is a scheme of finite type over $k$ and $F:=\oplus_{n \in \mathbb{Z}} \mathcal{O}(n)$ is a direct sum of locally trivial sheaves of rank one, in particular $\mathcal{O}(n)$ is quasi coherent. Hence it seems to me formula F1 should hold in your case. You should try to write down an explicit isomorphism
$$\Gamma(X, \oplus_{n} \mathcal{O}(n)) \cong \oplus_{n} \Gamma(X, \mathcal{O}(n)).$$


Is $R[i,j,k]$ a division ring whenever $R$ is a field? Let $R$ be a field , let us adjoin $i,j,k$ to $R$ and write $$R[i,j,k]:=\{a+bi+cj+dk :a,b,c,d \in R \}$$ where $i,j,k$ satisfies $a+bi+cj+dk=0 $ iff $a=b=c=d=0$, $i,j,k$ commutes with every element of $R$, $i^2=j^2=k^2=-1$ and $ij=k , jk=i , ki=j$.

  Then is it true that $R[i,j,k]$ is a division ring whenever $R$ is a field?

Suppose $-1 = x^2$ in $R$, then $(x+i)(x-i)=x^2-i^2 = 0$, so $R[i,j,k]$ is not zero-divisor free.
In general, we have $$R[i,j,k] \text{ is a division ring }\Leftrightarrow \forall a,b,c,d \in R: a^2+b^2+c^2+d^2= 0 \Rightarrow a=b=c=d=0.$$
For the one direction, suppose there are some $a,b,c,d$ not all zero, such that $a^2+b^2+c^2+d^2=0$ Note that in $R[i,j,k]$ we can factor the LHS as $(a+bi+cj+dk)(a-bi-cj-dk)$, so $a+bi+ci+dj$ is a zero divisor.
If we have $\forall a,b,c,d \in R: a^2+b^2+c^2+d^2= 0 \Rightarrow a=b=c=d=0$, then we can compute the inverse as $(a+bi+cj+dk)^{-1}= \frac{a-bi-cj-dk}{a^2+b^2+c^2+d^2}$.

Not true,
You can see if $R=\mathbb{Z}_3$, which is a field, but $R[i,j,k]$ is not division ring.


Given the result of a dot product and one of the vectors, is it possible to find the other vector? When processing geometry the dot product or $n\cdot L$ (where $n$ is the normal, $L$ is the light direction) is baked into the $w$ of a vertex, but since the $L$ is constant I wanted to know if there is any way to get $n$ without changing the backend processing?

Given a vector $\vec v$ and scalar $a$, there is no unique solution to the equation
$$\vec v\cdot\vec w=a.$$

Consider the case $\vec v=\vec k$, and $a=0$.  Then any vector of the form
$x\vec i+y\vec j$ is a solution to
$$\vec v\cdot \vec w=0.$$

You can't recover n from n.L and L:

Suppose v is any vector perpendicular to L, so that v.L $=0$. Then (n+v).L = n.L + v.L = n.L. So any such n+v also satisfies your condition on n.


What is $x^y$? How to understand it? $x+y=z$

I have a pen. He has a pen. Total is two pen. This is plus.

$x-y=z$

I had two pens. A pen was lost. So, I have a pen. Total remaining is one. This is minus.

$x\cdot y=z$

I have two pens. Three other friends have two pens. $4 \text{(persons)}\cdot 2 \text{(pens/person)}=8 \text{pens}$. This is multiply.

$x^y=z$

How to understand this?

I have one pen. I become really angry and I break it into $x$ pieces. Each time I get angry I break each of my pieces into $x$ even tinier pieces. I become angry $y$ times. I end up with $x^y$ pieces.

I have two friend. my friend has two more friend each which doesn't know each other, and they have 4 pen each.


Find a six digit integer Find an integer with six different digits such that the six digit integer is divisible by each of its digits.

For example, find ABCDEF such that A, B, C, D, E and F all can divide the number ABCDEF.

Show your answer along with mathematical reasoning.

The number $861432$ will work.  I guess $123864$ looks nicer.


Is there a non-continuous Riemann integrable function with an anti-derivative? Is there a function $f:[a,b]\rightarrow\mathbb{R}$ (for real $a<b$) which is Riemann integrable and has an antiderivative in $[a,b]$, but is not continuous?

Consider:

$$f(x) = \begin{cases} 2x \sin \left( \frac1{x} \right) - \cos \left( \frac1{x} \right), x \neq 0 \\ 0, x=0 \end{cases}$$

$f$ is Riemann integrable on $[-1,1]$ (by Lebesgue's theorem for Riemann integrals, for instance), and has the antiderivative:

$$F(x) = \begin{cases} x^2 \sin \left( \frac1{x} \right), x \neq 0 \\ 0, x = 0 \end{cases}$$

Assume we have a function $g(x)$ is continuous and Riemann integrable with an antiderivative. Let's define another a new function $$f(x)= \begin{cases} g(x), x \neq c \\ \neq g(c), x = c \end{cases}$$

The new function $f(x)$ is not continuous but it is Riemann integrable and has the same antiderivative as $g(x)$.


Show that $\frac{1}{MA^2}+\frac{1}{MB^2}+\frac{1}{MC^2}+\frac{1}{MD^2}\geq2$ for $M$ inside square $ABCD$ with side length $2$ Show that $$\frac{1}{MA^2}+\frac{1}{MB^2}+\frac{1}{MC^2}+\frac{1}{MD^2}\geq2$$ for any point $M$ inside of the square $ABCD$ whose side length is $2$.

I could manage to prove this using analytic geometry. Looking for a geometrical proof and possibly generalization of that.

For an analytic geometry proof, see @MichaelRosenberg's answer to the question Prove:$\frac{1}{(x-1)^2+(y-1)^2}+\frac{1}{(x+1)^2+(y-1)^2}+\frac{1}{(x-1)^2+(y+1)^2}+\frac{1}{(x+1)^2+(y+1)^2}\geq2 $ ,if $-1<x,y<1$ .

COMMENT:

An experimental approach;

In a Pythagorean triple (a, b,c) it can be seen that  $c^2<2.5 ab$.Now considering the sketch we have:

$MA^2<2.5(S_{AHME} =AE \times AH)$

$MB^2<2.5(S_{HBGM} =AE \times BH)$

$MC^2<2.5(S_{EMFC} =AH \times EC)$

$MD^2<2.5 (S_{MGDF}=BH \times EC)$

$\frac{1}{MA^2}+\frac{1}{MB^2}+\frac{1}{MC^2}+\frac{1}{MD^2}>\frac{EC\times BH+AH\times AH\times EC+AE\times BH+AE\times AH}{2.5(AE\times AH\times EC\times BH)}=\frac{AF(AH+BH)+EC(AH+BH)}{2.5\times S_{AHME}\times S_{MGDF}}=\frac{4}{2.5 S_{AHME}\times S_{MGDF}}=\frac{1.6}{S_{AHME}\times S_{MGDF}}$

The denominator $S_{AHME}\times S_{MGDF}$ is fractional, that is  it's value is less than unity; therefore the sum of fractions can be greater than 2. If M is at center of square, then all fractions are equal to $1$ and inequality changes to equality.


Discrete Mathematics - "Prove that if p and q are primes and p∣q , then p=q" I'm not sure how i would go about proving this. Help would be much appreciated. This was a question on a revision task sheet for my Computing course. I understand that since p and p' are both prime, and as such can't be one, they must equal eachother since p divides p'. I am, however, stuck on the proof and what method i would use to prove this.

Suppose $p$ and $q$ are primes. And suppose that $p\vert q$.
That means that $q=k*p$ for some integer $k$.
But! Since $q$ is prime, it cannot be a product of two other integers. Except, if $k=1$. So $q=1*p$. $q=p$

Since $q$ divides $p$ , $q$ must be a prime factor of $p$.  But Wait ! $p$ is itself a prime and it's only prime factors are $1,p$ , it should be one of those. Since $1$ is not a prime number , $\boxed{q=p}.$


$f(x)=\sin x$, $f$ polynomial $f$ is a polynomial and suppose that $f(x)=\sin x$ has infinitely many solutions. Prove that $f$ is a constant between -1 and 1.

I get the problem intuitively, but how would I prove this formally?

Can anyone give me any hints?

Not a High-School Level Solution:  First, we show that $f(x)=\sin(x)$ must have a solution for arbitrarily large $x$.  If not, then $f(x)=\sin(x)$ has infinitely many solutions on a compact subset of $\mathbb{R}$ (or $\mathbb{C}$).  By the Identity Theorem for Analytic Functions, as polynomials are analytic, we conclude that $f=\sin$, but this contradicts the assumption that $f$ is a polynomial (because $f$ would have infinitely many roots, making it the zero polynomial).  Hence, $f(x)=\sin(x)$ must have solutions with $|x|\to\infty$.  Then, use @newnewnewnewnenwwojpwjfpoergje's now deleted hint (I don't know why he deleted it, as it was a good hint).  If $f$ is nonconstant, then $\big|f(x)\big|\to\infty$ for $|x|\to\infty$, whence $f(x)=\sin(x)$ can't have arbitrarily large solutions $x$.

Assume that the polynomial is not constant.
we know that
$\displaystyle{\lim_{x \rightarrow \pm \infty}}$f(x)=$\pm$ $\infty$ (f(x) is not constant,also it has a leading term)
as f(x)  is a polynomial
for the equation f(x)=sinx to have infinitely many solutions f(x) must
lie below $\pm$ 1 when x $\rightarrow$$\pm$$\infty$.
But this is a contradiction.
Therefore f(x) is a constant function lying between $\pm$1.


Use Pumping Lemma to show that $L_7$ is not context-free I was studying an old test and struggled to answer this question:

Let $L_7$ be the language $\{ w@y \mid y \text{ is a substring of } w\}$, where $w, y \in \{c,d\}^*$. Use the Pumping Lemma for context-free languages to show that $L_7$ is not context-free.

Suppose $L7$ satisfies the Pumping Lemma and let $p$ satisfy the conditions of the Pumping Lemma as stated on Wikipedia. Let
$$s = c^pd^p @ c^pd^p \in L7$$
Note that $|s| > p$. Let $u, v, w, x, y \in \{c, d, @\}^*$ satisfy the conditions of the theorem (again, as stated on Wikipedia). First, let's consider the $@$. It obviously cannot lie in $v$ or $x$, as precisely one $@$ is allowed. It cannot lie in $u$, since considering $n > 1$ will make $uv^nwx^ny$ into the form $a@b$ where $|a| < |b|$. For the same reason, this time considering $n = 0$, we cannot have $@$ be in $y$. So, the $@$ must lie in $w$.

Since $|vwx| \le p$, it follows that $v = d^m$ and $x = c^l$ for some natural numbers $m$ and $l$. Then, it follows that
$$uv^2wx^2y = c^pd^{p+m}@c^{p+l}d^p \notin L7,$$
which is a contradiction.

I suggest to first intersect $L_7$ with the regular language
$$ddd\cdot\{cc,cd,dc\}^+ddd@ddd\cdot\{cc,cd,dc\}^+ddd.$$
This takes away all strings where the substring is not the entire string (and some more). The result is
$$\{ddd\cdot w\cdot ddd@ddd\cdot w\cdot ddd: w\in \{cc,cd,dc\}^+\}$$
which is very close to the copy language over three letters. Therefore you can apply the pumping lemma in the same way.

I have read "substring" as "factor," but this should even work if "substring" means "scattered substring."


Proving two basic results about linear maps without requiring rank-nullity Let $U,V$ be finite dimensional vector spaces. I've proven the following statements as easy consequences of the rank-nullity theorem. But now I'm curious as to how to prove them directly without requiring this theorem. I haven't had any success, however, and would appreciate seeing how it is done.

There exists a surjective $T \in \mathcal{L}(U,V)$ if and only if $\dim U \geq \dim V$.
There exists an injective $T \in \mathcal{L}(U,V)$ if and only if $\dim V \geq \dim U$.

Note: the scalars are from $\mathbb{R}$ or $\mathbb{C}$. (I realize now that any field will work, so disregard this stipulation if it's easier.)

Try to use the following facts about injective and surjective linear maps.

  Let $T\colon U \to V$ be a linear function and $b_1,\dots,b_n$ is a basis of the vector space $U$.

  $T$ is injective if and only if the vectors $T(b_1),\dots,T(b_n)\in V$ are linearly independent.
  $T$ is surjective if and only if the vectors $T(b_1),\dots,T(b_n)$ generate $V$, i.e., $[T(b_1),\dots,T(b_n)]=V$.

See also Prove that the linear transformation is injective iff $T(f_1),\ldots,T(f_n)$ are linearly independent for a proof of the first one.

1. There exists a surjective $T \in \mathcal{L}(U,V)$ if and only if $\dim U \geq \dim V$.

Let $u_1, u_2, \cdots, u_m$ be a basis of $U$ and $v_1, v_2, \cdots, v_n$ a basis of $V$.

For the "if" part:

Define $T$ as follows:

$$T(a_i) = \begin{cases}b_i & 1 \le i \le n \\ 0 & n < i \le m \end{cases}$$

The proof of its surjectivity is left as an exercise to the reader.

For the "only if" part:

(work in progress)

2. There exists an injective $T \in \mathcal{L}(U,V)$ if and only if $\dim V \geq \dim U$.

The proof is left as an exercise to the reader.