What would the 3D graph of GCD(x, y) and LCM(x, y) look like? To find the answer out, I was going to use a graphing calculator but I couldn't find any one that supports the two operations. I would try to draw by hand but since it'll a 3D graph, I would have to use domain coloring and that would be a lot of work and hard to interpret. So, I ask: What does the graph look like for each function, and does it have an extension like factorials where it extends to real and rational numbers too having it as a codomain (such as if $1.5!$ has a real result, does $\gcd(1.5, 1.2)$ have one too)?

The gcd(x,y) is only really defined for x & y in the natural numbers (or for intigers if you allow negatives and 0 but nothing really changes to allow those).

The first fact to consider if you were looking to extend how you allow the gcd to work would be to make the requirement for
gcd(x,y)lcm(x,y)=xy

If we let x=a/b and y=c/d where a, b, c & d are all intigers (thus the fraction of x & y) then we could define
gcd(a/b,c/d) = gcd(alcm(b,d)/b, clcm(b,d)/d)/lcm(b,d)
Through this idea we can do
gcd(1.5,1.2)=gcd(3/2,6/5)=gcd(3*lcm(2,5)/2,6*lcm(2,5)/5)/lcm(2,5)=gcd(3*10/2,6*10/5)/10=gcd(15,12)/10=3/10

The idea of gcd(1.5,1.2)=0.3 does look like it would make nice intuitive sense.

Edit: By looking at lcm(b,d) =bd/gcd(b,d) the odd formula seems to nicely fall down to just...
gcd(a/b, c/d) = gcd(ad, cb)/(bd)


How to find the sup, inf, max and min for the set $H=\{ x \in \Bbb R : x+\frac3x-1 \le 0\}$ Let $H=\{ x \in \Bbb R : x+\frac3x-1 \le 0\}$.  Find $\sup(H)$, $\max(H)$, $\inf(H)$, and $\min(H)$. I understand the terminology but I am new to this please just offer any first steps or any help on how to get started.

As the expression on the left is continuous, the values of $x$ for which it is true will form one or more intervals.  The transitions will either be where $x+\frac 3x-1=0$ or where it is undefined, so solve the equation, add $0$ to the set of roots because the expression is undefined there, and assess the truth of the inequality on each resulting interval.  Can you then find the $\inf, \sup, \max, \min$ once you have the interval(s)?

Notice that we have
$$x+\frac3x \ge 2\sqrt3$$
for $x>0$. There are various ways to show this, you can have a look at several posts with proofs of
similar inequality $x + \frac{1}{x} \geq 2 $.

Let us denote $f(x)=x+\frac3x-1$. For $x>0$ you have
$$f(x) = x+\frac3x-1 \ge 2\sqrt3-1 >0.$$
And for $x<0$ you have
$$f(x) = -\left(|x|+\frac3{|x|}\right) -1 \le -2\sqrt3 - 1 <0.$$

So you can see that $f(x)>0$ for positive values and $f(x)<0$ for negative values. (You can also try to sketch the graph to see this.)

Which basically means that
$$H=\{x\in\mathbb R; f(x)\le 0 \} = \{x\in\mathbb R; x<0\}.$$
Now that you have much simpler description of $H$, it should be easier to find supermum, infimum, maximum, minimum of $H$ (if they exist).


What is the shape of the graph $|z-1|+|z+i|=2$ in the complex plane? What is the shape of the graph $|z-1|+|z+i|=2$ in the complex plane?
$(A)\text{two points}\hspace{1cm}(B)\text{a line}\hspace{1cm}(C)\text{a parabola}\hspace{1cm}(D)\text{an ellipse}$
Let us take $z=x+iy$
$|(x-1)+iy|+|x+i(y+1)|=2$
$\sqrt{(x-1)^2+y^2}+\sqrt{x^2+(y+1)^2}=2$
Upon simplifying,$3x^2+3y^2-4x+4y-2xy=0$
But with this equation, i cannot tell the shape of the graph.Please help me.

Hint: $|a-b|$ represents the distance between the two points a and b in the complex plane. What geometric shape is defined by the sum of two distances being constant ? :-$)$

$|z+i|+|z-i|=2 \iff \max\{|(z+i)-(z-1)|;|(z+i)+(z-i)|\}=2$,
$\max\{|2z|;|2i|\}=2$,
because for sure $|2i|=2$, so $|2z|\leq2$,
$|z|\leq 1$  and there is just a circle.

When i'm using $\max\{\cdots\}$ i mean the highest number contained in $\{\cdots\}$

I used here theorem that: $|a|+|b|=c \iff  c=\max\{|a+b|;|a-b|\}$.

Proof: Considering $a<0,b<0; a>0,b>0$ we get$-a-b=c$ or $a+b=c$, but $c=|a|+|b| \geq 0$, so we can easy generalize it to $|a+b|=c$, when $a<0,b>0; a>0;b<0$, similar generalize $|a-b|=c$, but when $c=|a+b|, |a-b|$ is obviously smaller, and if $c=|a-b|, |a+b|$ is obviously smaller, so generalizing all combinations we get $c=\max\{|a+b|;|a-b|\}$.


How would I go about determining if these subsets are subspaces of a vector space? What would be the correct method/approach to evaluate if these two subsets are indeed subspaces of a vector space?

a) $S{1}=\{x\in\mathbb{R}^{29}| x_1+2x_2+3x_3+...+29x_{29}=0\} $

b) $S{2}=\{p\in P_{29}| p(0)=p´(0)=0\}$

For the first expression, I'm thinking about vector x as being linearly independent and solved by the trivial solution x = 0. Then it should have the same or lower dimension than $S_1$ in $\mathbb{R}^{29}$, thus being a subspace. Am I correct?

For the second expression(/equation?) I have no idea how to interpret how e.g.
$p(0)$ or the derivative $p´(0)$ is related to "$P_{29}$".

I don't understand your argument for the first question (i.e. linguistic comprehension). You should check the following:

$$\forall x_1, x_2 \in S_1, \forall a, b \in \mathbb{R}: a x_1 + b x_2 \in S_1$$

i.e. every linear combination of elements of $S_1$ again belongs to $S_1$. While it is true that $0$ needs to be an element of $S_1$ in order for it to be a subspace, this is by no means sufficient, and by checking the condition I gave, this will automatically be fulfilled.

For the second, do you know what $P_{29}$ is? And if so, do you see why it is a vector space?

For (a), try to find wich linear fonction S1 is the Kernel. ( I assume you know that if F is a linear fonction, then Ker(f) is a subspaces of a vector space.)

What is $P_{29}$?


What is category theory useful for? Okay, so I understand what calculus, linear algebra, combinatorics and even topology try to answer (update: this is not the case in hindsight), but why invent category theory?
In Wikipedia it says it is to formalize. As far as I can tell, it sort of generalizes a bunch of fields in mathematics, like in topology, graphs and groups we have isomorphisms and automorphisms and homomorphisms, it seems to me like it just finds a bunch of results that are true to these functions in a bunch of disciplines. But why would generalizing that be of use? I mean, wouldn't it be easier to prove them specifically in each of the important disciplines?

Category theory serves several purposes. On the most superficial level it provides a common language to almost all of mathematics and in that respect its importance as a language can be likened to the importance of basic set theory as a language to speak about mathematics. In more detail, category theory identifies many similar aspects in very different areas of mathematics and thus provides a common unifying language. The fact that almost any structure either is a category, or the  collection of all such structures with their obvious structure preserving mappings forms a category, means that we can't expect too many general theorems in category theory to be really interesting (since anything you can prove about a general category will have to be true of almost everything in maths). However, some general truths can be found to be quite useful and labour saving. For instance, proving that the tensor product of modules is associative up to an isomorphism can be quite daunting if done by working with the construction of the tensor product. But, if instead one observes first that the tensor product satisfies a certain categorical universal property then the associativity up to isomorphism becomes immediate since in any category any universal construction is unique up to an isomorphism.

Continuing the analogy between set theory and category theory as common languages for maths, the situation is like saying "a set is just a bunch of points. No structure. Nothing. How interesting and relevant can it possibly be to study set theory?". As it turns out it is both interesting and very important to the rest of mathematics. It is very helpful to know the basics of cardinals and ordinals, Zorn's Lemma, and similar techniques to actually prove things in other areas. The exact same phenomenon is true in category theory. True, a category is just a bunch of points and arrows and a composition rule, but it turns out that it is helpful to know the basics of functors, duality, adjunctions, (co)limits and so on when actually proving things.

Less superficially, category theory encourages a shift in attention to what structure is. In category theory the particular inner workings of an object do not matter at all. All that matters is how that object is related (via the morphisms) to the other objects in the category. This is a familiar situation in very classical mathematics. For instance, one can construct the real numbers in many ways (Dedekind cuts, Cauchy completion etc.). These are different objects, but they are essentially the same. Just what this essential sameness means is answered very clearly by category theory: these are different solutions to the same universal problem.

Still along the same theme, category theory allows to make precise the meaning of a certain construction being natural. A classical example is that for a finite dimensional vector space $V$, the double dual is naturally isomorphic to $V$. Of course, $V^{**}$ and $V$ are isomorphic simply because they have the same dimension, but that is not the content of the statement. Usually, something is mumbled about the lack of arbitrary choices, but that is not really satisfactory. Eilenberg and Mac Lane defined categories in order to define functors, and defined functors in order to define natural transformations. The naturality of natural transformations gives a precise definition for natural constructions of all sorts, making it very clear what the naturality means, and how to prove naturality.

More deeply, some questions will never have been asked if it were not for category theory. For instance, given a ring $R$ one can construct the category $R\text{-Mod}$ of $R$-modules. One can ask for two rings $R,S$ when is $R\text{-Mod}$ an equivalent category to $S\text{-Mod}$. The answer is that this holds precisely when $R$ and $S$ are Morita equivalent, a condition that is purely ring theoretic and makes no use of category theory language. But, one could not have asked the question without constructing the categories first.

Category theory is extremely useful for talking about invariants of structure. The classical example is the fundamental group of a topological space. The classical Seifert-van Kampen theorem for computing the fundamental group was rather tricky to prove. However, if simply restated using category theory a very clear path suggests itself and leads to a very simple proof. Modern homotopy theory was radically transformed by category theory, particularly the famous result of Quillen. Quillen described a certain kind of equivalence between two categories: the category of topological spaces and the category of simplicial sets. The importance of this equivalence to modern homotopy theory is immense and leads further the study of $\infty$-categories.

Other areas where categories have had a profound effect are algebraic geometry (the work of Grothendieck) and logic (in the form of topos theory). Since my answer is already getting quite lengthy, I won't elaborate on these topics.

Category theory is not something instead of other mathematical theories but an other and very interacting perspective. The search for theorems and their proofs will never end as long as there are still mathematicians left. Even the familiar system of natural numbers will always hide secrets and any theory that helps to prove or counter prove just one single conjecture is worth to be further developed.

The category language might or might not be fruitful for a certain study, but it is always a perspective worth considering. In number theory there are less and more complex functions. The less complex functions are the first to be studied but more complex functions, as the increasing prime number function $p: \mathbb Z_+\rightarrow\mathbb Z_+$, seems resist any attempt of finally survey.

There is a category with all functions $f: \mathbb Z_+\rightarrow\mathbb Z_+$ as objects and pair of commuting functions $\alpha,\beta: \mathbb Z_+\rightarrow\mathbb Z_+$,
$(\beta f=g\alpha)$, are the morphisms $\displaystyle f\overset{(\alpha,\beta)}{\longrightarrow}g$.

