Godel’s Completeness and Incompleteness Theorems

Fol­lowup to: Stan­dard and Non­stan­dard Numbers

So… last time you claimed that us­ing first-or­der ax­ioms to rule out the ex­is­tence of non­stan­dard num­bers—other chains of num­bers be­sides the ‘stan­dard’ num­bers start­ing at 0 - was for­ever and truly im­pos­si­ble, even unto a su­per­in­tel­li­gence, no mat­ter how clever the first-or­der logic used, even if you came up with an en­tirely differ­ent way of ax­io­m­a­tiz­ing the num­bers.

“Right.”

How could you, in your finite­ness, pos­si­bly know that?

“Have you heard of Godel’s In­com­plete­ness The­o­rem?”

Of course! Godel’s The­o­rem says that for ev­ery con­sis­tent math­e­mat­i­cal sys­tem, there are state­ments which are true within that sys­tem, which can’t be proven within the sys­tem it­self. Godel came up with a way to en­code the­o­rems and proofs as num­bers, and wrote a purely nu­mer­i­cal for­mula to de­tect whether a proof obeyed proper log­i­cal syn­tax. The ba­sic trick was to use prime fac­tor­iza­tion to en­code lists; for ex­am­ple, the or­dered list <3, 7, 1, 4> could be uniquely en­coded as:

23 * 37 * 51 * 74

And since prime fac­tor­iza­tions are unique, and prime pow­ers don’t mix, you could in­spect this sin­gle num­ber, 210,039,480, and get the unique or­dered list <3, 7, 1, 4> back out. From there, go­ing to an en­cod­ing for log­i­cal for­mu­las was easy; for ex­am­ple, you could use the 2 pre­fix for NOT and the 3 pre­fix for AND and get, for any for­mu­las Φ and Ψ en­coded by the num­bers #Φ and #Ψ:

¬Φ = 22 * 3

Φ ∧ Ψ = 23 * 3 * 5

It was then pos­si­ble, by dint of crazy amounts of work, for Godel to come up with a gi­gan­tic for­mula of Peano Arith­metic [](p, c) mean­ing, ‘P en­codes a valid log­i­cal proof us­ing first-or­der Peano ax­ioms of C’, from which di­rectly fol­lowed the for­mula []c, mean­ing, ‘There ex­ists a num­ber P such that P en­codes a proof of C’ or just ‘C is prov­able in Peano ar­ith­metic.’

Godel then put in some fur­ther clever work to in­vent state­ments which referred to them­selves, by hav­ing them con­tain sub-recipes that would re­pro­duce the en­tire state­ment when ma­nipu­lated by an­other for­mula.

And then Godel’s State­ment en­codes the state­ment, ‘There does not ex­ist any num­ber P such that P en­codes a proof of (this state­ment) in Peano ar­ith­metic’ or in sim­pler terms ‘I am not prov­able in Peano ar­ith­metic’. If we as­sume first-or­der ar­ith­metic is con­sis­tent and sound, then no proof of this state­ment within first-or­der ar­ith­metic ex­ists, which means the state­ment is true but can’t be proven within the sys­tem. That’s Godel’s The­o­rem.

“Er… no.”

No?

“No. I’ve heard ru­mors that Godel’s In­com­plete­ness The­o­rem is hor­ribly mi­s­un­der­stood in your Everett branch. Have you heard of Godel’s Com­plete­ness The­o­rem?”

Is that a thing?

Yes! Godel’s Com­plete­ness The­o­rem says that, for any col­lec­tion of first-or­der state­ments, ev­ery se­man­tic im­pli­ca­tion of those state­ments is syn­tac­ti­cally prov­able within first-or­der logic. If some­thing is a gen­uine im­pli­ca­tion of a col­lec­tion of first-or­der state­ments—if it ac­tu­ally does fol­low, in the mod­els pinned down by those state­ments—then you can prove it, within first-or­der logic, us­ing only the syn­tac­ti­cal rules of proof, from those ax­ioms.”

I don’t see how that could pos­si­bly be true at the same time as Godel’s In­com­plete­ness The­o­rem. The Com­plete­ness The­o­rem and In­com­plete­ness The­o­rem seem to say di­a­met­ri­cally op­po­site things. Godel’s State­ment is im­plied by the ax­ioms of first-or­der ar­ith­metic—that is, we can see it’s true us­ing our own math­e­mat­i­cal rea­son­ing -

“Wrong.”

