Mathematics - 2022-08-07

Warm-up: Say $R$ is a program that searches all proofs (in some fixed proof system such as ZFC). If it finds a proof that $R$ doesn't halt, it halts. If it finds a proof that $R$ halts, it enters an infinite loop. Does $R$ halt or not?

Note: it is perfectly OK for $R$ to check things against its own source code, using a standard trick called "quining".

Actual puzzle: Say $M$ is a program that searches all proofs (in ZFC, say), with the following behavior: if it finds a proof that $M$ halts, it halts. Otherwise, it keeps on searching proofs forever. Does $M$ halt or not?

Bonus puzzle: Say $L$ is a program that searches proofs, programmed with the following behavior: If it finds a proof that $L$ halts, it halts, and if it finds a proof that $L$ doesn't halt, it enters an explicit infinite loop. Does $L$ halt or not? Isn't this the same as $M$? (It isn't.)

rot13 for spoilers: E: qbrfa'g unyg, naq gurer'f ab cebbs (va MSP) bs guvf. Z: fhecevfvatyl, qbrf unyg, naq gurer vf n cebbs bs guvf. Y: hayvxr gur cerivbhf gjb, guvf qrcraqf ba ubj rknpgyl Y vf pbqrq (fbzr vzcyrzragngvbaf jvyy unyg naq fbzr jvyy abg).

Jakobian

ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn

Looks similiar

leslie townes

5:18 AM

my interest in godel-land halted a long time ago

copper.hat

5:38 AM

yeah, systems with arithmetic are just fundamentally flawed

Akiva Weinberger

5:58 AM

copper.hat

6:13 AM

:-)

user4539917

6:36 AM

(•‿•)

user4539917

7:38 AM

Why study the history of mathematics/science

ypercubeᵀᴹ

8:21 AM

@AkivaWeinberger where is that silly poster from?

user4539917

8:36 AM

Looks kinda self-made to me.

Akiva Weinberger

9:16 AM

@ypercubeᵀᴹ It's a meme

knowyourmeme.com/memes/stop-doing-math

(and, to be clear, it is a joke)

SHASHAANK B.H.

10:23 AM

Btw May I know when to integrate the problem with substitution or by parts, How to get that intuition?

Any way can I find out how to integrate the function?

Doesn't the Trick to remember selection of u and v (ILATE) fail for integral of the form e^ax cosbxdx?

because e^ax was taken as u

RaMathuzen

10:43 AM

Hi everyone, I was just reading this paper (arxiv.org/pdf/2204.06324.pdf) which is about using Rank-One approximation as a strategy to solve Wordle. I have a question related to it that is "How the Rank One approximation gives a dominant eigen vector $u_{1}$ that becomes most probable word that can match with a secret word of Wordle.

More Anonymous

2:56 PM

Is anyone familiar with spin vectors?

i saw them in this book

Spinors and Space-Time Volume 1 - Penrose and Rindler

Akiva Weinberger

4:46 PM

@SHASHAANKB.H. You can do it with integration by parts, but if you know Euler's identity (e^ix=cosx+i sinx) then there's a much easier way

Ted Shifrin

@SHASHAANKB.H. The intuition is that integration by parts is usually appropriate when trying to integrate the product of very different sorts of functions. Sometimes you have to ("cleverly") repeat the integration by parts. $\int x^2e^x\,dx$ is an example of that. So is $\int e^{ax}\cos(bx)\,dx$ — you just have to be careful when you do the second one not to just undo what you just did.

Lukas Heger

Hey @Ted

I finally found a proof of De Rham's theorem that I like

Ted Shifrin

Hi, Lukas. Yeah?

Lukas Heger

the idea is quite simple: Let $M$ be a smooth manifold. For $U \subset M$, we have the space $\Omega^p(U)$, so we may consider $\Omega^p$ to be a presheaf on $M$ and in fact it is a sheaf. Poincaré's lemma shows that the De Rham complex is a resolution of the constant sheaf. And by partition of unity, any sheaf of $C^\infty(M)$-modules is fine, so that's an acyclic resolution, so De Rham cohomology computes sheaf cohomology with values in $\Bbb R$.
On the other hand, for any open $U \subset M$, we can define the space of $\Bbb R$-valued singular cochains on $U$, in this way, we get a preshe…

no need to pass through smooth singular cohomology or something like that

though I guess we're invoking homological algebra a bit to see that different acyclic resolutions all compute the same sheaf cohomology

