How to prove $x^p\equiv x\mod p$ I have already proved that $(x+y)^p\equiv x^p+y^p\mod p$.

And if I take $y=1$, how do I prove the congruency $x^p\equiv x\mod p$? (I should use induction to $x$ but I dont know how to do that in this case)

$$(x+1)^p\equiv x^p+1\equiv x+1\pmod p$$

Using Euler's Theorem, we have that  $x^p\equiv x\cdot x^{p-1} \equiv x\cdot x^{\phi(p)}\equiv x\cdot 1 \equiv x (mod p)$.


Distribution of blood types and alleles The blood type distribution in the US is as follows (according to this link):

O 45%
A 40%
B 11%
AB 4%

However the blood type is a result of the 2 alleles (in lower case) that a person gets from her parents.

aa -> A
oa -> A
ao -> A
oo -> O
ob -> B
bo -> B
bb -> B
ba -> AB
ab -> AB

How can I extract the distribution of the alleles {a,b,o} from the the known distribution of the blood types {O,A,B,AB} ?

Think of many people in population meeting randomly, having your sought-after distribution of alleles. Let me denote by $a$ the fraction of people with allele $a$, and similarly for $b$ and $o$.

Suppose two people from the population meet. The rules for allele to blood type conversion imply the following (row is allele of one person, column is allele of the other person):
$$\begin{array}{cccc}
&a&b&c\\
a&\text{A}&\text{AB}&\text{A}\\
b&\text{AB}&\text{B}&\text{B}\\
o&\text{A}&\text{B}&\text{O}\\
\end{array}$$
If meeting probability is independent of allele and blood type, out of $100$ meetings, $40$ should be in cells with $\text{A}$, $11$ in cells with $\text{B}$, $45$ in cells with $\text{O}$ and $4$ in cells with $\text{AB}$. In terms of frequencies, these numbers are $40/100$, $11/100$, $45/100$ and $4/100$.

Your $a$, $b$ and $o$ fractions then imply following equations:
$$\begin{aligned}
\tfrac{40}{100}&=A=a^2+2oa\\
\tfrac{11}{100}&=B=b^2+2ob\\
\tfrac{40}{100}&=O=o^2\\
\tfrac{40}{100}&=AB=2ab\\
\end{aligned}$$

These are four equations with three variables so there is no guarantee it will have a solution. Since we are dealing with real-world data, your best hope is to solve for $a$, $b$, and $o$ using three of the equations and then check if the last one is approximately satisfied (you can try all possible combinations which one to leave out, but the results are insensitive to which one is left out). If I leave the last equation out and solve,  I am getting $0.25$, $0.08$ and $0.67$ (after rounding).

Let's start with the easiest one. Since the only way to be type O is to have genotype OO, and the probability of having OO is the SQUARE of the frequency of O. we have that p(O) = SQRT(p(OO)) = SQRT(0.45) = 0.67.

Then we have that p(type A) = p(AA) + p(AO) = 0.4. As before, p(AA) = p(A)^2; and p(AO) = p(A(father),O(mother)) + P(O(father),A(mother)) = 2*p(A)*p(O) = 1.34*p(A). So this gives a quadratic equation p(A)^2 + 1.34*p(A) - 0.4 = 0, which you can solve to get two answers, one of which is negative and must be ignored, and the other of which is p(A) = 0.25.

Finally, $p(B) = 1 - p(O) - p(A) = 0.08$. I've kept everything rounded to 2 decimals because that's all we got in the original data, but if you want to assume that those numbers are infinitely precise and calculate more digits, be my guest.


Find the order of a factor group $G/K$ Let $G$ be an abelian group and $g\in G$. Define a map $\phi:G\rightarrow G'$ when $\phi(x)=g^{-1}xg$. Let $K$ be the kernel of homomorphism $\phi$. Find the order of the factor group $G/K$.

I start to define $\phi$

Let $ϕ(x) = gxg^{−1}$ for all $x ∈ G$. Clearly $ϕ$ maps $G$ into $G$. First we will show $ϕ$ is a homomorphism. The homorphism condition holds for $ϕ$ because

$ϕ(xy) = g(xy)g^{−1} = gxyg^{−1} = gx(g^{−1}g)yg^{−1}=(gxg^{−1})(gyg^{−1})= ϕ(x)ϕ(y)$.

Next, $ϕ$ is injective, for if $ϕ(x) = ϕ(y)$ then $gxg^{−1} = gyg^{−1}$, so by multiplying this equation of the left of $g^{−1}$ and on the right by $g$ we get $g^{−1}(gxg^{−1})g = g^{−1}(gyg^{−1})g$, hence $(g^{−1}g)x(g^{−1}g) = (g^{−1}g) y(g^{−1}g)$, hence $x = y$. Finally, $ϕ$ is surjective because if $x ∈ G$ then $ϕ(y) = x$ where $y = g^{−1}xg$, since $ϕ(y) =ϕ(g^{−1}xg) = g(g^{−1}xg)g^{−1} = x$.

Am I fine in my definition?? Next:

Isomorphisms preserve order, so $|x| = |ϕ(x)| = |gxg^{−1}|$ for all $x ∈ G$. An
isomorphism is a bijection, and bijections preserve cardinality of sets, so for any subset $A ⊆ G, |A| = |gAg^{−1}|$.

Now how can I find the order of a factor group $G/K$??

I know
$$\frac{G}{ker\,\Phi}\cong \operatorname{Im}\,(\Phi )$$
let $x\in G$. It is clear $\Phi (gx{{g}^{-1}})=x$ then $G\subseteq G'$. On the other hand $\Phi$ is one to one so $G=G'$.

$\Phi$ is surjective, then
$$\frac{G}{K}\cong G$$
Edit


Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, given variables $a$, $b$ and $c$, as described by the equation below?

$ a x \equiv c \mod b $

For example, given

$ 154x \equiv 14 \mod 182 $, is there an efficient method for computing all the possibilities of $x$, without pure bruteforce?

Please note that I'm not necessarily asking for a direct solution, just a more optimized one.

I do not believe that the Extended Euclidean Algorithm will work here, because $a$ and $b$ are not co-prime.

Edit:
Follow up question, since the first one had a shortcut:

Could the be computed efficiently as well?

$12260x \equiv 24560 \mod 24755$.

$107$ needs to be one of the computed answers.

Solving $154x \equiv 14 \pmod{182}$ is the same as finding all solutions to
$$ 154x + 182y = 14.$$
In this case, we might think of this as finding all solutions to
$$14(11x + 13y) = 14(1),$$
or rather
$$11x + 13 y = 1.$$
Finally, solving this is the same as solving $11x \equiv 1 \pmod {13}$, which has solution $x \equiv 6 \pmod{13}$.

So we learn that $x \equiv 6 \pmod{13}$ is the solution. Of course, this isn't a single residue class mod $182$. Thinking modulo $182$, we see that the solutions are $x \equiv 6, 6+13,6+26,6+39, \ldots, 6+13*13 \equiv 6, 19, 32, \ldots, 175.$

This approach works generally --- factor out the greatest common divisor, consider the resulting modular problem, and then bring it back up to the original problem.

One way to solve the problem ax ≡ c (mod b) would be to treat it as a problem in finding 0,1 for the linear equation ax0 − bx1 = c where ,,,0,1 ∈ . One way to solve the linear equation would be to use substitution in two ways: first to introduce a new variable and a new equation at each step to create a linear system of equations, and second to turn every non-basic variable in the linear system of equation into a basic variable. The motivation for the use of substitution is to express each original variable (0,1) as a basic variable that is a function of parameter variables (0,1,…) such that for any integer value assigned to the parameter variables would result in the original variables taking on integer values. The computations in the algorithm may be organized using augmented matrices.

I have applied one such algorithm to your example problems in "Solving 154x ≡ 14 (mod 182) and 12260x≡ 24560 (mod 24755) Using Augmented Matrices". It also includes an explanation for the algorithm and an animation of the step-by-step solution to the problems.


Union of closure of sets is the closure of the union: true for finite, false for infinite unions Let $A_i$ be a subset of a metric space for each $i\in \mathbb{N}$.

  Let $B_n := \bigcup_{i=1}^n A_i$. Prove (for any) $n \in \mathbb{N}$ that $\overline{B_n} = \bigcup_{i=1}^n \overline{A_i}$.
  If $B = \bigcup_{i=1}^\infty A_i$, prove that $\overline{B} \supseteq \bigcup_{i=1}^\infty \overline{A_i}$. Give an example to show that this containment might be proper.

If $A_i$ is closed then $A_i = \bar A_i$, but I'm stuck as to how to prove $B=\bar B_n$. If I prove the first statement for when $A_i$ is closed does that mean it is also true for when $A_i$ is open because I can construct a closed set containing $A_i$?

For the example, would constructing a sequence of closed segments between $0$ and $1$ that gets arbitrarily close to $1$ and taking the union of the segments be considered a proper containment?

To prove the true statements we'll make use of the following facts:

If $A \subseteq B$, then $\overline{A} \subseteq \overline{B}$.
$x \in \overline{A}$ iff $U \cap A \neq \varnothing$ for every open neighbourhood $U$ of $x$.  (This is in the more general context of general topological spaces. For metric spaces it suffices to restrict the $U$s to the open $\varepsilon$-balls centred at $x$.)

To see that $\bigcup_{i=1}^n \overline{A_i} \subseteq \overline{B_n}$ observe that $A_i \subseteq B_n$ for each $i \leq n$, and apply the first fact above.

To see that $\overline{B_n} \subseteq \bigcup_{i=1}^n \overline{A}_i$ note that this is equivalent to showing $X \setminus \bigcup_{i=1}^n \overline{A}_i \subseteq X \setminus \overline{B_n}$. If $x \in X \setminus \bigcup_{i=1}^n \overline{A_i}$, then by the second fact above it follows that for each $i \leq n$ there is an open neighbourhood $U_i$ of $x$ which is disjoint from $A_i$. Now note that $U := U_1 \cap \cdots \cap U_n$ is an open neighbourhood of $x$ which is disjoint from $B_n$.

Note that the first fact above also shows that $\bigcup_{i=1}^\infty \overline{A_i} \subseteq \overline{\bigcup_{i=1}^\infty A_i} = \overline{B}$.

To give an example of where the equality does not hold, just enumerate the set $\mathbb{Q}$ of rational numbers as $\{ a_i : i \in \mathbb{N} \}$, and for each $i$ define $A_i = \{ a_i \}$. Working in $\mathbb{R}$ with the usual (metric/order) topology, we can show that
$$
{\textstyle \bigcup_{i=1}^\infty} \overline{A_i} = \mathbb{Q} \neq \mathbb{R} =
\overline { {\textstyle \bigcup_{i=1}^\infty} A_i }.
$$

$x \in \bar{A} \cup \bar{B}$

iff $\forall \delta >0,B_\delta(x) \,\cap A \neq \varnothing$ or
$B_\delta(x)\,\cap B \neq \varnothing$
iff $B_\delta(x) \,\cap A\cup B \neq \varnothing$
iff $x \in \overline{A\cup B}$

$x\in \overline{A\cup B}$

iff $\forall \delta >0, B_\delta(x) \cap A\cup B \neq \varnothing$
iff $B_\delta(x)\cap A \neq \varnothing$ or $B_\delta(x) \cap B \neq \varnothing$
iff $x\in \overline{A}$ or $x \in \overline{B}$
iff $x\in \overline{A} \cup \overline{B}$


how do you prove that $A\times (B\setminus C) = (A\times B) \setminus (A\times C)$? This is what I have come up with so far, but I am rather lost at lines 3-4...

$$\begin{align}
(a,b)\in A\times (B\setminus C)\iff& a\in A \land b\in (B\setminus C)\\
\iff& a\in A \land (b\in B \land \lnot(b\in C))\\
\iff& (a\in A \land b\in B) \land (a\in A \land b\notin C)\\
\iff& (a\in A \land b\in B)\setminus (a\in A \land b\in C)\\
\iff& (a,b)\in (A\times B)\setminus ((a,b)\in A\times C)\\
\iff& (a,b)\in (A\times B)\setminus (A\times C)
\end{align}$$

I'd go with the easier path of proving the double inclusion.

Suppose $(a,b)\in A\times(B\setminus C)$. Then $a\in A$ and $b\in B\setminus C$, that is, $b\in B$ and $b\notin C$. Hence $(a,b)\in A\times B$ and $(a,b)\notin A\times C$.

Therefore $(a,b)\in(A\times B)\setminus(A\times C)$.

Suppose $(a,b)\in(A\times B)\setminus(A\times C)$. Then $(a,b)\in A\times B$ and $(a,b)\notin A\times C$. Hence $a\in A$ and $b\in B$. The condition $(a,b)\notin A\times C$ implies that either $a\notin A$ or $b\notin C$. Since $a\in A$, it follows $b\notin C$. Hence $a\in A$ and $b\in B\setminus C$.

Therefore $(a,b)\in A\times(B\setminus C)$.

I think the most intuitive approach is to work from both ends, simplifying the expressions so that they "meet in the middle". As you have said, we have
$$\begin{align}
(a,b)\in A\times (B\setminus C)\iff& a\in A \land b\in (B\setminus C)\\
\iff& a\in A \land (b\in B \land b\notin C).\\
\end{align}$$
On the other hand, we can state
$$\begin{align}
(a,b) \in (A \times B) \setminus (A \times C)
\iff& (a,b)\in (A\times B) \wedge \neg ((a,b)\in A\times C)\\
\iff& [a \in A \wedge b \in B] \wedge \neg [a \in A \wedge b \in C]\\
\iff& [a \in A \wedge b \in B] \wedge [a \notin A \vee b \notin C]\\
\iff& b \in B \wedge [a \in A \wedge [a \notin A \vee b \notin C]]\\
\iff& b \in B \wedge [a \in A \wedge b \notin C].\\
\end{align}$$
Now, it suffices to note that
$$
a\in A \land (b\in B \land b\notin C) \iff b \in B \wedge [a \in A \wedge b \notin C].
$$