Investigating such a category (I don't know if it is done) could bring a new approach to some issues. After all, it is not only the prime number function that is unresolved. When using categories there is also a possibility to find functors to other categories, such that hard problems in the primary category is transformed to a less hard problem in the secondary category.


Show that if $S$ is an orthogonal set of nonzero vectors in $\mathbb{R}^n$ then $S$ is a linearly independent subset of $\mathbb{R}^n$. Use the dot product to show that if $S = \{\vec{v_1}, \vec{v_2}, ...,
> \vec{v_n}\}$ is an orthogonal set of nonzero vectors in $\mathbb{R}^n$
  then $S$ is a linearly independent subset of $\mathbb{R}^n$.

I believe that since the vectors are orthogonal to one another, this implies they are linearly independent from one another, and since they are nonzero, this further affirms that the set is not dependent, and since the vectors are a linearly independent set of $n$ vectors, this implies $\text{dim(span}{(S)}) = n$, which should show that $S$ is linearly independent, and a subset of $\mathbb{R}^n$.

However (and this is the problem I have most often in my linear algebra course) I am uncertain of how to put all of this together in a coherent and logically sound proof.

Let $(\lambda_k)_{k\in\{1,\ldots,n\}}\in k^n$ such that: $$\sum_{k=1}^n\lambda_kv_k=0.$$
Let $i\in\{1,\ldots,n\}$, since $\langle\cdot,v_i\rangle$ is linear, one has :$$(1)\;\left\langle\sum_{k=1}^n\lambda_kv_k,v_i\right\rangle=0.$$
Besides, once more using linearity of $\langle\cdot,v_i\rangle$, one has: $$(2)\;\left\langle\sum_{k=1}^n\lambda_kv_k,v_i\right\rangle=\sum_{k=1}^n\lambda_k\langle v_k,v_i\rangle.$$
Since $\{v_1,\ldots,v_n\}$ is a set of orthogonal vectors, one has: $$\forall k\in\{1,\ldots,n\},\langle v_k,v_i\rangle=\delta_{i,k}.$$
Therefore, with $(2)$ it follows: $$\left\langle\sum_{k=1}^n\lambda_kv_k,v_i\right\rangle=\lambda_ie_i.$$
Now, using $(1)$ one has $\lambda_ie_i=0$ and since $e_i\neq 0$, $\lambda_i=0$. Hence, one has: $$\forall i\in\{1,\ldots,n\},\lambda_i=0.$$
Finally, $\{v_1,\ldots,v_n\}$ is linearly independent.


Prove $\sum\left| f\left(\frac 1 n\right)\right|^r$ converges for all $r>1$. I just got out of an introductory real analysis exam. I had this question which I tried to solve for more than $1.5$ hours and yet I accomplished nothing.

  Let $f:\Bbb R \to\Bbb R$ be a differentiable function with $f(0)=f'(0)=0$.

  Prove that
  $$
\sum_{n=1}^\infty \left|f\left(\frac 1 n \right)\right|^r
$$
  Converges for all $r>1$.

I tried to use the ratio test, root test, Lagrange's theorem, and a few more things I know but I couldn't crack this.

Could someone explain how to solve this? (We only studied basic things about series)

Since $f$ is differentiable at $0$, the expression
$$
{f(\frac1n)-f(0)\over\frac1n}
$$
tends to $f'(0)=0$ as $n\to\infty$. But $f(0)=0$, so this means
$
nf(\frac1n)
$
tends to zero. In particular for all large $n$ we have
$$
\textstyle\left|nf(\frac1n)\right|\le1.
$$
Rearranging, this implies
$$
\left|f({\textstyle\frac1n})\right|^r\le\frac1{n^r}
$$
for all large $n$, which is enough to show $\sum|f(\frac1n)|^r$ converges.

By the MVT, $f(\frac{1}{n})=\frac{1}{n}\frac{f(\frac{1}{n})-f(0)}{\frac{1}{n}}=\frac{1}{n}f^\prime(x_n)$ with $0<x_n<\frac{1}{n}$. Therefore $x_n\to 0$. Then $|f(\frac{1}{n})|=\frac{1}{n}|f^\prime(x_n)|$.  Thus $f^\prime(x_n)\to f^\prime(0)=0$ since $nf(\frac{1}{n})=f^\prime(x_n)$ and $f$ is continuous. It implies that $\{f^\prime(x_n)\}$ is bounded. Say $|f^\prime(x_n)|\le M$.

Therefore $\sum_{n=1}^\infty|f(\frac{1}{n})|^r\le \sum_{n=1}^\infty|\frac{1}{n}f^\prime(x_n)|^r\le\sum_{n=1}^\infty\frac{1}{n^r}M^r=M^r\sum_{n=1}^\infty\frac{1}{n^r}<\infty$


Polynomials that suffice $S = V(f,g)$ for $S$ finite set in $\mathbb{A}^2(\mathbb{C})$ Let $ S \subset \mathbb{A}^2(\mathbb{C})$  a finite set of points. Show that exists polynomials $f$ and $g$ such that S = V(f,g).

I know that if I am working in $\mathbb{A}^2(\mathbb{R})$ I can make horizontal lines and little circles tangent to those lines and make the polynomials $f$ and $g$ the multiplication of such lines and circles, (given that the radius of these circles is less then the minimum of the vertical distance between all points).

My problem is if we consider $\mathbb{A}^2(\mathbb{C})$, because then I lose control of other intersection points. How can I solve this prroblem considering in $\mathbb{A}^2(\mathbb{C})$?

Suppose $S = \{ (a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n) \}$.  First, find a solution for the "generic" case in which all $a_i$ are distinct.  (Hint to get started: there exists a polynomial function $p$ such that $p(a_1) = b_1, \ldots, p(a_n) = b_n$.)

I will now give the idea of how to treat the general case.  The idea will be to find some perturbation of $\mathbb{A}^2(\mathbb{C})$ which maps our problem into a problem of the generic case which was solved in the previous paragraph.  As it turns out, instead of considering the whole class of automorphisms of $\mathbb{A}^2(\mathbb{C})$, it will suffice to consider a class of shear transformations $\phi_\lambda$, $(x, y) \mapsto (x + \lambda y, y)$.  So, what you will need to prove is:

There exists $\lambda \in \mathbb{C}$ such that $\phi_\lambda(S)$ has all $x$-coordinates distinct.
There exist $f,g$ such that $S = V(f,g)$ if and only if there exist $f', g'$ such that $\phi_\lambda(S) = V(f', g')$.


What is $\tan \alpha$, if $(a+2)\sin\alpha +(2a - 1)\cos\alpha =2a + 1$? I tried the following:
$$\begin{aligned}a\sin\alpha +2\sin\alpha + 2a\cos\alpha - \cos\alpha &= 2a+1\\
a(\sin\alpha +2\cos\alpha)+(2\sin\alpha-\cos\alpha)&=2a+1\end{aligned}$$
Therefore,
$$\sin\alpha +2 \cos\alpha=2$$
$$2\sin\alpha - \cos\alpha=1$$
From these two equations, we get
$$\sin\alpha=\frac{4}{5},\cos\alpha=\frac{3}{5}$$
Therefore,
$$\tan\alpha = \frac{\sin\alpha} {\cos\alpha} = \frac{4} {3}$$
Is this a correct method to solve the question? Since $a$ is a constant, it does not seem necessary to me that its coefficients on the two sides of the equation be equal. Should I find $\sin\alpha$ and $\cos\alpha$ using some other method? Are there specific cases where this method of equating the coefficients will break?

The OP finds one constant root that applies for all $a$.  But there is a second root for most specific values of $a$, which is a function of $a$.  The full answer is $\tan\alpha\in\{4/3,2a/(a^2-1)\}$.
Properly, the given equation should be combined with the identity $\sin^2\alpha+\cos^2\alpha=1$.  There are two ways to do this:
Method 1
Isolate one of the trigonometric function, square the resulting equations and substitute to get a quadratic equation for the remaining function.  Choosing to isolate the cosine we then have
$(2a-1)\cos\alpha=(2a+1)-(a+2)\sin\alpha$
$(2a-1)^2\cos^2\alpha=(2a+1)^2-2(2a+1)(a+2)\sin\alpha+(a+2)^2\sin^2\alpha$
$(4a^2-4a+1)-(4a^2-4a+1)\sin^2\alpha=(4a^2+4a+1)-(4a^2+10a+4)\sin\alpha+(a^2+4a+4)\sin^2\alpha$
$(5a^2+5)\sin^2\alpha-(4a^2+10a+4)\sin\alpha+8a=0$
The quadratic equation looks like a mouthful, but its discriminant is a squared quantity, to wit $(4a^2-10a+4)^2$, thus we get the two roots
$\sin\alpha=\dfrac{(4a^2+10a+4)\pm(4a^2-10a+4)}{2(5a^2+5)}\in\{4/5,2a/(a^2+1)\}$
For each root of $\sin\alpha$ the previous equation with $\cos\alpha$ isolated is used to assure the proper sign of that function:
$(2a-1)\cos\alpha=(2a+1)-(a+2)(4/5); \cos\alpha=3/5$
$(2a-1)\cos\alpha=(2a+1)-(a+2)(2a/(a^2+1)); \cos\alpha=(a^2-1)/(a^2+1)$
Correspondingly $\tan\alpha\in\{4/3,2a/(a^2-1)\}$.
Thus the answer given by the OP is correct for one root that applies for all $a$, but in most cases there will be a second root for any specific value of $a$ (the only exceptions being $a=2$ where there is one doubly degenerate root instead, and $a=\pm 1$ where the second root fails to give a defined value for $\tan\alpha$; also $a=-1/2$ gives the second root with $\tan\alpha=4/3$ but different values for the sine and cosine).  The existence of two roots ultimately comes from the fact that except for $\pm 1$, any value of the sine or cosine corresponds to two different arguments within any fundamental period.
Method 2
In this method, we use a trick by combining the original equation with one involving the orthogonal linear combination.  To get the orthogonal combination, switch the coefficients $a+2$ and $2a-1$ and then reverse the sign before the second term.
$(a+2)\sin\alpha+(2a-1)\cos\alpha=(2a+1)$
$(2a-1)\sin\alpha-(a+2)\cos\alpha=x$
Square both sides and add them together getting:
$(5a^2+5)(\sin^2\alpha+\cos^2\alpha)=5a^2+5=(2a+1)^2+x^2$
Thus $x=\pm\sqrt{5a^2+5-(2a+1)^2}=\pm(a-2)$.  We then have a linear system to solve for $\sin\alpha$ and $\cos\alpha$ for each root  of $x$.  For example, $x=+(a-2)$ gives
$(a+2)\sin\alpha+(2a-1)\cos\alpha=(2a+1)$
$(2a-1)\sin\alpha-(a+2)\cos\alpha=a-2$
whose solution is $\sin\alpha=4/5,\cos\alpha=3/5$.  Putting $-(a-2)$ for $x$ similarly gives a linear system with solution $\sin\alpha=2a/(a^2+1),\cos\alpha=(a^2-1)/(a^2+1)$.
The remainder of the solution, and the comments that follow, are identical to Method 1.

The problem is that $a$ is a constant, not a variable. Therefore equating by parts does not work here: if we separate $2a - 1$ into $2(a-1) + 1$, $2(a-2) + 3$ and so on, we end up with a different set of solutions each time. If you try substituting $\sin \alpha$ and $\cos \alpha$ back into the original question, the LHS does not equal $2a-1$, so clearly something must have gone wrong.
Instead, notice that as this is an identity, so it must hold for all $a$. Substituting $a = -2, \frac{1}{2}$ to cancel one of the terms, we get:
$$-5 \cos a = -5 \Rightarrow \cos a = 1$$
$$\frac{5}{2} \sin a = 0 \Rightarrow \sin a = 0$$


If there are $74$ heads and $196$ legs, how many horses and humans are there? I was going through some problems then I arrived at this question which I couldn't solve. Does anyone know the answer to this question?

  One day, a person went to a horse racing area. Instead of counting the number of humans and horses, he counted $74$ heads and $196$ legs. How many humans and horses were there?

A hypercentaur is a creature with two heads and six legs; an anticentaur is a creature with no head and two negative legs.

Since $74$ heads make for $37$ hypercentaurs, with $74\cdot 6/2=222$ legs, you have $(222-196)/2=13$ anticentaurs.

Since a hypercentaur is the same as a human on a horse, and an anticentaur is a human deprived of a horse, we have counted $37-13=24$ horses and $37+13=50$ humans.

Hint:

Let there be $x$ humans and $y$ horses.

Each human and horse have one head. Each human has two legs and each horse has four legs.

Then,
$$x+y=74$$
$$2x+4y=196$$

which can be solved.


Graph Isomorphism of Complete Graph. what  Is the complexity(computational complexity) of  graph isomorphism of

1.Complete graphs($K_n$) and

2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)?

is it in  polynomial ?

Looks like trivial case, looking for  results. Thanks.

Edition :

"polarized graphs" isomorphism is a GI-complete problem (made of a complete graph $K_m$ and an empty graph $K_n$ plus some edges connecting the two; their isomorphism must preserve the partition)[Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), "Graph isomorphism problem", Journal of Mathematical Sciences 29 (4): 1426–1481 ].

For $m,n\in\mathbb{N}$, $\text{Aut}\left(K_n\right)\cong S_n$ and, if $m \neq n$, $\text{Aut}\left(K_{m,n}\right) \cong S_m\times S_n$, whereas $\text{Aut}\left(K_{n,n}\right)\cong C_2\times S_n^2$, where $C_k$ and $S_k$ are the cyclic group of order $k$ and the symmetric group on $k$ elements, respectively.  If your complexity is the size of the automorphism group, then the complexity is definitely not in polynomial.  If your complexity is the size of a minimal generating set of the automorphism group, then the complexity is constant.

Complete graphs, for isomorphism have constant complexity (time). In any way you can switch any 2 vertices, and you will get another isomorph graph. If you switch vertex A with B, conditions will be same for both, because both are connected with every other vertex. Daniel


How to prove syntactic consequence? I have a problem like this:
$$ F = \{A\sim B, B \sim C, ¬C∨B\} $$
And I want to check if this is true: $\{A∨C\}\vdash F$.

I will assume for the purposes of this answer that $A \sim B$ means $\text{$A$ if and only if $B$}$.
I'm also going to assume that you want to show that the following is true when interpreted as a sequent.
$$ A \lor C \vdash A \leftrightarrow B, B \leftrightarrow C, \lnot C \lor B $$
Let's rewrite this slightly
$$ A \lor C, C \vdash A \leftrightarrow B, B \leftrightarrow C, B $$
This statement is not a tautology because if $A$ and $C$ are true, but $B$ is false, then all the premises are true, but the conclusion is false (in fact, all the disjuncts are false).


Limit $\lim_{n→∞} [log(2+3^n)]/2n$ Find $\lim_{n→∞} [log(2+3^n)]/2n$