What? I mean, I un­der­stand we can’t prove it within Peano ar­ith­metic, but from out­side the sys­tem we can see that -

All right, ex­plain.

“Ba­si­cally, you just com­mit­ted the equiv­a­lent of say­ing, ‘If all kit­tens are lit­tle, and some lit­tle things are in­no­cent, then some kit­tens are in­no­cent.’ There are uni­verses—log­i­cal mod­els—where it so hap­pens that the premises are true and the con­clu­sion also hap­pens to be true:”

“But there are also valid mod­els of the premises where the con­clu­sion is false:”

“If you, your­self, hap­pened to live in a uni­verse like the first one—if, in your mind, you were only think­ing about a uni­verse like that—then you might mis­tak­enly think that you’d proven the con­clu­sion. But your state­ment is not log­i­cally valid, the con­clu­sion is not true in ev­ery uni­verse where the premises are true. It’s like say­ing, ‘All ap­ples are plants. All fruits are plants. There­fore all ap­ples are fruits.’ Both the premises and the con­clu­sions hap­pen to be true in this uni­verse, but it’s not valid logic.”

Okay, so how does this in­val­i­date my pre­vi­ous ex­pla­na­tion of Godel’s The­o­rem?

“Be­cause of the non-stan­dard mod­els of first-or­der ar­ith­metic. First-or­der ar­ith­metic nar­rows things down a lot—it rules out 3-loops of non­stan­dard num­bers, for ex­am­ple, and man­dates that ev­ery model con­tain the num­ber 17 - but it doesn’t pin down a sin­gle model. There’s still the pos­si­bil­ity of in­finite-in-both-di­rec­tions chains com­ing af­ter the ‘stan­dard’ chain that starts with 0. Maybe you have just the stan­dard num­bers in mind, but that’s not the only pos­si­ble model of first-or­der ar­ith­metic.”

So?

“So in some of those other mod­els, there are non­stan­dard num­bers which—ac­cord­ing to Godel’s ar­ith­meti­cal for­mula for en­codes-a-proof—are ‘non­stan­dard proofs’ of Godel’s State­ment. I mean, they’re not what we would call ac­tual proofs. An ac­tual proof would have a stan­dard num­ber cor­re­spond­ing to it. A non­stan­dard proof might look like… well, it’s hard to en­vi­sion, but it might be some­thing like, ‘Godel’s state­ment is true, be­cause not-not-Godel’s state­ment, be­cause not-not-not-not-Godel’s state­ment’, and so on go­ing back­ward for­ever, ev­ery step of the proof be­ing valid, be­cause non­stan­dard num­bers have an in­finite num­ber of pre­de­ces­sors.”

And there’s no way to say, ‘You can’t have an in­finite num­ber of deriva­tions in a proof’?

“Not in first-or­der logic. If you could say that, you could rule out num­bers with in­finite num­bers of pre­de­ces­sors, mean­ing that you could rule out all in­finite-in-both-di­rec­tions chains, and hence rule out all non­stan­dard num­bers. And then the only re­main­ing model would be the stan­dard num­bers. And then Godel’s State­ment would be a se­man­tic im­pli­ca­tion of those ax­ioms; there would ex­ist no num­ber en­cod­ing a proof of Godel’s State­ment in any model which obeyed the ax­ioms of first-or­der ar­ith­metic. And then, by Godel’s Com­plete­ness The­o­rem, we could prove Godel’s State­ment from those ax­ioms us­ing first-or­der syn­tax. Be­cause ev­ery gen­uinely valid im­pli­ca­tion of any col­lec­tion of first-or­der ax­ioms—ev­ery first-or­der state­ment that ac­tu­ally does fol­low, in ev­ery pos­si­ble model where the premises are true—can always be proven, from those ax­ioms, in first-or­der logic. Thus, by the com­bi­na­tion of Godel’s In­com­plete­ness The­o­rem and Godel’s Com­plete­ness The­o­rem, we see that there’s no way to uniquely pin down the nat­u­ral num­bers us­ing first-or­der logic. QED.”

Whoa. So ev­ery­one in the hu­man-su­pe­ri­or­ity crowd gloat­ing about how they’re su­pe­rior to mere ma­chines and for­mal sys­tems, be­cause they can see that Godel’s State­ment is true just by their sa­cred and mys­te­ri­ous math­e­mat­i­cal in­tu­ition...

