Basics on group operation Let's $G$ be a group and $H \le G$. $H$ brings a partition of $G$, $\lambda_H(G)=(H,\complement_GH$), where $\complement_GH:=G \setminus H$. Firstly, I notice that, as $g \in G \Leftrightarrow g^{-1} \in G$, then also $g \in \complement_GH \Leftrightarrow g^{-1} \in \complement_GH$.

Now, I claim that $g \in H, g' \in \complement_GH \Rightarrow gg' \in \complement_GH$. In fact, $gg' \in H \Rightarrow g'=g^{-1}(gg') \in H$: contradiction. Then, $gg' \in \complement_GH$.

So, denoted by $f \colon G \times G \rightarrow G$ the group operation, we get:

$f(G \times G) \subseteq G$
$f(H \times H) \subseteq H$
$f(H \times \complement_GH) \subseteq \complement_GH$
$f(\complement_GH \times H) \subseteq \complement_GH$

Finally, I claim that $f(\complement_GH \times \complement_GH) \cap H \ne \emptyset$. In fact, differently, we'd have that $f(\complement_GH \times \complement_GH) \subseteq \complement_GH$ and then $\complement_GH \le G$: contradiction, because $e \notin \complement_GH$.

Is this whole correct?

It is not really clear what you are asking about. Though, your reasoning is correct.

But, note that, you cannot say that $H$ partitions the group $G$. It would be saying that it is a set's property to partition any other sets/groups/categories etc. in which it is included. You see, having a complement is not what we call partitioning, even if it seems similar. With complements, it is already too trivial! For example, you could omit all your proof between second line and the before last one: As $H$ is a subgroup of $G$, thus the identity element of $G$ is included in $H$, thus no way it can be for the complement of $H$; so that we conclude the complement can never be a subgroup of $G$.

But the properties you showed would still remain valid.

Except that:

When you tried to proceed by contradiction at the last line, you began with a logically false claim. The proof holds on itself. But it is not how it is done. We prefer(!) beginning with a logically valid statement which doesn't hold with the given propositional phrase, then we try to arrive either to a logically false conclusion or any conclusion which does not hold with predicate to prove a contradiction.
I surely think that $ f( \bar{H} \times \bar{H}) \subseteq \bar{H} $ cannot imply that $\bar{H}$ is a subgroup of $G$ too. (where $\bar{H}$ is the complement). It only shows an inclusion; and nothing about a property at all.

The inclusion relation is what we call an ordering. It is, in fact, a linear ordering in this case. A linear ordering is a partial ordering in which the comparaison quality is well defined for every element pairwise distinct. Now, I will initiate you to a higher theorem:

("higher" in the sense that, here, we don't make use of it within its usual definition for limits; but for a different metric, ie. topological space with different ordering, but which holds well because they are isomorphic, ie. homoemorphic.)

So, you can use here the Sandwich Theorem. You see, the image of complements is ordered by usual set inclusion between the complement of $G$ and the $H$ itself. Though we know that we cannot have any element outside $G$. But we cannot have any in $H$ neither: Otherwise we would have images of $H$ and its complement intertwining. And as $f$ is a homomorphism of groups, it cannot be, thus contradiction.

You see, with the reasoning I told above, adapting it to different cases is only up to your redaction and comprehension. It becomes free of your choice for underlying set (ie. $Dom(f)$ here). You just need: 1. the linear ordering of inclusion (which you surely have here -unless in higher mathematics), 2. the function $f$ to be homomorphism of groups.


Prove $ax^2+bx+c=0$ has no rational roots if $a,b,c$ are odd If $a,b,c$ are odd, how can we prove that $ax^2+bx+c=0$ has no rational roots?

I was unable to proceed beyond this: Roots are $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$
and rational numbers are of the form $\frac pq$.

You should think about factoring the polynomial rather than finding its roots.  If $ax^2 + bx + c$ has a rational root, then its other root must also be rational, and then it factors in some way like this:
$$ax^2 + bx + c = (Ax + B)(Cx + D) \quad A,B,C,D \in \mathbb{Z}$$
Then $a = AC$ and $c = BD$, so if both are odd, then all of $A,B,C,D$ are odd.  But then we also have $b = AD + BC$, which is the sum of odd integers, and therefore is even.

Assume the your root z is rational (= q/r where at at most one of q, r is even)

Re-write the  equation with z on the left hand size and 1/z * c/a  - b/a
on the other. Substitute q/r for z, and put the left hand side into a fraction.

enter image description here

If neither q or r are even then numerators don't match
(q != rc - qb because odd != odd + odd)
and if only one is even then the denominator doesn't match
(r != qa because odd != even * odd and even != odd * odd)

Therefore, z is not rational.


Find a mistake in the following bogus proof Theorem: The function $f:\mathbb{R} \rightarrow [-10,10]$ defined by $f(x) = \cos(x)+\sin(x)$ for all $x \in \mathbb{R}$ has no maximum or minimum on ($-\infty,+\infty$)

Proof: The function is differentiable on $\mathbb{R}$ so one should be able to find its extrema by setting the derivative to 0. In particular, $$(\sin(x)+\cos(x))' = 0$$
$$\cos(x)-\sin(x) = 0$$
$$\sin(x) = \cos(x)$$
$$\sin(x+\pi/2) = \sin(x)$$
$$x+\pi/2 = x.$$

And the final equation is never true.
Yet WolframAlpha disagrees with my conclusions...

The problem is that
$$
\sin(\pi/2 +x) = \sin(x)
$$
does not imply that
$$
x+\pi/2 = x.
$$
This would only be true if $\sin$ was one-to-one on the interval considered.

The function is continuous and periodic, so by Bolzano Weierstrass it must have a maximum and a minimum.


Find Number Of Roots of Equation $11^x + 13^x + 17^x =19^x $ The Equation
$11^x + 13^x + 17^x =19^x  $

Has

No Real Roots
Only One Real Roots
Exactly Two Real Roots
More than Two Real Roots

What I have done is

The function $f(x)=11^x + 13^x + 17^x -19^x  $ is strictly increasing and being always positive it have no roots

I'm afraid your answer is wrong.

One way to see that is consider the function

$$f(x)=\left(\frac{11}{19}\right)^x+\left(\frac{13}{19}\right)^x+\left(\frac{17}{19}\right)^x-1$$

is strictly decreasing and $f(-\infty)=\infty$, $f(\infty)=-1$.

So there is only ONE real root.

Let y= f(x)= (11÷19)^x+(13÷19)^x+(17÷19)^x-1.
When we put x=0 then  y=2 and when x->infinity then  y->-1 so graph of f(x) cuts the x axis. Hence it has atleast one real root. So option 1 is wrong.
Also f'(x)<0 for all x
Let us suppose that f(x) has two real roots a,b such that   f(a)=0 and f(b)=0. So f:[a,b]->R is continuous in [a,b] and differentiable in (a,b) then by mean value theorem, there exist c in (a,b) such that
(f(b)-f(a))=(b-a)f'(c) => (b-a)f'(x)=0 but f'(x)<0 for all x. Hence a=b. So f(x) has only one real root.


Geometric meaning of different dot products So, the standard dot product is defined by the $I$ matrix. If using this dot product between two vectors gives me the result $0$ i can say the vectors are perpendicular because $0$ is the relative lenght of the projection of the first vector on the second one.

If i have a different dot product defined by another matrix, what is the change in his geometric menaning?

You speak of length and perpendicularity (=angle), but those concepts are defined only after a scalar product is given. Geometrically, assigning a scalar product on a vector space amounts to specifying which bases are orthonormal. Once one has an orthonormal base, one can measure lengths and angles.

The "standard dot product" on $\mathbb R^3$ prescribes that the "standard base"
$$
(1,0,0), (0,1,0), (0,0,1)$$
is orthonormal. But that is only a choice. If you choose a different scalar product, that base is not going to be orthonormal.

Suppose we have drawn the two vectors so that their tails are at the same point. The angle between the two vectors has been labelled $\theta$\

$a.b=|a||b|\cos(\theta)$

$|a| , |b| $ is the modulus

$\theta$ is the angle between $a$ and $b.$

we sometimes refer to the scalar
product as the dot product.

If  the scalar product of
two vectors which are at right-angles is always 0.

We say that such vectors are perpendicular or orthogonal


When does (Riemann) regularization work? I've seen the Wikipedia articles on how to sum $1+1+1+1+\cdots=-1/2$ or $1+2+3+4+\cdots=-1/12$.

Is there a theory behind it or is it a random trick? It basically uses analytic continuation of the Riemann zeta?

The article says it may be  used in physical applications. So I wonder, what are the conditions that this type of regularization will give me a useful and consistent result?

There are other series which can be summed differently: $1+2+4+8+\dots=-1$. Is it possible to obtain the same result with Riemann regularization? Are different type of regularizations giving the same results (if they exist)? If not, how can I know which one will work for my (physical?) calculation?

One of the keys is surely, that any method of summation must be consistent with the results of a conventional sum, if the summation-method is applied to convergent sums/series. I find it fairly obvious (but in case a source in the literature is sought, for instance, Konrad Knopp explained it in his monography on infinite series:) "it must be made clear, what the symbol 1+2+3+4+... really means"; first thing we must do is to find/define an expression for each term in the sum relative to its index. Otherwise 1+1+1+1+... and 1+0+1+0+1+0+... cannot be distinguished of each other. In the geometric series with the base q we have the general term $q^k$ dependend on its index k, in the zeta-series we have the general term as $k^{-s}$ with the fixed exponent s and so on.

So we should first write $s(p)=\sum_{k=1}^\infty a(k,p) $ and define a dependend on k and possibly on another external parameter p to have a description of the general term.

After that we might either find

telescoping effects: subsequently following terms cancel (possibly only partially) and the whole expression reduces then to a finite sum
continuous intervals for some parameter p, for which $s(p)$ is a convergent series with a closed form expression $g(p)$ dependend on that parameter, where it might be consistent to extend $g(p)$ also for the cases, where the series $s(p)$ would be divergent
and so on.
$\cdots$

In the latter case it might happen, that we find such an extension and it seems to be a sensical re-expression, but it is found later, that there is also another reformulation, for instance as a sum with a telescoping effect, which reduces then to another value of the (originally divergent) sum. Then that found summation/regularization must be revised - and in general sthis is still a field of open research. There are accepted summation-procedures even for complete classes of infinite series - accessible for instance by Abel,- Cesaro-, Euler-, Borel-, Ramanujan-summation, to name only the classical ones; but there are arbitrarily many series for which we do not have an accepted summation-procedure.
L. Euler's zeta-"regularisation" for instance used that
$$s(p) = \sum_{k=1}^\infty k^p  $$
can seemingly be written as
$$\sum_{k=1}^\infty (-1)^k k^p +2\cdot \sum_{k=1}^\infty  (2k)^p$$
and then
$$\sum_{k=1}^\infty (-1)^k k^p +2\cdot  2^p \cdot \sum_{k=1}^\infty  k^p $$
and then $$ s(p) = t(p) + 2 \cdot 2^p \cdot s(p)$$
 $$ s(p)(1-2 \cdot 2^p) = t(p)$$
 $$ s(p) = {t(p) \over (1-2 \cdot 2^p)} $$
where t(p) can approximated for a wider range of the parameter p. But that this works in general depended on, that there is a) a continuous range for the parameter p where this is convergent (and allows the same simplification/reformulation) and b) this range can be continuously extended preserving the meaningfulness of finite values for the $s(p)$ .

These ridiculous-seeming summations are more a random trick than anything else, but they carry an important lesson.  The lesson is that it doesn't always make sense to write $a_0 + a_1 + a_2 + \cdots$ and treat this sum as if it had an actual value.  So these ideas are used to teach students that infinite sums don't always exist, or don't always make sense.  They're not generally re-visited after first-year analysis class.


proof that the series converges? I just need to make sure that I do it correctly

Thanks in advance,

Hint

$$
\frac{|\log x|}{1+x^2}\leq |\log x|
$$

You can use the fact $\ln(x) < x$ which makes it easier

$$ \int_{0}^{1}\frac{\ln(x)}{1+x^2}dx <  \int_{0}^{1}\frac{x}{1+x^2}dx=\frac{1}{2}\ln(1+x^2)|_{x=0}^{1}=\dots. $$

Note: Just note that, $ \frac{\ln(x)}{1+x^2} $ is Riemann integrable (in the extended sense if you wish and $x\sim 0$ $\frac{\ln(x)}{1+x^2}\sim \ln(x)$ ) and by the property of the Riemann integral, for $f$ and $g$ Riemann integrable functions such that