Matrix power series has linearly dependent terms Prove that for any $(n\times n)$ real matrix, the set of matrices $\{I,M,M^2,...,M^n\}$ are linearly dependent.

More formally, we have to prove that
$$\forall M \in \mathbb{R}^{n \times n},\\
\exists (a_0,a_1,\ldots,a_n)\neq (0,0,\ldots,0) \\
\text{such that}\;\; \sum_{i=0}^n a_i M^i =0\,\,.   $$

I have a solution which I will post below, but I would like to see if anyone has a more intuitive or elegant proof.

The characteristic polynomial,
$$\det(M-\lambda I)=0 $$
is an order $n$ polynomial in $\lambda$, ie
$$\sum_{i=0}^n a_i \lambda^i=0\,\,.$$

The Cayley-Hamilton theorem states that $M$ solves this equation which proves our theorem.

EDIT: @Traklon has pointed out that this does not prove the above theorem.  It only proves the special case for which $M$ is diagonalizable. My bad!

We start with the expression
$$\sum_{i=0}^n a_i M^i$$
and attempt to prove that there is some choice for the $\{a_i\}$ that makes this become zero.

We then diagonalize $M$, giving $M=C^{-1}DC$ where $D$ is a diagonal matrix with complex elements.  Substituting this into the expression above and using the relation $M^p=C^{-1}D^pC$ for an integer $p$, we get
\begin{align}\sum_{i=0}^n a_i M^i &=\sum_{i=0}^n a_i C^{-1}D^iC \\ &= C^{-1}\left\{\sum_{i=0}^n a_i D^i\right\}C\tag 2\end{align}

Since the set of matrices $\{D^0,D^1,D^2,\dots,D^n\}$ has $n+1$ elements, but only $n$ degrees of freedom (corresponding to its $n$ non-zero elements), it must be a linearly dependent set.  That is to say that for some choice of the $\{a_i\}$,
$$\sum_{i=0}^n a_i D^i = 0\,.$$

Plugging this into Eq (2) shows that for some choice of $\{a_i\}$,
$$\sum_{i=0}^n a_i M^i=0$$
QED.


Arriving at the conclusion that zero multiplied by undefined is zero I was working on a question which asked whether $f(x).g(x)$ is differentiable at $x=a$, given that $g(x)$ is not differentiable at $x=a$. My solution is as following:

I deduced that $f(x).g(x)$ is not differentiable at $a$.
But then I checked my solution using an example, and it seems that my solution was wrong.

In the above example, $f(x)=x-1$ and $g(x)= (mod(x-1)+1)$. Although $g(x)$ is not differentiable at $x=1$, $f(x).g(x)$ IS differentiable at $x=1$.

And this is how I am arriving at the conclusion that zero multiplied by something undefined is zero (at least in this case).
So my questions are:

Can zero multiplied by something undefined be zero?
If the answer to the above question is no, then what is the mistake in my argument?
Is $f(x).g(x)$ differentiable at $x=a$, when $g(x)$ is not differentiable at $x=a$? What are the necessary conditions for $f(x).g(x)$ to be differentiable at x=a?

Note: $f(x)$ is supposed to be differentiable at x=a.
PS: I have just begun studying calculus, and I am not really a genius in Maths. So please excuse me for any grave msitakes that I may have committed above. Thanks.

Zero multiplied by something undefined is undefined. So the answer is no.
Your mistake lies in a wrong application of the theorem which says: If $h=fg$ and $g$ and $f$ are differentiable at $a$, then $h$ is differentiable at $a$ and $h'(a)=g'(a)f(a)+g(a)f'(a)$. In your case, the hypotheses of the theorem are not fulfilled.
Depends on the situation. You show one example in which none are differentiable or continuous and the product is everywhere differentiable. What is not possible is that $f$ and $g$ are differentiable and $h$ is not. The product rule theorem gives you sufficient conditions, not necessary. Both differentiable, then the product is also. If any one is not differentiable, $h$ could either be or not.

Yes, you showed it yourself! Another fun example would be to look at $$ x\cdot\sin(1/x) $$ at $x=0$.
Your mistake lies in the fact that you have just written down $f(a) g'(a)$. Now, this does not exist but it might be the case that $$ \lim_{x\to a} f(x) g'(x) $$ exists.
Really depends on the situation, but if $f(a)$ is non-zero, it will definitely be not the case. In the other case, you can find examples at both ends.

I hope this helps!


What is {p(t):p(2) = 0} in linear algebra? In my linear algebra homework, it asks me if the subset of p2 is the subspace of p2, like the question no.2. I know how to verify if it’s the subspace, but I don’t get what it means by {p(t):p(2) = 0}.

From the context I would say $\{p(t) \,:\, p(2)=0\}$ are those polynomials that vanish at $t=2$, meaning if you substitute $t=2$ the polynomial evaluates to $0$. You could also say that this set is the set of polynomials which have $t=2$ as a zero/root.

$P_2$ is the set of all polynomial functions of degree at most 2

i.e. $p(t) = a t^2 +b t + c$

$\{p(t):p(2)=0\}$ would be the subset such $p(2)=0$

$p(t) = a (t-2)^2 + b(t-2) = at^2 + (-2a+b)t + 4a-2b$

What is the degree, what is the basis?


What about the 'geometry' in 'geometric progression'? Every time I have come upon a discussion of the geometric sequence, I have often wondered (in vain) about the qualifier 'geometric' since such sources never explained the origin of the term. Naturally, I have wondered about the related terms 'arithmetic' and 'harmonic' in the name of their respective sequences too; while I have been able to find some plausible explanation of the origin of these latter two terms, I have however wondered on end about the historical origin of the 'geometric' in the term geometric progression, without appreciable success.

You might have come across, or thought of, a plausible connection between exponential sequences and geometry that gave such sequences their collective name. Please share these below.

Thanks plenty.

In the geometric progression we have that every term is the geometric mean of its predecessor and successior:

  $a_n^2=a_{n-1}a_{n+1}$

The geometric mean (or mean proportional) of two numbers, $a$ and $b$, is the length of the side of a square whose area is equal to the area of a rectangle with sides of lengths $a$ and $b$.

In other terms, is a number $c$ such that :

  $a \times b = c \times c$

that comes from :

  $$\frac a c = \frac c b.$$

See Euclid's Elements VI.13.

The origin is with the Pythagorean School (see also: Archytas).

The early extant souce seems to be Fragment 2 of the lost work of On Music of Archytas [cited by Porphyry, On Ptolemy’s Harmonics, 1.5] :

  And Archytas speaking about the means writes these things:

    “There are three means in music: one is the arithmetic [αριθμητικά], the second geometric [γεωμετρικά] and the third sub-contrary [, which they call “harmonic”].

It's just a convention. Arithmetic means you take the sum and then average.
Geometric means you take the product and then the nth root. Harmonic means you take the sum of reciprocals, average and then take the reciprocal of that.

The main thing that has to happen is that the resulting average has to be from the min to the max. In particular, if all the values are the same, the average has to be that same value.


Confused by proof of the irrationality of root 2: if $p^2$ is divisible by $2$, then so is $p$. In typical proofs of the irrationality of $\sqrt{2}$, I have seen the following logic:

  If $p^2$ is divisible by $2$, then $p$ is divisible by $2$.

Perhaps I am being over-analytical, but how do we know this to be true? IE. do we require a proof of this implication, or is it simply fact?

The quickest proof of that fact is to note that every whole number $n$ is either even or odd.

If $n$ is even, $n=2k$ for some whole number $k$: $n^2 = 4k^2 = 2(2k^2)$ is even.

If $n$ is odd, $n=2k+1$ for some whole number $k$: $n^2 = (2k+1)^2 = 4k^2 +4k + 1 = 2(2k^2 +2k) +1$ is odd.

Therefore the square of a whole number is even if and only if that number is even.

$p^2$ is even iff $p$ is even. So if $2$ divides $p^2,$ it must divide $p.$


"The set of all true statements of first order logic" In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true statements of first order logic, the set of all proofs of them, and the set of all sets.

Now, for the last one, he drew a big line through it, claiming that it introduced issues. It would seem to me that the two before also introduce fairly massive issues, but when I asked a friendly academic, he brushed me off without any real explanation, saying there would be no such issues. I'm going to give my argument below; I hope that anyone can either tell me I'm right, or at least tell me how I'm wrong, so I can better understand the mistakes I made.

Ok, so it would seem to me that for the set of all true statements of first order logic to be useful to us, it would first be necessary for us to be able to check whether a statement is in the set, and also that it's complement is the set of all false statements of first order logic.

Now, by Gödel any formal logical system that can reason about arithmetic must be incomplete (there are true statements of arithmetic that cannot be proved to be true or false in the logical system) or inconsistent (there are statements that can be proved to be both true and false).

So, a simple way of proving whether a statement is in the set is to define a proof program. We have our simple laws of inference ($\vee$-introduction, elimination etc), so it's fairly easy to, looking at a proof in FOL see whether the prover's done something not allowed. So, we go through every string of length 1, then every string of length 2, etc until we find a valid proof of the statement; if the program terminates and there are no syntax errors, it is known that the statement is true. To avoid going on forever with statements which are not in the set, we also check to see whether the negation of the formula is true, since by the law of excluded middle, if something's not true it's false.

Now, by Gödel, the program must

a) go on forever for some statements, since if FOL is incomplete, there will be no proof in the system that certain statements are in the set (even though they are true).

or

b) there will be certain statements for which testing both the statement and its negation will result in an affirmative answer (i.e. FOL is inconsistent).

This implies that a useful set containing all true statements of first order logic cannot exist.

At which point have I gone wrong here?

Your mistake is right at the beginning where you say:

  Ok, so it would seem to me that for the set of all true statements of first order logic to be useful to us, it would first be necessary for us to be able to check whether a statement is in the set,

First of all "is useful to us" is a somewhat vague description, and it is not clear at all that it would mean the same as "is a set".

Moreover, there is no rule demanding that for something to be a "set", there needs to be a definite computable procedure for finding out what its elements are. It needs to be true that everything is either an element or not an element, but there's no demand that we're able to know with certainty which is the case for every prospective element.

It is certainly possible to consider the concept of "collections where we have a definite procedure for telling whether something as a member of the collection". This leads to constructive mathematics, which is an interesting and respectable area of study. It just happens not to be what mathematicians in general mean when they say "set".

Also, a first order statement can only be a member to a set if there is an identity defined for it. But there is no obvious identity relation for statements, between alphabetical identity and logical equivalence.


Prove that $f(\mathbb R) = \mathbb R$. Partially solved. Let $f:\mathbb R\to \mathbb R$ and $f(f(x)) = x + f(x)$, $x\in\mathbb R$
Prove that: a) $f$ is injective
b) $f(0) = 0$
c) $f(\mathbb R) = \mathbb R$

My solution:
a) Let $x_1, x_2 \in \mathbb R$ and $f(x_1) = f(x_2)$ then
$f(f(x_1)) = f(f(x_2))$
$x_1 + f(x_1) = x_2 + f(x_2)$
$x_1 = x_2$ therefore $f$ is injective.
b) Let $x=0$ then $f(f(x)) = x + f(x)$
$f(f(0)) = 0 + f(0)$
$f(f(0)) = f(0)$ but $f$ is injective therefore
$f(0) = 0$
c) Here is the point where I get stuck. How do I solve this?
I think I have to begin saying, let $y\in\mathbb R$ and prove that there is a $x\in\mathbb R$ for which $f(x) = y$.

It works if you assume $f(x)$ is continuous.

Claim:
Suppose $f(x)$ is continuous and $f(f(x)) = x + f(x)$ for all $x \in \mathbb{R}$. Then $f(\mathbb{R})=\mathbb{R}$.

Proof:
We already know that $f(0)=0$ and $f(x)$ is injective.  It follows that $f(1)\neq 0$.

-Case 1: Suppose $f(1)>0$.  Then (by the intermediate value theorem) we must have:
\begin{align}
&f(x) > 0 \: \: \mbox{ if $x >0$} \\
&f(x) < 0 \: \:   \mbox{ if $x<0$}
\end{align}

For all positive integers $n$ we have:
\begin{align*}
&f(f(n)) = n + f(n) \geq n\\
&f(f(-n)) = -n + f(-n) \leq -n
\end{align*}
and so $f$ takes arbitrarily large values and arbitrarily small values. By the intermediate value theorem, it must take all values in $\mathbb{R}$.

-Case 2: Suppose $f(1)<0$.  Then we must have:

\begin{align}
&f(x) < 0 \quad \mbox{ whenever $x >0$} \\
&f(x) >  0 \quad  \mbox{ whenever $x<0$}
\end{align}

Suppose there is a finite constant $-M$ such that $f(x) \in [-M,0]$ for all $x\geq 0$ (we reach a contradiction).  Then the infinite sequence $\{f(n)\}_{n=1}^{\infty}$ is in the compact interval $[-M,0]$, so the Bolzano-Wierstrass theorem ensures there is a subsequence $n_k$ such that $n_k\rightarrow\infty$ and $f(n_k) \rightarrow x^*$ for some $x^* \in [-M,0]$.  But for all $k$ we have:
$$ f(f(n_k)) = n_k + f(n_k) $$
and taking a limit as $k\rightarrow \infty$ gives $f(x^*) = \infty + x^*$, a contradiction.  Thus, $f(x)$ takes arbitrarily small values over $x\geq 0$.

