Set Theory in the Foundation of Math: Internal Classes, External Sets

Usual math sets have special types: countable, compact, open, occasionally Borel, rarely projective, etc. They are described by a single Set Theory formula with parameters unrelated to other formulas. Exotic expressions involving sets related to formulas of unlimited complexity appear mostly in esoteric or foundational studies.

Recognizing internal to math (formula-specified) and external (based on parameters in those formulas) aspects of math objects greatly simplifies foundations. I postulate external sets (not internally specified, treated as the domain of variables) to be hereditarily countable and independent of formula-defined classes, i.e. with finite algorithmic Information about them.

This allows elimination of all non-integer quantifiers in Set Theory sentences. All with seemingly no need to change almost anything in mathematical papers, only to reinterpret some formalities.

Slides can be found here: https://www.cs.bu.edu/fac/lnd/expo/sets/.

Logic in the Age of AI: What can it be? What should it be? What will it be?

I begin by extracting lessons from the development of

logic, from antiquity to the heyday of logic, to humbling realization that

logic can’t be the sole foundation of AI.

Then I examine how generative AI works.

Finally, I discuss three entangled objectives for logic in the age of AI.

Direct Contribution: While AI exhibit impressive reasoning, its coherence is statistical, not deductive. This invites logic to complement

learning through scaffolding (enforcing normative constraints),

auditing (detecting inconsistencies), and governance (tracking commitments).

Foundations: Clarifying vague foundational notions like intelligence, understanding, and alignment.

Scope Extension: One radical extension is to become a ”science of convincing reasoning”.

Relativization and Complexity

Relativization is a technique which saw its birth in set theory and

in computability theory, notably in Turing’s 1939 paper where Turing

defined what it meant for a set X to be A-computable. Classically, the

collection of A-computable sets are defined to be {B | B ≤T A}.

Relativization in computability theory is a longstanding love-affair,

notably allowing for effortless proofs of results about the jump operator

from results about the halting problem for example. These effortless results

also generated a number of false conjectures such as the homogenity

conjecture.

Computational complexity theory has a more turbulent relationship

with relativization. This is particularly since the classical results of Baker-

Gill-Solovay saying that there are oracles A and B such that PA ̸= NPA

and PB = NPB. Their conclusion is that methods that relativize are not

sufficient to settle the P =?NP question. The Baker-Gill-Solovay results

spawned a huge cottage industry of results showing similar separation

methods could not be settled by methods that relativized. This caused

computational complexity to think about methods such as arithmetization,

algebraization, etc.

In this talk, I will analyse relativization in complexity theory and argue

that it is wrongly applied; arguing that the current techniques are only

concerned with partial relativization. This argument resurrects the hope

that there might be some method of using oracles to settle questions such

as the P =?NP one.

Quasi-propositions and Quasi-individuals

“Quasi-Propositions and Quasi-Individuals'' is a short paper which first

appeared in 1968 as Paper XII in the first edition of Arthur Prior's book Papers on

Time and Tense. Despite its brevity, it is important both logically and philosophically.

Logically, Prior uses what he calls “quasi-modalities'' to build a small “egocentric

logic'' for reasoning about taller and shorter; as we shall see, this is perhaps the

earliest example of what computer scientists now call description logic. Moreover,

partially inspired by his earlier work on the tense logic of special relativity, he shows

how to hybridize this logic by defining a totalizing (universal) quasi-modality and

quantifying over “people-propositions” (quasi-Individuals); that is, he quantifies over

nominals. The philosophical discussion is equally interesting: the paper contains

Prior's first critical reflections on his earlier claims, boldly stated in "Tense Logic and

the Logic of Earlier and Later'' (Paper XI in the first edition of Papers on Timeand

Tense) on the significance of hybridization