$$ f \leq g\quad  \forall x\in[a,b] \implies \int_{a}^{b} f(x)dx \leq \int_{a}^{b} g(x)dx, $$

then above answer is true

Another approach: Note that the integrand has a singularity at $x=0$, so we have

$$ x\sim 0 \implies \frac{\ln(x)}{1+x^2} \sim \ln(x) $$

and using the fact

$$ \int_{0}^{1}\ln(x)dx < \infty $$

the original integral converges.


A king has n children, at least one of them is a daughter. What’s the probability that all of them are daughters? A king has n children, at least one of them is a daughter. What’s the probability that all of them are daughters?

So far I've considered the case of 3 children, which gives a probability of 1/7.
But I'm confused about how to generalise this?

The sample space has $2^n$ equi-probable points, assuming P(boy) = P(girl) = $\frac12$

Knowledge that there is at least one girl implies that one particular outcome is ruled out.

Continue....

Its generalisation can be P(n,1)+P(n,2)+....+P(n,n) where p represents permutation abd their addition is no of ways of having children.
So probability is P(n,n)/total no of ways of having children which is the above sequence


How to prove that if $A\subseteq B$and $|A|=|B|$, then $A=B$ Apart from the question in the title, the other question that related to the first question: Define: $f(X)=${$f(x)|x\in X$}. if $X$ is finite, $f(X)\subset X$ and $f$ is one to one, then $|f(X)|=|X|$, and according to the statement in the first question, $f(X)=X$. Then if $X$ is infinite, why could it be that $f(X)\neq X$ even if $f$ is one to one?
Note:"$|A|$" represents the number of elements in the set A.

If $A$ and $B$ are infinite, we may have $|A|=|B|$ but still $A \ne B$.

Let $A=\mathbb N = \{ 0,1,2,... \}$ and $B = \{ 0,2,4,...\}$; we have the one-to-one mapping (but not onto) $f : A \rightarrow B$ such that $f(n)=2n$ (Galileo dicovered it), but clearly $A \ne B$ ($B \subset A$, with proper inclusion).

$$
\text{First, I think your question is wrong}
$$
$$
A\subset B\quad \text{should be}\quad A\subseteq B
$$

$$
\text{Here is my proof}
$$
$$\text{Assume } A \neq B$$
$$\because A \subseteq B$$
$$\Rightarrow \forall a \in A \mid a \in B \tag{1}$$
$$A \neq B \tag{2}$$
$$(1)\quad \text{and} \quad (2)\Rightarrow \exists b \in B \mid b \notin \tag{3}A$$
$$(1)\quad and\quad(3) \Rightarrow\vert A \vert \neq \vert B \vert $$
$$\Rightarrow \text{Our assumption is false}$$
$$\Rightarrow A = B$$


Dickson's method for generating pythagorean triples can not find all triples - Known or not? I recently came across Dickson's method on Wikipedia for generating pythagorean triples. I implemented this in a computer programming language and found some oddities, which was based on the fact that there was missing triples, ie, the Dickson method did not generate all of the triples.

The specific example that I found was the triple $(65, 72, 97)$ which satisfies $65^2(=4225) + 72^2(=5184) = 97^2 (=9409)$ ie it is a valid pythagorean triple, but it can not be found with the Dickson method:

In the Dickson method $a = r + s$, $b = r + t$ and $c = r + s + t$ where $r$ and $s$ are factors of $r^2/2$. In this specific case, $r=40$ which implies $s = 25$ and $t = 32$ with neither of $s$ and $t$ being factors of $40$.

My question is whether this is a known fact or not? If it is a known fact, is there a source somewhere that I can cite to fix the Wikipedia page which claims it finds all triples?

Here is a proof that Dickson's method works. Let $a, b, c$ be three integers. Set
$$r = a + b - c$$
$$s = c - b$$
$$t = c - a$$

which are manifestly integers if and only if $a, b, c$ are integers. Now we compute that
$$r^2 - 2st = a^2 + 2ab + b^2 - 2ac - 2bc + c^2 - 2c^2 + 2ac + 2bc - 2ab = a^2 + b^2 - c^2$$

hence $r^2 = 2st$ if and only if $a^2 + b^2 = c^2$.

Here is a better solution which I have formulated.
$$a = s^2 + 2sn                ..................       \qquad\rm Formula\ 1.J$$
$$b = 2n^2 +2sn              ....................       \qquad\rm Formula\ 1.K$$
$$c = s^2 +2n^2 +2sn         ....................        \qquad\rm Formula\ 1.L$$

This will generate all triples.


General relationship between original and rotated+translated line I have a line $L$ in the plane expressed as the points in $L = \{(x,y) \in {\mathbb{R}}^2 : x \cos \theta + y \sin \theta = r \; \wedge \; 0 > \theta > \pi/2 \}$ (note that the line cannot be fully horizontal or fully vertical). This line can possibly intersect the $y$-axis in $w-m \leq y \leq w+m$ for a fixed frame width $w > 0$ and a margin $0 \leq m << w$ (the line is generally "stuck" to a certain distance from the origin).

Let's call the point of intersection $Q$. I need to rotate line L in either direction around Q with angle $\phi$ (generally quite a small rotation; $\phi < \lvert\pi/20\rvert$). After the rotation I need to translate the line by a vector $\mathbf{t}$ perpendicular to the now rotated line. Again the distance $\lVert \mathbf{t} \rVert$ is generally small but its direction is always in the direction of the previous rotation.

Question:
Was is the relationship between the original line $L$'s parameters $\theta$ and $r$ and the new rotated and translated line's parameters ${\theta}_\text{new}$ and $r_\text{new}$?

EDIT - Feb 8th 2012:
Major changes. Original posing of the question was entirely wrong. The geometrical situation is now quite different and not quite as trivial as hinted at below in the comments.

After some fidling around with triangles and trigonometry I found the solution myself:

${\theta}_\text{new} = \theta \pm \phi$,
$r_\text{new} = r \cos \phi [1 \pm (\tan \phi / \tan \theta)] \pm \lVert \mathbf{t} \rVert$.

Not trivial but also not very dificult. Seems to be working beautifully in Mathematica.

lets' go the following graph of a line: General equation of a line is: Y= mx +b where m= the slope of the line and -b = the x intercept of the line.
How how ever your question is not complete, in the sense that, the axes of rotation of the line is not mention.
if it is rotated around it self it will remain the same line withe same slope and x intercept.
But if it is rotated around the x axis it will generate two cones whose vertexes are joined at the same point. and so on.
But if it is translated to another point in the plane for example (n,p) as its new origin then coordinate of all points with respect to the original axes are: new x= x-n and new y=y-p


For $\langle Tx, x \rangle \geq \|x\|^2$, prove a solution exists for $Tx = y$. Edit

I've posted this a couple other times, so I now plan on deleting those, and just using this one.

Here's the original problem:

  $H$ is a real Hilbert space. Let $T: H\longrightarrow H$ be a bounded linear operator on $H$ such that the inner product satisfies
  $$\langle Tx, x \rangle \geq \|x\|^2 \tag{A}$$
  Prove that a solution for the equation $Tx = y$ exists for all $y \in H$.

I've been looking at this problem and studying orthogonal complements and the direct sum theorem for a few days now, to no avail, so I suspect there's something very fundamental I don't understand here. Below I'm posting W. Zhan's proof that I don't understand, and a couple of starting points of my own. W. Zhan's, as mentioned below, isn't working for me, so I'm starting a bounty. Thank you.

Proof given by W. Zhan

  Note that adjoint of a bounded operator always exists by Riesz Represenation Theorem. So we have
  $$ \langle Tx,x \rangle = \langle x, T^*x \rangle  \ge ||x||^2$$
  So $T^*$ is injective. We also have $im T^\perp =  \ker T^*$. Hence, $im T = H$.

I'm not sure what I'm not understanding. I do understand

  So $T^*$ is injective.

and also

  We also have $im T^\perp =  \ker T^*$

but not how those two facts yield the conclusion.

Here's a couple starts I've had on my own

Proof (alternate start 1)

Let $Tx = 0$, then

$$0 = \langle Tx, x\rangle \geq \|x\|^2 \geq 0$$

so $\|x \| = 0$, but by definition of the norm, only if $x = 0$. So $Tx = 0 \iff x = 0$, therefore $T$ is injective. This means $T$ has an inverse linear operator $T^{-1}$.

Now, let $y \in \overline{TH}$. By definition, $y$ is a limit point of $TH$, so there exists a sequence $(x_n)$ in $H$ such that $(Tx_n) \longrightarrow y$. However, $x_n = T^{-1}Tx_n$, which implies

$$\lim_{n\to \infty}x_n = \lim_{n\to \infty} T^{-1}Tx_n  = T^{-1}\lim_{n \to \infty}Tx_n = T^{-1}y$$

... here I think I'm in trouble because I don't know if I can actually show $T^{-1}y$ exits, which I think is equivalent to showint $T^{-1}$ is bounded.

Proof (alternate start 2)

Here, as W. Zhan pointed out, it's easy to see that $(TH)^\perp = \{0\}$, which implies that $TH$ is dense in $H$. In other words, $\overline{TH} = H$. So all that remains is to show that $TH$ is closed. But this is similar to the argument in my first attempt.

Discussion

I understand that $T^*$ is injective—because it is a linear operator and $Tx = 0 \implies x = 0$. In fact $T$ is as well. So I believe another option is to show surjectivity of $T$, but I can see how to do that.

Would somebody mind proving the original proposition in a detailed way?

Note that adjoint of a bounded operator always exists by Riesz Represenation Theorem. So we have
$$ \langle Tx,x \rangle = \langle x, T^*x \rangle  \ge ||x||^2$$
So $T^*x =0 \Rightarrow ||x||=0 $, hence $T^*$ is injective. We also have $im T^\perp =  \ker T^*$. Thus, $im T = H$.
To see why $T$ has closed range, note $||Tx||= \sup_{||y||\le1} |\langle Tx, y \rangle| \ge \langle Tx, x \rangle /||x|| \ge ||x||$.  Then result follows from characterization of closed image. The direction you need is actually already on MSE.
EDIT: Here's an easier way to see why $T$ has closed range. Suppose $Tx_n \rightarrow y$, then applying $x=x_n-x_m$ implies $x_n$ is Cauchy. Continuity implies $Tx = y$.

We can prove that $T$ is not singular, and from that, the problem is solved.

Assume $T$ is singular. Then there exists a vector $v \not= 0$ such that $Tv = 0$. But then $\langle Tv, v\rangle = 0 < \|v\|^2$ which contradicts our assumption that $\langle Tv, v\rangle \ge \|v\|^2$.

Okay, so now that $T$ is not singular, it has an inverse, implying that $x = T^{-1} y$.


Showing that the function given by $f(x,y)=\frac{xy}{\sqrt{x^2+y^2}}$ and $f(0,0)=0$ is continuous but not differentiable Let
$$
 f(x,y) =
\begin{cases}
\dfrac{xy}{\sqrt{x^2+y^2}}   & \text{if $(x,y)\neq(0,0)$ } \\[2ex]
0 & \text{if $(x,y)=(0,0)$ }  \\
\end{cases}
$$
Show that this function is continuous but not differentiable at $(0,0),$ although it has both partial derivatives existing there.

I can show this function is continous and the partial derivatives exist. But how can I show that this function is not differentiable?

Is showing that the function is differentiable similar to showing that a derivative exists?

There are no directional derivatives in nearly all directions. Consider, in particular, along the line $y=x$.  $f(x,y)$ is a constant times the absolute value function.

When a function of two variables is differentiable, then there is a tangent plane to the surface $z=f(x,y)$, and there are directional derivatives in all directions.  This one doesn't have directional derivatives except in two directions, and there's no tangent plane to the surface $z=f(x,y)$.

I don't know if I should write my answer here but can't write all this as a comment.
 This is what I tried to do:
According to the definition , $f$ is fifferentiable at $a $ if,
$\Delta$f=$f$(a$_1$+h$_1$,...,a$_n$+h$_n$)-$f$(a$_1$,a$_2$,..,a$_n$)
=l$_1$h$_1$+l$_2$h$_2$+...+l$_n$h$_n$+...+B$_1$h$_1$+...+B$_n$h$_n$
where l's are constants and $ \lim_{h1h2...hn\to 0,0,,..,0}$B$_i$=0