A similar argument shows $f(x)$ takes arbitrarily large values over $x \leq 0$.  Hence, by continuity, $f(\mathbb{R}) = \mathbb{R}$.

The solution (given by my teacher).

Let $y\in \mathbb R$ I'll prove that there is a $x \in \mathbb R$ for which $f(x) = y$

$f(x) = y$

$f(f(x)) = f(y)$

$x + f(x) = f(y)$

$x + y = f(y)$

$x = f(y) - y$

therefore $f(\mathbb R) = \mathbb R$


zero of polynomial integral => polynomial has invertible leading coefficient Let $A$ be a domain, $f \in A[x]$ irreducible and $b$ a zero of $f$, so we have
$A[x]/(f) \cong A[b]$. I want to show, under certain circumstances, that
$b$ integral over $A$ implies that $f$ has an invertible leading coefficient.

I consider the following: $A = K[Y]$, the coordinate ring of an affine variety $Y$. If $A$ would be integrally closed, then we would know that $b$ had a monic minimal polynomial $p$ over $A$ and would be done ($f = u \cdot p$, $u$ unit in $A[x]$, i.e. constant).

But here, as a coordinate ring, $A$ in general will not be integrally closed.
How do we proceed here?

So, if $A$ is a domain with $b$ integral over $A$, and if $f(x)\in A[x]$ is irreducible with $b$ as a root, then is the leading coefficient of $f$ invertible in $A$?

In general, no.  Let $A=\mathbb{Z}[\sqrt{-3}]=\{a+b\sqrt{-3}\,\vert\,a,b\in \mathbb{Z}\}$, and let $\omega=\frac{-1+\sqrt{-3}}{2}$ be a primitive third root of unity.  Note that $\omega\notin A$ and $\omega$ is a root of the monic polynomial $g(x)=x^2+x+1\in A[x]$, thus $\omega$ is integral over $A$.  Also, $g(x)$ is irreducible in $A[x]$, since the only roots of $g$ are $\omega$ and $\overline{\omega}:=\frac{-1-\sqrt{-3}}{2}$.

However, $f(x)=2x-2\omega = 2x+1-\sqrt{-3}\in A[x]$ is irreducible (and has $\omega$ as a root), but $2\notin U(A)=\{\pm 1\}$.

Isn't it by definition that a element is integral over a ring $A$ if it is the root of a monic polynomial with coefficients in $A$?


Homology and (co)Limits I've looked around on MSE and online only to find scattered results, which confuse me. I want to understand how homology behaves with (co)limits. I want to know in particular about singular homology, and in general about homology theories.

Does singular homology commute with arbitrary colimits? Where can I find proof of this? Under what conditions does it behave well with limits?
In A Concise Course in Algebraic Topology, the author proves using the additivity, weak equivalence, and MVS axioms that homology preserves direct limits. Unless I'm mistaken, preserving direct limits is equivalent to preserving filtered colimits. Is this correct? Is there a simpler proof for May's result?

Added:
In particular, I am confused by the answer to this question according to which homology preserves all kinds of colimits.

Singular homology already fails to commute with pushouts. A pushout of spaces doesn't give a pushout of homology groups, but instead gives (maybe under niceness conditions) a long exact sequence. For an explicit example consider the pushout of

$$D^2 \leftarrow S^1 \rightarrow D^2$$

which is $S^2$. This doesn't induce a pushout on $H_2$.

Singular homology also fails to commute with products. (Note that the tensor product is not the product in the category of abelian groups, or of graded abelian groups, so even if we're working over a field the Kunneth formula is not a response to this claim.)

The first fact is in some sense a reflection of a failure to be suitably higher categorical. There is a very abstract description of what it means to compute the homology (not the homology groups, but "the homology") of a space, namely tensoring it with some spectrum, and this construction preserves all homotopy colimits (in fact it is a left adjoint in a higher categorical sense). It's very natural to think about homotopy colimits rather than colimits because taking singular homology is homotopy-invariant, but taking colimits is not, while taking homotopy colimits is.

Then you have to figure out how to compute homotopy colimits of spaces, and also figure out what a homotopy colimit of spectra buys you once you pass to homotopy groups (e.g. long exact sequences, or more generally spectral sequences).

This is not exactly an answer to your question, except that it is relevant to the question of homotopical invariants preserving at least some colimits. For example, the fundamental group of based spaces does not preserve all colimits: the usual  Seifert-van Kampen Theorem determines the fundamental group of a union $X=U \cup V$ of based spaces if $U,V$ are open and $U \cap V$ is path connected. See  this mathoverflow discussion on this issue. .

A generalisation of this theorem, dating to  1981, and also involving connectivity conditions,   is given in the 2011 book Nonabelian Algebraic Topology, and concerns in part a homotopically defined functor $\Pi$ from filtered spaces to "crossed complexes", which are a kind of partially nonabelian chain complex with operators. This work does not involve an input from singular homology, although the relation to that is of interest.

Background to this work is given in this recent paper  Modelling and Computing Homotopy Types: I, which gives a methodology for  the use of colimit arguments  in homotopy theory.

We also  know that that homology groups as functors from chain complexes to say graded abelian groups do not preserve colimits.


Induced group homomorphism $\text{SL}_n(\mathbb{Z}) \twoheadrightarrow \text{SL}_n(\mathbb{Z}/m\mathbb{Z})$ surjective? Let $n, m > 1$. The map $\mathbb{Z} \twoheadrightarrow \mathbb{Z}/m\mathbb{Z}$, of reduction mod $m$, induces a group homomorphism $F: \text{SL}_n(\mathbb{Z}) \to \text{SL}_n(\mathbb{Z}/m\mathbb{Z})$. My question is, is $F$ surjective or not?

This turned out to be a non-example.  I'm leaving it up for posterity as a CW answer.

As it turns out, the answer is no.  The smallest counterexample I can think of is as follows: we note that
$$
\pmatrix{2&1&1\\1&2&1\\1&1&2} \in SL_n(\Bbb Z/3\Bbb Z)
$$
However, this matrix is not the reduction mod $3$ of any element of $SL_n(\Bbb Z)$.


Fitch-Style Proof ¬(A → B) → (A ∧ ¬B) Good Evening,
I want to proof this statement: ¬(A → B) → (A ∧ ¬B). I have no premises.
I already did other proofs where I have no premises and a implication. I guess I have to start with the antecedent as my premise and try to generate the consequence. But there is not much I can use, so I thought I can proof it with contradiction.
This is my idea:

I used this website: http://proofs.openlogicproject.org/

HINT:
Your proof by contradiction is a good idea, but instead of doing that on the whole $A \land \neg B$ statement, try and prove each of $A$ and $\neg B$ using proof by contradiction.  It's clear how to set that up for the latter (assume $B$, and try and get $\bot$). For the former, you would assume $\neg A$, and if that leads to $\bot$, you get $\neg \neg A$, from which you can then infer $A$.

Observe this fact: $\neg(p\to q)\equiv p \wedge \neg q$ this is true because both propositions have the same truth table.
Now notice that $p\to p$ is a tautology.
Then use the fact, if $P\equiv Q$ then we can "replace" $P$ instead of $Q$ in any statement that includes $Q$.
Now $p\to p$ is a tautology then $\neg(p\to q)\to \neg(p\to q)$ is a tautology, and now
$\neg(p\to q)\to (p \wedge \neg q)$  is a tautology.


What is the volume and surface area of the 1-Sphere? I am reading a post on here that mentioned something about the 1-sphere. I know that a 2-sphere is a circle, and 3-sphere is a volume, but what is this 1-sphere and how do you calculate the volume and surface area of a 1-sphere?

A 2-sphere is a standard sphere, if I understand correctly, because the surface itself is a mapping of a two dimensional space (the plane). The standard way of seeing this is called "stereographic projection" in which the circles sits on top of a place, and lines are drawn from the north pole through the sphere to the plane. This is a correspondence between the points in the plane and the points on the sphere.

The 1-sphere is the image of a function of one-variable, so it is a circle. The typical example is to parameterize it in terms of cosine and sine of a real variable $t$.

For a $0$-dimensional sphere: $V = 1$ and $S = 0$

For a $1$-dimensional sphere: $V = 2R$ and $S = 2$

For a $2$-dimensional sphere: $V = \pi R^2$ and $S = 2\pi R$

For a $3$-dimensional sphere: $V = \frac {4}{3} \pi R^3$ and $S = 4 \pi R^2$

Note that the derivative of the volume with respect to $R$ equals the surface area. This is true for spheres of every dimension $N$.


Proof about Clavius's Law Clavius's Law claimed:

$(\neg A \rightarrow A) \rightarrow A$

What it is the proof about it in Deductive System $L$?

Deductive System $L$ is:
L1: $A \rightarrow (B \rightarrow  A)$
L2: $(A \rightarrow (B \rightarrow C)) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$
L3: $(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$ or $(\neg B \rightarrow \neg A) \rightarrow (A \rightarrow B)$
And only it allows us to use Modus Ponens

I was trying this:

$\neg A \rightarrow (A \rightarrow \neg A)$ by L1
$(\neg A \rightarrow (A \rightarrow \neg A)) \rightarrow (\neg A \rightarrow A) \rightarrow (\neg A \rightarrow \neg A)$ by L2
$(\neg A \rightarrow A) \rightarrow (\neg A)$ by Modus Ponens (1,2)

Then I was thinking in show that
$\neg A \rightarrow A$
But don't get success and I'm not sure if that will help me

We need $\vdash A \to A$, easily provable from Ax.1 and Ax.2.

We need also some "auxiliary" results :

Lemma 1 (Syllogism) :

1) $A \to B$ --- premise

2) $B \to C$ --- premise

3) $\vdash (B \to C) \to (A \to (B \to C))$ --- Ax.1

4) $A \to (B \to C)$ --- from 2) and 3) by modus ponens

5) $\vdash (A \to (B \to C)) \to ((A \to B) \to (A \to C))$ --- Ax.2

6) $(A \to B) \to (A \to C)$ --- from 4) and 5) by modus ponens

  7) $A \to C$ --- from 1) and 6) by modus ponens.

Lemma 2 :

1) $\vdash \lnot A \to (\lnot B \to \lnot A)$ --- Ax.1

2) $\vdash (\lnot B \to \lnot A) \to (A \to B)$ --- Ax.3

  3) $\vdash \lnot A \to (A \to B)$ --- from 1) and 2) by Syllogism.

Lemma 3 :

1) $\vdash \lnot A \to (A \to \lnot B)$ --- Lemma 2

2) $\vdash \lnot A \to (A \to \lnot B) \to ((\lnot A \to A) \to (\lnot A \to \lnot B))$ --- Ax.2

3) $\vdash (\lnot A \to A) \to (\lnot A \to \lnot B)$ --- from 1) and 2) by mp

4) $\vdash (\lnot A \to \lnot B) \to (B \to A)$ --- Ax.3

  5) $\vdash (\lnot A \to A) \to (B \to A)$ --- from 3) and 4) by Syll.

Now for the main proof :

1) $\vdash (\lnot A \to A) \to ((\lnot A \to A) \to A)$ --- Lemma 3

2) $\vdash ((\lnot A \to A) \to ((\lnot A \to A) \to A)) \to (((\lnot A \to A) \to (\lnot A \to A)) \to ((\lnot A \to A) \to A))$ --- Ax.2

3) $\vdash ((\lnot A \to A) \to (\lnot A \to A)) \to ((\lnot A \to A) \to A)$ --- from 1) and 2) by mp

4) $\vdash (\lnot A \to A) \to (\lnot A \to A)$ --- from $\vdash A \to A$

    5) $\vdash (\lnot A \to A) \to A$ - from 3) and 4) by mp


The Mathematics of Tetris I am a big fan of the old-school games and I once noticed that there is a sort of parity associated to one and only one Tetris piece, the $\color{purple}{\text{T}}$ piece.  This parity is found with no other piece in the game.

Background: The Tetris playing field has width $10$.  Rotation is allowed, so there are then exactly $7$ unique pieces, each of which is composed of $4$ blocks.

For convenience, we can name each piece by a letter.  See this Wikipedia page for the Image ($\color{cyan}{\text{I}}$ is for the stick piece, $\color{goldenrod}{\text{O}}$ for the square, and $\color{green}{\text{S}},\color{purple}{\text{T}},\color{red}{\text{Z}},\color{orange}{\text{L}},\color{blue}{\text{J}}$ are the others)

There are $2$ sets of $2$ pieces which are mirrors of each other, namely $\color{orange}{\text{L}}, \color{blue}{\text{J}}$ and $\color{green}{\text{S}},\color{red}{\text{Z}}$ whereas the other three are symmetric $\color{cyan}{\text{I}},\color{goldenrod}{\text{O}}, \color{purple}{\text{T}}$

Language: If a row is completely full, that row disappears.  We call it a perfect clear if no blocks remain in the playing field.  Since the blocks are size 4, and the playing field has width $10$, the number of blocks for a perfect clear must always be a multiple of $5$.

My Question:  I noticed while playing that the $\color{purple}{\text{T}}$ piece is particularly special.  It seems that it has some sort of parity which no other piece has.  Specifically:

  Conjecture:  If we have played some number of pieces, and we have a perfect clear, then the number of $\color{purple}{\text{T}}$ pieces used must be even.  Moreover, the $\color{purple}{\text{T}}$ piece is the only piece with this property.