″...Is ac­tu­ally com­mit­ting a hor­ren­dous log­i­cal fal­lacy of the sort that no cleanly de­signed AI could ever be tricked into, yes. Godel’s State­ment doesn’t ac­tu­ally fol­low from the first-or­der ax­iom­a­ti­za­tion of Peano ar­ith­metic! There are mod­els where all the first-or­der ax­ioms are true, and yet Godel’s State­ment is false! The stan­dard mi­s­un­der­stand­ing of Godel’s State­ment is some­thing like the situ­a­tion as it ob­tains in sec­ond-or­der logic, where there’s no equiv­a­lent of Godel’s Com­plete­ness The­o­rem. But peo­ple in the hu­man-su­pe­ri­or­ity crowd usu­ally don’t at­tach that dis­claimer—they usu­ally pre­sent ar­ith­metic us­ing the first-or­der ver­sion, when they’re ex­plain­ing what it is that they can see that a for­mal sys­tem can’t. It’s safe to say that most of them are in­ad­ver­tently illus­trat­ing the ir­ra­tional over­con­fi­dence of hu­mans jump­ing to con­clu­sions, even though there’s a less stupid ver­sion of the same ar­gu­ment which in­vokes sec­ond-or­der logic.”

Nice. But still… that proof you’ve shown me seems like a rather cir­cuitous way of show­ing that you can’t ever rule out in­finite chains, es­pe­cially since I don’t see why Godel’s Com­plete­ness The­o­rem should be true.

“Well… an equiv­a­lent way of stat­ing Godel’s Com­plete­ness The­o­rem is that ev­ery syn­tac­ti­cally con­sis­tent set of first-or­der ax­ioms—that is, ev­ery set of first-or­der ax­ioms such that you can­not syn­tac­ti­cally prove a con­tra­dic­tion from them us­ing first-or­der logic—has at least one se­man­tic model. The proof pro­ceeds by try­ing to ad­join state­ments say­ing P or ~P for ev­ery first-or­der for­mula P, at least one of which must be pos­si­ble to ad­join while leav­ing the ex­panded the­ory syn­tac­ti­cally con­sis­tent—”

Hold on. Is there some more con­struc­tive way of see­ing why a non-stan­dard model has to ex­ist?

“Mm… you could in­voke the Com­pact­ness The­o­rem for first-or­der logic. The Com­pact­ness The­o­rem says that if a col­lec­tion of first-or­der state­ments has no model, some finite sub­set of those state­ments is also se­man­ti­cally un­re­al­iz­able. In other words, if a col­lec­tion of first-or­der state­ments—even an in­finite col­lec­tion—is un­re­al­iz­able in the sense that no pos­si­ble math­e­mat­i­cal model fits all of those premises, then there must be some finite sub­set of premises which are also un­re­al­iz­able. Or modus po­nens to modus tol­lens, if all finite sub­sets of a col­lec­tion of ax­ioms have at least one model, then the whole in­finite col­lec­tion of ax­ioms has at least one model.”

Ah, and can you ex­plain why the Com­pact­ness The­o­rem should be true?

No.

I see.

“But at least it’s sim­pler than the Com­plete­ness The­o­rem, and from the Com­pact­ness The­o­rem, the in­abil­ity of first-or­der ar­ith­metic to pin down a stan­dard model of num­bers fol­lows im­me­di­ately. Sup­pose we take first-or­der ar­ith­metic, and ad­join an ax­iom which says, ‘There ex­ists a num­ber greater than 0.’ Since there does in fact ex­ist a num­ber, 1, which is greater than 0, first-or­der ar­ith­metic plus this new ax­iom should be se­man­ti­cally okay—it should have a model if any model of first-or­der ar­ith­metic ever ex­isted in the first place. Now let’s ad­join a new con­stant sym­bol c to the lan­guage, i.e., c is a con­stant sym­bol refer­ring to a sin­gle ob­ject across all state­ments where it ap­pears, the way 0 is a con­stant sym­bol and an ax­iom then iden­ti­fies 0 as the ob­ject which is not the suc­ces­sor of any ob­ject. Then we start ad­join­ing ax­ioms say­ing ‘c is greater than X’, where X is some con­cretely speci­fied num­ber like 0, 1, 17, 2256, and so on. In fact, sup­pose we ad­join an in­finite se­ries of such state­ments, one for ev­ery num­ber:”

Wait, so this new the­ory is say­ing that there ex­ists a num­ber c which is larger than ev­ery num­ber?

“No, the in­finite schema says that there ex­ists a num­ber c which is larger than any stan­dard num­ber.”