Here a=(0,0,).
Therefore  $\Delta$f=f(0+h$_1$,0+h$_2$)-f(0,0)
=$\frac{h_1h_2}{\sqrt{h_1^2+h_2^2}}$-0

This is not in the above form .Therefore f is not differentiable at (0,0)


Is the definition of metric topology, discrete topology and topology equivalent? I am taking a course in intro topology and very confused because the lecturer has only given us a definition of metric topology while all the texts I have read have the axiomatic definition of topology.

I don't think they are the samee but what is the difference? Also is metric topology same as 'discrete topology'?

Definitions I have are:

Metric topology: Collection of open sets such that all subsets are in X.

Topology: The three axioms of it should contain X, empty set, union and intersectoin should be in the topology.

Discrete topology: T is the collection of all subsets of a non empty set X.

To me discrete and metric look the same?

I am not understanding anything in lectures so I am trying to teach myself with resources online. Thanks for your help.

A metric $d$ on $X$ lets us define a notion of open sets, i.e. a topology $\mathcal{T}_d$. The latter obeys the abstract axioms of a topology.

But many abstract topologies cannot have a metric defined on them that defines that topology in this way. There are theorems on when this is and is not the case. Many topologies in practical maths arise from metrics, so in the beginning there is often more focus on metrics (analysis has a lot of use for it). E.g. at my university we had a course in "metric topology" in year 1, introductory general topology in year 2, advanced topics later.

The discrete topology is actually a general topology that is generated by a metric: $d(x,y)=1$ when $x \neq y$, $d(x,x)=0$. The usual topology on $\Bbb R$, $\Bbb Q$ etc. all arise from metrics.

I took this out of a study book from University.  This book was written by me and by a handful of other high-performing students, edited and checked by our professors and other faculty.  Its basically an academia-verified study guide written by the best of students, checked by the best of teachers, spanning all of high level mathematics. Content for this book was taken directly out of college text books, lecture notes, etc.  The book was written for the purposes of studying, review, and refreshing over the years in academia.  It comprises a multitude of high level courses in abstract mathematics spanning several years of the bachelors program, from advanced logic to topology, set theory to abstract algebra. Its several hundred pages long, full of definitions, theorems, etc., without any of the explanatory filler one normally finds in lecture notes or text books.  Familiarity with the subject matter is assumed, as its meant only for review. And its a work in progress.

Content was made as abstract as possible: No assumption is made about the types of vectors or fields or sets being employed.  Nor the operators.  Thus no numbers are used. We refer to generic sets, generic identity elements, generic order relations, generic operators, etc.

Yes, these clipped images from a PDF were written by me and others in LaTeX, and verified by experts in the fields. No cheating here. This is my content, as good as if I typed it out into stack exchange myself.  If there are errors or typeos, or anything you conceptually disagree with on a well-researched and mathematically rigorous basis, please do let me know. Im open to being corrected, just not resentful egotists who want to play petty games. Otherwise I cant imagine why the inevitable down votes would be justified, but I doubt those of you who would even read this far.

On the concept of metrics

On the concept of a topology

Combining the two


Chebyshev’s inequality and variance I have the following exercice:

  Use Chebyshev’s inequality to find an upper bound on the probability that the number of tails that come up when a fair coin is tossed n times deviates from the mean by more than $5\sqrt{n}$.

My question is: how should I approach this kind of problems? I know I will need the variance to use Chebyshev's inequality, and it seems fair to say that the expected value of the number of tails that show up when a fair coin is tossed $n$ times will be $n/2$. But this doesn't allow me to calculate $\mathbb{E}[X^2]$, and I'm really lost at how I should find them with a bound such as n tosses.

Any input is much appreciated!

Hint: Each coin flip is an independent Bernoulli random variable $X_i$ of probability $1/2$ and variance $(1-1/2)(1/2)=1/4$. Since $X_i$ are independent the variance of $X = \sum_{i=1}^n X_i$ (n coin flips) is
\begin{equation}
Var(X) = \sum Var(X_i) = n/4
\end{equation}


Solve $x^2+a\, y^2=1009$ for integer $x$ and $y$. The question is :

  Write 1009 in the form $(x^2+a\,y^2)$ for $a=1,2,3$.
  Where $x$ and $y$ are integers.

It is a question where we have to show our work but I know no method other than trial and error which is obviously not allowed... So please tell the correct method/trick to solve the question. Although I found answer for the first part by guess work which is:
$(28)^2 + (15)^2 =1009$.
But as I mentioned above we can not simply write this we have to show the work so please help.

One way is check if there is an element in $\mathbb{Z}[\sqrt D ]$ with $D$ square-free (i.e if the form $a+b\sqrt{D}$) with norm 1009.

That number $z=a+b\sqrt{D}$ must to be prime in $\mathbb{Z}[\sqrt D ]$ because divisibility of its norm.

$15^2+28^2=1009$

$19^2+2\cdot18^2=1009$

$31^2+3\cdot 4^2=1009$

$15^2+4\cdot 14^2=1009 $

$17^2+5\cdot 12^2=1009 $

$$1009 = 15^2+28^2$$

$$1009 = 19^2+2\cdot 18^2$$

$$1009 = 31^2+3\cdot 4^2$$

Well I calulate this values manualy with the use of calculator. Just write $y = \sqrt{1009-x^2}$ for the first case where $x\leq 31 =[\sqrt{1009}]$.

$y = \sqrt{1009-x^2 \over 2}$ for the second case where $x\leq 31$ and odd.

$y = \sqrt{1009-x^2 \over 3}$ for the last case where $x\leq 31$.


How can I think of (visualize) 0.5 bits of information? I was studying Shannon's Entropy function and for a 35% chance of a particular event, the formula produced the answer 1.5 bits.

log2(0.35) = 1.5 bits(approx.) of information.

I know it's pretty trivial in context of practical applications, but how can one visualize 0.5 a bit of information. I mean a bit could be one or zero but 0.5? Analog values ?!?!?

Thank you to Jyrki Lahtonen in the comments for answering it convincingly.

  You seem to be confusing the set of possible values of a bit (as
  information stored in some device) and the use of bit as a unit of
  information. A single coin flip contains one bit of information
  because the two possible outcomes are equally likely. But if the coin
  were heavily loaded, say with 99 per cent chance of getting tails,
  then the outcome of flipping such a coin surely contains less
  information than that of flipping a fair coin.

One bit of perfect information will allow a person to double their money.  The simplest idea, is if you had a tipster than knew who would win the football game, you could go to a bookie, place a wager and double your money.

Suppose you have a tipster that is right 55% of the time.  It is still worth following your tipster's advice, but you are not going to reliably double your money. And, you are not going to wager all of your money on one bet.  You have a partial bit of information.


For which integer $x,y$ does $x^2+23=3(2^y)$ How do I solve this Lesbegue-Ramanujan-Nagell type equation ($x^2+D=AB^y$):
$x^2+23=3(2^y)$

I have been trying for quite some time now, to no end. Any suggestions/help would be greatly appreaciated.

Clearly $y\ge 0$. Three cases:

$1)$ $y=3k$. Then $(3x)^2+207=\left(3\cdot 2^k\right)^3$. But $a^2+207=b^3$ has $14$ integral solutions (see http://oeis.org/A081120, in particular http://oeis.org/A081120/b081120.txt), which can be found with a program or in this table:

$$(a,b)=(\pm3,6), (\pm39,12), (\pm75,18), (\pm172,31),$$

$$(\pm5511,312), (\pm6022,331), (\pm223063347, 367806)$$

This gives the solutions $(x,y)=(\pm1,3),(\pm13,6)$.

$2)$ $y=3k+1$. Then $(6x)^2+828=\left(3\cdot 2^{k+1}\right)^3$. But $a^2+828=b^3$ has $10$ integral solutions (http://oeis.org/A081120/b081120.txt), which with a program or this table are:

$$(a,b)=(\pm30,12), (\pm37, 13), (\pm114,24), (\pm1122,108), (\pm298254, 4464)$$

This gives the solutions $(x,y)=(\pm 5,4),(\pm 19,7)$.

$3)$ $y=3k+2$. Then $x^2\equiv 3\pmod{7}$, contradiction, because $3$ is not a quadratic residue mod $7$.

Remark: this uses the results from $1998$ (from this paper), namely the full solutions of Mordell's equation $x^2+k=y^3$ for $0<|k|\le 10^4$.

Ill give a Hint for a similar example . See Ramanujan-Nagell equation on the net it is clearly mentioned there that the numbers cannot be $n= 3,4,5,7, 15$ and some more . to $2^n-7=x^2$ the solutions to x  correspond to $1,3,5,11, 181$ and there exists no solution greter than $2^{15}$. for more info you can look up for http://mathworld.wolfram.com/RamanujansSquareEquation.html Hope you get your hints and solution from there.


Given $1 \le |z| \le 7$ Find least and Greatest values of $\left|\frac{z}{4}+\frac{6}{z}\right|$ Given $1 \le |z| \le 7$

Find least and Greatest values of $\left|\frac{z}{4}+\frac{6}{z}\right|$

I have taken $z=r e^{i \theta}$ $\implies$ $1 \le r \le 7$

Now $$\left|\frac{z}{4}+\frac{6}{z}\right|=\left|\frac{r \cos \theta}{4}+\frac{ir \sin \theta}{4}+\frac{6 \cos \theta}{r}-\frac{6 i \sin \theta}{r} \right|$$

So

$$\left|\frac{z}{4}+\frac{6}{z}\right|=\sqrt{\frac{r^2}{16}+\frac{36}{r^2}+3 \cos (2\theta)}$$

any clue from here?

$\left|\frac{z}{4}+\frac{6}{z}\right|=\left|\frac{z^2+24}{4z}\right|$

The function $f(z)=\frac{z^2+24}{4z}$ is analitic on $1\leq|z|\leq7$. Therefore, by the maximum modulus theorem its maximum absolute value is attained at the boundary. The boundary are the circles $|z|=1$ and $|z|=7$.

For $|z|=1$, observe that $z^2$ just travels the same circle. We have $|f(z)|=|z^2+24|/4$, which is maximum for $z=1$ or $z=-1$ (such that $z^2$ and $24$ point in the same direction).

For $|z|=7$, observe that $z^2$ travels the circle $|w|=49$. We have $|f(z)|=|z^2+24|/28$, which is maximum for $z=7$ or $z=-7$ (such that $z^2$ and 24 point in the same direction).

So, $f(7)=f(-7)$ seem to be the largest.

The minimum is zero at $f(\pm\sqrt{24}i)$.

We want to find the minimum and maximum of

$\left| \dfrac{z}{4}+\dfrac{6}{z}\right|$

When $1\le |z|\le 7$

Let $z=x+iy$ and plug it in the given expression

