2

Could somebody elaborate the meaning of following statement from wikipedia concerning intrinsical differences between set theory and type theory:

Unlike set theories, type theories are not built on top of a logic like Frege's.

Concretely, what does it mean for a theory to build "on top of a logic" and why this is the case for "naive set theory" in contrast to type theory? (Rmk.: A "logic" is for me a formal system).

So far I know one central issue with set theory which type theorist "not like" at all is that it's axioms, which should intrinsically be regarded at part of metatheory, are formulated in "internal" language, which may regarded as "undesirable" and drives the development of type theory? Is this correct?

8

1 Answer 1

4

The basic concept is that of Formal systems: a rigorously specified language with some (zero or more) axioms (initial formulas) and rules of inference (prescriptions how to derive new formuals from already derived ones). What counts is the respective "expressive capability".

Propositional calculus has a very limited expressive capability, but it is very useful for pedagogical reason, because with it it is possible to show the basic concept and properties of formal systems : syntax, semantics, consistency, completeness, etc.

First order logic is much more useful because it has a poweful expressive capability: with it we can formalize many (quite) all of mathematical thpories, like set theory and arithmetic.

First-order logic (FOL) is made of a language (the so called f-o language) with the quantifiers : ? and ?, rules of inference: like Modus Ponens and Generalization, and (zero or more) logical axioms.

A first-order theory is manufactured "on top" of FOL adding specific non-logical symbols and axioms: see PA for first-order Peano arithmetic or ZF for Zermelo-Fraenkel Set Theory.

In the case of set theory, for example, we have a single non-logical symbol, viz. the binary relation "in" () and several non-logical axioms, like e.g. the Null axiom: ?x?y ? (y ∈ x).

Starting from the non-logical axioms and using the machinery of the "underlying logic", i.e. logical axioms and rules of inference, we can derive new formulas of the thory that are the specific mathematical theorems of the theory.

Intuitionistic type theory (aka constructive type theory or Martin-L?f type theory)

is a formal logical system and philosophical foundation for constructive mathematics. It is a full-scale system which aims to play a similar role for constructive mathematics as Zermelo-Fraenkel Set Theory does for classical mathematics. [...] The main idea is that mathematical concepts such as elements, sets and functions are explained in terms of concepts from programming such as data structures, data types and programs.

MLTT, as well as the historical Type Theory, developed by Alfred North Whitehead and Bertrand Russell’s into Principia Mathematica (1910-1913), and its modern versions, are formal systems which includes first-order logic, but are more expressive in a practical sense: they are well suited to the formalization of mathematics.

A good textbook regarding Mathematical Logic: Dirk van Dalen Logic and Structure (2004, Springer).

For MLTT and similar, see e.g. L.Crosilla, Constructive TYpe Theory and Giuseppe Primiero, Information and knowledge: A constructive type-theoretical approach (2008, Springer).

See also L.Crosilla, The entanglement of logic and set theory, constructively.

8
  • let try to summarize the first part to develop a better overview for "what is retalated to what": So if understand the definitions correctly, then "Propositional calculus" and "FOL" are examples of a "Formal system". And moreover FOL "extends" PC in sense of an extension of formal systems (... ie extends the alphabet, symbols, axioms & inference rules), and consequenly becomes naturally more expressive.
    – user267839
    Commented Apr 24, 2024 at 12:03
  • Next, you wrote "A first-order theory is manufactured "on top" of FOL adding specific non-logical symbols and axioms [...]". May I assume that you treat the term "on top" (... of a fixed formal system) also synonymously for an extension of FS' in the sense I described above? Or do I missing the issue at that point?
    – user267839
    Commented Apr 24, 2024 at 12:04
  • To make it concretely, now let's specialize, for example "a first-order theory is on top of FOL" means that a first-order theory (consideres as FS) extends FOL as anFS extension? Is that what you mean by "on top", respectively the connection between a "first-order theory" and FOL?
    – user267839
    Commented Apr 24, 2024 at 12:05
  • 1st comment: Yes. FOL "analyze" the basic elements of the language of Prop Log; the statements, into variables and predicate and adds to the logical connective the quantifiers with the relevant logical axioms and rule (e.g. Generalization). Commented Apr 24, 2024 at 12:20
  • 2ns: predicate logic has variables, predicate symbols and (usually) equality (=). In first-order set theory we add a binary predicate symbol that "means" "in" with some specific axiom. Now we have not only the axioms and theorems of "pure logic", like e.g. x=x, but also some specific theorem regarding the properties of . Commented Apr 24, 2024 at 12:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.