I see, so this new the­ory forces a non­stan­dard model of ar­ith­metic.

“Right. It rules out only the stan­dard model. And the Com­pact­ness The­o­rem says this new the­ory is still se­man­ti­cally re­al­iz­able—it has some model, just not the stan­dard one.”

Why?

“Be­cause any finite sub­col­lec­tion of the new the­ory’s ax­ioms, can only use a finite num­ber of the ex­tra ax­ioms. Sup­pose the largest ex­tra ax­iom you used was ‘c is larger than 2256’. In the stan­dard model, there cer­tainly ex­ists a num­ber 2256+1 with which c could be con­sis­tently iden­ti­fied. So the stan­dard num­bers must be a model of that col­lec­tion of ax­ioms, and thus that finite sub­set of ax­ioms must be se­man­ti­cally re­al­iz­able. Thus by the Com­pact­ness The­o­rem, the full, in­finite ax­iom sys­tem must also be se­man­ti­cally re­al­iz­able; it must have at least one model. Now, adding ax­ioms never in­creases the num­ber of com­pat­i­ble mod­els of an ax­iom sys­tem—each ad­di­tional ax­iom can only filter out mod­els, not add mod­els which are in­com­pat­i­ble with the other ax­ioms. So this new model of the larger ax­iom sys­tem—con­tain­ing a num­ber which is greater than 0, greater than 1, and greater than ev­ery other ‘stan­dard’ num­ber—must also be a model of first-or­der Peano ar­ith­metic. That’s a rel­a­tively sim­pler proof that first-or­der ar­ith­metic—in fact, any first-or­der ax­iom­a­ti­za­tion of ar­ith­metic—has non­stan­dard mod­els.”

Huh… I can’t quite say that seems ob­vi­ous, be­cause the Com­pact­ness The­o­rem doesn’t feel ob­vi­ous; but at least it seems more spe­cific than try­ing to prove it us­ing Godel’s The­o­rem.

“A similar con­struc­tion to the one we used above—adding an in­finite se­ries of ax­ioms say­ing that a thingy is even larger—shows that if a first-or­der the­ory has mod­els of un­bound­edly large finite size, then it has at least one in­finite model. To put it even more alarm­ingly, there’s no way to char­ac­ter­ize the prop­erty of finite­ness in first-or­der logic! You can have a first-or­der the­ory which char­ac­ter­izes mod­els of car­di­nal­ity 3 - just say that there ex­ist x, y, and z which are not equal to each other, but with all ob­jects be­ing equal to x or y or z. But there’s no first-or­der the­ory which char­ac­ter­izes the prop­erty of finite­ness in the sense that all finite mod­els fit the the­ory, and no in­finite model fits the the­ory. A first-or­der the­ory ei­ther limits the size of mod­els to some par­tic­u­lar up­per bound, or it has in­finitely large mod­els.”

So you can’t even say, ‘x is finite’, with­out us­ing sec­ond-or­der logic? Just form­ing the con­cept of in­finity and dis­t­in­guish­ing it from finite­ness re­quires sec­ond-or­der logic?

“Cor­rect, for pretty much ex­actly the same rea­son you can’t say ‘x is only a finite num­ber of suc­ces­sors away from 0’. You can say, ‘x is less than a googol­plex’ in first-or­der logic, but not, in full gen­er­al­ity, ‘x is finite’. In fact there’s an even worse the­o­rem, the Lowen­heim-Skolem the­o­rem, which roughly says that if a first-or­der the­ory has any in­finite model, it has mod­els of all pos­si­ble in­finite car­di­nal­ities. There are un­countable mod­els of first-or­der Peano ar­ith­metic. There are countable mod­els of first-or­der real ar­ith­metic—countable mod­els of any at­tempt to ax­io­m­a­tize the real num­bers in first-or­der logic. There are countable mod­els of Zer­melo-Frankel set the­ory.”

How could you pos­si­bly have a countable model of the real num­bers? Didn’t Can­tor prove that the real num­bers were un­countable? Wait, let me guess, Can­tor im­plic­itly used sec­ond-or­der logic some­how.

“It fol­lows from the Lowen­heim-Skolem the­o­rem that he must’ve. Let’s take Can­tor’s proof as show­ing that you can’t map ev­ery set of in­te­gers onto a dis­tinct in­te­ger—that is, the pow­er­set of in­te­gers is larger than the set of in­te­gers. The Di­ag­o­nal Ar­gu­ment is that if you show me a map­ping like that, I can take the set which con­tains 0 if and only if 0 is not in the set mapped to the in­te­ger 0, con­tains 1 if and only if 1 is not in the set mapped to the in­te­ger 1, and so on. That gives you a set of in­te­gers that no in­te­ger maps to.”