$$\left| \dfrac{x+iy}{4}+\dfrac{6}{x+iy}\right|=\left| \dfrac{x+iy}{4}+\dfrac{6(x-iy}{x^2+y^2}\right|=\left|\frac{6 x}{x^2+y^2}+\frac{x}{4}+i\left(\frac{y}{4}-\frac{6 y}{x^2+y^2}\right)\right|$$

Which is
$$r=\sqrt{\left(\frac{6 x}{x^2+y^2}+\frac{x}{4}\right)^2+\left(\frac{y}{4}-\frac{6 y}{x^2+y^2}\right)^2}=\frac{\sqrt{r^4-48 r^2+96 x^2+576}}{4 r}$$
where $r^2=x^2+y^2$

As we have $1\le r\le 7$ let's plug $r=1$ and $r=7$ in the previous expression

for $r=1$ we get $\dfrac{ \sqrt{96 x^2+529}}{4}$ which is $\dfrac{25}{4}$ for $x=1$, maximum

for $r=7$ we get $\dfrac{\sqrt{96 x^2+625}}{28} $ which is $\dfrac{73}{28}$ for $x=7$, minimum

Hope this helps

Edit

Actually $\dfrac{z}{4}+\dfrac{6}{z}=0$ has a solution at $z=\pm 2 i \sqrt{6}$ whose module satisfies the condition $|z|\in[1,\;7]$ therefore that is the absolute minimum, zero.


About the fact that $\mathbb Q$ has gaps In my book there are two theorems:

$1.$ The number $\sqrt 2$ is irrational because if we put $\sqrt 2 = \frac pq$ for some integers  $p, q$ where $p, q$ have no common factors, then we get a contradiction.
$2.$ The set $A = \mathbb Q \cap (0, \sqrt 2)$ has no largest number and $B = \mathbb Q \cap (\sqrt 2, \infty)$ has no smallest number.

Are the two theorems above saying the same thing or are they mutually exclusive? The reason I ask is because in a math book (AFAIK) the same statement is not usually reproven again after it's proven the first time without an explicit mention. So I was wonderig if there's some subtle difference between the two theorems above.

The technical part of the second theorem is not difficult, but I am having some uneasy time linking the fact that $A, B$ have no largest/smallest numbers with the fact that $\mathbb Q$ has gaps. Is the theorem saying that $\sqrt 2 \not \in A$ and $\sqrt 2 \not \in B$? But isn't that by very definition of $A, B$?

Thanks.

Theorem $(1)$ would have been used in theorem $(2)$ if the open intervals were closed  at the $\sqrt 2$ side.

However taht  is not the whole core of theorem $(2)$

Theorem $(2)$ is about the idea of the difference between the maximum element of a set and its least upper bound or supremum.

While the set $A$ does not have a maximum, it does have a supremum,namely $\sqrt 2$ which is not in the set.

Similarly the set $B$ which does not have a minimum but it does have an infimum which does not belong to $B$

For any dense set of reals
$\mathbb{D}$
and any real
$r \not\in \mathbb{D}$,
the set $A = \mathbb D \cap (0, r)$ has no largest number and $B = \mathbb D \cap (r, \infty)$ has no smallest number.

For example,
you could take
$\mathbb D$
to be the set of dyadic rationals
(rationals of the form
$\dfrac{2n+1}{2^m}$)
and
$r = \dfrac13$.


Is this GCD statement true? If we have integers $h$, $i$, $j$, and $k$, would it be true to say that $\gcd(h,i)\gcd(j,k)|\gcd(hi,jk)$? If so, how can we prove it?

This statement is false, You will see it whenever you take $h,i,j,k$ such that the products $hi$ and $jk$ are coprime but the numbers $h,i$ and $j,k$ are not pairwise coprime.
Illustrations:

Select $h=2, i=4$ and $j=3,k=9$, you will see that $6\not| 1$.
Select $h=5,i=15$ and $j=2,k=4$, you will again see that $10\not|1$.


When do we need to prove the measurabiliy of a function to write its integral? Let $f : [1,2] \rightarrow \mathbb{R}$ be a function such that $f(x) \leq 5 \ \forall x \in [1,2]$. Then can we write $\int _{1} ^{2} f(x) \,dx \leq 5$. Or do we need to first prove the measurability of $f$ to write that last inequality? Of course, I am talking about Legesge integration and I am asking this because I see people usually does not prove the measurabilty and directly  write that last inequality.

Does one assume the measurability of $f$ before writing down that last integral inequality? If yes, then why it is ok to do so?

You don't need to "prove" that $f$ is measurable before you "write" the integral.  But if you write it, and try to integrate a function that isn't measurable, the relevant limits won't exist or converge.  The integral you wrote down is undefined, somewhat like $0/0$.


What is the formula to calculate Profit Percentage? Let cost price of an item be $C$, selling price be $S$. Assume the seller makes a profit.

Then profit would be: $P = S - C$.

Now, what is the formula for calculating Profit Percentage?

$P \% = \dfrac{P}{C} \times 100$
$P\% = \dfrac{P}{S} \times 100$

Which one is right and why?

They are both right.

The first expresses the profit as a percentage of the cost price. This is the profit mark-up.

The second expresses the profit as a percentage of the sales price. This is the profit margin.

Percentage profit on its own doesn't mean anything unless you are talking mark-up or margin. By convention, in a module I teach, percentage profit means profit mark-up.

answer two is right because :
Suppose
Cost of your product is 5400
Selling price is 8000
then profit is 2600

According to 2nd formula P%=P/S×100
profit % = 2600/8000 X 100 = 32.5%

Let's check
profit according to 32.5%

profit = Selling price X profit % /100
         8000 X 32.5% / 100 = 2600

hence formula 2nd is right


How do I prove that if $\gcd(n,m)$ divides $a-b$, then $x\equiv a \pmod n$ and $x\equiv b \pmod m $ has a solution? Let $n,m$ be positive integers $>1$.

Assume that $\gcd(n,m)\mid (a-b)$

Then how do I show that $x\equiv a \pmod n$ and $x\equiv b \pmod m$ has a solution?

I"m struggling with this for an hour and I can't find a solution..

In fact it can be proven that the system
$\begin{align}
x&\equiv a\mod(n)\\
x&\equiv b\mod(m)
\end{align}$
has a solution $x$ if and only if $(n,m)|a-b$. The $\Rightarrow)$ proof is obvious, but the other direction, which is precisely OP's question, is slightly less obvious.

Let $d=(n,m)$, then by Bezout's identity we know that there exists $s,t\in\mathbb{Z}$ such that $ns+mt=d$. Given $d|a-b$, then we know $a-b=dk$ for some $k\in \mathbb{Z}$. Therefore we have $nsk+mtk=a-b$. Rearrange the expression and we have $m(-tk)+a=nsk+b$. Let $x=m(-tk)+a$, we have $x-a=m(-tk)$, which immediately means $x\equiv a \mod(m)$. On the other hand we have $x=nsk+b$, which gives us $x-b=nsk$, which entails $x\equiv b \mod(n)$.

Assume $m>n$.  Let $g=\gcd{(m,n)}$.  Since $g|(a-b)$, there exists an integer $k$ such that $a-b=gk$

Since $g=\gcd{(m,n)}$, $gk_1=m, gk_2=n$ for integers $k_1, k_2$.

Finally, since $x\equiv a\pmod{n}$, then $$x-a=nb=gk_2b$$ and thus $x\equiv a\pmod{g}$ as well

Now, suppose that there is no solution to the system.  Then
$$x\not\equiv a\pmod{n}$$$$ x\equiv b\pmod{m}$$
is one case then.  This implies
$$x-a=nb+c, \text{ where }b,c\in \mathbb{Z}, 0\le c\lt n$$
$$x-b=md, \text{ where } d\in \mathbb{Z}$$
Now look at $(x-b)-(x-a)$
$$(x-b)-(x-a)=md-(nb+c)$$
$$a-b=gk_1d-gk_2b-c$$
$$a-b=g(k_1d-k_2b)-c$$
Note that it is possible that $c=g$, since $g\le n$.  But
$$x\not\equiv a\pmod{n}\Rightarrow x-a\neq nb\Rightarrow x-a\neq gk_2b$$And thus $x\not\equiv a\pmod{g}$. This implies that $c\neq g$ since
$$x-a=nb+c\Rightarrow x-a=gk_2b+g \Rightarrow x-a=g(k_2b+1)$$ which contradicts the fact that $x\not\equiv a\pmod{g}$.

But we have the initial condition that $a-b=gk$ for some integer $k$, but here, since letting $k=k_1d-k_2b$ gives us $a-b=gk+c$, we have a contradiction.  Therefore, our assumption that there is no solution is wrong and the system has a solution.


How to find minimal distant from one point to a parabola? Find the minimal distance from the point (2,0) to the parabola $y^2=2x$.


Using of Newton's method to find a complex root of a polynomial I have studied the Newton's method for real functions, and these are the conditions to find a function real root on $[a,b]$:

$$f(a) \ f(b)<0$$
$$f'(x)>0 \quad (\text{or} \quad f'(x)<0) \qquad \forall \in [a,b] $$

Convergence theorem:

$$\text{sign}(f' f'') = \text{sign}(x_0 -x^*)$$

Iterations:

$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \qquad x_n\in \mathbb{R}$$

How can I use Newton's method to find the complex roots of a polynomial (e.g. $z^2+1$) ?

I know a real coefficients polynomial of degree $p$ has $p$ different complex roots (for Fundamental theorem of algebra)

But, how can I verify the convergence of the Newton succession with an initial value $z_0$?

$$z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)} \qquad z_n\in \mathbb{C}$$

Thanks!

you don't need newton's method. you can use muller's method which can find complex roots, doesn't require a derivate but you need 3 points.
the method is awesome! basic requirements: knowledge on how to multiply, add, subtract, and divide. knowledge on how to take square roots if you only know that method that you need to have a polar form function, it will just waste your time.
as with square roots, you can find all roots by solving a system of equations:
we have a number called (a+bi)
we know that t^2=(a+bi)
2xy=b
x^2-y^2=a
x^2+y^2=(a^2+b^2)^0.5 solve for equation 2 and 3. then find x and y. obviously, x is real and y is not. y=i x=x


Does this apply: $\sin^2(\pi t-\pi) + \cos^2(\pi t-\pi) = 1$ So I'm solving for the length of the following parametric description:

$$
\Bigg[x(t)=3\cos(\pi t-\pi)\,\,\,\,\,\,\,y(t)=3\sin(\pi t - \pi)$$
I applied the formula for solving for length, namely:
$$\int_{0}^{2} \sqrt{(-3\pi \sin(\pi t - \pi))^2+(3\pi \cos(\pi t - \pi))^2 }\,\,\, dt$$
$$\int_{0}^{2} \sqrt{9\pi^2\times1}\,\,\, dt$$

My question is:
Is it correct that [ $(\sin(\pi t - \pi))^2+ (\cos(\pi t - \pi))^2 = 1$ ] because of the rule: $\cos^2(x) + \sin^2(x) = 1$ ? Can I always apply this convention as long as I have the same on the inside of the sin and cos?

Highly appreciated,

-Bowser

Yes it is, the relation $\sin^2(x)+\cos^2(x)=1$ holds for any $x$ value

Hint you can verify using formulae $$\sin(a-b)=\sin(a)\cos(b)-\cos(a)\sin(b)$$ and $$cos(a-b)=\cos(a)\cos(b)+\sin(a)\sin(b)$$


How to find a nth primitive root of unity over $\mathbb{Z}_2$? For instance, one can find 15th roots of unity by letting $f(x) := x^{15}-1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1)$. Then roots of $f(x)$ are roots of its factors. e.g. When $\omega$ is a root of $(x^2 + x + 1)$, it is a root of $f(x)$. But how would one go further around with finding a "primitive" root?

First Approach

The roots of unity live on a unit circle and are equally spaced. If you let

$$ x = exp \left(i\theta\right)$$

Then you are greatly simplifying the problem, as you are only considering solutions on the unit circle. As a result:

$$ \exp \left(in\theta\right) - 1 = \exp \left(in\theta\right) - \exp\left( {2\pi ik} \right) $$

Now they are only roots when $\theta = {2 \pi k \over n}$. Which indicates that the roots are spread evenly around the unit circle.

  Note $\exp\left(2\pi i k \right) = \cos(2\pi k) + i \sin(2\pi k) = 1$ always equals 1, since sin is zero for all multiples of $2\pi$.

Hope that helps.

Alternative Approach

Since $f(x) = x^{15} -1$, it is easy to show that $f(\bar x ) = f(x)$. This means that all roots must occur in conjugate pairs. As a result, the roots of unity must occur in pairs. If you expand these pairs, you always get quadratic terms.

n is odd

If n is odd, then we must have a factorisation:

$$x^n - 1 = (x-1)(x-\alpha_1)(x-\bar\alpha_1)...$$

n is even

If n is even, then we have two known roots:

$$x^n - 1 = (x-1)(x+1)(x-\alpha_1)(x-\bar\alpha_1)...$$

Hopefully that helps :)


How to calculate combinations count for this problem I will explain my question using simple example, cause I don't know to descrive it properly.
If we have 2 numbers $\{a,b\}$, by comparing them, we get 3 possible combinations: $$a>b, \hspace{3pt} a<b, \hspace{3pt} a=b$$ For 3 numbers $\{a,b,c\}$ we get, $$b<a>c, \hspace{3pt} b>a<c, \hspace{3pt} a<b>c, \hspace{3pt} a>c<b, \hspace{3pt} \hspace{3pt} a=b=c, \hspace{3pt} a=b>c, \hspace{3pt} etc...$$

How to calculate how many combinations exist for n numbers.

If I understand the problem correctly, these are the ordered Bell numbers, aka the Fubini numbers. Perhaps the cleanest formulation of the problem is that we have $n$ (distinct) runners in a race, and we want to count the number $a(n)$ of possible orders of finish, including ties.

There are useful recurrences, ways to express $a(n)$ as sums,  and asymptotics, but no known closed form.

Put the n numbers in any order. There are $(n-1)$ spaces between the numbers in which you have to put signs. There are 3 signs to choose from for each space. Therefore, the solution is 3^(n-1).