I have verified the second part; all of the other pieces can give a perfect clear with either an odd or an even number used.  However, I am not sure how to prove the first part.  I think that assigning some kind of invariant to the pieces must be the right way to go, but I am not sure.

Thank you,

My colleague, Ido Segev, pointed out that there is a problem with most of the elegant proofs here - Tetris is not just a problem of tiling a rectangle.

Below is his proof that the conjecture is, in fact, false.

Edited to add: The following is only correct if you build up your four lines from 0 (or if you only eliminate four rows at once) which is the way to get maximal points in Tetris. For a counterexample in the general case of clearing the screen in any way you like, see (and vote for) the answer by Gilad Naor

My original answer:

Color the squares black and white in a chessboard fashion and regard the parity of black squares. This is your invariant.

(The $10\times 4$ rectangle has an even number of black squares, each $\color{purple}{\text{T}}$-piece has $3$ or $1$ black squares and all other pieces clearly have $2$ black squares, so not only do you have an even number of $\color{purple}{\text{T}}$s, you have the same number of predominantly black $\color{purple}{\text{T}}$s and predominantly white $\color{purple}{\text{T}}$s.)

There is a similar further relation for the combined number of $\color{orange}{\text{L}}$s and $\color{blue}{\text{J}}$s:

The number of $\color{orange}{\text{L}}$s, $\color{blue}{\text{J}}$s and $\color{purple}{\text{T}}$s with a horizontal line of three squares is even.

Instead of the checkboard colouring, you just look at the alternate coloring of whole rows and see that these pieces are exactly the ones that contribute an odd number of black squares.


Evaluate $\int_0 ^x \frac{\sin\left(\frac{1}{2}-n\right) t}{\sin\frac{t}{2}}\,dt$. Evaluate
$$\int_0 ^x \frac{\sin\left(\frac{1}{2}-n\right) t}{\sin\frac{t}{2}}\,dt$$
for $x\in(0,2\pi)$ and $n\in\mathbb Z$. From trigonometric formulas, we have:
$$\int_0 ^x\cos nt\, dt-\int_0 ^x \frac{\cos\frac{t}{2}}{\sin\frac{t}{2}}\, \sin nt\,dt$$
What can we say for the second integral? I was not able to solve it.

Only a partial answer for $n\in\mathbb{N}$, but maybe helpful nonetheless. Call $f_n(x)=\int_0^x dt \sin(nt)\cot(t/2)$ and consider the generating function
$$
F(z,x)=\sum_{n=0}^\infty f_n(x)z^n=\int_0^x dt\cot(t/2)\frac{\mathrm{i} \left(-1+e^{2 \mathrm{i} t}\right) z}{2 \left(-z+e^{\mathrm{i} t}\right) \left(-1+e^{\mathrm{i} t} z\right)}=
$$
$$
=-\frac{z}{2}\int_0^x dt\ \frac{\left(1+e^{\mathrm{i} t}\right)^2 }{\left(-z+e^{\mathrm{i} t}\right) \left(-1+e^{\mathrm{i} t} z\right)}\ ,
$$
using the Euler's representation of the cotangent. The real part of it can be computed with the help of Mathematica, yielding eventually (for $0<x<2\pi$ and $|z|<1$)
$$
F(z,x)=-\frac{(x+\pi ) z+2 (z+1) \arctan\left(\frac{(z-1) \cot \left(\frac{x}{2}\right)}{z+1}\right)-x+\pi }{2 (z-1)}\ .
$$
[This agrees with numerics]. The generating function can be represented as
$$
F(z,x)=\varphi\left(\frac{z-1}{z+1};x\right)+\frac{x}{z-1}\ ,
$$
where
$$
\varphi(\xi,x)=-\frac{1}{\xi}\arctan(\xi\cot(x/2))-\frac{x+\pi}{2\xi}\ .
$$
With any symbolic software, you can obtain a closed form solution for any $n$ by simply Taylor-expanding this result around $z=0$. For example:
$$
f_3(x)=x+2 \sin (x)+\sin (2 x)+\frac{1}{3} \sin (3 x)\ ,
$$
and based on some experiments, one might conjecture a general form as
$$
f_n(x)=x+\sum_{k=1}^n \frac{n_k}{m_k}\sin(k x)\ ,
$$
with $n_k$ and $m_k$ small integers. A closed-closed form solution might be obtained after some painstaking work on the generating function (using also the great simplification that $\arctan(\cot(x/2))=(\pi-x)/2$). But that's not for me tonight.

It is sufficient to  consider an integral of the form $$\int \frac{\sin \left(\left(2k+1\right)t\right)}{\sin t}dt.$$ One has $$\frac {\sin\left(\left(2k+1\right)t\right)}{\sin t}=\frac{e^{i\left(2k+1\right)t}-e^{-i\left(2k+1\right)t}}{e^{it}-e^{-it}}=2\left[\cos 2kt +\cos \overline{2(k-1)}t + \cos \overline{2(k-2)}t + \cdot\cdot\cdot+\cos 2t \right]+1.$$ Each of the terms are easily integrated, but can't think of a further simplification.


Proof of $(0,1)$ is not compact with usual metric. In the proof we say $\left\{\left(\frac1n,1\right):n\geq 1\right\}$ is an infinite cover with no finite subcover.

But, $(0,1)$ set also belongs to cover mentioned above.
We can say $\{(0,1)\}$ is a subcover of mentioned above cover.

I am not able to understand what I am doing wrong.

$(0,1)$ is not in your open cover (for which integer $n$ is $0$ of the form $1/n$?). Therefore it can't be in a subcover.

To show that it has no finite subcover, take such a finite subcover. Being finite, it would have a maximum integer $n$ included, say $N$. But then the subcover is a subset of
$$ \left( \frac{1}{N}, 1 \right), $$
since every other $1/n$ is larger than $1/N$. Hence you miss any point between $0$ and $1/N$.

(Alternatively, use that a subset of a metric space is compact iff sequentially compact, and consider the sequence $1/n$, which is clearly Cauchy, &c.)

I suggest you go the following way:
First try to show all compact sets are closed, then see why (0,1) is not compact.


Proving $H$ is a normal subgroup of $G$ Let $V$ be a non-empty set and $(SV,\circ)$ the symmetric group of $V$. Let $W \subseteq V$ a non empty subset of $V$. We define the next two subgroups of $SV$: $ G = \{ \sigma \in SV  \mid \sigma(W)=W  \} $ and $H = \{ \sigma \in SV\mid \forall w \in W: \sigma(w)=w \} $.

I have to prove that $H$ is a normal subgroup of $G$. But I have some trouble visualising which elements there are in $G$ and $H$. For me it looks like the condition $\sigma(W)=W$ is always true and $\sigma(w)=w$ is only true for the identical permutation. This looks too easy and trivial. So I'm asking is this true what I'm saying?

Thanks in advance!

Well, for example let us take the set $V = \{a,b,c\}$. Then there are six permutations in $(SV,\circ)$. A non trivial permutation is one sending $a \to b , b \to a$ and $c \to c$, for example. I am sure you can figure out the rest of the elements.

Now, take $W = \{a,b\}$. $G$, for this $W$ is defined as the permutations which keep $W$ in $W$.

For example, let $\sigma_1$ be defined as $a \to b, b\to a , c \to c$. We note that $\sigma_1(a) = b \in W$ and $\sigma_1(b) = a \in W$. Thus, $\sigma$ sends every element of $W$ to some other element in $W$. This need not be the same element : for example, $a,b$  are not going to themselves under $\sigma_1$, but we have $\sigma_1 \in G$.

An example of an element not in $G$ would be $\sigma_2$ sending $a \to b , b \to c, c \to a$,  because $\sigma_2(b) = c$ which is not in $W$, but $b \in W$, so $\sigma_2(W) \neq W$.

However, if every element of $W$ is sent to itself, that is more special than every element going to another in $W$. For example, the identical permutation has this property, because it sends every element to itself,and  therefore those in $W$ as well. Such permutations come into $H$.

