Pseudofinite structures and limits
| Název práce v češtině: | Pseudokonečné struktury a limity |
|---|---|
| Název v anglickém jazyce: | Pseudofinite structures and limits |
| Klíčová slova: | pseudokonečné struktury|forcing|složitost|svědci|TFNP|klika |
| Klíčová slova anglicky: | pseudofinite structures|forcing|complexity|witnessing|TFNP|clique |
| Akademický rok vypsání: | 2020/2021 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 10.01.2021 |
| Datum zadání: | 11.01.2021 |
| Datum potvrzení stud. oddělením: | 01.02.2021 |
| Datum a čas obhajoby: | 09.06.2022 09:00 |
| Datum odevzdání elektronické podoby: | 04.05.2022 |
| Datum odevzdání tištěné podoby: | 09.05.2022 |
| Datum proběhlé obhajoby: | 09.06.2022 |
| Oponenti: | doc. Mgr. Jan Šaroch, Ph.D. |
| Zásady pro vypracování |
| Pseudofinite structures are infinite structures satisfying
all first-order properties that all finite structures satisfy. Their model-theoretic properties reflect in a sense asymptotic properties of sequences of larger and larger finite structures. The task is to study this phenomenon and to give its mathematically precise example. |
| Seznam odborné literatury |
| M. Ajtai, Generalizations of the Compactness Theorem and Godel’s Completeness Theorem
for Nonstandard Finite Structures, in: Proc. of the 4th International Conference on Theory and Applications of Models of Computation, (2007), pp.13-33. M. Garlik, A New Proof of Ajtai’s Completeness Theorem for Nonstandard Finite Structures, Archive for Mathematical Logic, 54(3-4), (2015), pp.413-424. J. Krajicek, Expansions of pseudofinite structures and circuit and proof complexity, in: Liber Amicorum Alberti, eds.Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten, Tributes Ser. 30, College Publications, London, (2016), pp.195-203. J.Krajicek, Proof Complexity, Cambridge U. Press, (2019). [Sec.20.2 there] |
| Předběžná náplň práce |
| A relation between infinite and larger and larger finite structures. |
| Předběžná náplň práce v anglickém jazyce |
| A relation between infinite and larger and larger finite structures. |