What is the correct way to read $f\circ g$? Let $f : X \to Y$ and $g : Y \to Z$ be functions. We define the composition $g \circ f : X \to Z$ by $g \circ f(x) = g(f(x))$ for each $x \in X$.

I have also heard the composition read out like this:

"The composition of $f$ with $g$ is . . ."
"Consider the function $g$ composed with $f$, given by . . ."
"The function $g$ of $f$ is . . ."

Is this an appropriate way to speak of $g \circ f$? It sometimes happens that I (or my teachers) reverse the order of $f$ and $g$ when describing $g \circ f$ in any of the above ways. Surely, it can't be that both ways are correct. It doesn't cause confusion because the function being talked about is quite straightforward. But I'm still interested in knowing what the "correct" way/s to describe $g \circ f$ is/are among the above.

I know that some people prefer the functional notation that operates the other way, but this question is not about that scenario.

(I have not yet learnt the nitty gritty definitions of functions so I'm not sure how useful my answer is.)

When saying aloud $g \circ f$ I've always said "$g$ of $f$" - the same way you would say $g(x)$ as '$g$ as a function of $x$'. My mathematics teachers in high school and at university have exclusively said $g$ of $f$.

Your second and third examples make perfect sense to me. I find the first one confusing. The answers in the comments e.g. $g$ after $f$ also make sense.

Here's your answer via Wikipedia:

  For instance, the functions $f : X \to Y$ and $g : Y \to Z$ can be composed. . . The resulting composite function is denoted $g \circ f: X \to Z$, defined by $(g \circ f)(x) = g(f(x))$ for all $x$ in $X$. The notation $g \circ f$ is read as "$g$ circle $f$", "$g$ round $f$", "$g$ about $f$", "$g$ composed with $f$", "$g$ after $f$", "$g$ following $f$", "$g$ of $f$", or "$g$ on $f$".


Is it possible to learn ring theory if one's familiar, but not good at group theory? Is it possible to learn ring theory if one is familiar with but not good at group theory?

Background: I’m using Dummit and Foote's Abstract Algebra, and I am an undergrad.

Is it possible to learn ring theory if one's familiar, but not good at group theory?

Absolutely yes; your study of Dummit and Foote should give you enough of a foundation in "group theory" to successfully study "ring theory" in greater depth. So it is indeed possible to learn ring theory before being fully proficient in group theory.

But I also want to add:

It is far too early for you to conclude you are not good at group theory! You're an undergrad, as you point out, and your experience when first encountering any new theory or topic is not really sufficient evidence to determine how "good" you are at it, especially if you're making that judgment based on your progress through one book's coverage of groups.

Every serious student of math encounters a wall at one point or another (and for most of us, many many times). Sometimes the things that first "trip us up" are precisely the things that end up fascinating us.

Furthermore, try not to judge your mastery of any topic (e.g. group theory) based on its presentation in only one text. (In my humble opinion) Dummit and Foote's text is not all that great in covering groups.

So explore a bit by supplementing Dummit and Foote's coverage of groups with other resources: e.g., find a text or two that approach groups differently:

Artin's Algebra covers groups well; see especially chapter 2.
Or - if you're really struggling with groups - try looking at Fraleigh's A First Course in Algebra, which does great with introducing groups and motivating the material. The book is written in a way that is very readable, intuitive, and includes a lot of examples.
If you can't access one of the above texts through a library, and are looking to limit expense, J.S. Milne has a nice site for course-notes, including a ~$140$-page pdf on Group Theory.

So try not to "write off" group theory quite yet; you may find you like group theory, after all!

I must say I don't see why you are interested in ring theory if you are not good at group theory ; you don't give interest in a subject just because it looks cool, but because you want to be able to use it in some way. If you just want to read about it, you can, whether you are good or not, it's not a problem. Your eyes will still open and you will still be able to read the book! The issue is when you will want to do exercises ; group theory and ring theory are theories among the algebraic theories, so their nature is very similar ; it is very likely that being good/bad at understanding one will imply being good/bad at understanding the other, although it is possible that you feel a little bit more comfortable working with objects with a little bit more structure than groups.

As amWhy points out, we interpret your "not being good at group theory" as "you're not comfortable with it". You might turn out to feel comfortable with it later and be very good at it.

If this is because you want to read about a ring theory course you must take before you finished your group theory class or something like that, I think it is a bad idea ; the Dummit & Foote book is a good book to use as a reference and is full of relevant exercises, I am a fan of it myself, but I must say I did not begin learning group theory using this one, it lacks a little bit intuition. For books that build intuition on groups in a more relevant way, I could provide you a reference.

I'll add that when one begins ring theory, the first examples of rings differ a lot from the group-theoretic ones, mostly by the fact that they are infinite. A lot of the elementary group theory focuses on finite groups because they are easier to study ; in ring theory, the basic examples would come from subrings of fields ($\Bbb Z$ or $n\Bbb Z$ would be an example), number rings or function rings, and their quotients. This gives them a quite different feeling from the elementary examples in group theory such as $\Bbb Z/n \Bbb Z$, $S_n$, $A_n$, $D_n$, etc.

To sum things up : give it a try and see what happens, if you have the time to do so.

Hope that helps,


Are there infinitely many primitive Pythagorean $n$-tuples? Let's define a Pythagorean $n$-tuple ($n \geq 3$) as a tuple of distinct natural numbers $(x_1, ... , x_{n-1}, y)$, such that $x_1^{n-1} + ... + x_{n-1}^{n-1} = y^{n-1}$. Let's call a Pythagorean $n$-tuple primitive if $GCD(x_1, ... , x_{n-1}, y) = 1$

It is a rather well known fact, that there are infinitely many primitive Pythagorean triples. Indeed, $(2k(k + 1))^2 + (2k + 1)^2 = (2k(k + 1) + 1)^2$ $\forall k \in \mathbb{N}$.

But is it true that $\forall n \geq 3$ there are infinitely many primitive Pythagorean $n$-tuples?

No construction, similar to the one used for $n = 3$ comes to my mind for arbitrary $n$...

For $n=4$ we have this [1] infinite parametrised set of solutions for 1:
$$(9t^4)^3 + (-9t^4 \mp 3t)^3 + (\pm 9t^3 + 1)^3 = 1$$

[1] Kurt Mahler, Note On Hypothesis K of Hardy and Littlewood, Journal of the London Mathematical Society 11 (1936), 136–138.

The answer is yes. For every side C in a primitive, a side A can be found in another primitive. For example, $(3,4,5)\rightarrow (5,12,13)\rightarrow (13,84,85)$ and these can be joined to make a single 4-dimensional figure. Let's reason this backward. If we have $5,12,13$, we can replace $5^2$ with $3^2+4^2$ and not affect the equation. Moving forward, $\quad 3^3+4^2+12^2+84^2=85^2.\quad$ One formula (mine) for generating Pythagorean triples is:
$$A=(2n-1)^2+2(2n-1)k\qquad B=2(2n-1)k+2k^2\qquad C=(2n-1)^2+2(2n-1)k+2k^2$$

It creates sets within the subset of triples where $GCD(A,B,C)=(2m-1)^2, m\in\mathbb{N}$ as shown here
$$\begin{array}{c|c|c|c|c|c|c|}
n & k=1 & k=2 & k=3 & k=4 & k=5   &  k=6  \\ \hline
Set_1 & 3,4,5 & 5,12,13& 7,24,25& 9,40,41& 11,60,61 & 13,84,85 \\ \hline
Set_2 & 15,8,17 & 21,20,29 &27,36,45 &33,56,65 & 39,80,89 & 45,108,117 \\ \hline
Set_3 & 35,12,37 & 45,28,53 &55,48,73 &65,72,97 &  75,100,125 & 85,132,157 \\ \hline
Set_{4} &63,16,65 &77,36,85 &91,60,109 &105,88,137 &119,120,169 & 133,156,205 \\ \hline
Set_{5} &99,20,101 &117,44,125 &135,72,153 &153,104,185 &171,140,221 & 189,180,261 \\ \hline
\end{array}$$

If you have any side C, you can find a match in $Set_1$––side-A in $Set_1$ contains all odd numbers greater than one and all members of $Set_1$ are primitive––and sometimes elsewhere. If we solve the $A$-function for $k$, we can find a matching $A$, if it exists, with defined finite search limits. Any of the $n$-values that yield an integer $k$ gives us a triple.

$$A=(2n-1)^2+2(2n-1)k\quad\longrightarrow\quad k_A=\frac{A-(2n-1)^2}{2(2n-1)}\quad\text{where}\quad 1\le n\le\biggl\lfloor\frac{\sqrt{A+1}}{2}\biggr\rfloor $$ for example, beginning with $\qquad F(2,4)=(33,56,65)\qquad$ we have

$$\\ A=65\quad \longrightarrow \quad  1\le n\le\bigg\lfloor\frac{\sqrt{65+1}}{2}\bigg\rfloor=4  \quad\text{and we find} \quad n \in \{1,3\}\quad \Rightarrow \quad  k\in\{32,4\}\\ $$
$$F(1,32)=(65,2112,2113)\qquad F(3,4)=(65,72,97)$$

Here, we have already created a new tuple where
$$33^2+56^2+72^2=97^2$$
How about
$$(3,4,5)\&(5,12,13)\&(13,84,85)\&(85,132,157)\&(157,12324,12325)\\\Longrightarrow 3^2+4^2+12^2+84^2+132^2+12324^2=12325^2$$

It is easy to see that the process can continue to infinity.


Cluster probabilites: Bayesian network (sprinkler example, Russel/ Norvig) as a clustered network like others here I am also learning with Russel's and Norvig's book about artificial intelligence. My question is about the conditional probability tables of a clustered multiply connected network with a meganode.

We have the following Bayesian multiply connected network.

In order to reduce computation (according to the book). We combine Sprinkler and Rain and get a meganode.

I have my difficulties with understanding the conditional probability table for the new meganode.

I assume that the values

$P(S+R|C) = .08$ can be calculated with $.08 = P(S|C) \cdot P(R|C) = .10 \cdot .80$.
Same goes for  $.02$ with  $.02 = P(S|C) \cdot P(R|\neg C) = .10 \cdot .20$.

However I do not understand why

$P(S+R|\neg C) = .40$ could be computed with $.40 = P(S|\neg C) \cdot P(R|C) = .40 \cdot .80$: Since according to the $TT$ column Sprinkler should be true and Cloudy should be true, same with Rain. However we have to use Sprinkler true but Cloudy false.
or $0.72$ could be computed with $.72 = P(R|C) - ( P(S|C) \cdot P(R|C)) = .80 - .10 \cdot .80 = .80 - .08$

Hence my overall question is how $P(S+R=x)$ can be computed.

Thank you!

There are no typos.

Say Sprinklers = False and Rain = True GIVEN Cloud = False.

Then probability $= P(S = F|C = F) \cdot P(R = T | C = F) = 0.5 \cdot 0.8 = 0.4$,

which is what the 3rd column in the second row corresponds to.


Number of $3 \times 3 \times 3$ magic cubes A $3 \times 3 \times 3$ magic cube is a three-dimensional array of the consecutive integers $1$ through $27$, with the special property that the sum along any row, any column, any pillar, or any of the four space diagonals is equal to the same number. (Rotations of a certain solution are considered the same solution and therefore not counted.)

How many different $3 \times 3 \times 3$ magic cubes are there?

I got that the sum of each of these should be equal to $\frac19\left(\frac{27\cdot28}{2}\right)=42$, but I have no idea how to proceed after that.

Any help would be appreciated!

Up to rotation and reflection, there are four.


How can we measure how "irrational" a number is? I wonder, can we, for instance, say that $\pi$ is more irrational than $e$? Or that $e$ is more irrational than $\sqrt{2}$? What kind of irrationality measurement can we use to say that $A$ is (much) more irrational than $B$? (in particularly rigorous sense)

Well, there is a sort of extension of the idea of irrationality called "transcendental". You can think of "irrational" as meaning "There is no way to relate this number to $1$ by thinking only about addition and subtraction". That is, a number $q$ is rational if we can write something like:
$$q+q+q-1-1-1-1=0$$
or some other similar equation involving only $q,\,+,$ and $1$. The above represents the number $\frac{4}3$ and more generally, you can, for $q=\frac{a}b$ write:
$$\underbrace{q+\ldots+q}_{b \text{ repetitions}}-\underbrace{1-\ldots-1}_{a \text{ repetitions}}=0.$$
or appropriately change signs for negative $a$.

The next logical step would be to consider the idea of allowing multiplication too - and this extends the rational numbers to algebraic numbers, which are (potentially) irrational, but can be related to the rationals via multiplication and addition. For instance, $x=\sqrt{2}$ satisfies
$$x^2-2=0$$
and we can come up with similar expressions (the set of such equations would be polynomials to be precise) for any expression built with radicals and addition and such - and we could say that the degree of an algebraic number (i.e. how many multiplications we need) represents how irrational it is - that is $\sqrt{2}$ can be related to integers by squaring it, but $\sqrt[3]{2}$ requires cubing to get to an irrational - and numbers like $\sqrt{2}+\sqrt{3}$ require fourth powers. We might say that the degree represents a sort of "distance" from the rational numbers.

However, this only extends to a narrow class of numbers - $\pi$ and $e$ are both transcendental, meaning "not algebraic". We have much less understanding of these, since we can't relate them to the rationals through arithmetic - so we could be justified in saying that they are less well behaved then algebraic numbers. One way we can talk about their
 irrationality measure which essentially tells us how far from rational numbers a given irrational is, relating the growth of the denominator of the best rational approximations to how close they are - this represents how these numbers are comprehended by looking at sequences of rational approximations, rather than algebraic properties. However, this isn't terribly useful to compare actual numbers, because we hardly know how to calculate any. We do know that, from its infinite series, that $e$ acts very similarly to an algebraic number (looking at its series definition) and its irrationality measure is $2$. We don't know the irrationality measure of $\pi$, though we might suspect that it greater than $2$ - but it's hard to compare numbers this way, given our limited knowledge thereof, and all it means to have a small irrationality measure is that it's "far" from any rationals with small denominators.

No rational number is irrational, but in the same way we can measure how "black" a shade of grey is, given that every irrational number has an infinite continued fraction, a fair measure of how irrational a rational number is, is by the length of its continued fraction.
As part of my studies of the Collatz conjecture I discovered (proof thanks to Torsten Schoeneberg) that every rational number has precisely one finitely-long continued fraction of the form $1-\dfrac1{2^{m_0}-\dfrac1{2^{m_1}-\dfrac1{2^{m_2-\frac1{\ldots}}}}}$
provided the terms are measured by letting $\lvert x\rvert_2$ be the 2-adic value of $x$ and iterate $1-\dfrac1{x\lvert x\rvert_2}$ until you get to zero.  The number of steps taken is the length of the continued fraction and the measure.
What is more, if you wish more resolution, you can assign every rational number (up to bijection) an ordinal less than $\omega^\omega$.  To do this, simply identify $m_0, m_1,\ldots$ by counting the number of divisions by $2$ required at each step. Then use any bijection $f$ from $\Bbb Z\to \Bbb N$ to send $m_i\to n_i$ and:
$1-\dfrac1{2^{m_0}-\dfrac1{2^{m_1}-\dfrac1{2^{m_2-\frac1{\ldots}}}}}\mapsto \displaystyle\sum_{i=0}^\infty\omega^i\cdot n_i=\displaystyle\sum_{i=0}^\infty\omega^i\cdot f(m_i)$
is a bijection from the rationals into the ordinal $\omega^\omega$.


In which kinds of books can I find the definition of exponential operator? I have been studying real and functional analysis recently, but I hadn't encountered an exponential operator such as $e^{L}$ until I recently read a paper. In which kinds of books can I find the definition of this concept? Operator algebra or functional analysis or Lie algebra? I'd appreciate it if you'd help me. Thank you.

A. Pazy, "Semigroups of Linear Operators and Applications to Partial Differential Equations".

This is one of the most readable books on the subject, and he starts with bounded operators and defines $e^{-tL}$ using an exponential series. He then works more general theories.

The original ideas for treating time solutions with an exponential came from the Electrical Engineer O. Heaviside. His ideas were highly original, controversial, and not well-understand. Heaviside's ideas eventually led to the development of the modern version of Laplace transform and its Bromwich integral inverse.

Heaviside introduced the idea of an evolution operator $S(t)$ that would take the state $x$ of an electrical system to its state $S(t)x$ after $t$ seconds. He reasoned that a time-independent circuit would have the property that $S(t')(S(t)x)=S(t+t')x$; that is, evolving $t$ seconds and then $t'$ more seconds would be the same as evolving $t+t'$ seconds. And $S(0)=I$ would hold because you're not doing anything to the system by evolving $0$ seconds.

Some suggested linear algebra topics for research. Also leads to practical application in Quantum Mechanics.

A lot of the analysis is based off of common ways of building up these concepts from the basic arithmetic.

For example, $2^N$ for integer N means $2\cdot 2 \cdot2...\cdot 2$ for a list of N 2's in a row.

From this meaning you can find $2^M \cdot 2 ^N=2^{(M+N)}$. You can also work backwards by dividing by two an get $2^0=1$, $2^{-1}=1/2$, $2^{-2}=1/4$, and so on.

But don't think of this as division, but multiplying by the inverse, which is the formal, more fundamental definition of division.

From hear you can generalize to how the concepts apply to matrices.

Given invertible matrix M, we can multiply it by itself n times. You can multiply the identity matrix by the inverse of M to get negative exponents of M.

You can diagonalize matrices to facilitate understanding fractional powers of a matrix.

If $M=A^{-1}BA$, then in general, $M^p=A^{-1}B^pA$ even for fractional powers of p, for suitable M.

You can generalize using the Binomial theorem:

$(I+A)^p=\sum_{k=0}^p \ {p \choose k}A^k$, the general form allowing for fractional exponents.

A text on Real Analysis teaches that from the binomial theorem and its general form, you can map exponentiation with the argument as the independent variable to having the base  as the independent variable, i.e. $e^x=1+x+x^2/2+x^3/3!+...$ once you define limits as they apply to matrices.

In particular, $(1+a)^N=1+Na+...$ can be swapped with $(1+a/N)^N=1+a+...$. Take the limit as N goes to infinity and we get $e^a$.

By similar reasoning, for a matrix M, you have $e^M=I+M+M^2/2+M^3/3!+...$

In quantum mechanics you can let $M=-i\hbar\Delta x_0 \hat{D}$ where $\hat{D}$ is the differential operator, $\frac{\partial}{\partial x}$ in one dimension.

Plugging it in you get:

$e^M=I+(-i\hbar \Delta x_0)\frac{\partial}{\partial x}/1!+(-i\hbar \Delta x_0)^2/2!\frac{\partial^2}{\partial x^2}+...$

So the exponential operator, which can be expressed as a matrix, is the sum of the powers of other Linear Operators. This operator being The Translation Operator


Find All Cycles (Faces) In a Graph I have a graph $G$ with a list of edges $E$, all the edges can form cycles, as shown below:

All the coordinates for the vertex $V$ are known.

Wat is the algorithm to find all the faces $F$? For the example above, there are 4 such faces, as indicated by the looping arrow.

Update: Why is it that the algorithm to find the face in the case without coordinate is different from the one with coordinates? Simply because by specifying the coordinates there is a unique set of faces, and without coordinates there could be sets of faces that are topologically equal. See the diagram below:

Update 2: Clear up the terminology

UPdate 3: It is suggested that I construct a cyclically linked list at each vertex, sorted according to the angles made between the incoming edge and the outgoing edge. Then one would just have to continue along the edge, but I afraid this algorithm doesn't work with the so called butterfly graph. Consider this graph:

Assume that we start at $e_1$, and the arrow denotes the direction of the movement. If we take the left turn as our orientation then we would be visiting $v_1$ twice before completing a cycle-- and the cycle is not really a cycle.

In  your previous question better use was made of graph theory terminology:  you refer to the graph as planar and to a cycle basis.

Assuming you understand those terms, perhaps I can point out how Mariano's answer builds on the earlier problem.  In fact here you asked, "Why is it that the algorithm to find the face in the case without coordinate is different from the one with coordinates?"  Although this is probably meant rhetorically to explain your assumption "All the coordinates for the [vertices] are known," it's important to point out that "faces" you've asked to find will depend on where the edges are as well as where the vertices are.

Let's illustrate with the complete graph on four vertices $K_4$.  Define planar coordinates for the vertices to be corners of the unit square {(0,0),(1,0),(1,1),(0,1)}.  There will be four edges, but we cannot take all of them to be straight line segments in the plane, since doing so produces an intersection (something a planar embedding of graph does not allow).

In fact depending on how you connect the vertices, you will get different faces.  Draw two squares (with four edges each), and connect one pair of "diagonal" vertices inside one square and the other pair inside the other square.  Now complete both graphs with an outside edge that connects the remaining diagonal pairs, looping over the square in one case and under the square in the other.  Two (or more) cases with different arrangments of "faces".

The point is that knowing a planar embedding well enough to make the "faces" cycle basis you're looking for unique requires you to "know the coordinates" of the edges as well as the vertices.

Mariano's answer focuses on the edges.  This has the nice effect of allowing us to count each edge as belonging to exactly two cycles or faces, once for each direction that the edge is travelled.  [No such simple statement will hold for the number of faces that a vertex appears in.]  However to make that "two cycles per edge" work, we must include the "unbounded face" or the cycle that runs all around the outside of the planar graph.  In the simplest case, a triangle say, we have a cycle that goes clockwise around it (following the direction you've used in your diagrams at top).  To get each edge appearing twice, once in each direction, we need to get a counterclockwise cycle.  You can think of one being the "finite" face bounded by the triangle, and the other being the face corresponding to the unbounded region outside the triangle.