I have my work till the very last step then i dont know how to continue

$\lim_{n→∞} [log(2+3^n)]/2n$

=$\lim_{n→∞} log(3^n)+\lim_{n→∞} log[(2+3^n)/3n]$

=$\lim_{n→∞} log(3^n)+\lim_{n→∞} log[(2/3^n)+1/1]$

="I dont know what it is"$+1$

Since $\lim_{n→∞} log(3^n)$ is infinity???

What should I do?? Thanks!!

I don't see how your first step is valid.

But note
$$
{\log(3^n)\over 2n}\le {\log(2+3^n)\over 2n}\le  {\log( 3^{n+1})\over 2n}.
$$

Now use the Squeeze theorem (the power rule for logarithms will prove useful when computing the required limits of the left and right hand sides of the above inequality).

I think I see now what you were attempting:
$$
{\log(2+3^n)\over2n}
={\log\bigl(3^n( {2\over3^n}+1)\bigr)\over2n} ={\log 3^n+\log  ( {2\over3^n}+1)
\bigr)\over2n}
=\color{maroon}{{\log 3^n\over 2^n}}+\color{darkgreen}{{\log  ( {2\over3^n}+1)\over 2n}}.
$$
This will prove useful:

$\displaystyle \qquad\lim\limits_{n\rightarrow\infty}\color{darkgreen}{\log  ( {2\over3^n}+1)\over 2n}=0\ \ $ and  $\displaystyle\ \ \lim\limits_{n\rightarrow\infty}\color{maroon}{\log 3^n\over 2^n}={\log 3\over 2}$;$\ \ $ so
  $\displaystyle\ \ \lim\limits_{n\rightarrow\infty}{\log(2+3^n)\over2n} ={\log 3\over 2}$.

Much cleaner than my solution!


Intuitive Reason that Quantifier Order Matters Is there some understandable rationale why $\forall x\, \exists y\, P(x,y) \not \equiv \exists y\, \forall x\, P(x,y)$?
I'm looking for a sentence I can explain to students, but I am failing every time I try to come up with one.
Example
Let $P(x,y)$ mean that $x$ is greater than $y$.

$\forall x\, \exists y\, P(x,y)$ means that for all $x$, there is a number $y$, such that $x$ is greater than $y$.
$\exists y\, \forall x\, P(x,y)$ means that there is some $y$, that every number $x$ is greater than.

These don't seem to mean different things to me. Is this perhaps an example where they do mean the same thing or am I just translating to English incorrectly?

Take $P(x, y)$ to mean $y$ is a parent of $x$.

Then $\forall x \exists y P(x, y)$ means everybody has a parent, while $\exists y \forall x P(x, y)$ means there is someone who is the parent of every son and daughter.

I stumbled on this page asking the same question, but I think I understand now why $\forall x\exists yP(x,y) \not\equiv \exists y\forall xP(x,y)$. It seems that the quantifiers for x and y are essentially nested in each other, such that the second quantifier is dependent on the first.

Let's use the parent example where $P(x,y)$ is a predicate function meaning that y is the parent of x, which can also be stated that x is the child of y. Then, $\forall x\exists yP(x,y)$ can be interpreted as "For all children, there exists a parent." Switching the order of the quantifiers gives $\exists y\forall xP(x,y)$, which can be interpreted as "For some parent, there exists all their children." It seems that the second interpretation has the domain of children limited to the children of the parent, whereas in the first it was all children.


Trouble with a group presentation I'm trying to prove that the elements of the group $\langle h_{0},h_{1} | h_{1}h_{0}h_{1}^{-1}=h_{0}^{2}\rangle$ can be expressed uniquely as $h_{0}^{n}h_{1}^{m}$ for some $n$, $m\in \mathbb{Z}$. In order to prove that, I only need to prove that $h_{1}h_{0}$, $h_{1}^{-1}h_{0}$, $h_{1}h_{0}^{-1}$ and $h_{1}^{-1}h_{0}^{-1}$ can be written in that way. I know that $h_{1}h_{0}=h_{0}^2h_{1}$ and $h_{1}h_{0}^{-1}=h_{0}^{-2}h_{1}$, but I'm not able to prove the other two cases. Can anyone help me, please?

The answer is that it's not possible.  Let's use $a$ and $b$ for our group generators, so our group is
$$
G = \langle a,b \mid bab^{-1} = a^2\rangle.
$$
Let
$$
A = \begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix},\qquad
B = \begin{bmatrix}2 & 0 \\ 0 & 1\end{bmatrix}.
$$
It is easy to check that $BAB^{-1}=A^2$, so there exists a homomorphism $\varphi\colon G\to \mathrm{GL}(2,\mathbb{R})$ satisfying $\varphi(a)=A$ and $\varphi(b)=B$.

Now, if $m$ and $n$ are integers, then
$$
\varphi(a^mb^n) = A^mB^n = \begin{bmatrix}1 & m \\ 0 & 1\end{bmatrix}\begin{bmatrix}2^n & 0 \\ 0 & 1\end{bmatrix} = \begin{bmatrix}2^n & m \\ 0 & 1\end{bmatrix}.
$$
However,
$$
\varphi(b^{-1}a) = B^{-1}A = \begin{bmatrix}1/2 & 0 \\ 0 & 1 \end{bmatrix}
\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}
= \begin{bmatrix}1/2 & 1/2 \\ 0 & 1\end{bmatrix}.
$$
Since $m=1/2$ is not an integer, it follows that $b^{-1}a$ cannot be written as $a^mb^n$ for any $m,n\in\mathbb{Z}$.

Using $a$ and $b$ instead of $h_0$ and $h_1$ for obvious reasons:

We have the group $\langle a,b \mid bab^{-1} = a^2 \rangle$.

So, $ba=a^2b$.

We show that:

$$\begin{array}{lcl}
1 &=& a^0b^0 \\
a^m b^n a &=& a^{m+2^n}b^n \\
a^m b^n b &=& a^mb^{n+1} \\
a^m b^n a^{-1} &=& a^{m-2^n}b^n \\
a^m b^n b^{-1} &=& a^mb^{n-1}
\end{array}$$

That means, the identity is expressible in $a^xb^y$ and for any expressible word, so is its right product with $a$, with $b$, with $a^{-1}$, and with $b^{-1}$.


If a matrix has an inverse, then the transpose also has an inverse I just have simple one question.

"If a matrix $A$ has an inverse, then the transpose $A^T$also has an inverse."

I think the statement is 'true'.

Because

$AA^{-1} = I \\
(AA^{-1})^{T} = I^T \\
(AA^{-1})^T = I \\
(A^{-1})^TA^T = I \\$

since $(A^{-1})^TA^T=\operatorname{Id}$, $A^T$ has an inverse (which is $(A^{-1})^T$).

Is it right?

Yes, it is right. The statement is true (not just 'true' as you wrote). At the end, instead of writing “since $A^{-1}$ exists, $(A^{-1})^T$also exists”, I would have written that, since $(A^{-1})^TA^T=\operatorname{Id}$, $A^T$ has an inverse (which is $(A^{-1})^T$).

Suppose $A \in M_n(R)$. If $R/J(R)$ is commutative and $A$ has an inverse, then so does its transpose. Otherwise the transpose of $A$ may not have an inverse. See Journal of Algebra 322 (2009) 1627–1636.


Prove the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$ using combinatorial proof Prove the identity $\sum_{k=0}^n \binom{n}{k}=2^n.$ using combinatorial proof.

Suppose you have $n$ distinct objects and you want to choose some (possibly none) of them.

One way to look at this is as follows. You can either select no object, or one object, or two objects, and so on, you can select all the $n$ objects. The number of ways of selecting $k$ objects is $\binom{n}{k}$, and as $k$ varies from $0$ to $n$, the total value is $$\sum_{k=0}^n\binom{n}{k}$$

Another way is to look at each object. For every object, you have two choices - either you choose it or you don't. Thus, for $n$ objects, you have $2^n$ choices, and by varying your choices, you can select any number of objects in any configuration.

As both the above refer to counting the number of ways of doing the same thing, they must be equal. So,
$$\sum_{k=0}^n\binom{n}{k}=2^n$$

Use the binomial theorem $(1+x)^n=\sum_{k=0}^n {n\choose k}x^k$, with $x=1$.


Can someone please explain to me how I did this summation formula wrong? I was trying to show that
$\sum \limits_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$ but instead I got this $[\frac{n(n+1)}{2}]^2$ which from my understanding I basically proved another summation formula which is $\sum \limits_{k=1}^n k^3$. Obviously I must have done something wrong. So I am going to show you how I got the summation formula wrong.

$s_n = 1^2 + 2^2 + ... + (n-1)^2 + n^2 $

In reverse order

$s_n = n^2 + (n-1)^2 + ... + 2^2 + 1^2 $

I decided to square root the partial sum which probably what led to the wrong answer. But I do not know, I am clumsy when I write on paper.

$\sqrt{s_n} = 1 + 2 + ... + (n-1) + n$

In reverse order

$\sqrt{s_n} = n + (n-1) + ... + 2 + 1$

Adding the two partial sums

$\sqrt{s_n} + \sqrt{s_n} = 2\sqrt{s_n}$

$2\sqrt{s_n} = (n+1) + (n+1) + ...$

$2\sqrt{s_n} = n(n+1)$

$\sqrt{s_n} = \frac{n(n+1)}{2}$

$(\sqrt{s_n})^2 = [\frac{n(n+1)}{2}]^2$

Now my question what did I do wrong. Can somebody show me the correct way. I am pretty sure this a fake proof, or a minor error. Thank you.

P.S. I am no latex expert and this not homework just for practice.

$\sqrt{a^2+b^2}\ne a+b$ in general unless at least one of $a,b$ is $0$

If $s_n=1^2+2^n+\cdots+(n-1)^2+n^2,$

how can you write $s_n=1+2+\cdots+(n-1)+n?$

(1)One way to proof is :

$ (r+1)^3-r^3=3r^2+3r+1$

Put $r=0,1,2,\cdots,n-1,n$ and add to get

$(n+1)^3=3S_n+3(1+2+3+\cdots+n)+n=3S_n+3\frac{n(n+1)}2+n$

So, $S_n=...$

(2)We can use induction too:

Let $S(m)= \frac{m(m+1)(2m+1)}6$

$S(1)=\frac{1\cdot\cdot3}6=1$ which is true.

So, $S(m+1)=S(m)+m+1$
$=\frac{m(m+1)(2m+1)}6+(m+1)^2=\frac{(m+1)\{(m+1)+1\}\{2(m+1)+1\}}6$

So the proposition holds true for $n=m+1$ if it is true for $n=m.$


Useful analogy to interpret the notion of evolutionary stable strategy (ESS) I am seeking a good analogy to understand the concept of evolutionary stable strategy (state)

Let $\pi$ denote the fitness of a population, $\pi_{ij}$ is the fitness of strategy $i$ against strategy $j$

Then, a strategy $i$ is an evolutionary stable strategy (ESS) (or state) satisfies:

  $i$ is an ESS iff $\forall j \neq i$, the following holds:

  $\pi_{ij} \geq \pi_{ji}$
  $\pi_{ij} = \pi_{ji}$, then $\pi_{ij} > \pi_{jj}$

It is well known that (1) corresponds to the definition of Nash equilibrium point. A strategy $i$ is Nash if it yields better payoff (fitness) than any other strategy $j$ (under assumption of unilateral deviation).

What about the second condition? In most textbook, it says

  "If $i$ is a Nash equilibrium but not a strict one, then $i$ can still
  be an ESS if it can invade mutant strategy $j$"

Hmm...invasion...mutants....unfortunately these terminologies are not very meaningful to me without the biological context for which evolutionary game theory is built upon.

  Can someone provide an useful analogy or realistic case study to
  motivate the second condition of ESS?

A strategy is an ESS if it is not profitable for a small fraction of the population to deviate from the societal norm. Think of folks developing software in a research lab. Folks can either use the .NET platform on Windows or the Python platform on Linux. If most folks adopt Linux, then it doesn't make sense for a minority to play Windows. The folks adopting Windows won't be contributing, and evolutionary forces will drive them to adopt Windows.

Intuitively, a societal norm is an ESS if a small fraction of the population can deviate (be it by mistake, experimentation, etc.) and find this deviation not to be profitable. So evolutionary forces drive them back to the ESS.

Note: The definition you provided (the standard textbook definition) works for infinite populations. In finite populations, we do not have this notion of replacement. So suppose we have $n$ agents, with $a$ of them programmed to play $A$ and $b$ programmed to play $B$. If we draw an $A$ player, there are $a-1$ remaining $a$ players. So the odds of drawing another $A$ player are lower. This is because agents are not replaced. This blog entry provides a generalized notion of an ESS which converges, and discusses the convergence to a Nash equilibrium.

Example: A group of people is allowed to buy liquor (with assumed utility for all) if at least one of them carries an ID. (Carrying an ID is an earlier, individual, uncoordinated choice that is assumed not to hurt or benefit your utility otherwise.) In the ESS everybody will carry their ID.

NB: Your statement that (1) defines a NE is not correct. (1) is not unilateral.