You know, when I was very young in­deed, I thought I’d found a coun­terex­am­ple to Can­tor’s ar­gu­ment. Just take the base-2 in­te­gers − 1=‘1’, 2=’10′, 3=‘11’, 4=‘100’, 5=‘101’, and so on, and let each in­te­ger cor­re­spond to a set in the ob­vi­ous way, keep­ing in mind that I was also young enough to think the in­te­gers started at 1:

1 10 11 100 101 110 111 1000 1001
{1} {2} {2, 1} {3} {3, 1} {3, 2} {3, 2, 1} {4} {4, 1}

Clearly, ev­ery set of in­te­gers would map onto a unique in­te­ger this way.

“Heh.”

Yeah, I thought I was go­ing to be fa­mous.

“How’d you re­al­ize you were wrong?”

After an em­bar­rass­ingly long in­ter­val, it oc­curred to me to ac­tu­ally try ap­ply­ing Can­tor’s Di­ag­o­nal Ar­gu­ment to my own con­struc­tion. Since 1 is in {1} and 2 is in {2}, they wouldn’t be in the re­sult­ing set, but 3, 4, 5 and ev­ery­thing else would be. And of course my con­struct didn’t have the set {3, 4, 5, …} any­where in it. I’d mapped all the finite sets of in­te­gers onto in­te­gers, but none of the in­finite sets.

“In­deed.”

I was then tempted to go on ar­gu­ing that Can­tor’s Di­ag­o­nal Ar­gu­ment was wrong any­how be­cause it was wrong to have in­finite sets of in­te­gers. Thank­fully, de­spite my young age, I was self-aware enough to re­al­ize I was be­ing tempted to be­come a math­e­mat­i­cal crank—I had also read a book on math­e­mat­i­cal cranks by this point—and so I just quietly gave up, which was a valuable life les­son.

“In­deed.”

But how ex­actly does Can­tor’s Di­ag­o­nal Ar­gu­ment de­pend on sec­ond-or­der logic? Is it some­thing to do with non­stan­dard in­te­gers?

“Not ex­actly. What hap­pens is that there’s no way to make a first-or­der the­ory con­tain all sub­sets of an in­finite set; there’s no way to talk about the pow­er­set of the in­te­gers. Let’s illus­trate us­ing a finite metaphor. Sup­pose you have the ax­iom “All kit­tens are in­no­cent.” One model of that ax­iom might con­tain five kit­tens, an­other model might con­tain six kit­tens.”

“In a sec­ond-or­der logic, you can talk about all pos­si­ble col­lec­tions of kit­tens—in fact, it’s built into the syn­tax of the lan­guage when you quan­tify over all prop­er­ties.”

“In a first-or­der set the­ory, there are some sub­sets of kit­tens whose ex­is­tence is prov­able, but oth­ers might be miss­ing.”

“Though that image is only metaphor­i­cal, since you can prove the ex­is­tence of all the finite sub­sets. Just imag­ine that’s an in­finite num­ber of kit­tens we’re talk­ing about up there.”

And there’s no way to say that all pos­si­ble sub­sets ex­ist?

“Not in first-or­der logic, just like there’s no way to say that you want as few nat­u­ral num­bers as pos­si­ble. Let’s look at it from the stand­point of first-or­der set the­ory. The Ax­iom of Pow­er­set says:”

Okay, so that says, for ev­ery set A, there ex­ists a set P which is the power set of all sub­sets of A, so that for ev­ery set B, B is in­side the pow­er­set P if and only if ev­ery el­e­ment of B is an el­e­ment of A. Any set which con­tains only el­e­ments from A, will be in­side the pow­er­set of A. Right?

“Al­most. There’s just one thing wrong in that ex­pla­na­tion—the word ‘all’ when you say ‘all sub­sets’. The Pow­er­set Ax­iom says that for any col­lec­tion of el­e­ments from A, if a set B hap­pens to ex­ist which em­bod­ies that col­lec­tion, that set B is in­side the pow­er­set P of A. There’s no way of say­ing, within a first-or­der log­i­cal the­ory, that a set ex­ists for ev­ery pos­si­ble col­lec­tion of A’s el­e­ments. There may be some sub-col­lec­tions of A whose ex­is­tence you can prove. But other sub-col­lec­tions of A will hap­pen to ex­ist as sets in­side some mod­els, but not ex­ist in oth­ers.”