When you ask Mariano to tell you how to "sort the edge[s] cyclically," I guess there are two aspects of this.  One is to understand what he means by that, and the other is to connect this task with how you "know the coordinates" of the graph including its edges.

What Mariano means is just to know, when we arrive at a vertex along one "inbound edge", what will be the right "outbound edge" to take next?  Let's suppose you want to construct all the "finite" faces going in the clockwise direction, as in your diagrams.  Then you would need to sort the edges around each vertex into a cyclically linked "list" that goes around the vertex in the counterclockwise direction.  This "list" wraps around; it has no specific beginning or ending edge.  It also does not distinguish the directions of travel along the edge.  It just tells us, for all the edges at a given vertex, which follows which going counterclockwise around the vertex.

Now we can elaborate Mariano's solution to your question.  For each edge and each direction of travel along that edge, build a cycle by this algorithm:

Algorithm FollowYourNose
(1) Follow the given edge in the given direction to its end vertex.
(2) Consult the cyclically linked list of edges at that vertex to determine the next edge.
(3) Repeat steps (1) and (2) until you return to the original edge.
(4) Stop.  You have built a cycle that uses the given edge and given direction.

When you've done this for each edge and each direction, you will have a list of cycles that contains duplicates.  If a cycle contains $k$ edges, you will have built that same cycle $k$ times.  Discard the duplicates, leaving just one copy of each cycle.  [If it's important for performance reasons, we could keep track of which edges have been travelled in which directions and preemptively avoid creating the duplicates.]

You will then have one copy left of the cycle that corresponds to the unbounded face, the outside of the planar graph.  You want to remove that also.  Where all the cycles that correspond to the bounded faces are going in the clockwise direction, the cycle that corresponds to the unbounded face goes in the counterclockwise direction.  In fact it is algebraically minus the sum of all the clockwise/bounded face cycles.

Added: A cyclically linked list (or some would write, cyclic linked list) is a special case of  a linked list.  It means that the linked list comes around in cycle or loop.  No confusion with the "cycles" of the graph is intended here.  We are simply asking for some concrete way to systematically determine how to continue a path in the graph with each vertex we come to.  An informal description would be to say "bear right at each intersection".  Doing so will of course take us around the block in terms of ordinary street traffic, and it has a similar effect in navigating a planar graph.

What Mariano proposed was to answer the question of "which way to go" by sorting the edges that are incident to each vertex in an order corresponding to the angles at which they reach the vertex.  Think of standing in a intersection (vertex) of two or more streets (edges).  List them (the edges or streets) in the order they appear as you turn counterclockwise through one revolution, and use that list/ordering in the algorithm outlined by Mariano, so that when you enter an intersection (vertex) on one street (edge), you leave along the next one on the list (bear right!).

We should also be a bit careful about the kind of planar graph that the algorithm applies to.  If you are willing to accept certain degeneracies, then planar graph is good enough.  But consider the case of a single edge connecting two vertices.  What is the face?

If you wish to avoid such degeneracies, then assume a simple planar graph that is 2-connected.  What 2-connected means is that the graph is connected and remains connected even after any one edge is removed.  "Simple" means that there are no "self-edges" (edge that connects a vertex to itself) nor multiple edges connecting a single pair of vertices.

