Wikipedia:Reference desk/Archives/Mathematics/2021 November 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 22

C^∞ functions with compact support

What does that mean? My first reaction is that if it's C^∞ then it's analytic, so the Taylor series converges everywhere; but if it has compact support, then outside the supported region it is zero. So unless the function is 0 everywhere, there must be discontinuity in the derivatives, contradicting the premise of C^∞. Obviously this can't be right: what am I missing? Thanks. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 11:03, 22 November 2021 (UTC)

This is explained at Smoothness, especially at Smoothness § Differentiability classes and Smoothness § Relation to analyticity.

"The function f is said to be infinitely differentiable, smooth, or of class C^∞, if it has derivatives of all orders. The function f is said to be of class C^ω, or analytic, if f is smooth and if its Taylor series expansion around any point in its domain converges to the function in some neighborhood of the point. C^ω is thus strictly contained in C^∞."

See also Non-analytic smooth function and especially Non-analytic smooth function § A smooth function which is nowhere real analytic. —Tea2min (talk) 11:40, 22 November 2021 (UTC)

(Forgot to mention that, of course, complex functions are much nicer: Holomorphic functions are analytic. —Tea2min (talk) 11:49, 22 November 2021 (UTC))

"Nicer" is a value judgment. My reaction would be more "weirder". To me it's very strange that just being differentiable means that the functions are constrained to behave in such odd ways, for example not being bounded, and having integrals around a closed loop vanish.

Bump functions are what allow us to develop differential topology. The corresponding analysis in the analytic category is very different, and much less intuitively "topological". --Trovatore (talk) 18:32, 22 November 2021 (UTC)

The functions of class C^∞ with compact support are the so-called bump functions; like the class C^ω functions, they form a subset of the class C^∞ functions. These two subsets have one function in common: the constant function that has value 0 everywhere.  --Lambiam 13:47, 22 November 2021 (UTC)

@2602:24A:DE47:B8E0:1B43:29FD:A863:33CA: I'm curious, what led you to conclude that the Taylor series of a C^∞ function should converge everywhere? All the derivatives exist, which means you can write down the Taylor series, but I don't know why you thought it should necessarily converge. --Trovatore (talk) 18:38, 22 November 2021 (UTC)

You presumably wanted the domain to be $\mathbb {R}$, but if not, you can also just restrict the domain of the C^∞ function to a compact set and now you have compact support. JoelleJay (talk) 20:00, 22 November 2021 (UTC)

Thanks everyone. I had thought for some reason that the C in C^∞ stood for "complex", i.e. it referred to complex-valued functions with continuous derivatives, which are necessarily analytic. But I seem to remember now that it instead stands for "continuous". The article Non-analytic smooth function made it clear refers to real-valued functions on the reals, which can be smooth on the reals while having sharp discontinuities on $\mathbb {C}$, such as in the example near the top of the article. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 18:58, 22 November 2021 (UTC)

Does PA + ¬G have a Gödel-proof-number of any statement?

The answer to this one is probably yes, I'd just like to make sure I'm reading this right.

I'm re-reading Gödel, Escher, Bach, and I'm thinking about PA + ¬G, an extension of Peano arithmetic with the negation of Gödel's statement as an additional axiom. This system is consistent if PA is consistent, and since G roughly means "There is no Gödel-proof-number of G", then in the extended system there is one; and furthermore it is necessarily a nonstandard number, since for every standard number, we can separately prove that it's not the Gödel-proof-number of G. So far so good.

Here's the question. Since ¬G, being an axiom, has a trivial proof consisting of just itself, it also has a Gödel-proof-number — so do I understand correctly that by Gödel-numbering the principle of explosion, in PA + ¬G we can obtain a Gödel-proof-number of absolutely any statement, even 0=1, thus completely losing the ability to Gödel-number sound proofs of theorems, and only them? A second question would be: with our original Gödel numbering scheme rendered useless, would it be possible to define a different Gödel numbering for PA + ¬G that would restore our ability to arithmetically differentiate proofs of theorems from unsound "proofs" of nontheorems? - Linneris (talk) 18:47, 22 November 2021 (UTC)

No. The statement G is true, in the sense that it makes a true claim about the natural numbers. But it isn't provable in PA (or in PA+¬G), so there isn't a Gödel number for a proof in PA (or even in PA+¬G) of G.

It's true that for every natural number n, you can prove "n is not the Gödel number of a proof of G in PA+¬G". But you can't collect those infinitely many proofs into a single proof of G. --Trovatore (talk) 18:55, 22 November 2021 (UTC)

From what I understand (again from reading GEB), G is true in the standard model of PA, but there exist models of PA in which it's false. (If it was true in every model, then by Gödel's completeness theorem it would be provable.) In particular, wouldn't G necessarily be false in every model of PA + ¬G? - Linneris (talk) 19:11, 22 November 2021 (UTC)

Your first statement is true; there are nonstandard models that falsify G. However G is true full stop. For a statement of arithmetic, "true" means exactly the same thing as "true in the standard model". I find it a little confusing to drag in the phrase "in the standard model", because it makes it sound complicated, whereas it's really very simple: G makes an assertion that every natural number has a certain property, and in fact, every natural number does have that property.

Your second statement is also true; G is false in every model of PA+¬G. I'm not sure how you're getting from that to the idea that you can find a Gödel number for a PA+¬G-proof of 0=1. --Trovatore (talk) 20:00, 22 November 2021 (UTC)

Oh, looked over this discussion a little bit, and maybe I see what your intended argument is. Is it something like this?