@Ted presumably you know a more elementary proof

Ted Shifrin

5:07 PM

Yeah, just a Mayer-Vietoris argument, basically, but I like the sheaf proof. Bott/Tu and Spivak both have good proofs.

Warner's book essentially does the sheaf argument.

Lukas Heger

@TedShifrin oh yeah the good old Mayer-Vietoris + 5 lemma + induction argument

iirc that's how we proved Poincaré duality or something

Ted Shifrin

Right. I haven't thought about this in decades, but yeah.

Thorgott

yeah, though these are essentially sheaf-theoretic proofs distilled into more accessible language

Poincaré duality can be proven similarly

iirc the business about sheafifying cochain presheafs and observing that doesn't destroy the cohomology is really annoying, though

Lukas Heger

@Thorgott hmm? Sheafification is an exact functor

it doesn't change cohomology

Thorgott

after taking global sections, I mean

Lukas Heger

5:15 PM

oh I see

Thorgott

www-personal.umich.edu/~mmustata/SingSheafcoho.pdf

this business, essentially

Koro

93% humidity where I am right now.

Lukas Heger

@Thorgott I see yeah that was some detail I didn't think about, but yeah that is what I had in mind

Ted Shifrin

Yeah, it is a pain. This is the sort of thing I just said, "Yeah, sure" and went on my way.

It's just part of the global warming hoax, @Koro.

Thorgott

yeah, a devil in the details kind of thing

copper.hat

6:08 PM

this deletion of questions is very aggravating

Koro

6:39 PM

Aug 4 at 17:02, by Koro

2 hours ago, by Koro

can anyone please suggest a beginner a book on multivariable calculus that also covers operator norms, path connectedness etc. ? Thanks.

and the problems like GL(n,R) is connected or not etc.

Ted Shifrin

That is a totally off-the-wall question, @Koro. My book has operator norm (without calling it "operator") and alludes to path-connectedness in an exercise. The former is appropriate in a multivariable analysis book that proves theorems; the latter is sorta tangential.

That isn't multivariable; that requires linear algebra tools, Koro.

Whisper your suspicion to me, copper.

Koro

professor Ted, it was solved something like this: let $\alpha: [0,1]\to "determinants"$ be a continuous map, called path; and then $\alpha(0)=|I|$ and $\alpha(1)$= determinant of matrix obtained by changing two columns of I =-1. So by IVT, $\alpha $ attains 0. This somehow shows that GL(n, R) is not connected. I didn't understand it actually. :(

Ted Shifrin

Seeing $GL(n)$ is disconnected is easy. It's just the intermediate value theorem. However, seeing that $GL^+(n)$ is connected is much harder.

Koro

is this covered in your book, professor Ted?

Ted Shifrin

No, the intermediate value theorem is single-variable calculus. It does show up in some exercises in my book, yes.

I do a little bit of point-set topology (basic open, closed, compact stuff), not in the most general point-set way, but to be used in the context of subsets of $\Bbb R^n$.

All they're saying is that if you join a matrix with positive determinant to a matrix with negative determinant with a path, then by continuity of the determinant function (that is in my book) somewhere along the path the determinant must be $0$, contradicting nonsingularity of the matrices.

Koro

6:49 PM

@TedShifrin no, I didn't mean IVT. I meant the problems like showing GL (n, R) is connected or not; O(n, R) is connected or not etc. Also, I want to know how the the following series for a matrix A makes sense: $I+A+A^2/2!+...$.

Ted Shifrin

Yes, that is in an exercise in my book. Absolute convergence implies convergence, etc.

But it's not the main thrust of the text to prove all these things in the text.

That is proved using the operator norm, for example, although I just call it norm (defined in the chapter on compactness).

The norm is essential for the proof of the inverse/implicit function theorem, for example.

Koro

@TedShifrin I'll look that up. Thanks. :)

Ted Shifrin

My book also includes standard linear algebra material, integrated in with the multivariable. One of the final exercises is a very cool and famous linear algebra result, called Sylvester's law (relating the signature of a symmetric matrix to the number of positive/negative eigenvalues).

copper.hat

@Koro The sequence $1+\|A\| + ... = e^{\|A\|}$, so the sequence of matrices converges absolutely.

Koro

@TedShifrin yes, the confusion I had (have) is why such a path exists? Because if existence is there then, we have pretty much answered the question. This is because path by definition is continuous and so intermediate value theorem holds.

Ted Shifrin