Regarding Update 3:  It is not suggested that you sort edges "according to the angles made between the incoming edge and the outgoing edge."  You are asked to make for each vertex a list of the edges ordered going counterclockwise around that vertex (a circular list if you will), without any regard to incoming or outgoing.  In your butterfly graph there is only one vertex with more than two edges, so only the list for that vertex requires care in sorting.

Worked Examples Involving Butterfly Graph

Let's consider first a planar embedding of the butterfly graph similar to what was once part of the Question:

   v2    v3    +e1: (x,v1)  -e1: (v1,x)
    |\   /|    +e2: (x,v2)  -e2: (v2,x)
    | \ / |    +e3: (x,v3)  -e3: (v3,x)
    |  X  |    +e4: (x,v4)  -e4: (v4,x)
    | / \ |    +e5: (v1,v2) -e5: (v2,v1)
    |/   \|    +e6: (v3,v4) -e6: (v4,v3)
   v1    v4

I've used plus and minus signs to (arbitrarily) assign directions for each of the six edges.  Only the center vertex x has more than two incident edges, so I'll be explicit about ordering the edges (without regard to incoming or outgoing direction) in counterclockwise order around x:

...e4,e3,e2,e1,e4,...

It should be clear that this is a circular list, that it repeats, looping through the same order of edges over and over again, which in data structures we would represent as a cyclically linked list.  Nothing more than the standard apparatus for linked lists is required to do this.  One simply makes the final node of the linked list point back to the first node of the linked list, and voila, a cyclically linked list.  But let's not confuse the details of the implementation with the details of the algorithm.  All that the algorithm requires is how to find the next edge at a vertex which is counterclockwise from a given edge at that vertex.  A cyclically linked list does that function, in that we would search the list linearly for the given edge at the given vertex, then take the next edge on the list.

Since there are six edges, there are twelve directed edges, and thus we will apply the algorithm FollowYourNose twelve times (once for each directed edge).  Each time we will get a cycle (a loop on edges).  Cycles may visit a vertex more than once but will never use an edge more than once (assuming the planar graph is simple and 2-connected).  However the twelve results will contain duplicates.  Once the duplicates are removed, there are just three unique cycles left:

[+e1,+e5,-e2]

[+e3,+e6,-e4]

[-e1,+e4,-e6,-e3,+e2,-e5]

It appears from the diagrams provided in the Question, that "faces" are meant to be the bounded components of the plane after the edges of the embedded graph are removed (thereby disconnecting the plane into one unbounded and finitely many bounded components).  So we should remove from the list of three cycles above that one which corresponds to the boundary of the unbounded component.

This distinction can be made algorithmically on the clockwise or counterclockwise orientation of the cycles.  The cycles that give "faces" are going clockwise around their bounded components.  The cycles which is a boundary of the unbounded component goes counterclockwise.  In this case it is the third cycle that should be discarded.

To illustrate how the distinction is made on the basis of clockwise orientation, and not on some other criterion such as which cycle has greatest length, let's look at another embedding of the butterfly graph:

           _ x _              +e1: (x,v1)  -e1: (v1,x)
         _/ / \ \_            +e2: (x,v2)  -e2: (v2,x)
       _/  /   \  \_          +e3: (x,v3)  -e3: (v3,x)
     _/   v2___v1   \_        +e4: (x,v4)  -e4: (v4,x)
    /                 \       +e5: (v1,v2) -e5: (v2,v1)
   v4_________________v3      +e6: (v3,v4) -e6: (v4,v3)

I have taken care to make the labelling of the edges with respect to the vertices the same here, as well as the orientations of the two 3-cycles in the plane the same.  The algorithm will now produce a different result based on the change in how the edges incident to vertex x are ordered going counterclockwise around that vertex:

...e4,e2,e1,e3,e4,...

Again we will apply algorithm FollowYourNose to each of the twelve directed edges and obtain twelve cycles, including duplicates.  After eliminating duplicates the following three cycles remain:

[+e1,+e5,-e2]

[+e3,+e6,-e4,+e2,-e5,-e1]

[+e4,-e6,-e3]

It is left to the reader to verify which of these has counterclockwise orientation and that it is not the longest of the three cycles.  The one with the counterclockwise orientation is the "outermost" and thus the boundary of the unbounded component of the plane\graph.

This was my project not so long ago.

I solved it in more than one way. But I will present you the easiest of the methods I used. Use quick fill inside of a region. Then find the lines that border the region.

It fails in certain situations, however, in most cases, those situations are not that serious anyway. If this method fails for you, post back and I will share the other methods that I used.


Concept of infimum of covers in Lebesgue outer measure The Lebesgue outer measure of of a set $E$ is denoted as $m^*(E),$ and defined as

$$m^*(E)=\inf\Bigg\{\sum_{k=1}^\infty \ell(I_k)\;\Bigg\vert \;E\subseteq   \bigcup_{k=1}^\infty I_k  \Bigg\}$$

where $\{I_k\}$ are collections of open intervals.

I understand that the idea is to extend the idea of measure to sets that are not all that intuitive, but I'm having problems picturing the "process" even in straightforward sets.

I have found that there isn't a single $\{I_k\}_{k=1}^\infty=\bigcup_{k=1}^\infty I_k ,$ but a collection: $$\Big\{\{I_k^1\}_{k=1}^\infty,\{I_k^2\}_{k=1}^\infty,\dots\Big\}$$

and for each one of them (i.e. covers) the calculation

$$\sum_{k=1}^\infty \ell(I_k)$$ is carried out. Eventually the infimum or greatest lower bound is calculated.

What is the need for these multiple collections of open intervals - at first sight it sounds like a process of approximation, where some unions of open intervals might be extremely redundant.

What is the process involved in this search for the infimum?

In the context of $\mathbb R$, explicitly naming the sequence of open intervals is not really necessary. Since every open subset of $\mathbb R$ is the union of such a countable sequence, you can restate the definition of outer measure as follows, first given an arbitrary open set $U = \cup \{ I_k: k \in \mathbb{N} \} \subset \mathbb R$ define,
$$ m^\ast(U) = \sum_{k=0}^\infty \ell(I_k)$$
then, extend the definition of $m^\ast$ to arbitrary subsets $E \subset \mathbb R$ by asserting $m^\ast(E) = $ $\inf \{ m^\ast(U): E \subset U \text{ and } U \text{ is open } \}$.

What does this simplification/restatement accomplish? It enables a cleaner analysis of the process by which the open sets $\mathcal{U} = \{ U \subset \mathbb{R}: U \text{ is open and } E\subset U\}$ are used to find the outer measure of $E$.

Recalling that the infimum $M = \inf \{ m^\ast(U): U \in \mathcal{U}\} = m^\ast(E)$ must satisfy,

  For every $\delta > 0$, there exist some $U \in \mathcal{U}$, such that, $ M \le m^\ast(U) < M - \delta$

we can choose/find/fix a sequence of open sets $U_0, \ldots, U_n, \ldots \in \mathcal{U}$ such that, for each $n\ge 0$,

$$ M \le m^\ast(U_n) < M - \frac{1}{2^n}. $$

Letting $V_n = U_0 \cap \ldots \cap U_n$, we get, $V_n \in \mathcal{U}$
(since $E \subset U_0 \cap \ldots \cap U_n = V_n$ and $V_n$ is open.) Moreover, applying the definition of $m^\ast$ for open sets, we have $V_{n+1} \subset V_n  \implies$ $m^\ast(V_{n+1}) \le m^\ast(V_n)$,and

$$ M \le m^\ast(V_n) \le  \min \{ m^\ast(U_0), \ldots, m^\ast(U_n) \} < M - \frac{1}{2^n}.$$

Putting this all together, we've extracted a descending sequence $V_n$ of open sets containing $E$, whose measures converge to the value of the outer measure $M = m^\ast(E)$ of $E$.

You can think of the sets $V_k$ as approximating $E$ by shrinking and progressively discarding non-essential segments. Moreover, capturing that processing is the whole idea behind how the outer measure is defined.


Partial Derivatives and defining a function. Define

  f(x,y) = x+2y and w = x+y.

What is $\frac{df}{dw}$? Does it make sense to define the partial derivative of a function f with respect to an arbitrary function w(not just x or y)? If so, what does this definition give for the specific example $f(x,y) = x+2y$ and $w = x+y$?

No, it's not meaningful unless you specify a coordinate system $(w,z)$ where $w$ is one of the coordinates. When computing $\partial f/\partial w$, you should first express $f$ in terms of $w$ and $z$, and then hold the other variable $z$ constant when you differentiate, so the result depends on what $z$ is.

Sometimes the notation
$$\left. \frac{\partial f}{\partial w} \right|_z$$
is used, to emphasize this.

$\dfrac{df}{dw} = \dfrac{df}{dx}\cdot \dfrac{dx}{dw} + \dfrac{df}{dy}\cdot \dfrac{dy}{dw}= \dfrac{\dfrac{df}{dx}}{\dfrac{dw}{dx}}+\dfrac{\dfrac{df}{dy}}{\dfrac{dw}{dy}}=\dfrac{1}{1}+\dfrac{2}{1}=3.$


parametrize surface region S is the elliptic region of the plane $y+z=1$ inside the cylinder $4x^2+4(y-0.5)^2=1$.
First parametrize $S$ using $(x,y,z)=G(u,v)$ and then calculate $\displaystyle \frac{dG}{du}\times \frac{dG}{dv}$.

How can I parametrize this crazy region??

Perhaps an additional question:  Find the centers of the Dandelin Spheres associated with this construction. Their points of tangency with the plane
are the foci of the ellipse.

The parametrization : $ x = u/2 \cos(v) , y = 1/2 + u/2 \sin(v) ,  z = 1/2 - u/2 \sin(v)$   with  $ v =[0,2\pi)$ and $ u = [0,1]$ seems to work.

