Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

An Investigation into the Non-Constructive Parts of Proving Completeness for First-Order Logic

Carlsson, Hugo Carl Samuel LU (2024) In Bachelor's Thesis in Mathematical Sciences MATK11 20241
Mathematics (Faculty of Engineering)
Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
Abstract
This thesis will be an investigation into different proofs of Completeness in first-order logic. Particular attention will be put on analyzing the role of the Ultrafilter Lemma and its necessity in proving the Completeness Theorem. An attempt will be made to develop a proof that separates out this non-constructive aspect, but still uses the law of excluded middle. The overall aim is to understand why and when non-constructive arguments are needed. Different proofs of the theorem will then be showcased and compared, and equivalents of the Completeness Theorem will be discussed.
Popular Abstract (Swedish)
Matematisk logik är läran om matematikens mest fundamentala grunder och en koppling mellan filosofi och matematik. I denna kandidatuppsats utforskas en av de tyngsta satserna inom matematisk logik, \textit{Gödels Fullständighetssats}. Den kända satsen är en koppling mellan sanning och bevisbarhet - två koncept som a priori är vitt skilda. Kort sagt så säger satsen att en formel i predikatlogik är bevisbar om den är sann.

Vi undersöker bevis för denna sats med särskilt fokus på användningen av icke-konstruktiva medel. Vi jämför olika formuleringar av satsen och utforskar hur de förhåller sig till varandra. Vi utforskar sedan vad som kan visas utan icke-konstruktiva medel, och undersöker därefter hur dessa medel används för att bevisa den... (More)
Matematisk logik är läran om matematikens mest fundamentala grunder och en koppling mellan filosofi och matematik. I denna kandidatuppsats utforskas en av de tyngsta satserna inom matematisk logik, \textit{Gödels Fullständighetssats}. Den kända satsen är en koppling mellan sanning och bevisbarhet - två koncept som a priori är vitt skilda. Kort sagt så säger satsen att en formel i predikatlogik är bevisbar om den är sann.

Vi undersöker bevis för denna sats med särskilt fokus på användningen av icke-konstruktiva medel. Vi jämför olika formuleringar av satsen och utforskar hur de förhåller sig till varandra. Vi utforskar sedan vad som kan visas utan icke-konstruktiva medel, och undersöker därefter hur dessa medel används för att bevisa den mest generella versionen av satsen. Det visar sig att Fullständighetssatsen inte nödvändigtvis kräver Urvalsaxiomet - det räcker att anta Ultrafilterlemmat och de vanliga Zermelo-Fraenkel axiomen. Vi avslutar med en diskussion om hur Fullständighetssatsen och Ultrafilterlemmat förhåller sig till varandra, och visar att även Kompakthetssatsen hör ihop med dessa två påståenden. (Less)
Please use this url to cite or link to this publication:
author
Carlsson, Hugo Carl Samuel LU
supervisor
organization
course
MATK11 20241
year
type
M2 - Bachelor Degree
subject
keywords
Completeness, Proof, Gödel, Non-Constructive, First-Order Logic, Ultrafilter Lemma
publication/series
Bachelor's Thesis in Mathematical Sciences
report number
LUNFMA-4164-2024
ISSN
1654-6229
other publication id
2024:K6
language
English
additional info
There are two publications with this title. This is the correct and final one.
id
9156351
date added to LUP
2025-06-12 15:52:29
date last changed
2025-06-12 15:52:29
@misc{9156351,
  abstract     = {{This thesis will be an investigation into different proofs of Completeness in first-order logic. Particular attention will be put on analyzing the role of the Ultrafilter Lemma and its necessity in proving the Completeness Theorem. An attempt will be made to develop a proof that separates out this non-constructive aspect, but still uses the law of excluded middle. The overall aim is to understand why and when non-constructive arguments are needed. Different proofs of the theorem will then be showcased and compared, and equivalents of the Completeness Theorem will be discussed.}},
  author       = {{Carlsson, Hugo Carl Samuel}},
  issn         = {{1654-6229}},
  language     = {{eng}},
  note         = {{Student Paper}},
  series       = {{Bachelor's Thesis in Mathematical Sciences}},
  title        = {{An Investigation into the Non-Constructive Parts of Proving Completeness for First-Order Logic}},
  year         = {{2024}},
}