So in the same way that first-or­der Peano ar­ith­metic suffers from mys­te­ri­ous ex­tra num­bers, first-or­der set the­ory suffers from mys­te­ri­ous miss­ing sub­sets.

“Pre­cisely. A first-or­der set the­ory might hap­pen to be miss­ing the par­tic­u­lar in­finite set cor­re­spond­ing to, oh, say, {3, 8, 17, 22, 28, …} where the ‘...’ is an in­finite list of ran­dom num­bers with no com­pact way of spec­i­fy­ing them. If there’s a com­pact way of spec­i­fy­ing a set—if there’s a finite for­mula that de­scribes it—you can of­ten prove it ex­ists. But most in­finite sets won’t have any finite speci­fi­ca­tion. It’s pre­cisely the claim to gen­er­al­ize over all pos­si­ble col­lec­tions that char­ac­ter­izes sec­ond-or­der logic. So it’s triv­ial to say in a sec­ond-or­der set the­ory that all sub­sets ex­ist. You would just say that for any set A, for any pos­si­ble pred­i­cate P, there ex­ists a set B which con­tains x iff x in A and Px.”

I guess that tor­pe­does my clever idea about us­ing first-or­der set the­ory to uniquely char­ac­ter­ize the stan­dard num­bers by first as­sert­ing that there ex­ists a set con­tain­ing at least the stan­dard num­bers, and then talk­ing about the small­est sub­set which obeys the Peano ax­ioms.

“Right. When you talk about the num­bers us­ing first-or­der set the­ory, if there are ex­tra num­bers in­side your set of num­bers, the sub­set con­tain­ing just the stan­dard num­bers must be miss­ing from the pow­er­set of that set. Other­wise you could find the small­est sub­set in­side the pow­er­set such that it con­tained 0 and con­tained the suc­ces­sor of ev­ery num­ber it con­tained.”

Hm. So then what ex­actly goes wrong with Can­tor’s Di­ag­o­nal Ar­gu­ment?

“Can­tor’s Di­ag­o­nal Ar­gu­ment uses the idea of a map­ping be­tween in­te­gers and sets of in­te­gers. In set the­ory, each map­ping would it­self be a set—in fact there would be a set of all map­ping sets:”

“There’s no way to first-or­der as­sert the ex­is­tence of ev­ery pos­si­ble map­ping that we can imag­ine from out­side. So a first-or­der ver­sion of the Di­ag­o­nal Ar­gu­ment would show that in any par­tic­u­lar model, for any map­ping that ex­isted in the model from in­te­gers to sets of in­te­gers, the model would also con­tain a di­ag­o­nal­ized set of in­te­gers that wasn’t in that map­ping. This doesn’t mean that we couldn’t count all the sets of in­te­gers which ex­isted in the model. The model could have so many ‘miss­ing’ sets of in­te­gers that the re­main­ing sets were de­nu­mer­able. But then some map­pings from in­te­gers to sets would also be miss­ing, and in par­tic­u­lar, the ‘com­plete’ map­ping we can imag­ine from out­side would be miss­ing. And for ev­ery map­ping that was in the model, the Di­ag­o­nal Ar­gu­ment would con­struct a set of in­te­gers that wasn’t in the map­ping. On the out­side, we would see a pos­si­ble map­ping from in­te­gers to sets—but that map­ping wouldn’t ex­ist in­side the model as a set. It takes a logic-of-col­lec­tions to say that all pos­si­ble in­te­ger-col­lec­tions ex­ist as sets, or that no pos­si­ble map­ping ex­ists from the in­te­gers onto those sets.”

So if first-or­der logic can’t even talk about finite­ness vs. in­finite­ness—let alone prove that there are re­ally more sets of in­te­gers than in­te­gers—then why is any­one in­ter­ested in first-or­der logic in the first place? Isn’t that like try­ing to eat din­ner us­ing only a fork, when there are lots of in­ter­est­ing foods which prov­ably can’t be eaten with a fork, and you have a spoon?

“Ah, well… some peo­ple be­lieve there is no spoon. But let’s take that up next time.”

Part of the se­quence Highly Ad­vanced Episte­mol­ogy 101 for Beginners

Next post: “Se­cond-Order Logic: The Con­tro­versy

Pre­vi­ous post: “Stan­dard and Non­stan­dard Num­bers