$\newcommand{\+}{^{\dagger}}
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\down}{\downarrow}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\isdiv}{\,\left.\right\vert\,}
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left( #1 \right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}
 \newcommand{\wt}[1]{\widetilde{#1}}$
\begin{align}
x&\equiv \half\,\cos\pars{\theta}\,,\quad
y \equiv \half + \half\,\sin\pars{\theta}\,,\quad
z = 1 - y = \half - \half\,\sin\pars{\theta}\,;\qquad\qquad 0 \leq \theta < 2\pi
\end{align}

  $$
\vec{\rm r}\pars{\theta}
=\half\braces{%
\cos\pars{\theta}\,\hat{x} + \bracks{1 + \sin\pars{\theta}}\,\hat{y}
+ \bracks{1 - \sin\pars{\theta}}\,\hat{z}}
$$


For which integer values of $n$ does there exist an integer $m$ such that $n^{3} - m^{2} = -23$? For which integer values of $n$ does there exist an integer $m$ such that $n^{3} - m^{2} = -23$?

I'm having a lot of trouble with this one, any help would be appreciated :)

So far, I've seen that if the expression were a perfect square we would have:
$n^{3} + 23 = x^{2}$
For some integer $x$. From this I've deduced that $n^{3}$ must be congruent to $x^{2}$ modulo $23$, however, I'm not sure how to proceed.

Suppose that $n^3+23=m^2$ for some integers $n,m$.  Observe that
$$(n+3)(n^2-3n+9)=n^3+27=m^2+4.$$

If $m$ is odd, then $n$ is even.  Since $m^2\equiv 1\pmod{8}$, we must get $n^3\equiv 1-23\equiv 2\pmod{8}$.  However, this is impossible as $n^3\equiv 0\pmod{8}$ for every even integer $n$.  Thus $m$ is even.

Since $m$ is even, say $m=2k$, we get that $n$ is odd.  Because $m^2\equiv 0\pmod{4}$, we obtain $n^3\equiv -23\equiv 1\pmod{4}$.  Thus $n\equiv 1\pmod{4}$.  That is,
$$k^2+1=\frac{m^2+4}{4}=\frac{n+3}{4}\left(n^2-3n+9\right).$$
Since $n\equiv 1\pmod{4}$, we must have
$$n^2-3n+9\equiv 1-3+9\equiv 3\pmod{4}.$$
Because $n^2-3n+9>0$, we conclude that a prime natural number $p\equiv 3\pmod{4}$ must divide $n^2-3n+9$.  Thus, $k^2+1$ is divisible by $p$, so that $-1$ is a quadratic residue modulo $p$, which implies that $p\equiv 1\pmod{4}$.  This is a contradiction.

Hint: Try to prove that every perfect square is congruent to $0$ or $1(mod 4$).


Why do un-integrable functions exist? By un-integrable I mean functions whose antiderivative can not be expressed in terms of elementary functions.

I recently learnt that any differentiable function can be expanded using the Taylor expansion, which essentially provides a polynomial representation. And polynomial funcitons are very easy to integrate. Then, why is it that there are functions whose antiderivative can not be expressed in terms of elementary functions?

Two reasons:

1) Not all integrable functions are differentiable, not all differentiable functions are smooth (i.e., have derivatives of all orders, which is necessary for the series to exist), and not all smooth functions converge to their Taylor series. The canonical example for the latter is $f(x) = e^{-1/x^2}$ (with $f(0) = 0$), which is smooth with $f^{(n)}(0) = 0$ for all $n$ and thus has a Taylor series around $0$ that's exactly $0$.

2) An arbitrary Taylor series is not a polynomial or even an elementary function. Take $\operatorname{erf}(x) = \frac{2}{\sqrt{\pi}}\int_0^x dt\; e^{-t^2}$, for example, or $\Gamma(x) = \int_0^\infty dt\;t^{x-1}e^{-t}$.

The definition of Taylor expansion can be loosely defined as "The best polynomial approximation of $f(x)$ near $a$", which means that the approximation gets worse and worse as the neighborhood of $a$ gets larger. Therefore the Taylor expansion is not a sufficient approximation with all values of $x$. More than that, sometimes the Taylor expansion of a function is infinite, and infinite sum of polynomials is not an elementary function.


How to show that a Dyck-Language $K$ is equals to $L$? let $L,K\subseteq \Sigma^*$ be Languages over $\Sigma=\{(,)\}$.

$L$ is defined as follows :

1- $\epsilon \in L$

2- $u,v \in L \Rightarrow uv\in L $

3- $u\in L \Rightarrow (u)\in L$

4- a String is only in $L$, if it's according to the above mentioned Rules in $L$

$K = \{w\in \Sigma^*|\: |w|_(=|w|_)\wedge \forall u,v : uv =w,|u|_(\ge|u|_)\}.$

i want to show that $L=K$, but i don't exactly understand the definition of $L$.

now i know that $K$ is the same one from https://en.wikipedia.org/wiki/Dyck_language right ?

1- What is the use of the Rule 4 in $L$ ?

2- is a String like $(^nw)^n$ in $L$ ?

3- how to show the equality of $L$ and $K$ ?

Rule 4 seems to clarify the role of the first three rules; that is, $x \in L$ if and only if $x$ can be constructed using the first three rules. One might interpret the rules as stating that "if $x$ can be constructed by the rules, then $x \in L$", without the converse statement. Rule 4 avoids this ambiguity.
Are you assuming $w \in L$? If so, then by rule 3, $(w) \in L$, so we can apply rule 3 to $(w)$, meaning $((w)) \in L$, etc. This repeated application of rule 3 shows that $(^n w )^n \in L$.
Hint: To prove that $L = K$, you need to show that for all strings $x$, $x \in L$ if and only if $x \in K$. To do this, first take any $x_L \in L$, and show that $x_L \in K$ must be true. Then, take any $x_K \in K$, and show that $x_K \in L$ must be true. You will certainly need to use the definitions of $L$ and $K$ to make these arguments.

$L$ is indeed the language of balanced parentheses, the one you cite is an inductive definition. Rule 4 is there to ensure that no word other than those that may be obtained with rules 1-3 is in the language.

Proving equality is trivial by structural induction. (Hint: if the parentheses are well-matched, then there must be a pair of external ones...)


Langley's Adventitious Angles I've been running in circles and couldn't give a rigorous mathematical proof that the angle is x = 20°.

Any idea? This is my try:

I got the answer $x=20^\circ$ using a computer program: https://www.geogebra.org/classic/qt79hpec

This is a variant of the original Langley's puzzle and it does have a geometric solution, albeit a bit involved.  Below is a straightforward trigonometric solution. Apply the sine rule to the triangles ADE, ADB and BDE,

$$\frac{\sin x}{\sin 10}\cdot \frac{\sin 20}{\sin (30+x)}\cdot \frac{\sin 80}{\sin 60}
=\frac{DA}{DE}\cdot \frac{DE}{DB}\cdot \frac{DB}{DA} = 1$$

which simplifies to

$$2\cos^210\sin x = \sin60\sin(30+x) =\frac{\sqrt3}4\cos x + \frac{3}4\sin x$$

Solve for $\tan x$,

$$\begin{align}
\tan x  & = \frac{\sqrt3}{1+4\cos 20}  = \frac{\sqrt3\sin 20}{(\sin 20 +\sin 40 )+ \sin40} \\
& = \frac{\sqrt3\sin 20}{2\sin30\cos10 +\sin 40} = \frac{\sqrt3\sin 20}{\sin 80 +\sin 40} = \frac{\sqrt3\sin 20}{\sqrt3\cos 20}  =\tan 20 \\
\end{align}$$

Thus, $x = 20$.

The large triangle is isosceles. Let the left base angle be $B.$ Them in the triangle $BCE,$ we find that $B=10°,$ as given, then $C=20°$ (consider the large isosceles triangle). Thus, we have that $C\hat E D=(70+60+20)°=150°.$ Hence we have that $$150+x+10+20=180.$$ This shows us that  $x=0,$ or in other words that the configuration is impossible.


How can the probability that a number contains the digit 3 be 1? Based on this Numberphile video which claims almost all integers contain a $3$, I have a few questions on the reasoning behind recurring decimal numbers like $0.9999\ldots =1$

What they have shown is that $$\lim_{n \to + \infty} \frac{10^n-9^n}{10^n} = 1$$

this basically means that probability of eg. a $3$ occurring in a set of numbers like for $1-10, 1-100,$ increases as the upper bound gets large.

So you are more likely to see a $3$ when you take $1-100000$, than $1-10$ as the probability gets higher.

So what I would like to know is as '$n$' approaches $∞$ does probability of seeing a '$3$' equals $0.99999....$?

But since $0.9999... = 1$ wouldn't this not make sense, since there are infinitely many numbers that do not have a '$3$'?

All I need is for an explanation as to why this logic is wrong. Simpler answers are most appreciated.

Note

I am not looking for the reason as to why 0.9999...=1.

The probability increases as the range increases, like you say; the probability that a 3 appears when we choose a random number between 1 and 100000 is much greater than when we pick a number between 1 and 100.  As we let the range increase, the probability increases; when we do not have an upper bound, the probability is $0.999\ldots = 1$.  So yes, the probability that, taking a completely random integer, it has a 3 as one of its digits is 1.

Ok now wait; there are lots of integers without a 3 (infinitely many), so how can this be?

The problem is the interpretation of "probability 1". We tend to think this means that taking a random number, it would be impossible for it not to contain a 3 (which is clearly not true).  But this interpretation only works when we are talking about the probability of an event from a finite sample space. When the number of possibilities are infinite (as in this situation, where there are infinitely many integers to choose from), this has a slightly different meaning. It means that the event happens "almost surely". So taking a random number, the probability it does not contain a 3 is zero, but is not impossible. It would just be like splitting an atom when you throw a dart at a dartboard.

The logic is both right and wrong, depending what kind of math you're using. But I'm a programmer, rather than a mathematician, so take what I say with a pinch of salt.

In programming at least, once you start working with different infinities, perhaps using libraries which allow you to handle the Aleph numbers of well ordered infinite sets, you also start playing with different kinds of zeroes, or rather, with different kinds of infinitesimals, which get all called "zero" in almost all branches of mathematics (algebra, calculus), in the same way as they treat all types of infinity as a single "inverse-zero", 1/0, the conceptual "upper bound" of the integers.

Once you start using math that is aware of relative infinities, then 0.999... is not one, it's just infinitesimally far from one. The fact that there are two ways of thinking about this, mathematically, is why there are so many arguments about it: as in all great arguments, both sides are right.

If you are using math which is aware of infinite sets, then 0.999... != 1, but 0.999... == 1 - (1/infinity).

If we randomly select an integer, the chance of there being few enough digits in it that we could express just its magnitude (even using shortcuts like powers of powers, terms like "googol" and "graham's number", or knuth's up-arrow notation) in a single lifetime is infinitesimal: there are only a finite number of magnitudes that we can express, and an infinite number of magnitudes.

Since "everyone knows" that dividing any integer by infinity gives zero, then there are apparently zero integers that we can express. But using math which is aware of different infinities, there aren't zero: just an infinitesimally small fraction of integers that we can express.

The chance of it being a number without a 3 in it, is infinitely larger than that. Because there is an infinite quantity of numbers with no 3s in, and only a finite list of numbers that could not be expressed by humans.

But it is still infinitesimally small, because for every number with no threes, there is an infinite number that does contain threes.

Picturing no-threes is hard. I find this easier to picture when considering the "countable" integers and the uncountable 'real' numbers between. It's clear to me that there are infinite integers; between each of those, there are infinite real numbers.

The chances of hitting an integer when panning through the numbers from 0.5 to 1.5, are 100%. The chances of randomly selecting an integer in a random pick form that range are infinitudinously small.


Prove using congruences that $ 7\mid\left(5^{2n}+3\cdot 2^{5n-2}\right)$ , $n \ge 1$ Prove using congruences that:
$$ 7\mid\left(5^{2n}+3\cdot2^{5n-2}\right)$$
(is divisible by 7)
So I'm trying to use mathematical induction to show that for all integers $n \ge 1$
but i cant prove this!!

Claim : $$5^{2n}+3\times 2^{5n-2}\equiv 0\pmod 7$$ for $n\ge 1$

Base case : $25+3\times2^3=25+24=49\equiv 0\pmod 7$

Induction step

$$5^{2n+2}+3\times 2^{5n+3}=25\times 5^{2n}+96\times 2^{5n-2}=25\times(5^{2n}+3\times 2^{5n-2})+21\times 2^{5n-2}$$

I think you can finish the proof now.

Let's call the expression f(n). For n=k, assume that 7|f(k) --> 7|5^(2k)+3*2^(5k-2). Then multiply the expression by $5^2*2^5$ and it is still divisible by 7. So we get 2^5*5^(2k+2)+5^2*3*2^(5k+3) which is equivalent to 4*5^(2k+2)+4*3*2^(5k+3) mod 7. 7 divides the expression and 4 and 7 are co-primes. So,7|5^(2k+2)+3*2^(5k+3) and the last expression is equal to f(k+1) (7|f(k+1)).


Noetherian ring that isn't euclidean? Can anyone give me an example of one? I know it's equivalent to finding a noetherian that isn't PID, but I'm not sure!

The ring of integers of $\mathbb{Q}(\sqrt{-19})$ is a principal ideal domain that is not Euclidean.


pointwise $\implies$ uniform? (Dini's theorem) Is this right?
If $f_{n}(x):C \rightarrow \mathbb{R}$ is continuous, $C$ is compact, and $f_{n}(x)$ converges to $f(x)$ pointwisely for each $x$ in $C$, and $f(x)$ is continuous, then $f_{n}(x)$ converges to $f(x)$ uniformly on $C$.
I thought that since $C$ is compact, and each $f_{n}, f$ is continuous, by extreme value theorem, there exists $c$ in $C$ s.t $f_{n}(c)-f(c)=\sup|f_{n}(x)-f(x)|$ and $f_{n}(c) \rightarrow f(c)$ as $n \rightarrow \infty$, so we get $\limsup|f_{n}-f|=0$.
I know that if I add a condition that $f_{n}$ is monotone, then this is Dini's theorem, but I don't know why we need that condition. Where am I wrong?

Probably the most prominent counterexample is the following. Let $f_n:[0,1]\to\mathbb{R}$ be such that

$$f_n(x)=\begin{cases}n^2x& x\in[0,1/n]\\ 2n-n^2x& x\in[1/n,2/n]\\0& \text{otherwise}
\end{cases}$$

Then $f_n$ converges poitnwise to $f=0$ which is continuous but $||f_n-f||_\infty=n$ hence we do not obtain uniform convergence!

Edit: As you see here, the existence of $c$ u claimed is precsiley the point $c_n=1/n$. Particularly, $c_n$ depends on $n$, hence the argument with the pointwise convergence for a fixed $c$ fails.

Dini's theorem requires that the sequence $\{f_n(x)\}$ is monotone!  (it.wikipedia.org/wiki/Lemma_di_Dini)