6:55 PM

For open subsets of Euclidean space, prove that path connectedness is equivalent to connectedness.

True on manifolds, too.

If connected, then path connected, whence contradiction. Therefore ...

@copper Most people don't know absolute convergence implies convergence in a Banach space :)

I proved it for finite-dimensional vector spaces in my book, though.

Koro

people like me don't yet even know what Banach space is :).

@copper.hat yes!! $||I+A+...||<=1+||A||+...=e^{||A||}$

Ted Shifrin

Well, no, $\le$ some more. You need to know/prove that $\|A^k\|\le \|A\|^k$. Very important.

Koro

to be more precise, I should use Cauchy criteria, i.e., $||S_n-S_m||$, where $S_n:=I+\sum _{k=1}^n \frac{A^k}{k!}$

Ted Shifrin

Yes, so you still need to argue that the space of $n\times n$ matrices with the norm is complete.

I avoided that in my book.

Koro

Ohh I see.

But that follows from "norms on finite dimensional vector spaces are equivalent,i.e., they generate the same topology."?

hmm may be not. I'll think more about this one.

Ted Shifrin

7:03 PM

But you absolutely need a norm with the multiplicative property I mentioned: $\|AB\|\le \|A\|\|B\|$.

2

Pun intended.

Lukas Heger

@TedShifrin fun fact, you can reverse that: a normed space is Banach iff absolute convergence implies convergence

probably not really useful (or fun)

Ted Shifrin

LOL ... If it's not fun, why are you assigning it as homework?

Koro

Banach space, Applach Space, Guavavach space, Spinach space.

Lukas Heger

the category of Banach analytic manifolds is called BanAnaMan

@TedShifrin totally random thought (maybe this question is more suited for Balarka): can you prove Sylvester's law by Morse theory?

oh no probably it's the other way around

you need Sylvester to make sense of Morse theory

nevermind

Ted Shifrin

I don't see how Morse theory is going to recognize the difference between a bilinear form and a linear map.

Lukas Heger

7:15 PM

the Hessian transforms like a bilnear form and the Jacobi matrix like a linear map

Ted Shifrin

Yes, the Hessian is a bilinear form. But I don't follow you.

I guess the intrinsic derivative comes in here, too.

Lukas Heger

I was thinking about the index at a non-degenerate critical point

copper.hat

@Koro There is a cute (I think) proof of the path connectivity of $GL(n, \mathbb{C})$ here math.stackexchange.com/a/139595/27978

Lukas Heger

I think you need Sylvester to make that well-defined

@copper.hat $\mathrm{GL}_n(\Bbb C)$ is irreducible in the Zariski topology, because it's open in affine space, so it's connected by GAGA it's connected in the analytic topology, too. For manifolds, connected implies path-connected

Ted Shifrin

→ 8 messages moved to Trash

copper.hat

7:20 PM

@LukasHeger Yep, I know, but I think the use of the exponential to show an explicit path is cute.

i'm a minimalist :-) except when it comes to overreaction.

Ted Shifrin

Yes, that is true. I've expunged you, by the way.

copper.hat

Thanks!

Lukas Heger

@Ted I think I just had it backwards. I thought that Morse theory proves that the index at a non-degenerate critical point is well-defined, independently from Sylvester, that could be used to prove Sylvester I think, but I guess that'd be circular

I never looked at proofs for anything in Morse theory...

Ted Shifrin

Well, it depends on your definition of index, too. The usual differential topology blends Sylvester in and uses eigenvalues, I think.

But that's not the "right" definition.

Lukas Heger

what's the right one?

Koro

7:25 PM

@copper.hat: That's very nice. Thank you! The answer shows existence of the path, which I doubted existed. But the answer involves log A, where A is a matrix. The existence of log A involves Cauchy contour integral, which I studied years ago. It'll take me some time to fully understand the answer :).

Ted Shifrin

Talk just about bilinear forms; largest possible positive-definite subspace, etc.

In my book, I did the $LDL^\top$ representation of symmetric matrices. Then we count positives/negatives/zeroes of $D$.

Completely different from eigenvalues. So it's actually rather a stunning result. :)

Lukas Heger

That's how we did it in our linear algebra course

and then the stuff about eigenvalues was an exercise

Ted Shifrin

That's a nontrivial exercise. Especially if there is a nullspace. But I have it as the last exercise of my book.

OK, time for lunch.

Thorgott

8:17 PM