For an example where a non-identical permutation can be in $H$ : take the set $V' = \{a,b,c,d\}$ and $W = \{a,b\}$. Then the permutation $a \to a , b\to b , c \to d , d \to c$ is not identical, but it sends every element of $W$ to itself. Such a permutation would be in $H'$ (where $H'$ is the subgroup for this $V',W'$).

However, $a \to b, b\to a , c\to d , d \to c$ is not an element of $H'$, but rather of $G'$, because every element of $W'$ is not going to itself, but at least is going to another element of $W$.

The permutation $a \to b,b\to c , c \to a, d\to d$ is seen to belong to neither $H'$ nor $G'$.

From the above , I leave you to see that $H$ is a subset of $G$(we don't know if they are groups, so we don't use subgroup yet).

We will show that $G$ is a group, I leave $H$ to you.

It is enough to check that $G$ contains the identity, and is closed under inverse and multiplication.

Let $\sigma,\tau \in G$. We claim $\sigma \circ \tau \in G$. To see this, take $w \in W$. Then $\sigma \circ \tau(w) = \sigma(\tau(w))$. Now, $\tau(w) \in W$ by definition of $\tau \in G$, and then $\sigma(\tau(w)) \in W$ by definition of $\sigma \in G$ (andd because $\tau(w) \in W$). Thus, $\sigma \circ \tau \in G$, because every element of $W$ goes to another in $W$.

For inverse, we need to use $\sigma(W) = W$.  Let $w\in W$. Then, from the equality, $\sigma(W) = W $ so $w \in \sigma(W)$. By definition of $\sigma(W) = \{\sigma(v) : v \in W\}$, there is some $v \in W$ so that $\sigma(v) = w$. But then, $\sigma^{-1}(w) = v\ in W$ by definition of the inverse. Thus, $\sigma^{-1}$ keeps elements of $W$ in $W$, so inverse closure is done.

The identity is clearly in $G$. Thus $G$ is a group.

Work similarly for $H$, it is even easier.

Here is a slightly more conceptual way to view these groups:

Let $U$ be the complement of $W$ in $V$. Then there is a natural way to identify $G$ with $SW\times SU$, using the notation for symmetric groups from the OP.

With this identification in place, the subgroup $H$ can be seen as just the component $\{e\}\times SU$, which is normal since it is a direct factor.


Correct term for percentage in decimal form I have 35% of something, but when I calculate how much that is I multiply the total by 0.35

Is there a unambiguous word for the decimal form of a percent? "Decimal" is too broad because it can refer to any number with a fractional component. "Fraction" suggests the format 35/100.

I am partial to what Omnomnomnom mentioned in a comment: it is a proportion, and the authoritative Oxford English Dictionary supports this terminology (snippet produced below):

If we look at the decimal $0.35$ and want a word to describe "$0.35$ of a number", we should notice that it would be convenient to describe it as a ratio, say $\frac{35}{100}$. That is, we have $35$ parts of a hundred.
We can rephrase this as $35$ parts per hundred, and then use some Latin and get fancy to call this $35$ parts per centum. This is a bit too wordy, so I would propose that we shorten this even further to "$35$ per-cent".

Tldr: The word "percent" itself was invented to describe (almost) exactly what you want.


A problem V.I. Arnold solved as a primary school student According to a 1995 interview that Vladimir I. Arnold gave to the Notices of the AMS,
his primary school teacher I.V. Morozkin gave in 1949 (when Arnold was 12 years old) to a Soviet classroom, most likely the 6th grade, the following question

  Two women started at sunrise and each walked at a constant velocity. One went from $A$
  to $B$ and the other from $B$ to $A$.  They met at noon and, continuing with no stop,
  arrived respectively at $B$ at 4 p.m. and at $A$ at 9 p.m. At what time was the sunrise
  that day?

The question is not how to solve this problem, but rather How to solve this problem using what 12 year old kids know (or knew during the Soviet era).

UPDATE. In the same interview, Arnold also said:

  I spent a whole day thinking on this
  oldie, and the solution (based on what
  is now called scaling arguments,
  dimensional analysis, or toric variety
  theory, depending on your taste) came
  as a revelation.

It would be of interest to know how, in Arnold's mind, dimensional analysis and toric varieties are related to this problem.

Triangle similarity

He could have solved the question by drawing a figure such as the one below. If he knew about similar triangles at the age of $12$, he could easily set up the equation $ \dfrac{x}{4} = \dfrac{9}{x} $. From here, if he knew how to solve equations like this, he could solve $ x^2=36 $. If he did not, he could simply try a few different values of $x$ until he found one that works.

Colored triangles are similar. The problems with this explanation are:

This is essentially drawing a time-position plot. Since this is a $12$ year old who does not know multivariate algebra, it's a bit of a stretch to assume he would know how to use kinematic plots to solve problems. But then again, who knows, maybe he was imagining the women walk and the plot seemed intuitive.
It requires him to be able to set up and somehow find the solution of the quadratic equation.
What does this have to do with "scaling arguments, dimensional analysis or toric variety theory"?

Trial and error

He could have simply tried a bunch of possible values until he found a solution.

Let's say he decided to try $9$ am: That means woman $A$ walked the first distance in $3$. So the ratio of distances is $\dfrac{3}{4}$. But if woman $B$ walked the first part in $3$ hours, then the ratio comes out $$\dfrac{3}{9+3}=\dfrac{3}{12}!$$ So $9$ am isn't right.

Luckily the solution is an integer, and somewhere between $4$ and $9$ hours before noon, since the quick woman would have walked more than half the distance in the morning and the slow one would have walked less than half (drawing a $1$D diagram makes this obvious). Even if the solution was not an integer, after exhausting integers he could have tried half hours, then quarter hours, and so on. I'm sure a binary search type of strategy would become obvious if he kept track of how much each sunrise hour was off by. Since he spent "all day" on it, there's plenty of time for numeric solutions.

The problem is that solving it by brute force teaches you absolutely nothing (well, it's arithmetic practice, and you do end up discovering binary search). There's also the question of what this has to do with scaling arguments, dimensional analysis or toric variety theory. It's also the sort of solution that you would expect from perhaps a future clerk, not mathematician.

Incidentally, after trying a bunch of numbers like this, the $\dfrac{x}{4}=\dfrac{9}{x}$ equation does suggest itself.

Sort of trial and error

It's not too great a leap to realize that the distance itself doesn't matter, so let's say he decided to let it be 50 km. Then the speed of woman $A$ is $\dfrac{50}{x+4}$. The speed of woman $B$ is $\dfrac{50}{x+9}$. We know that the ratio of their speed must be $\dfrac{x}{9}$ based on how long it took both women to walk the distance between $A$ and the meeting point. So $\dfrac{\dfrac{50}{x+4}}{\dfrac{50}{x+9}} = \dfrac{9}{x}$ which after some basic manipulation simplifies also to $x^2=36$. When the $50$s cancel, he would see right away that his hunch about distance not mattering was correct.

The problem with this is that requires a $12$ year old to reason about kinematics (ratio of speeds from ratio of times, deriving speed from time and distance) without having the mathematical vocabulary for doing so. It also requires him to not be daunted by the ugly looking equations that come out. Last, it requires him to have a hunch about the distance, otherwise he has to use a variable to represent distance and at that point we are back at multivariate algebra.

This method also does not appear to have anything to do with scaling arguments, dimensional analysis, or toric variety theory, except perhaps in the slightest sense.

Conclusion

None of these options really satisfy me. For instance, I can't really imagine myself using any of these solutions when I was $12$. The only one I would have comprehended would be the straight trial and error, which I would have been too lazy to actually carry out. Though then again, I was never very good at math.

The problem seems to be a simple linear equation system, so I don't see what it has to do with the concepts he refers to. Perhaps he was making a metaphorical point about how this sort of problem is the "tip of the iceberg" of linear algebra that children first get exposed to? Or perhaps he actually figured out linear equations over the course of that day, and that was the revelation?

Arnold said his solution was based on what  are “now called scaling arguments” and “came as a revelation.”
Did Arnold draw something like this?straight line with points A, P and P creating "fractions" t over 9 and 4 over t

Since the women (lets call them Ekaterina and Yelena) are walking at constant velocity v_Y=k v_E. Rearranging, v_Y/v_E =k.  Then from the diagram, or otherwise, t/9=4/t  . Hence t^2=36 and t = 6.   Sunrise occurs 6 hours before noon, that is  06.00 or 6 am. (Actually I have omitted one step (AP/t)/(AP/9)=(PB/4)/(PB/t), but this seems trivial.)


Finding the difference in dimension for Null Spaces We have $N(A + vv^T) = N(A) ∩ N(vv^T)$ where $N$ represents the null space. A is a symmetric positive semidefinite matrix. We know that $\mathrm{dim}(R(vv^T)) = 1$, and therefore $\mathrm{dim}(N(vv^T)) = n-1$. However, does anyone know why $\mathrm{dim}(N (A + vv^T
)) ≥ \mathrm{dim}(N (A)) − 1$ is true based on the facts given?

Given , $N(A+vv^{T})=N(A)∩N(vv^{T})$
And, $dim(N(vv^{T}))=n-1$
$dim(N(A+vv^{T}))=dim(N(A)∩N(vv^{T}))=dim(N(A))+dim(N(vv^{T}))-dim(N(A)+N(vv^{T}))$
$\implies dim(N(A+vv^{T}))= dim(N(A))+(n-1)-dim(N(A)+N(vv^{T}))$
$\implies dim(N(A+vv^{T}))= dim(N(A))-1+(n-dim(N(A)+N(vv^{T})))$
Now, since , $N(A) $ and $N(vv^{T})$ are subspaces of some space $\mathbb{F}^{n}$ of dimension $n$.
So, $N(A)+N(vv^{T})$ is also subspace of $\mathbb{F}^{n}$.
Hence, $dim(N(A)+N(vv^{T}))\le n $
So, $dim(N(A+vv^{T}))\ge dim(N(A))-1$

Update
Actually the statement is true even without $N(A + vv^T) = N(A)$ $\cap$ $N(vv^T)$ or symmetric positive semidefiniteness as the following proof demonstrates. In fact this easily follows form A learner's answer because while they prove $dim(N(A)$ $\cap$ $N(vv^T))\geq ndim(N(A))-1$, we know that $$N(A) \cap N(vv^T) \subseteq N(A + vv^T)$$

Example
As an example suppose $v=e_5=\begin{bmatrix}0\\0\\0\\0\\1\end{bmatrix}$, and $A=\begin{bmatrix}1&0&0&0&0\\1&0&0&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\end{bmatrix}$
then $N(vv^T):=span(e_1, e_2, e_3, e_4)$, $N(A):=span(e_4, e_5)$ and $N(A+vv^T):=span\left(e_4, \begin{bmatrix}0\\0\\1\\0\\-1\end{bmatrix}\right)$
which is not the intersection of the first two and yet $dim(N(A+vv^T))=2\geq 1=dim(N(A))-1$.

This is a prescriptive proof. We will find an orthonormal basis $B$ of $N(A + \mathbf{v}\mathbf{v}^T)$ with $|B|\geq dim(N(A))-1$
Let $k=dim(N (A))$. Let an orthonormal basis of the $N(A)$ be denoted by the set $\{a_1, a_2, a_3...a_{k}\}$. Firstly, if $\mathbf{v}\cdot a_i=0$ for all $a_i$, $B:=\{a_1, a_2, ..., a_k\}$ and $|B|=k$. Let us assume this is not so.
Then the following vector is non-zero: $$\mathbf{v_{\parallel}}=\sum\limits_{i=1}^{k}(\mathbf{v}\cdot a_i)\,a_i$$
Notice that $\mathbf{v_{\perp}} = \mathbf{v}-\mathbf{v_{\parallel}}$ is such that for all $a_i$, we have $\mathbf{v_{\perp}}\cdot a_i=0$.
Now the set $\{a_1, a_2, a_3...a_{k}, \mathbf{v_{\parallel}}\}$ is clearly linearly dependant but spans a subspace of dimension only $k$. We now drop any one of the $a_i$s, where $\mathbf{v}\cdot a_i\neq 0$, say $a_1$ was one such vector. Now we do a Gram Schmidt orthogonalization on $\{a_2, a_3...a_{k}, \mathbf{v_{\parallel}}\}$ to get a basis with $\mathbf{v_{\parallel}}$ in it. Consider the vectors in this new basis other than $\mathbf{v_{\parallel}}$, let's say $\{a'_1, a'_2, a'_3...a'_{k-1}\}$. Now each $a'_j$ is in $N(A)$ because $a'_j$ must be in the span of $\{a_2, a_3..., a_{k}, \mathbf{v_{\parallel}}\}$ and thus in the span of $\{a_1, a_2, a_3...a_{k}\}$. But since $a'_j\cdot\mathbf{v_{\parallel}}=0$, notice that $a'_j\cdot\mathbf{v} = a'_j\cdot(\mathbf{v_{\parallel}}+\mathbf{v_{\perp}}) = a'_j\cdot\mathbf{v_{\perp}}=0$. The last equality is true because $a'_j$ is in the span of $\{a_1, a_2, a_3...a_{k}\}$ and as we noted, $\mathbf{v_{\perp}}\cdot a_i=0$ for each $a_i$. These thus constitute $B$ and $|B|=k-1$


Just do the integrals in order. For example,
$$\int_0^1 f(x, y) d x = \frac{-1}{1+y^2},$$ and integrating the RHS with respect to $y$ should be easy peasy.

The other integral is almost identical.

Let's take the first case
$$ \int_0^1dx $$ evaluated to $1$
and
 $$ \int_0^1f(x,y)dy $$ evaluated at $x$ as constant.

And to get the result, multiply the two above.


What is an "indecomposable" matrix? What is an indecomposable matrix? I tried to find what it is, but Wikipedia does not have an entry for it. Also, what properties does such matrix have?

See this entry in Planet Math: Fully Indecomposable Matrix.

See also Special matrices: scroll to "Decomposable". You'll find what it means to be decomposable, partly decomposable, and fully indecomposable.

Note: The term irreducible is usually used instead of indecomposable.

Wikipedia: "...a matrix is irreducible if it is not similar via a permutation to a block upper triangular matrix (that has more than one block of positive size)." (Replacing non-zero entries in the matrix by one, and viewing the matrix as the adjacency matrix of a directed graph, the matrix is irreducible if and only if the digraph is irreducible.)

PlanetMath: reducible matrix "An $n\times n$ matrix $A$ is said to be a reducible matrix *if and only if* for some permutation matrix $P$, the matrix $P^TAP$ is block upper triangular matrix." If a square matrix is not reducible, it is said to be an irreducible matrix.

An irreducible matrix has a corresponding graph which is strongly connected. On the other hand, an indecomposable matrix has a corresponding graph which has a directed spanning tree. So irreducibility is a stronger condition than indecomposibility.


If $\cos A = \sin B$ , does $A+B = 90$ degrees? If $\cos A = \sin B$ , does $A+B = 90$ degrees?

My school teacher says that this works but I was unable to understand how. I have been unable to find a proof for this. How does this work?

Edit I should add that this is for an acute case

Sometimes a picture says more than 1000 words:

But this isn't the only solution.
$$\cos A=\sin(A+pi/2)=\sin B \implies B=A+\pi/2 +2k\pi$$
for $k=0$, $B=A+\pi/2  \iff B-A= \pi/2$.


PMF function: joint pmf question For the PMF of $X$
$$P(X = x) = (0.5)^x \;\text{ for }\;x\in\mathbb{Z}^+,$$

would the PMF of $Y= X-1$ just be

$$P(Y = x) = (0.5)^{x-1}.$$

if X is a continus random variable whith PMF f that f(x) > 0 for all x, supose that y=H(x) be a function strictly monotonous, so the PMF Y=H(x) is:
$$
g(y) = f(x)|\frac{\mathrm{d}x}{\mathrm{d}y}|
$$
Solving the question...
$$
\\ g(y)=x-1\\ x = y+1\\\frac{\mathrm{d}x}{\mathrm{d}y}=1\\g(y)=0.5^{y+1}
$$


Why do Fourier Series work? I would like to have an intuitive understanding of Fourier Series. I mean, I know the formulas:
$$
f(t) =\frac{a_0}{2}+\sum_{n=1}^\infty a_n\cos(n\pi tL)+\sum_{n=1}^\infty b_n \sin(n\pi tL)
$$
And given a Wave, I know how to do the calculations, however, I have no idea why this formula works besides the fact it sums an infinity of sines and cosines.

How did Fourier arrive at this formula? And what's it meaning? I would be thankful if one could give me a brief explanation or point me reference material.

Thanks in advance

$\newcommand{\Vector}[1]{\mathbf{#1}}\newcommand{\vece}{\Vector{e}}$The linked questions provide good answers, but may be at the technical end of "intuitive". Here's a fast-and-loose conceptual motivation:

If $\bigl(V, \langle\ ,\ \rangle\bigr)$ is an $N$-dimensional real inner product space, and if $\{\vece_{n}\}_{n=1}^{N}$ is an (ordered) orthonormal basis, then an arbitrary vector $v$ in $V$ may be written as a linear combination
$$
v = \sum_{n=1}^{N} \langle v, \vece_{n}\rangle \vece_{n}.
\tag{1}
$$
Indeed, $\{\vece_{n}\}$ is a basis of $V$, so there exist real coefficients $a_{k}$ such that
$$
v = \sum_{k=1}^{N} a_{k} \vece_{k}.
\tag{2}
$$
Taking the inner product of each side with $\vece_{n}$ gives
$\langle v, \vece_{n}\rangle = a_{n}$ because the basis $\{\vece_{n}\}$ is orthonormal.

Loosely, one might expect a similar conclusion to hold if $V$ is infinite-dimensional. Getting the definitions and hypotheses right, and proving a version of (1) in this new setting, is why any "honest" answer is bound to be technical. Phrases in quotes below are not mathematically correct, and therefore require careful inspection and/or justification.

Intuitively, let $L > 0$ be real, let $V$ be "the space of real-valued functions" on $[-L, L]$, and define an "inner product" by
$$
\langle f, g\rangle = \frac{1}{L} \int_{-L}^{L} f(t) g(t)\, dt.
$$
The functions
$$
C_{n}(t) = \begin{cases}
1/\sqrt{2}, & n = 0, \\
\cos(n\pi t/L), & n > 0;
\end{cases}\qquad
S_{n}(t) = \sin(n\pi t/L),\quad n > 0;
$$
turn out (by elementary calculus and trigonometry) to form an "orthonormal basis" of $V$.

Loosely, we expect that if $f$ is a function, we can express $f$ as an infinite sum of these basis functions, and the coefficients are the inner products of $f$ with the basis elements, i.e. (for $n > 0$),
\begin{align*}
a_{0} &= \langle f, 1\rangle = \frac{1}{L} \int_{-L}^{L} f(t)\, dt, \\
a_{n} &= \langle f, C_{n}\rangle = \frac{1}{L} \int_{-L}^{L} f(t) \cos(n\pi t/L)\, dt, \\
b_{n} &= \langle f, S_{n}\rangle = \frac{1}{L} \int_{-L}^{L} f(t) \sin(n\pi t/L)\, dt, \\
f(t) &= \frac{a_{0}}{2} + \sum_{n=1}^{\infty} (a_{n} C_{n}(t) + b_{n} S_{n}(t), \\
  &= \frac{a_{0}}{2} + \sum_{n=1}^{\infty} a_{n} \cos(n\pi t/L) + b_{n} \sin(n\pi t/L).
\end{align*}
(The "special" factor of $1/2$ on the constant term arises because $C_{0} = 1/\sqrt{2} \neq 1$.)

Fourier was looking at guitar strings. He reasoned that the waveform (of the string) changes with time and the amplitude at the ends are allways zero. He intuitively reasoned that any waveform of the strings can be represented as a weighted sum of sine/cosine waves that can fit into the guitar by having zero amplitude at the ends (i.e. the harmonics). He then proposed that by removing the restriction that the amplitude must be zero at the ends, any continuous function can be represented as a sum of sine/cosine waves (waves with different wavelengths/frequencies).


Trigonometric identities from differential equation If one knows that the solutions of $y''+ y=0$ are two functions $s(x)$ and $c(x)$, and we know that $s(0)=0$, $s'(0)=1$, $c(0)=1$, $c'(0)=0$, then how can one start to prove that $s(x+a)=s(x)c(a)+c(x)s(a)$? What is it that has to be observed in order for one to understand how to initiate the proof?

One is not supposed to use the actual trigonometric functions in this case. Here we assume that we know nothing about sin and cos.

Here's a hint: You can use the Existence and Uniqueness theorem for linear differential equations to prove many different identities.

If you need to prove an identity $y_1(x)=y_2(x)$, first prove that both $y_1(x)$ and $y_2(x)$ are solutions to the provided differential equation. Then show that $y_1(a)=y_2(a)$ and $y_1'(a)=y_2'(a)$ for a value $a$ by using the initial conditions. Because there can only be one such solution, $y_1(x)$ must equal $y_2(x)$.

You'll want to use this approach to first prove $s'(x) = c(x)$ and $c'(x) = -s(x)$ which will allow you to differentiate each side of the identity when you need it. Then you can use the same approach to prove $s(x+a)=s(x)c(a)+c(x)s(a)$.

We use the following Theorem: [Page 82 of  Simmons Differential Equations with Applications and Historical Notes]  If P(x), Q(x), and R(x) be continuous functions on a closed interval [a,b].  If x0 is any point in [a. b], and if y0 and y0' are any numbers whatever, then equation y"+P(x) y'+ Q(x)y=R(x) has one and only one solution y(x) on the entire interval such that y(x0)=y0, and y'(x0)=y0'.

Y1=**s(x+a) is a solution of y"+y=0.
**Y2=**s(x)c(a)+c(x)s(a) is also a solution of y"+y=0.
Also, Y1(0)=s(a) and Y2(0)=s(a).  Y1'(0)=s'(x+a)|x=0=s'(0)=1
 and Y2'(0)=s'(x)c(a)+c'(x)s(a)|x=0  =  1.  **Hence by Theorem Y1=Y2.


Pushforward measure integral property Let $\mu$ be a Borel measure on $X$ and $T: X \rightarrow Y$ a Borel map ($Y$ topological space). I define $$ T _* \mu(E) = \mu(T^{-1}(E))  \qquad \forall E \subset Y \quad \text{Borel} $$
It is easy to prove that $T_* \mu$ is a measure on $Y$. But why, if $f : Y \rightarrow \mathbb{R}$ is $L^1(T_* \mu)$,
$$ \int_Y f \ d T_* \mu = \int_X f \circ T \ d \mu$$

First consider $f=1_E$ for some Borel set $E \subseteq Y$. Note that $$1_{T^{-1}(E)}(x)= 1 \Leftrightarrow x \in T^{-1}(E) \Leftrightarrow T(x) \in E \Leftrightarrow 1_{E}(T(x))=1 \tag{1} $$
Thus $$\int_Y f \, dT_{\ast} \mu = T_{\ast} \mu(E) \stackrel{\text{def}}{=} \mu(T^{-1}(E)) = \int 1_{T^{-1}(E)}(x) \, d\mu(x) \\ \stackrel{(1)}{=} \int 1_E (T(x)) \, d\mu(x) = \int_X f \circ T \, d\mu$$ so the assertion holds for all $f$ of the form $f=1_E$.
By linearity, we conclude $$\int_Y f \, dT_{\ast} \mu = \int_X f \circ T \, d\mu \tag{2}$$ for all $$f = \sum_{j=1}^n c_j \cdot 1_{E_j}$$ for some $n \in \mathbb{N}$, $c_j \in \mathbb{R}$, $E_j \subseteq Y$ Borel. This means that the formula holds for all simple functions.
Let $f \in L^1(T_{\ast} \mu)$ such that $f \geq 0$. Then there exists a sequence $(f_n)_n$ of simple functions such that $f = \sup_n f_n$. Thus, we obtain by monotone convergence $$\int f \, dT_{\ast} \mu = \sup_n \int f_n \, dT_{\ast} \mu = \sup_n \int f_n \circ T \, d\mu = \int f \circ T \, d\mu$$
For arbritrary $f \in L^1(T_{\ast} \mu)$, we write $f$ as a sum, $f = f^+ - f^-$ where $f^+, f^- \geq 0$ and $f^-, f^+ \in L^1(T_{\ast} \mu)$. By 3. the assertion holds for $f^-$ and $f^+$, so the assertion follows easily for $f$ using the linearity of the integral.

It is true for the characteristic functions, so it is true for any measurable function.


Prove that ${n^5 - n}$ is divisible by 5 I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it.

I am trying to prove it for several hours now, I started with ${n^5 - n} \mod  5 = 0$ but then I realized that I have no idea how to use modulo for transformations.

The next thing I tried was $(5 + n)\frac{n^5 - n}5 = \frac{(n+1)^5 - n+1}5$ but it didn't get me anywhere.

How would you do it?

Let $\displaystyle f(n): n^5-n$ is divisible by $5$ holds true for $n=m$

$\displaystyle\implies 5\mid(m^5-m)$

Now, $\displaystyle f(m+1)-f(m)=(m+1)^5-(m+1)-(m^5-m)=\sum_{1\le r \le 4}\binom5 rm^r$ which is divisible by $5$

as each $\displaystyle\binom5r,1\le r\le4$ is divisible by $5$

Finally, establish the base case i.e., $n=1$

Generalization :

More generally prime $p$ divides $\displaystyle\binom pr$ (can you prove this?) for $1\le r\le p$ or more genrally $p\not\mid r$

So, we can prove  $\displaystyle n^p-n$ will be divisible by $p$ (Fermat's Little Theorem)

I would like to give you a more simple approach to this question:
=>n^5-n is given to you.
So, on taking n common n(n^4-1) is you got.
so this expression has to be divisible by 5 the multiplication of both n and n^4-1 have to divisible by 5. And, Clearly for each number we have n^4-1 have to be divisible by 5.
Now, calling the number
Any number which has even in unit's place like 2,4,6,8
2^4=6
4^4=6
6^6=6
8^6=6
Any number which have even number in unit's place is leading to in 6 and subtracting 1 we got 5 so each expression is divided by 5
And, similarly for odd numbers
1^4=1
3^4=1
7^4=1
9^4=1
And, subtracting 1 from we got 0 so it is again divisible by 5.
And, when we have 5 at unit's place n is divisible by 5.
Sorry , for the poor presentable form, but I think this will work


Increasing Function bounded below by a polynomious Suppose $g:[0,\infty)\rightarrow [0,\infty)$ is a cotinuous increasing function with $g(0)=0$. Is it possible to find two constants $C>0$ and $q>0$ such that $$g(s)\geq Cs^q,\ \forall\ s\in [0,\delta)$$

where $\delta>0$ is an small number.

Thank you.

Edit: Sorry, I forgot one hypothesis.

This is still not true. Recall the classical example of a smooth non-zero function with all Taylor coefficients vanishing at 0 (you can construct it with $e^{-1/x}$ for $x>0$ and 0 otherwise).

The Taylor Young theorem says that you won't be able to find such constants for that function.

No,. this need not be true. One simple way it could fail is if $g$ is bounded (since $Cs^q$ is unbounded). So for example $g(s)=\arctan(s)$ is a counterexample.


why do we use $\pi \cdot d/2+d$ for semicircles I'm in grade seven and right now we are learning perimeter of a semicircle, and I noticed we use the formula $\pi\cdot D/2+D$ (where $D$ is the diameter) instead of $(\pi+2)D/2$, why do we do the first formula instead of the second, where they both have the same answer?

You can use either formula as they are identical, as you've noted.  A reason for preferring the first is that it makes the perimeter calculation explicit: $\pi\cdot D/2$ is the length of the curve, and $+D$ then adds on the straight line across the bottom.

The results are the same:
$$\left( \pi + 2 \right) D/2 = \pi D/2 + D.$$
The perimeter of a circle of radius $r$ is $2 \pi r$. Since the diameter, $D$, is twice the radius, $D = 2 r$ this gives the perimeter of a circle as $\pi D$. It follows that the perimeter for a semi (half) circle is $\pi D/2$. Now just add the remaining length $D$ of the line joining the two ends of the semi circle.

Since the results are the same which one you use is simply your preference. Personally, I prefer the second form since it makes clear the contributions from each part of the curve (the semi-circle versus the straight line segment).


Can anyone explain the convolution of independent random variables? Specifically, suppose that $X_1$ and $X_2$ are independent and $f$ is a Borel-measurable function s.t. $f(x_1, x_2)=\begin{cases}
1, & \text{if } x_1+x_2 \leq x\\
0, & \text{otherwise}
\end{cases}$ and $\mu$ is a product measure for $X_1$ and $X_2$.

Why do the following steps hold?

\begin{align}
\int_\Omega f(X_1,X_2)\,d\mathscr P & = \iint\limits_{\mathscr R^2} f(x_1,x_2) \, \mu^2(dx_1,dx_2) \\[6pt]
& = \int_{\mathscr R^1} \mu_2(dx_2) \int_{\mathscr R^1} f(x_1,x_2)\,\mu_1(dx_1) \\[6pt]
& = \int_{\mathscr R^1} \mu_2(dx_2) \int_{(-\infty,x-x_2]} \mu_1(dx_1) \\[6pt]
& = \int_{-\infty}^\infty dF_2(x_2) F_1(x-x_2).
\end{align}

The first step is probably the hardest.  It's the "change of variables" theorem of measure theory.  If $f \in L^{1}(\Omega)$, then
\begin{equation}
\int_{\Omega} f(X_{1}(\omega),X_{2}(\omega)) \, \mathbb{P}(d\omega) = \int_{\mathbb{R}^{2}} f(x_{1},x_{2}) \, \mu^{2}(x_{1},x_{2}).
\end{equation}  Here $\mu^{2}$ is the measure you obtain when you "pushforward" $\mathbb{P}$ by $(X_{1},X_{2})$, which is a fancy way of saying $$\mu^{2}(A) = \mathbb{P}\{\omega \, \mid \, (X_{1}(\omega),X_{2}(\omega)) \in A\}$$ whenever $A \subseteq \mathbb{R}^{2}$.  Alternatively, if you're familiar with distribution functions, then $\mu^{2}$ is the measure corresponding to the distribution function of $(X_{1},X_{2})$.  Either way, if you're not familiar with the change of variables theorem, say so and I'm sure people on here can help out.

The rest is simpler.  We know
\begin{align*}
\mu^{2}(A_{1} \times A_{2}) &= \mathbb{P}\{\omega \, \mid \, X_{1}(\omega) \in A_{1}, \, \, X_{2}(\omega) \in A_{2}\} \\
&= \mathbb{P}\{X_{1} \in A_{1}\} \mathbb{P}\{X_{2} \in A_{2}\} \\
&= \mu_{1}(A_{1}) \mu_{2}(A_{2})
\end{align*} by independence.  (I dropped some $\omega$'s to eliminate unnecessary symbology.)  It follows by e.g. the Hahn-Caratheodory theorem that $\mu^{2}$ is the product of $\mu_{1}$ and $\mu_{2}$.  In particular, in the integral sign, we can replace $\mu^{2}(dx_{1},dx_{2})$ with $\mu_{1}(dx_{1}) \mu_{2}(dx_{2})$.

Finally, applying Fubini's theorem (which is no problem since $f$ here is non-negative),
\begin{align*}
\int_{\Omega} f(X_{1}(\omega),X_{2}(\omega)) \, \mathbb{P}(d \omega) &= \int_{\mathbb{R}^{2}} f(x_{1},x_{2}) \, \mu_{1}(dx_{1}) \mu_{2}(dx_{2}) \\
&= \int_{-\infty}^{\infty} \left(\int_{-\infty}^{\infty} \mathbf{1}_{\{x_{1} + x_{2} \leq x\}} \mu_{1}(dx_{1})\right) \mu_{2}(dx_{2}) \\
&= \int_{-\infty}^{\infty} \left(\int_{-\infty}^{x - x_{2}} \mu_{1}(dx_{1})\right)\mu_{2}(dx_{2}) \\
&= \int_{-\infty}^{\infty} F_{1}(x - x_{2}) \mu_{2}(dx_{2}).
\end{align*}
(I replaced $f$ with the fancy $\mathbf{1}$ to help us figure out what the bounds of integration should be.)  Here I used the fact that $F_{1}$ is the distribution function of $\mu_{1}$, which just means $$F_{1}(y) = \mu_{1}(-\infty,y] = \int_{-\infty}^{y} \mu_{1}(dx_{1}).$$  Finally, we can replace $\mu_{2}(dx_{2})$ with $dF_{2}(x_{2})$ (or I would prefer $F_{2}(dx_{2})$), but either way it's just notational.  This is just the inverse of what I wrote above; it goes back to the correspondence between distribution functions and probability measures (on $\mathbb{R}$).

Recall conditional expectation:
$$E(X) = E(E(X\mid\theta))$$

Condition on the value of $x_2$ (the last equality follows from independence):
$$P(x_1 + x_2 < a) = P(x_1 < a - t : x_2 = t) P(x_2 = t) = P(x_1 < a - t) P(x_2 = t)$$
Now take expectation over $x_2$ to get rid of $t$ and you get
$$P(x_1 + x_2 < a) = \int_R F_1(a-x_2)dF_2(x_2).$$

Intuitively, for any value of $x_2=t$ the probabilty is the product of $F(t)$ and $F(x-t)$ and we need to take the average (probability-weighted) over all possible values of $t$.


Expectation of Continuous variable. Given the probability density function

$$
f(x) =
\begin{cases}
\frac{cx}{3}, &  0 \leq x < 3, \\
c, & 3 \leq x \leq 4, \\
0 & \text{ otherwise}
\end{cases}
$$

I have found $c$ to be $0.4$ and $E(X)$ to be $2.6$. But I'm being asked to find $E(3X - 5)$ and I'm unsure of what to do.


Shapley values as a hash/compression of a game Computing a Shapley value, we are mapping the set of coalition games on $N$ to a vector of $N$ elements:

$$ \phi: \; \mathbb{R^{2^N}} \to \mathbb{R}^N $$

In a sense, this is compression, or more precisely hashing (since compression is often thought of as being a lossless injection).

What does the inverse direction look like? What do two games $v$ and $w$ that have Shapley values ($\phi(v)=\phi(w)$) have in common?

If we parametrized games with $N$ parameters, what would the relationship between these $N$ parameters and the $N$ Shapley values be? That is, if we have a function

$$ \rho: \; \mathbb{R}^N \to \mathbb{R^{2^N}} $$

whereby, for any $x \in \mathbb{R}^N$ we get a coalition game $\rho(x)$, then what would the Shapley values $\phi(\rho(x))$ of the latter be? More specifically, what would the relationship between $\phi(\rho(x))$ and $x$ be?

Examples of parametrized coalition games $\rho$: The "sum game" or the "product game", where the value of a coalition is the sum (resp. product) of the values (parameters) of the members of the coalition.

First of all I think that there is a fundamental misunderstanding of the meaning or reflection of the Shapley value. The Shapley value does not reflect a hash or compression of a TU-game. It reflects inter alia the bargaining power of the players involved in a fictitious bargaining process in accordance with a set of objective principles. Subjects involved can form different coalitions which have some bargaining power to assure to its members a certain payoff. This is reflected by the coalition value $v(S)$. The distributive rule of the overall profit in accordance with the Shapley value captures the intrinsic bargaining power of the players represented by the coalition values. This means, the Shapley value is a solution concept of a TU-game, i.e., an outcome of a coalitional bargaining game.

Moreover, the Shapley value refers to nondiscriminatory and upright standards that even apply in situation with unequal partners. These standards define objective principles on which subjects can agree or disagree. This set of objective principles determines a fair division of the profits among subjects. This means, the Shapley value relies on an axiomatic foundation on which subjects can obey. The axiomatic characterization of the Shapley value as given by Shapley (1953) is as follows: Efficiency, Symmetry, Dummy Player and Additivity (see a textbook for the exact definitions). Thus, if a set of subjects agree to obey the distributive rule given by this axiomatization, then the total profit must be distributed in accordance with the Shapley value. However, in case that a subject proposes a different distribution of the profit, then this proposal is vulnerable in the sense that it does not reflect the agreed upon rule of arbitration. From this consideration it should be obvious that it is not necessarily required that an agreement on a rule of distributive justice needs to be binding (cf. Chapter 3-4 of my book http://www.springer.com/us/book/9783642395482).

From the preceding discussion, it should also be obvious that $\phi$ is not a bijective mapping, and that $\rho$ is not the inverse of $\phi$. Thus, we do not have a particular inverse direction for $\phi$. As a consequence, we can only observe a tight relationship between $\phi(\rho(x))$ and $x$, if the game is, for instance, additive. Then we have $\phi(\rho(x)) = x$. As an example let us consider the vector $x=\{3,7,2,5\}$, the corresponding additive game is (lexi-order)

$$ v=[3,7,2,5,10,5,8,9,12,7,12,15,10,14,17], $$

and the Shapley value of this game is again the vector $x=\{3,7,2,5\}$.

In addition, if we have a game $v$, then we can decompose it by a linear basis approach into a flat game $z$ and an additive game $w$, s.t. $v=z+w$. The Shapley value of game $v$ can be decomposed by $\phi(v)=\phi(z+w)=\phi(w)$, thus $\phi(z)=\mathbf{0}$. Let us consider as an example the following convex game (lexi-order)

$$ v=[0,0,0,0,0,0,0,0,0,0,0,3,0,2,5],$$

the Shapley value of this game is given by $\phi(v)=\{1,5/3,2/3,5/3\}$.

The linear decomposition of $v$ produces a flat game given by

$$ z=[-1,-5/3,-2/3,-5/3,-8/3,-5/3,-8/3,-7/3,-10/3,-7/3,-10/3,-4/3,
-10/3,-2,0], $$

where the Shapley value is given by $\phi(z)=\mathbf{0}$, and an additive game

$$ w=[1,5/3,2/3,5/3,8/3,5/3,8/3,7/3,10/3,7/3,10/3,13/3,10/3,4,5], $$

with a Shapley value of $\phi(w)=\{1,5/3,2/3,5/3\}$, hence $\phi(v)=\phi(w)$. Therefore, in both games the bargaining power of the players is similar in accordance with the rule of arbitration represented by Shapley value, and distributes the profit for both games in the same way. However, note that this is not the case for the pre-nucleolus. There we obtain $\nu(v)=\{4/3,4/3,1,4/3\}, \nu(z)=\{1/3,1/3,1/3,-1/3 \}$, and $\nu(w)=\{1,5/3,2/3,5/3\}$ respectively.


Convergence of $\sum\limits_{n=0}^{\infty}\frac{n^3+n^4}{2^{n+1}}$ Does $\sum\limits_{n=0}^{\infty}\frac{n^3+n^4}{2^{n+1}}$ converges (absolute)?

I've already tried the Ratio test and the Root test test, but they failed both...

Hint:
For each c>0, there exists $n_0$ s.t. if $n>n_0$ then $n>c\log(n)$ (by calculate the limit of $log(n)/n$) , then for $c=10$
you gets $2^\frac{n}{2}>n^5$, and by sum of geometric sequence you gets $n^5>n^4+n^3$ then...

Now, you can use comparison.


Product of a geometric series from it's middle term If the $5$-th term of the G.P is its middle term and its value is 2,then find the product of all terms of this GP?

My approach:

Since $a_5$ is the middle term, so the GP contains 9 terms.

$$P_9 = a\cdot ar\cdot ar^2 \cdot ar^3 \cdot 2\cdot ar^5 \cdots ar^8$$

which leaves us $P_9 = 2\cdot (ar^4)^8$ ... I am not getting how to proceed further? Is this approach even correct?

The fourth term is $2/r$ and the sixth term is $2r$.  What happens when you multiply these?  What about the third and seventh terms?

The fifth term is the middle term which means there are $4$ terms to the either side of the middle term (a total of $9$ terms). Thus the product of the terms of the GP is $2^9=512$.


Definition of monomial I thought the definition of a monomial is an algebraic term that has no subtraction or addition. I saw on my online college homework that 2/x is not a monomial. Why?

As @Fundamental pointed out in a comment, your definition of monomial is wrong. See Wikipedia for a better definition.

Or here is a simpler definition. A monomial is a constant, a variable, or the product of constants and/or variables.

Details: The monomial is usually simplified to place the constant, if any, first, and to combine multiple copies of the same variable into a positive integral power of the variable. The variables are also usually written in alphabetical order.

Your expression $2/x$ does not meet my definition or Wikipedia's, so it is not a monomial.


An exercise about convergence of series Possible Duplicate:
  Convergence/divergence of $\sum\frac{a_n}{1+na_n}$ when $\sum a_n$ diverges.

Let $a_n$ be a non-negative sequence such that the series $\sum a_n$ does not converge. Could the series $\sum a_n/(1+na_n)$ be convergent?

Hint: Try $a_n=1$ if $n$ is a power of $2$ and $0$ otherwise.

If $\sum a_n = \infty$, then there exist $n_0: n\ge n_0 \Rightarrow a_n \ge 1$. Hence,
\begin{equation}
\infty = \sum_{n\ge n_0} \dfrac{a_n}{a_n(n+1)} \le \sum_{ n \ge n_0}\dfrac{a_n}{(na_n+1)}.
\end{equation}
Then $\sum a_n/(1 + na_n)$ does not converge.

I messed up. My argument is if $\lim a_n=\infty$.


If $x$ and $y$ are odd, prime integers, then $xy+x+y$ is not necessarily a prime number? Prove the theorems:

1) If $x$ and $y$ are odd, prime integers, then $xy+x+y$ is not necessarily a prime number.

2) If $x$ is a positive odd integer, then $x^4$ can be written in the form $8m+1$ where $m$ is an integer. Hint: $x$ can be written in the form $8i+j$ where $j$ is one of $1$, $3$, $5$ or $7$.

Thanks in advance!!

For (1), find a counterexample. You shouldn't have to look too long.

For (2), use the hint. Note in particular that $$x^4=(8i+j)^4=(8i)^4+4(8i)^3j+6(8i)^2j^2+4(8i)j^3+j^4.$$ You can factor an $8$ out of every term except the $j^4$ term, which lets you rewrite it in the form $$x^4=8(\text{a bunch of stuff})+j^4.$$ If you can show for each $j=1,3,5,7$ that there is some $n$ such that $j^4=8n+1$ (prove by cases), then it follows that $$x^4=8(\text{a bunch of stuff}+n)+1,$$ which has the right form.

A better approach for (2)--that completely avoids the need for a case-by-case proof--is to note that $x=2k+1$ for some integer $k$. Then $$x^4=(2k+1)^4=(2k)^4+4(2k)^3+6(2k)^2j+4(2k)+1.$$ There ends up being a factor of $8$ in each term but the last, so we can rewrite it as $$x^4=8(\text{different stuff})+1$$ right away.

For number 1, I see nothing saying $x$ and $y$ need to be distinct.  In this case, the number can be rewritten as $x(x+2)$.  Finding a counterexample is a little more complicated if $x$ and $y$ must be distinct.  Since $x$ and $y$ are odd, $x+1$ and $y+1$ are even, $(x+1)(y+1)$ is divisible by 4, and $xy+x+y=(x+1)(y+1)-1\equiv 3\pmod4$.  Checking composite numbers congruent to 3 mod 4, the first counterexample I can find is

$$55=5\times11=(3+1)(13+1)-1$$


Probability of B and C happening at least once, in five independent trials. I am performing a product trial. The trial has three possible outcomes with the following probabilities:

Outcome A = .3

Outcome B = .5

Outcome C = .2

If I perform five trials, what are the odds of B and C occurring at least once throughout testing?

The complement of this event is that only $A$ and $C$ occur or only $A$ and $B$ occur. The probabilities for those are $(.3+.2)^5=.5^5$ and $(.3+.5)^5=.8^5$, respectively. However, adding these two double-counts the possibility that only $A$ occurs, so we have to subtract $.3^5$, for a total of

$$
.5^5+.8^5-.3^5=0.3565\;.
$$

Thus the probability of your event is $1-0.3565=0.6435$.

This is the complement of the probability that all five are outcome A.  Assuming independence this complement is 1 - .3^5 = .99757

Sorry this is for B or C occurring at least once.  Please downvote more.


For what values of $x$ is $\cos x$ transcendental? For what values of $x$ is $\cos x$ transcendental? Is there any way I can figure out the values of $x$ where $\cos x$ is transcendental or do I have to check individually for every $x$ whether it is or not?

I'm not an expert on this, but I'm pretty sure this is not known in general.  Here are some partial results:

There are only countably many values of $x$ such that $\cos x$ is algebraic (because there are only countably many algebraic numbers and $\cos$ takes every value only countably many times).  So $\cos x$ is "almost always" transcendental in a rather strong sense.
If $x\neq 0$ is algebraic, then $\cos x$ is transcendental (this follows from the Lindemann-Weierstrass theorem).
If $x$ is a rational multiple of $\pi$, then $\cos x$ is algebraic (this is elementary and follows from the fact that $e^{ix}$ is a root of unity).  More generally, if $y$ is such that $\cos y$ is algebraic and $x/y$ is rational, then $\cos x$ is algebraic.
If $x$ is an algebraic irrational multiple of $\pi$, then $\cos x$ is transcendental (this follows from the Gelfond-Schneider theorem).  More generally, if $y$ is such that $\cos y$ is algebraic and $x/y$ is algebraic and irrational, then $\cos x$ is transcendental.

(Note that the general transcendence theorems tend to be stated in terms of exponentials; to translate them into results about cosines, you can use the fact that $\cos x$ is algebraic iff $e^{ix}$ is algebraic.)

Let $T \subset (-1,1)$ be the set of transcendental numbers in the interval $(-1,1)$. Then $\cos(x)$ is transcendental for all numbers $x$ belonging to the set $\arccos(T) = \{\arccos(t): t \in T\}$. To get all the elements in the set, we can add multiple of $\pi$ to all the elements in $\arccos(T)$.


if $f(x)-a\int_x^{x+1}f(t)~dt$ is constant, then $f(x)$ is constant or $f(x)=Ae^{bx}+B$ Question:

  let $a\in(0,1)$, and such $f(x)\geq0$, $x\in R$ is continuous on $R$,

  if
  $$f(x)-a\int_x^{x+1}f(t)dt,\forall x\in R $$ is constant,

  show that

  $f(x)$ is constant;

  or $$f(x)=Ae^{bx}+B$$ where $A\ge 0,|B|\le A$ and $A,B$ are constant, and the positive number  $b$ is such
  $\dfrac{b}{e^b-1}=a$

My try:

let $$f(x)-a\int_x^{x+1}f(t)dt=C$$
then we have
$$f'(x)-af(x+1)+af(x)=0,\forall x\in R$$

other idea:

let $$F(x)=\int_{0}^{x}f(x)dx$$
then
$$f(x)-a\int_x^{x+1}f(t)dt=F'(x)-a[F(x+1)-F(x)]=C$$
then I can't solve this ODE? maybe my idea is not good.

Thank you very much.

A very pretty problem! Under the hypotheses stated, we will conclude that
$f(x) = A e^{bx}+B$ with $A, B\ge0$. The amplitude of $B$ cannot be restricted.

Since $f$ is continuous, the integral is differentiable and by the OP's calculation,
$$
\frac{d}{dx}(e^{ax} f(x)) = e^{ax}(f'(x)+a f(x)) =  e^{ax} a f(x+1)\ .
$$
It follows $u(x)=e^{ax}f(x)$ is nonnegative and
satisfies
$$
u'(x) = c u(x+1) ,  \quad c=a e^{-a}.
$$
By a simple induction argument, $u$ is infinitely differentiable with
all derivatives nonnegative on $\mathbb R$.  Thus its reflection $v(x)=u(-x)$
is completely monotone,
meaning all its even derivatives are nonnegative and all its odd derivatives are nonpositive.

By Bernstein's theorem on completely monotone functions,
 there is a unique Borel measure $d\mu$ on $[0,\infty)$ such that
 $$
 v(x) = u(-x) = \int_0^\infty e^{-tx}\,d\mu(t)
 $$
 for all $x>0$.  But then, since $v'(x)=-u'(-x)=-c v(x-1)$, we find that for $x>1$,
 $$
 c v(x) = -v'(x+1) = \int_0^\infty e^{-tx} e^{-t}t\,d\mu(t).
 $$
 By uniqueness of the representing measure, $c\,d\mu(t)=te^{-t} d\mu(t)$
 as measures on $[0,\infty)$.  Hence $(c-te^{-t})d\mu(t)=0$, and
 the support of $d\mu$ must lie in the set of $t$ such that $c=te^{-t}$.

Since $t\mapsto te^{-t}$ increases on $(0,1)$
 and decreases on $(1,\infty)$, this set consists of two points:
 the number $a\in(0,1)$ and the unique
 $\hat a>1$ such that $ae^{-a}=\hat a e^{-\hat a}$.   Therefore $d\mu$ is a nonnegative combination of  delta masses at $a$ and $\hat a$:
 $$
 d\mu(t) = B\,\delta(t-a) + A\, \delta(t-\hat a)
 $$
 where $B, A\ge0$. Consequently, for all $x>1$,
$$
 v(x) = B e^{-ax} + A e^{-\hat a x} = e^{-ax}f(-x),
 $$
 hence $f(x) = B + A e^{bx}$ where $b=\hat a-a>0$ satisfies $a e^b = \hat a = b+a$
 as desired.

The argument above actually applies for any translate $v(x-k)$. Consequently the desired representation of $f$ holds for all $x$.

I need help proving the following result:

If $f(x)-a\int_x^{x+1}f(t)dt$ is constant, then $f(x)$ is constant or $f(x)=Ae^{bx}+B$.

Firstly, we transform this ODE to the form:
$$\frac{dy}{dx}+P(x)y=Q(x).$$

Such equation has the solution:
$$y=e^{-\int{Pdx}}$$[\int{Qe^{\int{Pdx}}+C}].$$

Then,we calculate this solution as the following way:
$$fe^{ax}=\int{Qe^{ax}dx+C}\implies(Ae^{bx}+B)e^{ax}=\int{Qe^{ax}dx+C}\implies Qe^{ax}=Aae^{b}e^{(a+b)x}+Bae^{ax}\implies Q=Aae^{b}e^{bx}+Ba.$$

Therefore,
$$f(x+1)=f^{'}(x)\frac{e^{b}}{b}+C\implies Q=f(x+1)$$
where
$Aae^{b}\ge0,$ $Ba\le{Aae^{b}}$.

From my point, this ODE has the solution of $f=Ae^{\lambda{x}}+B$ is obviously, the only thing we should prove is that $\lambda=b=a(e^{b}-1)$.


What is surjective comparability equivalent to? By surjective comparability I mean the following principle:

"For any nonempty sets $A,B$: there exists a surjective function $f$ from $A$ to $B$ or there exists a surjective function $g$ from $B$ to $A$."

Is this statement provable in $ZF$?
If not then what exactly that principle is equivalent to (over $ZF$)?

This principle (for nonempty sets, to avoid a trivial counterexample) is equivalent to the axiom of choice. One direction is in a previous answer. For the converse, let $X$ be an arbitrary set (which I want to well-order). Apply Hartogs's theorem to get an ordinal $\alpha$ so large that it cannot be mapped one-to-one into the power set $\mathcal P(X)$. Then $X$ cannot be mapped onto $\alpha$, because if $f:X\to\alpha$ were surjective then $\alpha\to \mathcal P(X):\beta\mapsto f^{-1}(\{\beta\})$ would map $\alpha$ one-to-one into $\mathcal P(X)$. So, by your principle, there is a surjection $g:\alpha\to X$. Then $X$ can be well-ordered by setting $x\prec y$ iff the first $\beta$ with $g(\beta)=x$ is smaller than the first $\beta$ with $g(\beta)=y$.

In ZFC you can well-order any set (in fact, this is equivalent to AC over ZF). Thus you can compare cardinalities of any two sets and then you have a surjection in (at least) one direction. In general, it is impossible to do this without AC.


Integer solutions to $a^{2}+b^{2}+c^{2} = d^{2}+e^{2}+f^{2}$, where $a, b, c, d, e, f \neq 0$ How does one approach something like this? Is there an equivalent Legendre's three-square theorem for the sum of three squares in two different ways?

It seems like the only way to approach it would be via some computer power.

There is a method to find the different primitive representations of an integer $n$ as the sum of three squares, see here. This gives solutions to the above equation. For example, we have $150$ different representations of $n=225=a^2+b^2+c^2$, and $96$ primitive ones among them. So we can choose each pair of these solutions to obtain
$$
a^2+b^2+c^2=n=d^2+e^2+f^2.
$$

When $ a = -d, b=-e, c=-f $ then it satisfies the equality.

Consider

$$ (-99)^2+(-100)^2+(-101)^2 = (99)^2+(100)^2+(101)^2 $$

Similarly

$$ (-d)^2+(-e)^2+(-f)^2= d^2+e^2+f^2 $$

Where $ a≠b≠c≠d≠e≠f$

So infinite integral solutions are possible. (Not positive integral).


Basis of a linear transformation If $V$ and $W$ are vectorial spaces of finite dimension, we denote $\mathscr{L}(V,W)$ like the set of all linear maps of $V$  in $W$. Let a linear map $L\in \mathscr{L}(\mathbb{R}^{2},\mathbb{R}^{2})$ defined like $L(x,y)=(-x+y,2x+y)$ for each $(x,y)\in \mathbb{R}^{2}$. Find a basis $S=\{u_{1},u_{2}\}$  of $\mathbb{R}^{2}$ such that
$$[L]_{S} := M_{L}^{S \rightarrow S}= \begin{pmatrix} 0 & -1 \\ -3 & 0 \end{pmatrix}$$
Where $M_{L}^{S \rightarrow T}$ denote the matricial representation of the linear map $L\in \mathscr{L}(V,W)$ respective to the basis $S$ of $V$ and $T$ of $W$.
Let $u_{1}=(v,w)$,$u_{2}=(a,b)\in \mathbb{R}^{2}$. We have that the columns in the matricial representation are $L(u_{1})$ and $L(u_{2})$, so
$$L_{u_{1}}=(-v+w,2v+w)= (0,-3)^{T}$$
and
$$L_{u_{2}}=(-a+b,2a+b)=(-1,0)^{T}$$
Then, $v=w=-1$,$a=\frac{1}{3}$ and $b=-\frac{2}{3}$. Am I right?

In your attempt you are forgetting that the columns of $[L]_S=M^{S\to S}_L$ are not the images of $u_1$ and $u_2$ but their coordinates with respect to $S$. Hence, the conditions on the basis $S=\{u_1, u_2\}$ given by $[L]_S$ should have been
\begin{align}
L(u_1) &= \phantom{-}0 u_1 - 3 u_2, \\
L(u_2) &= -1 u_1 + 0 u_2.
\end{align}
Setting $u_1=(v,w)^T$ and $u_2=(a,b)^T$ as you did, this translates to
\begin{align}
(-v+w,2v+w)^T &= (-3a, -3b)^T, \\
(-a+b,2a+b)^T &= (-v, -w)^T.
\end{align}
This is a homogeneous linear system of four equations and four variables:
\begin{align}
-v+w+3a\phantom{{}+3b} &= 0,\\
2v+w\phantom{{}+3a}+3b &= 0,\\
v\phantom{{}+w}-\phantom{3}a+\phantom{3}b &= 0,\\
w+2a+\phantom{3}b &= 0.
\end{align}
Row reduction yields that this is equivalent to
\begin{align}
v&=a-b,\\
w&=-2a-b.
\end{align}
In addition, $u_1$ and $u_2$ need to be linearly independent, which is equivalent to $vb-wa\neq 0$ and hence to $ab\neq 0$ (by substituting $v$ and $w$).
Picking $a=b=1$ we get $v=0$, $w=-3$ and indeed $u_1=(0,-3)^T$ and $u_2=(1,1)^T$ are linearly independent and yield
\begin{align}
L(u_1) &= L((\phantom{-}0,-3)^T) = (-3,-3)^T = -3 u_2, \\
L(u_2) &= L((\phantom{-}1,\phantom{-}1)^T) = (\phantom{-}0, \phantom{-}3)^T = -1 u_1.
\end{align}
Note that any other choice of non-zero $a,b$ also yields a valid solution.

Notice that the linear map L can be represented by the matrix $A=\left(\begin{matrix}-1&1\\2&1\end{matrix}\right)$ such that $L(x)=Ax$. Using your representation of $u_1=\left(\begin{matrix}v\\w\end{matrix}\right), u_2=\left(\begin{matrix}a\\b\end{matrix}\right)$ to be the new basis, the following equations are gotten:
$\left(\begin{matrix}[Au_1]_\beta&[Au_2]_\beta\end{matrix}\right)= \left(\begin{matrix}0&-1\\-3&0\end{matrix}\right)$, where $\beta$ represents the new basis
This means
$\begin{cases}Au_1=0u_1+-3u_2\\ Au_2=-1u_1+0u_2\end{cases}$
Further elaborating,
$\begin{cases}w-v=-3a\\2v+w=-3b\\b-a=-v\\2a+b=-w\end{cases}$
$v=a-b, w=-2a-b$
Further, as mentioned in Cristoph's post, the basis vectors must be linearly independent. $u_1\ne cu_2\implies \frac v a\ne \frac w b \text{ or } bv-wa\ne0$
Picking $a=b=1,v=0,w=-3$, is a valid basis. Note that this basis is neither orthogonal nor are the vectors normalized. If you attempt to normalize the vectors, the transformation will not work due to the contraints in the equations above.
It is possible, however, to find an orthogonal basis. $\left(\begin{matrix}\frac 1 2 (13+5\sqrt {13})\\\frac 1 2 (13-\sqrt {13})\end{matrix}\right), \left(\begin{matrix}\sqrt {13}\\\frac 1 2 (-13-3\sqrt {13})\end{matrix}\right)$ is one such possible orthogonal basis. It is not possible to find an orthonormal basis. In fact, it is not possible to find a normalized basis i.e. where both vectors have euclidean norm 1.

Test transformation in standard basis and new basis:
$\left(\begin{matrix}-1&1\\2&1\end{matrix}\right)\left(\begin{matrix}1\\-2\end{matrix}\right)=\left(\begin{matrix}-3\\0\end{matrix}\right)$
$\left(\begin{matrix}0&-1\\-3&0\end{matrix}\right)\left(\begin{matrix}1\\1\end{matrix}\right)_\beta=\left(\begin{matrix}-1\\-3\end{matrix}\right)_\beta$
$\left(\begin{matrix}-3\\0\end{matrix}\right)=\left[\left(\begin{matrix}-1\\-3\end{matrix}\right)_\beta\right]_{\{e_1,e_2\}}$


gradient descent with respect to a matrix I am trying to solve a maximize a scalar function f(X), where X is a matrix. I want to solve this using gradient descent, I have taken the derivative of f(X) w.r.t X. This seems a naive question, but does anyone know what to do next? Thanks so much!

Have you tried the naive answer that you can find in the wikipedia? http://en.wikipedia.org/wiki/Gradient_descent

Yes, I read that. I didn't want to mislead other people into the wrong solution. The thing is I'm not sure how to use it correctly, suppose X is an m by n matrix, the derivative of f(X) would be an n by m matrix. So should I take the transpose of the derivative first before using gradient methods? If so, why?