How to compute the following limit$ \lim\limits_{x\to \infty }[( 1+x^{p+1})^{\frac1{p+1}}-(1+x^p)^{\frac1p}],$ I am trying to find

$$  \lim\limits_{x\to \infty }[( 1+x^{p+1})^{\frac1{p+1}}-(1+x^p)^{\frac1p}],$$

where $p>0$. I have tried to factor out as

$$(1+x^{p+1})^{\frac1{p+1}}- \left( 1+x^{p}\right)^{\frac{1}{p}} =x\left(1+\frac{1}{x^{p+1}}\right)^{\frac{1}{p+1}}- x\left(1+\frac{1}{x^{p}}\right)^{\frac{1}{p}},$$
 but still was not able to make progress. Any other approach to this is welcome.

Let try to use a general method to solve this kind of limits by
looking at the first order Taylor expansion of your expression:

\begin{aligned}\left( 1+x^{p+1}\right)^{\frac{1}{p+1}}- \left( 1+x^{p}\right)^{\frac{1}{p}} &=
x\left(1+\frac{1}{x^{p+1}}\right)^{\frac{1}{p+1}}- x\left(1+\frac{1}{x^{p}}\right)^{\frac{1}{p}} \\
&= x\left[ \left(1+\frac{1}{x^{p+1}}\right)^{\frac{1}{p+1}}- \left(1+\frac{1}{x^{p}}\right)^{\frac{1}{p}}\right] \\
&= x\left[1+\frac{1}{x^{p+1}{p+1}}+o(x^{-p-1}) - 1 -\frac{1}{x^{p}{p}}+o(x^{-p})\right]\\
&= x\left[\frac{1}{x^{p+1}{p+1}} -\frac{1}{x^{p}{p}}+o(x^{-p})\right]\\
&=\frac{1}{x^{p}{p+1}} -\frac{1}{x^{p-1}{p}}+o(x^{-p+1})
\end{aligned}
So that the whole expression tends to 0 when $x\rightarrow \infty$.


Write a formula expressing $z=\langle \langle x,y\rangle, \langle u,v\rangle \rangle$ This is an exercise from Kunen's book.

Write  a formula expressing $z=\langle \langle x,y\rangle, \langle u,v\rangle \rangle$ using just $\in$ and $=$.

What I've tried: because $\langle x,y\rangle= \{\{x\},\{x,y\}\}$ and $\langle u,v\rangle= \{\{u\},\{u,v\}\}$, and hence $z=\{\{\langle x,y\rangle\},\{\langle x,y\rangle,\langle u,v\rangle\}\}= \{\{\{\{x\},\{x,y\}\}\} ,\{\{\{x\},\{x,y\}\},\{\{u\},\{u,v\}\}\}\}$.

  So the formula expressing is this: $z_1\in z$, then $z_1= \{\{x\},\{x,y\}\}$ or $z_1= \{\{u\},\{u,v\}\}$

Am I right? Thanks ahead:)

Write a formula:

$$\varphi(u,v,z)=
\forall  x\bigg(x\in z\leftrightarrow
\underbrace{\forall y(y\in x\leftrightarrow y=u\lor y=v)}_{\Large x=\{u,v\}}\lor\underbrace{\forall y(y\in x\leftrightarrow y=u)}_{\Large x=\{u\}}\bigg)$$

Note that $\varphi(u,v,z)$ holds if and only if $z=\langle u,v\rangle$.

Now define the following formula:

$$\psi(x,y,u,v,z)=\exists a\exists b(\varphi(x,y,a)\land\varphi(u,v,b)\land\varphi(a,b,z))$$

Namely, $z$ is the ordered pair $\langle a,b\rangle$, and $a,b$ are both the ordered pairs $\langle x,y\rangle,\langle u,v\rangle$ respectively.

Note that not only that you can "expand" $\psi$ by replacing the instances of $\varphi$ by its explicit formulation; you can replace equality by $\in$, and use the axiom of extensionality to prove it is the same thing.

Although I am not an expert in this field (merely a beginning student), maybe I can help you out.
We will have to find a formula only using $\in$ and $=$ to describe $z = \langle \langle x, y \rangle, \langle u, v \rangle \rangle$. This essentially means we want to say that: '$z$ is an ordered pair of two ordered pairs $a$ and $b$. The ordered pair $a$ consists of the elements $x$ and $y$, the ordered pair $b$ consists of the elements $a$ and $b$.'
--
To describe that $z$ is an ordered pair, you can use the formula:
$$(\exists a \in z)(\exists b \in z)(\exists d \in a)(\exists f \in b) \left[ (\forall c \in z)(c = a \vee c = b) \wedge (\forall c \in a)(c = d) \wedge (d \in b) \wedge (\forall c \in b)(c = d \vee c = f) \right]$$
Lets call this formula $o(z)$.
--
Given that $z$ is an ordered pair, we can describe that $g$ is the first coördinate of $z$ with:
$$(\forall a \in z)(g \in a)$$
Lets call this formula $p(z, g)$.
--
Given that $z$ is an ordered pair, we can describe that $i$ is the second coördinate of $z$ with:
$$(\exists a \in z)(i \in a) \wedge (\forall b \in z)(\forall c \in z)(b \neq c \Rightarrow (i \notin b \vee i \notin c))$$
Call this formula $q(z, i)$.
--
By combining these formulas, we can describe $z = \langle \langle x,y \rangle, \langle u,v \rangle \rangle$ as follows:
$$o(z) \wedge (\exists a)(\exists b)(o(a) \wedge o(b) \wedge p(z, a) \wedge q(z, b) \wedge p(a, x) \wedge q(a, y) \wedge p(b, u) \wedge p(b, v))$$
--
EDIT (NOT APPLICABLE ANYMORE)

As I do not have enough reputation to post a comment on other answers yet (:-s), I will comment on Asaf Karagila's answer in this way. The formula $\phi(u,v,z)$ you use is not correct, because $\phi(u,v,z)$ does not hold if and only if $z = \langle u, v \rangle$. It is for example possible that $z = \{ \{ u \} , \{ v \} \}$, or $z = \{ \{ u \} \}$ with $u \neq v$.
You really need to use the definition of ordered pairs with first and second coördinate I use in my answer, elsewise you won't have an 'if and only if':
$$z = \langle u, v \rangle \mbox{ if and only if } o(z) \wedge p(z, u) \wedge q(z, v)$$


Question about the definition of a semialgebra This question has been asked here

Question about definition of Semi algebra

The OP unfortunately has selected an incorrect answer and no agreed upon correct answer has been given. The most upvoted answer finishes by saying he would be interested if someone could solve the conundrum. Therefore, I am reposting the question hoping to receive a definitively correct answer.

We say that $S$ is a semialgebra of subsets of $X$ if

$\emptyset \in S$
If $P_1,P_2 \in S$, then $P_1 \cap P_2 \in S$
If $P\in S$, then $X \backslash P$ can be written as a finite union of sets from $S$.

But I have found the following definition 3' is used sometimes instead of 3:

3'. If $P \in S$, then $X \backslash P$  can be written as a disjoint finite union of sets from $S$.

My question

Are the definitions 3 and 3' equivalent? If so can someone show me how we can obtain 3' from the first three conditions?

The Statement 3 is a combination of 3' and 2: Assuming 3' is true (then X\P can be written as a disjoint Union of sets of $S$) and moreover 2 is true. Since intersections also lie in $S$, one obtains statement 3.


Prove that there are infinitely many natural numbers that are not powers of any prime. I am wondering whether there is a way to prove that the set consisting of all natural numbers that are not powers of any prime is infinite. For example, 6 is such a natural number. Just to make this clear, what I mean is that any numbers that are powers of 2,3,5,7... (prime numbers) are not in the defined set. So 2,4,8 ; 3,9,27 are not in the set.

For a set to be infinite, I mean the following:

I am trying to this by proving that this set is equivalent to $ \Bbb N$ but it is really hard to find an explicit bijection. Another way to do this is that I can prove the set consisting of all natural numbers that are powers of a primes is countably infinite. But it seems that the complement of a countably infinite set in $ \Bbb N$ may not be countably infinite?

Can someone please give me a hand? Thanks.