@Koro perhaps you will find some enjoyment in Tapp's "Matrix Groups for Undergraduates"

Ted Shifrin

8:35 PM

Or Curtis's book Matrix Groups.

Thorgott

personally, the only way I actually remember why $GL^+(n;\mathbb{R})$ is path-connected is that a) Gram-Schmidt implies $GL^+(n;\mathbb{R})$ deformation retracts onto $SO(n;\mathbb{R})$, so they are homotopy-equivalent and b) $SO(n;\mathbb{R})$ is path-connected by inducting from the trivial case $n=1$ by using the fiber bundles $SO(n-1;\mathbb{R})\rightarrow SO(n;\mathbb{R})\rightarrow S^{n-1}$ and the fact that path-connected base + path-connected fiber implies path-connected total space

yes, it's overkill, but I think it's cute

I don't remember what the honest way is to be honest, using the ugly JNF?

Ted Shifrin

You can do a normal form for $SO(n)$ (coming from the spectral theorem).

Jordan (or upper triangularizing) won't help, as there can be even numbers of negative eigenvalues, so it's hard to join?

Thorgott

8:51 PM

you can get rid of those in pairs by connecting $\begin{pmatrix}-1&0\\0&-1\end{pmatrix}$ and $\begin{pmatrix}1&0\\0&1\end{pmatrix}$ via $\begin{pmatrix}\sin t&-\cos t\\\cos t&\sin t\end{pmatrix}$, no?

I always forget the spectral theorem exists to be honest, I never use it for some reason

Ted Shifrin

I love to use the spectral theorem wherever possible.

I was trying to avoid Jordan, because then you have to leave $\Bbb R$. Your suggestion certainly leaves upper triangular, but should work. Actually, I think Guillemin & Pollack have an exercise by induction that probably uses your idea rather than mine.

When I assigned it, I always wanted my students to learn the normal form for $SO(n)$, so I hinted along those lines.

Thorgott

there's a JNF for $\mathbb{R}$ too, but I didn't wanna think about the uglier blocks

what's the normal form for $SO(n)$? the Iwasawa decomposition or how it's called?

Ted Shifrin

Yeah, the uglier blocks are quite like the block form for $SO(n)$, of course.

No, just a bunch of $2\times 2$ block rotation matrices.

Thorgott

I think you can replace part b) of my argument with something more explicit. You just need to compose an element of $SO(n;\mathbb{R})$ with a rotation (not changing the path-component as those are connected to the identity) so that it fixes $e_1$ and then you're down to $SO(n-1;\mathbb{R})$.

Oh right, it's all just rotations and reflections. I used to know this.

Ted Shifrin

Yeah, there are inductive arguments, as I already said.

Anyhow, the point stands that this is more linear algebra than anything else, which was my issue to Koro.

Lukas Heger

9:14 PM

another approach: retract to $\mathrm{SL}_n(\Bbb R)$, this is generated by elementary matrices of the type $E_{x,y}(a)$, where this matrix differs from the identity matrix only at the off-diagonal place $(x,y)$, where it has value $a$. So it suffices to show that there's a path connecting $M$ and $E_{x,y}(a)M$ inside $\mathrm{SL}_n(\Bbb R)$. This is easily done, just conside the path $t \mapsto E_{x,y}(ta)M$

still linear algebra, though

Gwyn

9:33 PM

Is it correct to argue that $(\mathbb{N} \setminus \{0\}, \cdot)$ with $a \cdot b=\max\{a,b\}$ for any $a,b \in \mathbb{N} \setminus \{0\}$ is not a group because for any $a \in \mathbb{N} \setminus \{0\}$ it is $\max\{a,a\}=a$ and, since $a \ge 1$, it is also $\max\{a,1\}=a$ and so for any $a \ge 2$ there would be two different identity elements, which is impossible in a group?

copper.hat

what would be the inverse of 2?

Akiva Weinberger

@Gwyn The fact that any element has only one other element that makes it stay the same, is a consequence of the group axioms. It might be nicer to investigate the axioms themselves though and find out which ones break.

Ted Shifrin

10:23 PM

@copper.hat How can I think about that if I don’t know what the identity is?

copper.hat

i was thinking that if $\max(n,e) = n$ for all $n$ then $e=1$.

Ted Shifrin

But that’s the issue the OP needs to understand, not muddying the waters with an inverse.

copper.hat

11:06 PM

muddying the waters is my speciality

Thorgott

it's also true groups only have one idempotent