1. There is a model M that satisfies PA+¬G
2. Since M satisfies ¬G, there is an element n of M, a nonstandard natural, such that M satisfies the claim "n is the Gödel number of a PA-proof of G"
3. But for any natural number n, PA also proves "n is not the Gödel number of a PA-proof of G"

The problem is that the n of step 2 is a nonstandard natural, which means it's not actually a natural number at all. It's just an object that M thinks is a natural number, but M is wrong about that. Therefore step 3 does not apply; PA does not prove the statement "n is not the Gödel number of a PA-proof of G" for the n under consideration, because it's not a natural number. (Actually PA in general doesn't even have a way to talk about this n, so you can't even state the claim that we want to know whether PA proves it, but that's a distraction at the current time.) --Trovatore (talk) 01:27, 23 November 2021 (UTC)

But I think the question is whether, in a model of PA+¬G, there is even a nonstandard natural that codes a proof that 1=0. And I believe the answer is no, because that would mean 1=0 in the model, but we know that there are no models where 1=0 because 1≠0 is provable in PA. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 03:34, 23 November 2021 (UTC)

Thanks for the extended reply! It clarifies matters. My train of thought went like this:

1. PA+¬G proves that "there is a number that is the Gödel number of a proof of G".
2. Therefore, there is an element n of M, a nonstandard natural, that M thinks is the Gödel number of a proof of G. But it can't actually encode a proof of G, since G is not a theorem of PA+¬G.
3. Therefore (thought I), in M, if one follows all the rules for constructing a Gödel number of a proof, it is nonetheless possible — if nonstandard numbers are used — to Gödel-number something that is not a proof.
4. Now, and that is my original question, what happens if we append the Gödel number of ¬G to n, like we would do when adding an extra step to a normal Gödel-numbered proof? Would M think (in the same sense that it thinks n Gödel-numbers a proof of G) that this new Gödel number encodes a proof of a contradiction? And so, thought I, from this number, we can construct yet a third nonstandard Gödel number that "encodes a proof" of 0=1 in the same wrong sense that n supposedly "encodes a proof" of G?

Or, since n is nonstandard, it doesn't make sense to say that it "follows the rules"? Or does it make no sense to talk about appending steps to nonstandard Gödel numbers like n? - Linneris (talk) 05:44, 23 November 2021 (UTC)

@Linneris: I think it turns out that the interpretation of the arithmetization of predicate "n is a proof of σ", when n is nonstandard, turns out to be fairly recognizable. You still have a tree where the root is the thing you want to prove, each node follows from its children by the application of a rule, and the leaves are axioms. It's just that, first, the tree might not be wellfounded and second, the axioms might be "nonstandard axioms" (for example, you might have an axiom that looks like $\left(\varphi (0)\land \forall m[\varphi (m)\implies \varphi (m+1)]\right)\implies \forall m\varphi (m)$, except that $\varphi$ is not a genuine formula of first-order logic, but again breaks up into sub-parts in a way that you never get to the bottom of). I'm not quite certain of that, but I think that's true. --Trovatore (talk) 00:09, 30 November 2021 (UTC)

You are correct that a model of PA + ¬G believes PA + ¬G is inconsistent. In fact, it believes PA is inconsistent. Specifically, it contains a nonstandard number which it believes encodes a proof of 0=1 from PA. And so, by explosion, it contains a nonstandard number encoding a proof of any statement in the language. And no, there's no hope of definably distinguishing valid proofs from invalid, because you could use that to define a cut in the model: the set of all numbers bounding invalid proofs is ill-founded.

(There's a subtlety about the proof of 0=1 from PA. PA is an infinite c.e. set, so it's referred to by a c.e. index. A "proof from PA" is actually a proof from the axioms enumerated by that index, and in a nonstandard model there will be nonstandard axioms enumerated.)--108.36.85.111 (talk) 17:15, 25 November 2021 (UTC)

Re your original question: if a theory T proves 1=0 then T is inconsistent and has no models. Since PA+¬G is consistent and has models, it can't prove 1=0. Re G being false in every model of PA+¬G, I think you are right. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 19:31, 22 November 2021 (UTC)

proper classes

The set theories NBG and MK are extensions of ZFC (one conservative, one not) that allow for proper classes. Both have an axiom of limitation of size, which says any proper class is as large as the whole set universe. Are there other theories that still extend ZFC, but allow some proper classes to be larger than others? Alternatively, is there a particular reason to believe the axiom of limitation of size? Thanks. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 21:47, 22 November 2021 (UTC)

Links: Von Neumann–Bernays–Gödel set theory, Morse–Kelley set theory. --RDBury (talk) 00:15, 23 November 2021 (UTC)

It's easy to see (given choice) that the largest possible class is the class of all sets, and the smallest possible proper class is the class of all ordinals. So the question is whether they are the same; that is, whether there's a global wellordering of all sets at once, rather than just each set having a wellordering (which follows from the ordinary axiom of choice). The existence of such a global wellordering is equivalent to the axiom of global choice.

As to whether there's a convincing justification for that axiom, this is going to get into philosophy pretty fast. If you take a realist view of sets based on the von Neumann hierarchy, the essential difference between sets and classes is that every set is a completed totality, whereas a proper class is a convenient way of talking about a predicate on sets. That's why many thinkers don't consider MK to be a convincing picture of all sets (though it's a nice theory for the universe cut off at an inaccessible). If you're really talking about all sets, a convincing motivation for global choice seems elusive. --Trovatore (talk) 20:41, 29 November 2021 (UTC)

User:Trovatore, thanks! I just saw this (was away and didn't receive your talk message til last night). I may have a further question later, which I'll post on the refdesk. I had thought of proper classes somewhat differently, as large collections of sets rather than as predicates. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 17:08, 6 December 2021 (UTC)