$\newcommand{\Set}[1]{\left\{ #1 \right\}}$$\newcommand{\N}{\mathbb{N}}$Is there any reason why you would want an explicit bijection?

Because you can prove that your set
$$
X = \Set{ x \in \N : \text{$x$ is not a power of a prime}}
$$
is in a bijection with the natural numbers without making the bijection explicit.

First note that
$$
n \mapsto 2 \cdot (2 n + 3)
$$
is an injective map from $\N$ to your set $X$. (I have taken $2 n + 3$ so that it works whether one includes zero in $\N$ ot not.)

Then $x \mapsto x$ is an injective map $X \mapsto \N$.

This guarantees that there is a bijection $\N \to X$.

If i understand your question correctly, your set is defined as :

$S = n \in \mathbb N | n \ne p^q$ for any prime $p$ and positive integers $q$

It is sufficient to prove that a subset of $S$ is infinite.

Consider the subset $P = n!, n \in \mathbb N, n\ge 3$ clearly, it satisfies your condition that they are not the powers of a single prime.

Now suppose we have a set $T = [1,2,....,n]$ such that $P(T) = n$ for some natural n. ($P(T)$ denotes the cardinality of set $ T$). For there to exist a bijection $f: P \to T, P(T) = P(P)$. But clearly, $(n+4)! \in P$. Which means that the cardinality of $P$ is at least $(n+4) -3 =n+1$. Thus there cannot exist any bijection,for any natural $n$. Thus, $P$ is an infinite set. Since, $P \subset S$, $S$ is also infinite.

I just made the proof up right now. If there are anu fatal errors,please point it out. I will remove/edit the answer likewise.


continuous (on 3, 4 and 5) f is constant, if $f(x+2)+f(4x)=f(2x+1)+f(2x+2),\forall x\in\mathbb{R}$ Let $f:\mathbb{R}\to\mathbb{R}$ be a function that is continuous on 3,
  4 and 5, such that $f(x+2)+f(4x)=f(2x+1)+f(2x+2),\forall x\in\mathbb{R}$. Show that f is constant.

I don't know what to do here!! I think that we may be able to prove that f is continuous on $\mathbb{R}$, but then what? Also, I don't have any school knowledge of sequences, but only some calculus, including integrals, derivatives, IVT, MVT, EVT, Rolle, Fermat, Darboux, limits and such things.

Any hint of a proof that doesn't use Taylor or sequences?

The statement is false. Continuity at $2$ is necessary and sufficient for the function to be constant.  Continuity at all $x \neq 2$, which is more than what is assumed in the problem, is not sufficient for the function to be constant.

The functional equation is

$(T^2 + D^2) f = (TD + DT) f$,

or equivalently, $(T - D)^2 f = 0$, where

$D$ is the doubling operator $f(x) \to f(2x)$  and
$T$ the translation operator $f(x) \to f(x+1)$.

First we solve $(T-D)g = 0$.  This says $g(x+1) = g(2x)$ or $g(2+t)=g(2+2t)$.  The solution is any function $g$ invariant under the transformation $2+t \to 2+2t$. The only solutions continuous at $2$ are $g = $ constant.  There are nonconstant solutions continuous everywhere except at $2$, which shows that the conclusion of the problem is incorrect even for the stronger functional equation $f(x)=f(2x-2)$ that implies the 4-term equation in the problem.

Next, to solve the 4-term functional equation, we want $g = (T-D)f$ to be a solution of $(T-D)g = 0$.  The functions $f$ making that true are exactly the functions linear in $n$ along geometric progressions $(2 + 2^n a)$.  The linear function can be any $P(a) + nQ(a)$ where $P$ and $Q$ are arbitrary functions of $a \in [1,2)$.

Continuity at points other than $x=2$ is not enough to force the function to be constant, or to have $Q=0$, or to have $P$ or $Q$ be constant.

Denote $g(x) = f(2x) - f(2x-2)$. Then given condition implies that $g(x) = g(2x-3)$ and $g$ is continuous at $x_0=3$. Now suppose, there exists $y<3$ such that $g(y)\neq g(3)$. Set $a$ = $\limsup_{g(y)<g(3), y<3} y$. Because $g$ is continuous at $3$, such $a$ exists. However, $g(3-\epsilon) = g(3-2\epsilon)$ for $\epsilon>0$. Contradiction. So $g$ is constant.  Now only you need to show that $g(x) = 0$ for all $x\in\Bbb{R}$.


Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to right:
$$
{\exists_x(\phi(x) \rightarrow \psi) ~~~~~~~~{{[\phi[t/x]\rightarrow \psi]~~~~~~~ {{[\forall_x\phi(x)]}\over{\phi[t/x]}}} \over {\psi}}}\over{\psi \over {\forall_x\phi(x) \rightarrow \psi}}
$$

but I am not able to prove implicatin from right to left. I would appreciate any help.

Arguing informally in natural deduction style, assume as premiss

  $\forall x\phi(x) \to \psi$

Now remember that that is elementarily equivalent to

  $\neg\forall x\phi(x) \lor \psi$

So the obvious brute force proof strategy is to argue by cases. You need to show, first, that $\neg\forall x\phi(x)$ implies $\exists x(\phi(x) \to \psi)$. But we have

  $\neg\forall x\phi(x)\\ \exists x\neg\phi(x)\\ \quad|\quad \neg\phi(a)\\ \quad|\quad \phi(a) \to \psi \\ \quad|\quad \exists x(\phi(x) \to \psi) \\  \exists x(\phi(x) \to \psi) $

using existential quantifier elimination at the key step. And now you need to show that $\psi$ implies $\exists x(\phi(x) \to \psi)$. But that's easy, we just need to fill in the proof

  $\psi\\ \phi(a) \to \psi \\ \exists x(\phi(x) \to \psi) $

So put everything together and we are done, in this informal Fitch-style presentation.

It remains to massage the proof into your preferred tree layout: exercise!

Well, $\exists x \phi(x) \rightarrow \psi$ is not logically equivalent to $\forall x \phi(x) \rightarrow \psi$. If every $x$ has some property, certainly there exists an $x$ with that property. However, just because some $x$ has a property does not mean every $x$ has a property.

Unless your domain of discourse has only one element.

Edit: or if $\phi(x)$ is always false.


Proof of "every convex function is continuous" A real valued function $f$ defined in $(a,b)$ is said to be convex if
  $$f(\lambda x+(1-\lambda)y)\le \lambda f(x)+(1-\lambda)f(y)$$
  whenever $a < x < b,\; a < y < b,\; 0< \lambda <1$.
  Prove that every convex function is continuous.

Usually it uses the fact:
If $a < s < t < u < b$ then $$\frac{f(t)-f(s)}{t-s}\le \frac{f(u)-f(s)}{u-s}\le\frac{f(u)-f(t)}{u-t}.$$

I wonder whether any other version of this proof exists or not?

The pictorial version.  (But it is the same as your inequality version, actually.)

Suppose you want to prove continuity at $a$.  Choose points $b,c$ on either side.  (This fails at an endpoint, in fact the result itself fails at an endpoint.)

By convexity, the $c$ point is above the $a,b$ line, as shown:

Again, the $b$ point is above the $a,c$ line, as shown:

The graph lies inside the red region,

so obviously we have continuity at $a$.

The best alternative proof (in my humble opinion) is a function is convex if and only if its epigraph is a convex set.  If a function is NOT continuous then the epigraph can't be convex (obviously... draw a picture); but then by the above, the function can't be convex.  This proof used the contrapositive.


Why is the definition of an image of a subset use existential quantifier rather than universal? According to my textbook (Discrete Mathematics and Its Applications by Rosen), the definition of the image under function $f $ $(f:A\rightarrow B)$ of the subset $S$ $(S\subseteq A)$ is $$f(S) = \{t | \exists s \in S (t = f(s)) \}$$
What I'm confused about this is that I think it should be a universal quantification since we're talking about the set containing all the images of elements in set $S$, right?

Just because a definition in spoken English uses the word 'all' doesn't mean there should be a universal quantifier. Here's another example: suppose you have a bunch of sets $X_1, X_2, \dots$. The set of all elements appearing in these sets is
$$\bigcup_{n \in \mathbb{N}} X_n = \{ x \mid \exists n \in \mathbb{N},\, x \in X_n \}$$
which is defined using an existential quantifier, not a universal quantifer. This is because the set of 'all the elements' of these sets is precisely the set of elements which appear in 'at least one' of these sets.

In this case, $f(S)$ is the set of all the elements in the image of $S$ under $f$. That is, it's the set of elements which are of the form $f(s)$ 'for some' $s$... that's why we have an existential quantifier.

If we had a universal quantifier instead, the set would be
$$\forall_f(S) = \{ t \mid \forall s \in S,\, t = f(s) \}$$
That is, $t \in \forall_f(S)$ if every element of $S$ maps to $t$ under $f$. If $S \ne \varnothing$ then this set is either empty (if $f$ is non-constant on $S$) or has one element (if $f$ is constant on $S$)... so in general not very interesting.

I've never seen this notation ($s\in S(t = f(s))$), is it really exactly like this in your textbook? It simply means, that the image of $S$ under $f$ is the set of all points $t \in B$, such that there is a $s \in S$ with $f(s) = t$. You can also write is like this:
$$ f(S) = \{ f(s) \; | \; s \in S \} \subset B $$


Understanding the Leibniz formula for determinants I am a programmer and trying to write the Leibniz formula for determinants into C++ code, but I am unable to fully understand it.
Can someone walk me through it?

$$\det(A)=\sum_{\sigma \in S_n}\text{sgn}(\sigma)\prod_{i=1}^{n} a_{\sigma(i),i}$$

For one, but that might be irrelevant to you, this formula is not the way you want to actually compute determinants; there are much more efficient methods for that. But I will try to help you understand the formula.

We have an $n \times n$-matrix $A$. Its elements are $a_{i,j}$ as usual, or $a[i,j]$ in more C-like notation.
The outer sum sums over all permutations (this set is $S_n$), so that is an outer loop. A permutation is just a reordering of the indices, like $(1,3,2)$ for $n=3$; for $n=3$ there are $3!$ permutations of the indices: $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$, and for $n$ indices there are $n!$ in general. Here we can interpret this as a function: $(3,2,1)$ is the function that sends $1$ to $3$, $2$ to $2$ and $3$ to $1$, e.g. Now, each permutation has a sign $\operatorname{sgn}(\sigma)$, which is either +1 or -1. The identity has sign +1, while interchanging two elements of a permutation changes the sign to the opposite one. So $(1,3,2), (3,2,1), (2,1,3)$ are odd permutations on $n=3$, because we interchanged one pair. One can prove that half the permutations are even (have sign +1), and the other half has sign -1.

Now for each permutation $\sigma$ we take the multiplication of the elements of $A$ as specified by the permutation, interpreted as a map. So $(1,3,2)$ is the map $1 \rightarrow 1, 2 \rightarrow 3, 3 \rightarrow 2$, so we get the product $a_{1,1}a_{3,2}a_{2,3}$, where the second index is the original, the first its image under $\sigma$.

The formula says that $\det(A)$ is the sum of all such products where we consider all permutations of the index set, and the products from an odd permutation get a minus sign.

So for $n=3$ we get $$\det(A) = a_{1,1}a_{2,2}a_{3,3} - a_{1,1}a_{2,3}a_{3,2} - a_{1,3}a_{2,2}a_{3,1} - a_{1,2}a_{2,1}a_{3,3} + a_{1,2}a_{2,3}a_{3,1} + a_{1,3}a_{2,1}a_{3,2}$$ where the minus signs correspond to the odd permutations from above.

So you need algorithms to enumerate all permutations, and compute their signs, and then loop over all these products. It's quite complicated to get right, and not very efficient. But this formula allows one to prove some facts for determinants, so it has its uses.

The best method to calculate determinant would be to first perform LU decomposition followed by calculating the determinants of L and U, which are the products of their main diagonals.


Basic set operations: Simplify (A−Bc)∪(B∩(A∩B)c). Could someone please help with answering the questions below?

Question 1: Simplify $(A−B^c)∪(B∩(A∩B)^c).$

Question 2: Simplify $(A∪B)∪(C∩A)∪(A∩B)^c.$

Answer for $2$nd question. (I suggest you to draw this sets, it would be much easier.)

Since $C\cap A\subseteq A \subset A\cup B$ we have $$(A∪B)∪(C∩A)= A\cup B$$

Since $A\subset A\cup B$ and $A'\subseteq A'\cup B' = (A\cap B)'$
we have $$U = A\cup A' \subseteq (A\cup B)\cup (A\cap B)'$$ so the result is whole universal set $U$.

$1$st question.

Since $A−B^c = A\cap B$ and $B∩(A∩B)^c = B- A$ we get

$$(A−B^c)∪(B∩(A∩B)^c) = (A\cap B)\cup (B-A) = B$$

I will show you how to solve question one and proceed similarly to question 2 , note that A-Bˣ=A∩B then it equals to (A∩B)∪(B∩(A∩B)ˣ)=B∩(A∪(A∩B)ˣ) then using demorgan rules it equals to B∩(A∪(Aˣ∪Bˣ))=B cus B⊂A∪Aˣ


More detailed question about MAP hypothesis I have asked a similar question here before, I got one answer but I'm still not sure the user arrived at the answer. So I have actually changed the question I asked to help me figure out how to get the solution to this problem.
  And to be clear, I am not looking for the final answer, only to understand how to set up the problem with the given data.

This problem is looking to find the MAP hypothesis. I understand the simpler problems but this is given threw me off a bit.

You are given a coin that may or may not be biased. Specifically,
you have three hypotheses about the coin:

H1 = “the coin has probability 1/2 of landing heads”

H2 = “the coin has probability 1/3 of landing heads”

H3 = “the coin has probability 2/3 of landing heads”

The priors are:

$P(H_1)$ = $P(H_2)$ = $P(H_2)$ =  $\frac 13$

The event $D_1$ = " You toss the coin seven times and observe five

heads.

Which is the maximum a posteriori hypothesis?"

The answer given previously is $H_3$

The way I break it down is:

I have one event, thus, I am trying I believe I am to find:
$$P(D_1\mid H_1)P(H_1)$$
$$P(D_1\mid H_2)P(H_2)$$
$$P(D_1\mid H_3)P(H_3)$$

and compare all of them to see which is the postiori.

What is confusing to me is:$$P(D_1\mid H_i)$$Which value should I use for $H_i$?

And since they are independent, should I just multiply ($H_i$)($\frac57$)($\frac13$)?

You should review the lecture slides. Specifically the one on MAP

https://people.cs.umass.edu/~mcgregor/240S16/lec20.pdf

You should find it helpful.


Metric space gluing: the double-disk boundary metric This may not be well posed, but I hope you get the idea...

If two closed, flat disks of equal size are glued at their boundary, i.e. an equivalence is established between the two boundaries, I believe that the equivalence should be an isometry - i.e. distance preserving.

Now, the metric is defined for the interior and the boundary of each disk, and is flat, but the result of the gluing (a flattened sphere) is not flat and has infinite curvature at the points that were on the boundaries of the two disks, so the metric is no longer flat at those points.

Can someone explain how the metric "changes" in the process of gluing. Was it, contrary to my assumption, somehow undefined on the boundary previously.

I think I am mssing something fundamental here...

You are confused: Topological 'gluing' together of two spaces which happen to have metrics does not automatically create a combined metric on the combined space.  You have to explicitly define the new metric from the old by stipulating how to compute the distance between a point in the interior of one disk from a point in the interior of the other (or create a fresh metric from scratch).

Incidentally, 'curvature' is not a property of the intrinsic metric; it is a property of how the space is embedded in a larger space with a metric of its own (example: the surface of a cylinder, with respect to the obvious geodesic metric, is not considered to be curved [the Gaussian curvature is zero]).


Triangle inscribed inside a circle: prove that $abc = 4 \times area \times R$ The solution to Putnam 2000 A5 uses this formula, for which the following proof is given:
(source: https://mks.mff.cuni.cz/kalva/putnam/psoln/psol005.html)

Let the sides (of triangle $ABC$) have lengths $a, b, c$ as usual. The question suggests that we use some relationship of the form $abc = constant \times R$. ...

To prove the relation, let $O$ be the centre of the circumcircle. Project $AO$ to meet the circle again at $K$. Let $AH$ be the altitude. Then angle $ABC = \angle AKC$, so triangles $ABH$ and $AKC$ are similar. Hence $\frac{AB}{AH} = \frac{AK}{AC}$ or $\frac{c}{AH} = \frac{2R}b$. Hence $abc = 2R·a·AH = 4\Delta R$.

The bold part confuses me. How does $ABC = AKC$? $K$ is dependent wholly on $O$ and $A$ whereas $B$ is independent of both. And if $ABC = AKC$, how does that lead to $ABH \sim AKC$?

Angles intercepting the same arc are equal. Both angles are intercepting $\widehat{AC}$.

Area of the inscribed $ \triangle = \frac 12 a.b\sin C$

Try to draw the plane and we will get $\sin C = \frac{c}{2R}$


Show that a Norm Obtains a Minimum Consider a real normed vector space, and a collection of linearly independent vectors $x_i \in X$ for $i=1,2,3,4..., n$. For a fixed $y \in X$ show that:

$\inf_{\alpha_i \in \mathbb{R}, i=1,2,3...,n} ||{y-\sum_{i=1}^{n}\alpha_ix_i}||$ assumes a minimum.

So this is an engineering math course and were going over function fitting. First off, I know that infimum and minimum are not the same thing, but the way the problem is posed seems to imply that there is an absolute minimum and it is equal the infimum of the set. I think it may that I'm not understanding his notation.

Conceptually, as I see it, if $X$ were the space of continuous functions, and we wanted to fit a polynomial to that continuous function, we certainly would want to minimize the norm difference between our function, $y$, and the fit polynomial $\sum_{i=1}^{n}\alpha_ix_i$. In this case the $x_i$ could be a basis of $n$th order polynomials. Hence, if we find a minimum norm value and the vector $\sum_{i=1}^{n}\alpha_ix_i$ that generates it, then we've found a "best" fit approximation for $y$.

My first thought to go about showing a minimum exists was to say that we could simply go through every possible $\sum_{i=1}^{n}\alpha_ix_i$, evaluate the norm with $y$, and then find one particular selection of $x_i$ and $\alpha_i$ that generates the minimum. However, since the $\alpha_i$ can be any numbers, I can't "check" every possible fit function. So this won't work.

Another small note I made is that $0$ is always a bound I can make below by properties of norms, but I'm unsure of how to refine the minimum value from that point.

Here is a one answer:

If a matrix $X$ has linearly independent columns, then there is some $k>0$ such that $\|Xz \| \ge  k \|z\|$ for all $z$.

Let $f(\alpha) = \|X \alpha -y\|$, where $X$ is the matrix composed of the vectors $x_k$. Note that $f(\alpha) \ge 0$ and let $m = \inf_\alpha f(\alpha)$.
We have $f(\alpha) \ge \|X \alpha \| - \|y\| \ge k \|\alpha \| - \|y\|$.

In particular, if $\| \alpha \| > {1 \over k} (m+1+\|y\|)$ we have
$f(\alpha) > m+1$, and so the set $\{ \alpha | f(\alpha) \le m+1 \}$ is non empty and compact and hence $f$ has a minimiser $\alpha_0$
such that $f(\alpha_0) = m$.

Here is a more satisfactory answer, but it relies on the result
that says that a differentiable convex function $f$ is minimised at a point $\alpha^*$ iff ${\partial f( \alpha^*) \over \partial \alpha} = 0$.

Ley $\phi(\alpha) = {1 \over 2} \|X\alpha -y \|^2$ (the ${1 \over 2}$
is a conventional convenience, the square makes $\phi$ differentiable everywhere). It should be clear that minimising $\phi$ is the
same as minimising $f$.

We can write $\phi(\alpha) = {1 \over 2}\langle \alpha , X^T X \alpha \rangle - \langle X^T y, \alpha \rangle + {1 \over 2} \|y\|^2$ and
note that since $X^T X$ is positive semi definite (in fact definite,
in this case) that $\phi$ is convex. Furthermore,
${\partial \phi(\alpha) \over \partial \alpha} = \alpha^T X^T X -y^T X = (X^T(X\alpha-y))^T$.

Hence $\alpha^*$ minimises $\phi$ (and hence $f$) iff
$X^T(X\alpha^*-y) = 0$ (these are the normal equations).

In particular, there is always a solution to the normal equations
(for any matrix $X$, not just one with linearly independent columns), and if $X^T X$ is invertible (iff the columns are
linearly independent) then there is a unique minimiser given by
$\alpha^* = (X^TX)^{-1} X^T y$.

If the columns of $X$ are not linearly independent, a solution still exists but is not unique.

Let $\delta=\inf \left\{\left\lVert{y-\sum_{i=1}^{n}\alpha_ix_i}\right\rVert\,;\, (\forall i=1,\dots,n)\,\alpha_i\in\mathbb{R}\right\}$ and $S=\text{span}(x_1,\dots,x_n)$.
Notice that $\lVert x-y\rVert=d(x,y)$.
Then $\delta=\inf_{v\in S} d(y,v)=d(y,S).$

Proposition: Let $(M,d)$ be a metric space with the property that closed and bounded sets are compact (for instance, any finite dimensional, normed vector space). Let $K\subset M$ be compact and $C\subset M$ closed.
Then there are $x\in C$ and $y\in K$ with $d(C,K)=d(x,y)$.

Proof: Let $(x_n,y_n)\subset C\times K$ be a minimizing sequence for $d(C,K)$, say with $$d(x_n,y_n)<d(C,K)+\frac1n.\tag{*}$$
The existence of such a sequence is guaranteed by the infimum property -- it shows up in the definition of $d(C,K)=\inf_{x\in C,\,y\in K}d(x,y)$.
Because $K$ is compact, there is a subsequence $(x_{n_k},y_{n_k})$ such that $\lim_{k\to\infty}y_{n_k}=y\in K$.
In particular, this implies that $\big(d(y_{n_k},y)\big)_{k\in\mathbb{N}}$ is bounded, say by $M\geq 0$.
Then:
$$d(x_{n_k},y)<d(x_{n_k},y_{n_k})+d(y_{n_k},y)<d(C,K)+(M+1)$$
With $R=d(C,K)+(M+1)$, it follows that $\big(x_{n_k}\big)_{k\in\mathbb{N}}$ lies in $\stackrel{\sim}{K}=\overline{B(R, y)}\cap C$.
As the intersection of two closed sets, $\stackrel{\sim}{K}$ is closed.
Moreover, since $\overline{B(R, y)}$ is bounded, $\stackrel{\sim}{K}$ is also bounded.
It follows that $\stackrel{\sim}{K}$ is compact.
Thus, there must be a subsequence $\left(x_{n_{k_j}},y_{n_{k_j}}\right)$ with $\lim_{j\to\infty} x_{n_{k_j}}=x\in\, \stackrel{\sim}{K}\subset C$.
Since $d:M\times M \longrightarrow \mathbb{R}$ is continuous, we have that
$$\lim_{j\to\infty} d\left(x_{n_{k_j}},y_{n_{k_j}}\right)=d(x,y)$$
Moreover, by the defining property $(*)$ of $(x_n,y_n)$, we must have $d(x,y)\leq d(C,K)$.
Since $x\in C$ and $y\in K$, and $d(C,K)$ is the infimum over $x\in C$ and $y\in K$, it must be that $d(x,y)=d(C,K)$, which concludes our proof. $\square$.

To see that the proposition applies here, it suffices to consider $M=\text{span}(y,x_1,\dots,x_n)$, $d$ the metric induced by the norm of $X$, $K=\{y\}$ and $C=S$.


Find other root of equation $4x^2+ 2x –1 = 0$. If $k$ be a root of the equation $4x^2+ 2x -1 = 0$ then prove that $4k^3-3k$ is the other root.

I simply get the other root as $-\dfrac{1}{4k}$.

As product of roots is $-\dfrac{1}{4}$.

But how to prove that?

Let the other root be given by $\alpha $. Then we have, $$ k+\alpha =- 0.5 \text {  and  } k\alpha =-0.25$$ Then, $k-\alpha = \sqrt { (k+\alpha)^2-4k\alpha} = \sqrt {0.25+1} =\frac {\sqrt {5}}{2} $

Thus, $k = \frac {\sqrt {5}-1}{4} $ and $\alpha = -\frac {\sqrt {5}+1}{4} $. We know that $\sin 18^\circ = \frac {\sqrt {5}-1}{4} = k $ and $\sin 54^\circ = \frac {\sqrt {5}+1}{4} = -\alpha = \sin (3\times 18^\circ) = -4\sin^3 18^\circ + 3\sin 18^\circ = -4k^3+3k $ giving us $\alpha =4k^3-3k $ proving the result. Hope it helps.

Consider $2x=T$.
You can then solve it quickly.


Simple theorems that are instances of deep mathematics So, this question asks about how useful computational tricks are to mathematics research, and several people's response was "well, computational tricks are often super cool theorems in disguise." So what "computational tricks" or "easy theorems" or "fun patterns" turn out to be important theorems?
The ideal answer to this question would be a topic that can be understood at two different levels that have a great gulf in terms of sophistication between them, although the simplistic example doesn't have to be "trivial."
For example, the unique prime factorization theorem is often proven from the division algorithm through Bezout's lemma and the fact that $p\mid ab\implies p\mid a$ or $p\mid b$. A virtually identical proof allows you to establish that every Euclidean Domain is a unique factorization domain, and the problem as a whole - once properly abstracted - gives rise to the notion of ideals and a significant amount of ring theory.
For another example, it's well known that finite dimensional vector spaces are uniquely  determined by their base field and their dimension. However, a far more general theorem in Model Theory basically lets you say "given a set of objects that have a dimension-like parameter that are situated in the right manner, every object with finite "dimension" is uniquely determined by its minimal example and the "dimension." I don't actually quite remember the precise statement of this theorem, so if someone wants to explain in detail how vector spaces are a particular example of $k$-categorical theories for every finite $k$ that would be great.
From the comments: In a certain sense I'm interested in the inverse question as this Math Overflow post. Instead of being interested in deep mathematics that produce horribly complicated proofs of simple ideas, I want simple ideas that contain within them, or generalize to, mathematics of startling depth.

In school they teach us that

$$\int\frac 1x\;\mathrm dx=\log\left|x\right|+C$$

But as Tom Leinster points out, this is an incomplete solution. The function $x\mapsto 1/x$ has more antiderivatives than just the ones of the above form. This is because the constant $C$ could be different on the positive and negative portions of the axis. So really we should write:

$$\int\frac 1x\;\mathrm dx=\log\left|x\right|+C\cdot1_{x>0}+D\cdot1_{x<0}$$

where $1_{x>0}$ and $1_{x<0}$ are the indicator functions for the positive and negative reals.

This means that the space of antiderivatives of the fuction $x\mapsto 1/x$ is two dimensional. Really what we have done is to calculate the zeroth de Rham cohomology of the manifold $\mathbb R-\{0\}$ (the domain on which $x\mapsto 1/x$ is defined). The fact that $\mathrm{H}^0_{\mathrm{dR}}\!\!\left(\mathbb R-\{0\}\right)=\mathbb R^2$ results from the fact that $\mathbb R-\{0\}$ has two components.

You learned the Taylor expansion of a smooth function. It tells you that there is a polynomial function "identical" to your starting function.

It also tells you that pretty much all the math you have learned up until that moment is fake, and can be thrown away. Be a little patient with me here while I explain.

So all properties of all functions you have seen is contained in its property at 0, all you need to represent a function is just a list of all derivatives at 0.

This is very different from any real function like the temperature outside. You can not study the weather at midnight, and then know the temperature for all time to come, and all time that was. Nothing in the real world behave like this

All the analysis of slopes, max, intersections, limits etc can be done by only looking at the function for x=0. No purpose in drawing a function in a diagram. That is just meaningless doodling.

For real functions like the temperature outside a graph and intersections make sense. Is the air warmer than the lake? etc. The weather is a real mathematical problem that a lot of math is used to solve.

Back to our smooth functions: it is all a charade. As you draw functions, and wonder when they will intersect or when they will reach a max, you are doing something useless. The answer is already in the functions property at 0, or at any other location for that matter. So instead of drawing a function across some interval, just draw it carefully around 0. Done. No more needed.

Example when does x^2 intersect e^x. You might as well ask

{0,0,2,0...} = {1,1,1,1...}.


How to prove that square-summable sequences form a Hilbert space? Let $l^2$ be the set of sequences $x = (x_n)_{n\in\mathbb{N}}$ ($x_n \in \mathbb{C}$) such that $\sum_{k\in\mathbb{N}} \left|x_k\right|^2 < \infty$, how can I prove that $l^2$ is a Hilbert space (with dot-product $\left(x,y\right) = \sum_{k\in\mathbb{N}} x_k\overline{y_k}$). This is a standard textbook exercise: apparently this is easy and, even to me, it seems self-evident. However, I don't know what to do with the infinite sum.

Show that your definition $\left(x,y\right) \equiv \sum_{k\in\mathbb{N}} x_k\overline{y_k}$  Satisfies all the inner product axioms.

Hint: axioms are

conjugate symmetric
linearity in one of the arguments
Positive definite: $(u,u)\geq 0$ equality iff u=0

Now show that $F(x) = (x,z)$ defines a bounded linear functional $F$ on your inner product space $X$ of norm $||z||$. If the mapping $z\rightarrow F$ (  $X\rightarrow X'$ where X' is space of continuous linear functionals) is surjective, it must be a hilbert space.

EDIT OK, since you're worried about infinites  let me share something I discovered recently in a book called the Cauchy Schwarz masterclass, the author calls it the principle of qualitative inference.

Given: $\sum_{k\in\mathbb{N}} a_k^2 \lt \infty$  and $\sum_{k\in\mathbb{N}} b_k^2 \lt \infty$ then it can be shown that $\sum_{k\in\mathbb{N}} a_k  b_k \lt \infty$

For large k

$a_k b_k \leq \frac{1}{2} (a_k^2+b_k^2)$

$\Rightarrow \sum_{k\in\mathbb{N}} a_k b_k \leq \sum_{k\in\mathbb{N}}  \frac{1}{2} (a_k^2+b_k^2)$

This already gives you a glimpse at the truth of the assertion.

(On a sidenote, you can go on to introduce $\hat{a}_k=\frac{a_k}{\sqrt{\sum_{k\in\mathbb{N}} a_k^2}}$
and derive the Cauchy inequality!)

Now do for conjugate symmetric what was done for real symmetric.

This is more of an addendum for later, when you dig deeper into functional analysis:

Complex analysis tells us, that every holomorphic function can be represented by its Taylor series, locally. Actually, the space of square summable complex numbers is, as a Hilbert space, isomporph to all holomorphic functions on the unit disc $D := \{ z \in \mathbb{C}, |z| \le 1 \}$, that are square integrable:
$$
\int_D |f(z)|^2 dz \le \infty
$$
with the obvious scalar product
$$
(f, g) = \int_D \bar f (z) g(z) dz
$$
via the mapping
$$
f(z) \to \sum_{i = 0}^{\infty} a_i z^i
$$
and vice versa.

It may help to compare the proof of the Hilbert space axioms for the space of sequences with the proof of the axioms for the function space (the latter needs some "advanced" knowledge of complex calculus). Some may seem to be easier, some more involved. For example it is easy to see that the scalar product actually is a scalar product, without the need to handle infinite sums.


Few beginner set theory questions I have two problems in beginner set theory, and one I am having lot of trouble with, one I am not sure and would want to know if is it correct.

The first one I am having trouble with is

(1)

Suppose $B \subset A_{1}$ and $B \subset A_{2}$

if $$|A_{1}\setminus B|=|A_{2} \setminus B|$$

Then what can be said about the statement $|A_{1}|=|A_{2}|$

Either it is always true, or true if $A_{1}$ and $A_{2}$ are finite but not in general, or it could be false regardless of if they are finite or not.

I keep trying to come up with counter examples but I don't seem to get anywhere, I know the definition of cardinality we are using implies there is a bijection between the sets. To me, it seems like this would be true when finite, I am having trouble finding out fersure. I think when infinite, we could probably come up with an example but I am again not sure. I also don't know how to prove such statements. If I did have to pick right now I would probably choose True if finite but not always.

Update;   But how I can say there a bijection between the set without b implies a bijection between the A?

(1)

   No, that claim is false. Take $A_1 = \mathbb{N}, A_2 = \mathbb{R}, B = \mathbb{R}\setminus\mathbb{Q}$ (I'll assume you know $|\mathbb{N}| = |\mathbb{Q}| = \aleph_0 < \aleph_1 = |\mathbb{R}|$

Oops, sorry, I missed the part where $B \subset A_1, A_2$

Then it's true, because $|X| = |Y| \iff \exists f:X \rightarrow Y$ where $f$ is bijective, and it's easy to extend the bijection on $B$ to get $f':A_1 \rightarrow A_2$ bijective.

(2) To prove equality between sets you should always proceed by showing  double inclusion, i.e. $$X = Y \iff X \subset Y \land Y \subset X$$


Failure of Newton-Leibniz formula Suppose that $f : \mathbb{R} \rightarrow \mathbb{R}$ is differentiable but  $f \notin C^1 ( \mathbb{R} )$ . It means that $f'$ exist but it is not continuous.

Question 1 Is function $f'$ locally integrable. I.e. does there exist for every $a , b \in \mathbb{R}$

$$ \int_{a}^{b} f'(x) dx $$

I think, I should ask about existence of Lebesgue integral.

Question 2 If it exist, does the Newton-Leibniz formula holds?

$$ \int_{a}^{b} f'(x) dx = f(b) - f(a) $$

Comment. I am asking because I wanted to prove Cauchy's integral theorem using Stokes' theorem. One told me that I am not allowed to use Stokes' theorem if derivatives are not continuous.. So I wonder whether it is important. The simplest case of Stokes' theorem is Newton-Leibniz formula.

Question 1. If $f=x^2\sin(x^{-2})$, then $f'$ exists everywhere (including $x=0$) but $f'$ is not Lebesgue integrable on $[0,1]$ (precisely because of the singularity at $x=0$).(Taken from here).

Question 2. By this thread, $f$ is absolutely continuous on each segment $[a,b]$. Then the positive answer follows from the fundamental theorem of calculus for Lebesgue integral (see, for instance, [?, Theorem 6.10], [Ba], [Be, Theorem 2]).

References

[Ba] Diómedes Bárcenas, The Fundamental Theorem of
Calculus for Lebesgue Integral, Divulgaciones Matemáticas 8:1 (2000), 75-85.

[Ba] Stephen Becker, Absolutely continuous functions, Radon-Nikodym Derivative, APPM 5450 Spring 2016 Applied Analysis 2.

[?] “Section 6.5. Integrating Derivatives: Diﬀerentiating Indeﬁnite Integrals”.

Q1: Since $f$ is differentiable on $(a,b)$ then $f(x):=\int_a^x{f'(t)dt}$, where $f'$ is absolutely continuous on $(a,b)$ (we can guarantee this case by Lebesgue theorem), so the answer is Yes $f$ is locally integrable in both senses Riemann and Lebesgue.

Q2: No cannot apply this. Since $f$ is not continuous on $(a,b)$. You may refer to the fundamental theorem of integral calculus.


A function that satisfies the $n$-th derivative where $x=0$ is $\frac{1}{n}$ Is there a function that satisfies $f^{(n)}(0)=\frac{1}{n}$ for every positive integer $n$?

If you assume $\forall n\geq 1$, then I gather any primitive of $f(x) =\frac{e^x-1}{x}$ should do.

The rationale behind it is to find a power series $F$ with $F(x) = \sum_{n=1}^\infty \frac{f^{(n)}(0)}{n!} x^n$ (and non-zero radius of convergence) satisfying what you want. That is,
$$
F(x) = \sum_{n=1}^\infty \frac{x^n}{n\cdot n!}.
$$
Deriving this, you get
$$
F'(x) = \sum_{n=1}^\infty \frac{x^{n-1}}{n!} = \frac{1}{x}\sum_{n=1}^\infty \frac{x^{n}}{n!} = \frac{e^x-1}{x}.
$$

There infinitely many of them... obviously as long as the function is $n$-times differentiable and $f^{(n)}(0)\neq 0$ you can always multiply constant to modify it to be $1/n$. One example is $e^x/n$


How to solve this indefinite integral using integral substitution? So while working on some physics problem for differential equations,  I landed at this weird integral $$ \int \frac 1 {\sqrt{1-\left(\frac 2x\right)}}\,dx $$

So since there is a square root, I thought I could use trig substitution, but I couldn't find anything that works out. How can one solve this integral in a nice simple manner? If you can solve it in a different way, it is still fine. $Thank$ $you!$
This is the answer given to me by symbolab $$ 4\left(-\frac{1}{4\left(\sqrt{1-\frac{2}{x}}-1\right)}-\frac{1}{4\left(\sqrt{1-\frac{2}{x}}+1\right)}-\frac{1}{4}\ln \left|\sqrt{1-\frac{2}{x}}-1\right|+\frac{1}{4}\ln \left|\sqrt{1-\frac{2}{x}}+1\right|\right)+C $$

HINT:

Make the substitution $x=2\sec^2(\theta)$ and arrive at

$$4\int \sec^3(\theta)\,d\theta$$

Some hints

First of all, simple, thing, just rewrite the integrand this way

$$\frac{1}{\sqrt{\frac{x-2}{x}}}$$

Then substitute

$$y = \frac{x-2}{x} ~~~~~~~ \text{d}y = \frac{1}{x} - \frac{x-2}{x^2}\ \text{d}x$$

You're now with

$$2\int \frac{1}{(1 + y^2)\sqrt{y}}\ \text{d}y$$

And for this one, use

$$z = \sqrt{y} ~~~~~~~ \text{d}z = \frac{1}{2\sqrt{y}}\ \text{d}y$$

and your integral is now:

$$4\int \frac{1}{(1 - z^2)^2}\ \text{d}z$$

which is easily solvable by partial fractions:

$$\frac{1}{(1 - s^2)^2} = \frac{1}{4(z+1)} + \frac{1}{4(z+1)^2} - \frac{1}{4(z-1)} + \frac{1}{4(z-1)^2}$$

Split and do the easy integrals.

Final Result

$$x\sqrt{\frac{x-2}{x}} - \ln\left(\sqrt{\frac{x-2}{x}} - 1\right) + \ln\left(\sqrt{\frac{x-2}{x}} + 1\right) + C$$


Finding $7$ inverse modulo $11$ I'm trying to find the inverse of $7$ modulo $11$. From what I understand, the steps are:

\begin{align}
&11 = 1(7) + 3 \\
&7 = 2(3) + 1 \\
\end{align}

From here, you work backwards

\begin{align}
1 &= 7 - 2(3) \\
&= 7 - 2(11-7) \\
&= 7 - 2(11) + 2(7) \\
&= -2(11) + 3(7)
\end{align}

Now, here I see that $7$'s inverse modulo is $3$ but there can be many more (right?). The answer book says that one of them is $8$. Now, assuming my previous steps are correct; how do I find the others?

Thanks!

EDIT:

\begin{align}
11 &= 1(7) + 4 \\
7 &= 1(4) + 3 \\
4 &= 3(1) + 1
\end{align}

Then,

\begin{align}
1 &= 4 - 1(3) \\
&= 4 - 1(7 - 4) \\
&= 4 - 7 + 4 \\
&= -7 + 2(4) \\
&= -7 + 2(11 - 7)\\
&= -7 + 2(11) - 2(7) \\
&= 2(11) - 3(7)
\end{align}


Finding the point through which a circle passes if the general equation is given No idea how it is even possible to do this.

So we have the general equation (but the y-coordinate of the center is still kept variable as you can see below):-
$$x^2+y^2-2x-3ky-2=0$$

We have to find through which two fixed points does the circle pass.

Hint If the points $(x, y)$ of interest satisfy the equation for distinct parameter values $k$ and $k'$, then subtracting the two equations gives that $(x, y)$ must satisfy $$3ky' - 3ky = 0.$$

Hint: at which points does your circle meet the axes?


If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$. If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

This is what I was attempting or trying:

Let $d =$ gcd$(a,b)$.

$d|a \Rightarrow \exists k \in \mathbb{Z}$ s.t. $a = dk$.

$d|b \Rightarrow \exists l \in \mathbb{Z}$ s.t. $b = dl$

Substituting these in we get $dkx + dly = c \Rightarrow d(kx + ly) = c \Rightarrow d|c$ and $(kx+ly)|c$.

I'm not sure if this proves it or not. The help would be appreciated!

You have proved that if $d\mid a$ and $d\mid b$, and $c=ax+by$, then $d\mid c$. That is not at all what we want to show.

The result will be easy once we prove:

Lemma: If $\gcd(a,b)=1$, there exist integers $s$ and $t$ such that $as+bt=1$.

Taking the Lemma for granted temporarily, note that if $as+bt=1$ then $a(cs)+b(ct)=c$, so we can take $x=cs$ and $y=ct$ to prove our result. But the hard part is

Proof of Lemma: We sketch the standard proof. Let $K$ be the set of all positive integers that  can be represented in the form $au+bv$, where $u$ and $v$ range over the integers. The set $K$ is non-empty, so has a smallest positive element $k$.  So there is a $u_1,v_1$ such that $k=au_1+bv_1$. We show that $k=1$. That will complete the proof.

Suppose to the contrary that $k\gt 1$. The number $k$ cannot divide both of $a$ and $b$, for if it did we would violate $\gcd(a,b)=1$. Without loss of generality we may assume $k$ does not divide $a$. Then $a=qk+r$, for some integers $q$ and $r$ such that $0\lt r\lt k$.

But then
$$r=a-qk=a-q(au_1+bv_1)=a(1-qu_1)+b(-qv_1).$$
Since $0\lt r\lt k$, this contradicts the fact that $k$ is the smallest positive integer of the shape $au+bv$.

If $a$ and $b$ are relative primes, the numbers $ax\bmod b$ with $x$ from $0$ to $b-1$ are all different. [Otherwise, $ax\bmod b=ax'\bmod b\implies a(x-x')\bmod b=0$  so that $b$ divides $x-x'$ ($a$ and $b$ having no common factor), a contradiction.] As they are different, they take all values from $0$ to $b-1$, in disorder.

So there is certainly an $x$ such that $ax\bmod b=c\bmod b$, which we can rewrite $ax+by=c$.

For example, $31$ and $17$ are relatively primes. The sequence of $31x\bmod 17$ is
$$0,14,11,8,5,2,16,13,10,7,4,1,15,12,9,6,3.$$

To solve $31x+17y=100$, lookup $100\bmod17=15$, which is $31\cdot12\bmod 17$, and deduce $31\cdot12-17\cdot16=100$.


Is $\exp(-2/X_1)$ an unbiased estimator of $\exp(-2/\theta)$? If $X_1, ..., X_n$ are i.i.d. with pdf
$$f(x\mid\theta) = \frac{1}{\theta}e^{-x/\theta}\quad x>0,\, \theta>0$$
I would like to estimate $P (X_1 > 2) = e^{-2/\theta}$. I think $e^{-2/X_1}$ is a biased estimator, but I don't know how to prove. I tried to prove by definition,
$$ E(e^{-2/X_1}) = \int_{0}^{\infty} e^{-2/x}\frac{1}{\theta}e^{-x/\theta}dx$$
but the integral is very complex to evaluate. Are there any other ways to prove it? Thanks in advance!

If I understand your question, I believe you can directly compute $P\left(X_{1} \gt 2\right)$ from:
$$
P\left(X_{1} \gt 2\right)= \int_{2}^{\infty}\frac{e^{-x/\theta}}{\theta}\mathrm{d}x
$$
$$
P\left(X_{1} \gt 2\right)= -\frac{1}{\theta} \theta \left[e^{-x/\theta}\right]_{2}^{\infty}=e^{-2/\theta}
$$
I hope this helps.


Probability about three independent exponential random variables Suppose we have three independent exponential random variables $A$, $B$ and $C$  with respective parameters $1$, $2$ and $3$.

Calculate $P(A<B<C)$.

The hint says this problem could be solved with calculus and without calculus. I am really curious how to approach it with different methods.

It is rather well known that $$P(A<B)=\frac{\lambda_a}{\lambda_a+\lambda_b}.$$

You should also know the fact that $$\min(A,B)\sim \mathcal E(\lambda_a+\lambda_b),$$ think about the first arrival time of the addition of two Poisson processes, for example.

From there, you could decompose the event $\{A<B<C\}$ into the intersection of the two independent events $$\{A<\min(B,C)\}$$ and $$\{B<C\}$$ to get an intuition of the result.

I have written a program to test the probabilities for three independent exponential random variables A, B and C with respective parameters λa = 1, λb = 2, λc = 3. Here are the results:

P (A < B < C) = 0.3275
P (A < C < B) = 0.2181
P (B < A < C) = 0.2047
P (B < C < A) = 0.0681
P (C < A < B) = 0.1211
P (C < B < A) = 0.0603

P (A < B < C) is not 1/15.

Here is the source code of the program:

Random Rand = new Random(2015);

public Double GetExponential(Double mean)
{
    return -mean * Math.Log(Rand.NextDouble());
}

var totalCase = 0;
for (int i = 0; i < 1000000; ++i)
{
    var p1 = GetExponential(1);
    var p2 = GetExponential(2);
    var p3 = GetExponential(3);

    if (p1 < p2 && p2 < p3)
        ++totalCase;
}
Console.WriteLine(totalCase / 1000000.0);


Probability of $3+3$ cards, out of $6$ cards drawn from a solitaire A solitaire consists of $52$ cards. We take out $6$ out of them (wihout repetition). Find the probability there are $3+3$ cards of the same type (for example, $3$ "1" and $3$ "5").

Attempt.

First approach. There are $\binom{13}{2}$ ways to choose $2$ out of the $13$ types and by the multiplication law of probability, the desired probability is $$\binom{13}{2}\frac{4}{52}\,\frac{3}{51}\,\frac{2}{50}\,
\frac{4}{49}\,\frac{3}{48}\,\frac{2}{47}.$$

Second approach. There are $\binom{13}{2}$ ways to choose $2$ out of the $13$ types and the desired probability is $$\binom{13}{2}\frac{\binom{4}{3}\binom{4}{3}\binom{4}{0}\ldots\binom{4}{0}}{\binom{52}{6}}.$$

These numbers don't coincide, so I guess (at least) one of them is not correct.

Thanks in advance for the help.

In order to fully clear your confusion, let us tackle a simpler problem first.

We are dealing with drawing w/o replacement, (hypergeometric distribution)
If asked to find the Pr of drawing $2$ red and $3$ blue balls from a pool of $5$ red and $4$ blue balls,

Using the multiplication rule, $P(RRBBB)$ in that particular order$\;= \dfrac59\dfrac48\dfrac47\dfrac36\dfrac25$,
but we would need to multiply it by $\dfrac{5!}{2!3!}$ to take care of all possible orders.
[ But this multiplication factor is all too often forgotten by students]

By the combination approach, we would simply use $\dfrac{\binom52\binom43}{\binom95}$

I would advise that you use direct multiplication of probabilities when a specific order is given, and combinations otherwise.

To come back to your problem, you should be able to see that in your first approach, since there are $3$ each of the two types, you need a multiplier of $\dfrac{6!}{3!3!}$,

thus $\dbinom{13}2\dfrac4{52}\dfrac3{51}\dfrac2{50}\dfrac4{49}\dfrac3{48}\dfrac2{47}\times \dfrac{6!}{3!3!}$

whereas the second approach directly gives the correct answer,

in fact you should simplify it to $\dbinom{13}2 \frac{\binom43\binom43}{\binom{52}6}$

For a variety of problems on drawing colored balls from an urn without replacement, you could have a look here

Start with a simple test case, and build up:

Say we are to find $A\heartsuit$, $A\clubsuit$, $A\diamondsuit$, $J\heartsuit$, $J\clubsuit$, $J\spadesuit$, in any order, in the first six cards dealt.

There are $52!$ shuffles, of which $6!\times 46!$ have our cards in the required position.

Now we want to know how many ways we can produce $3$ Aces and $3$ Jack's from the $4$ available in each suit, and this is obviously $\binom43^2=16$.

So far then we have $6!\times 46!\times16$ shuffles that give us what we want.

Now we have $\binom{13}{2}$ ways to pick our two card ranks, so the final answer is:

$$\binom{13}{2}\frac{6!46!16}{52!}\approx0.0000613$$


Validity of an argument Can anyone help me solve this question?

Determine whether the following argument is valid. Explain why:

"If Batman were able and willing to prevent corruption, then he would do so. If Batman were unable to prevent
corruption, he would be ineffective; if he were unwilling to prevent corruption, then he would be cruel. Batman
does not prevent corruption. If Batman exists, he is neither ineffective nor cruel. Therefore, Batman does not
exist."

What do you know that you can bring to bear on this question???

It could be that you are being asked to informally assess the argument (in something of the manner suggested in @Lord_Farin's answer). But (since you are asking in a maths forum!), here's how I imagine you are intended to tackle the question:

  The inference here turns on the propositional connectives "if ..then ...", "and", "not" and "or" -- so obvious first step: render the argument into the language of the propositional calculus.

Do you know how to do that?

  Second step: use the truth-table test to determine whether the formalized argument is valid.

Do you know how to do that?

If you in principle know how to do both steps, this example is straightforward  and should present no problems (this site isn't for doing all your homework for you! -- but ask again if you got stuck at a particular stage)  If you don't know how to do both steps then you'd better do some background reading and get up to speed!

This argument reminds me of some "proofs" of the non-existence of god. First, you assume that god is good and omnipotent and then notice that despite god being all that there is still evil in the world. Ergo, god doesn´t exist.

The argument is valid, and to see that all you need to know is that P => Q is equivalent to not Q => not P. And that if any proposition is implying a contradiction, then that proposition must be false.

Batman exist. => Batman is not cruel. Batman exists also implies that Batman is not ineffective. Bataman is neither ineffective nor cruel => he prevents corruption. And so Batman exists implies both corruption is prevented AND corruption is not prevented. Therefore that statement must be false.


How to calculate percentile? Is it possible to get 100 percentile? How do we calculate percentile? I think it should be calculated as:

P = Total number of candidates
L = Number of candidates whose marks are below yours

Percentile = (L/P)*100
That means if you are the highest in the range, and there are 200,000 candidates and if your marks are same as 7 others then;

your percentile = (199992/200000)*100 = 99.996

That means in any circumstances you can't have perfect 100 percentile.

Then how come this is possible, see links:-
http://www.zeenews.com/news680105.html
http://economictimes.indiatimes.com/cat/two-cat-aspirants-get-100-percentile/articleshow/2685824.cms

There are different definitions of "percentile."

Usually a percentile is computed by first ranking all the data with 1 the lowest, 2 the next lowest, up through $N$.  (The possibility of ties is a complication but does not change the essential idea.)  Ranking from lowest to highest instead of highest to lowest is arbitrary but it gives definite rules.  However, it would be nice if the percentile computed from ranking in one direction agreed with the percentile from ranking in the other.

You can convert a rank $k$ into a percentile by:

Computing $100 k /N$.  This value will range from $100/N$ through $100N/N = 100$.  Note the asymmetry: the highest is 100 but the lowest is nonzero.
Computing $100(k-1)/N$.  This is the rule quoted in the question.  The value will range from $0$ through $100(N-1)/N \lt 100$.
You can make the range of percentiles symmetric.  This means that the percentile corresponding to rank $k$ is $100$ minus the percentile corresponding the rank in reverse order, which is $N+1-k$.  To do this, compute $100(k-1/2) / N$.  The values range from $100/(2N)$ to $100(1 - 1/(2N))$.
There are other ways to make the range symmetric.  For instance, compute $100(k-1)/(N-1)$.  Values range from $0$ through $100$.

(There are yet other rules, used especially for constructing probability plots, but you get the idea.)

Either using the first rule, the last rule, or rounding to the nearest percent, can produce a 100th percentile.  As I recall, Excel's function for computing percentiles can produce 100 for the top-ranked value.

For percentiles, there are actually only 99 equal partitions of the population being ranked: 1 to 99.  It is thoughtless hand waving to say there are 100 equal percentile bands when calculating percentiles.


Compute $B=QAQ^{-1}$ $A,B$ are $n\times n$ matrices, $B=QAQ^{-1}$, and I know $A$ and $B$, how to compute $Q$?

I know if $T$ a linear transformation, and with different basis we get $A$ and $B$, and we could use these basis to compute $Q$, but how to compute if we only got the matrices?

This amounts to finding an invertible solution $Q$ to the Sylvester equation
$$
BQ - QA = 0
$$

You should use SVD decomposition in a such way you decompose them.


Probability notation There is a random variable $B$ (a box) and a particular value it takes $r$ (red color). In Bishop's Pattern recognition and machine learning textbook, he said in p. 14:

  Instead, we may simply write $p(B)$ to denote a distribution over the random variable $B$, or $p(r)$ to denote the distribution evaluated for the particular value $r$...

And then he goes on to say for r.v.s $X$ and $Y$.

  ...the quantity $p(Y |X)$ is a conditional probability and is verbalized as "the probability of $Y$ given $X$"

Here are my questions:

What exactly does "a distribution over the random variable $B$" mean?
Does this distribution mean some mapping of values that r.v. can take to probability values? I usually think about distribution in terms of PDF or CDF. I think $p(r)$ is the density (or PMF in discrete r.v. case).
How can we condition on a random variable $X$? My understanding is that we can only condition on events. Does $p(Y |X)$ mean conditional distribution of $Y$ given $X$ taking some value which is not specified?

What exactly does "a distribution over the random variable $B$" mean?
  Does this distribution mean some mapping of values that r.v. can take to probability values? I usually think about distribution in terms of PDF or CDF. I think $p(r)$ is the density (or PMF in discrete r.v. case).

$p(B)$ represent the probability mass functions of random variable $B$ at arbitrary values.   It is a terribly lazy (but unfortunately common) shorthand used when authors are more interested in showing the dependencies between random variables rather than any particular evaluations.

$p(r)$ demonstrates why this is a horribly confusing idea, as the "probability mass function of value $r$", is meaningless unless it is implicitly clear what is the random variable being discussed.

More properly we should write something like $p_{\small B}(r)$ to indicate the probability mass function of random variable $B$ evaluated at $r$.   In this case that is $\mathsf P(B=r)$; the probability for the event of the box being red.

  How can we condition on a random variable $X$? My understanding is that we can only condition on events.   Does $p(Y |X)$ mean conditional distribution of $Y$ given $X$ taking some value which is not specified?

Again, the this appears to be an abbreviation for $p_{\lower{0.5ex}{\small Y\mid X}}(y\mid x)$, or $\mathsf P(Y=y\mid X=x)$, where $x,y$ are arbitrary arguments.

The occurrence of $X$ realising a particular value is an event.

I have the following distinctions:

$X$ is a random variable, it is a set of possible values associated with a density (which somebody called, a $\sigma$ algebra). Being in caps or not is more or less insensitive as expressions goes more involved, such when we include matrices, for example, in Kalman and DSP topics. We always can say $x$, $y$ and $\omega$ are random variables (are you capitalizing $\omega$?). I would suggest you do not rely on caps for this, though this do not harms so much.
$x$ is a realization of a random variable, this is, a particular value taken. In stochastic models, when a variable can take several realizations at different instants, this convention will automatically render obsolete itself. One always can say $x_0$ or $x_k$ or even $x_t$ are realization of the random variable $x$.
$P(X)$ is the probability of $X$ taking a value $x$ in the set $\mathscr A$. Because $X$ is a random variable, the probability operator $P$ can be applied for every random variables and every subsets of its domain, even for single values $P(X=x_0)$.
$P$ is an operator always applicable over sets, which you call an event is a realization over a set of possible states. Because we talk about sets we can solve much of the simplest problems and Bayes propositions as Venn diagrams. By thinking on events the situation goes a little intuitive and sometimes esoteric,
$y=p(x)$ is the probability density distribution for the random variable. $p$ is a function and also there is no confusion when knowing its value at, e.g. $y_0=p(0)$.
This function allows the calculation:  $p_0=P(X \in \mathscr A )=\int_{\mathscr A}p(x) dx$,
$p(x_0)$ is the distribution for the realization value $x_0$. This is bad. A realization after performed, is no longer stochastic. And you know that the distribution of deterministic values is $y=\delta(x-x_0)$. $p$ no longer exists.
$P(X|Y)$ is the conditional probability. This then, if we want to be consistent, is bad. We should put $P(X \in \mathscr A | Y \in \mathscr B)$, turning the calculation for explicit sets. Here we have two variables, uncorrelated (independent) at the best, unknownly correlated (dependent) at worst. You have to think in a combined density distribution $z=p(x,y)$ as your choice for expressing the most general case. In the best independency cases $z=p(x)q(y)$ in which you only deal with the variables individually.
The calculation in the previous case requires the identity $P(X|Y)={P(X,Y) \over P(Y)}$. $P(Y)$ is calculated as ussually, while $P(X \in \mathscr A ,Y \in \mathscr B)=\int_{\mathscr A} \int_{\mathscr B}p(x,y)dydx$.