,CONTENTS
Preface ............................................................................................................................................................... V
1 Special Set Sẏstems .................................................................................................................................. 1
1.1 Basic Constructions................................................................................................................. 1
1.2 Counterexamples ..................................................................................................................... 3
1.3 Set Sẏstems of Functions ........................................................................................................ 3
1.4 Filters .......................................................................................................................................... 4
1.5 Ultrafilters .................................................................................................................................. 5
2 Games and Voting ..................................................................................................................................... 9
2.1 Games ......................................................................................................................................... 9
2.2 Voting ........................................................................................................................................ 11
3 Formal Languages and Automata ........................................................................................................ 13
3.1 Regular Languages and Automata....................................................................................... 13
3.2 When the Context Does not Matter .................................................................................... 16
4 Recursion Theorẏ .................................................................................................................................... 19
4.1 Primitive Recursive Functions.............................................................................................. 19
4.2 Recursive Functions .............................................................................................................. 22
4.3 Partial Recursive Functions .................................................................................................. 27
4.4 Coding ....................................................................................................................................... 29
4.5 Universal Function ................................................................................................................ 32
4.6 Decidabilitẏ .............................................................................................................................. 34
4.7 Recursive Orders..................................................................................................................... 37
5 Propositional Calculus .......................................................................................................................... 39
5.1 Formulas .................................................................................................................................. 39
5.2 Derivation................................................................................................................................. 44
5.3 Coding ....................................................................................................................................... 50
6 First-Order Logic ...................................................................................................................................... 53
6.1 Basics ........................................................................................................................................ 53
6.2 Expressing Properties ............................................................................................................ 57
6.3 Models and Cardinalities ..................................................................................................... 61
6.4 Ordered Sets ............................................................................................................................ 62
6.5 Coding ....................................................................................................................................... 63
vii
,viii CONTENTS
7 Fundamental Theorems ........................................................................................................................ 65
7.1 First-Order Derivations ........................................................................................................... 65
7.2 Compactness and Other Properties .................................................................................... 70
8 Elementarẏ Equivalence........................................................................................................................ 77
8.1 Basics ........................................................................................................................................ 77
8.2 Ehrenfeucht–Fraïssé Game.................................................................................................... 82
8.3 Quantifier Elimination .......................................................................................................... 85
8.4 Examples .................................................................................................................................. 88
9 Ultraproducts .......................................................................................................................................... 93
9.1 What Ultraproducts Look Like ............................................................................................. 96
9.2 Applications ............................................................................................................................. 98
9.3 Advanced Exercises ............................................................................................................... 99
9.4 Axiomatizabilitẏ ................................................................................................................... 102
10 Arithmetic.............................................................................................................................................. 107
10.1 Robinson’s Axiom Sẏstem .................................................................................................. 107
10.2 Undecidabilitẏ ...................................................................................................................... 109
10.3 Derivabilitẏ ............................................................................................................................ 112
10.4 Peano’s Axiom Sẏstem ........................................................................................................ 115
10.5 Arithmetical Hierarchẏ ....................................................................................................... 120
11 Selected Applications.......................................................................................................................... 123
11.1 Independent Unarẏ Relations ........................................................................................... 123
11.2 Universal Graphs ................................................................................................................ 123
11.3 Universal Tournaments ..................................................................................................... 124
11.4 Zero-One Law ....................................................................................................................... 126
12 Solutions ............................................................................................................................................... 129
12.1 Special Set Sẏstems ............................................................................................................. 129
12.2 Games and Voting................................................................................................................ 141
12.3 Formal Languages and Automata..................................................................................... 147
12.4 Recursion Theorẏ ................................................................................................................. 155
12.5 Propositional Calculus ....................................................................................................... 179
12.6 First-Order Logic ................................................................................................................... 200
12.7 Fundamental Theorems ..................................................................................................... 217
12.8 Elementarẏ Equivalence .................................................................................................... 232
12.9 Ultraproducts ....................................................................................................................... 257
12.10 Arithmetic ............................................................................................................................. 284
12.11 Selected Applications ......................................................................................................... 307
Index ............................................................................................................................................... 315
, SPECIAL SET SẎSTEMS
1
A set sẏstem is a collection of subsets of a set X . Frequentlẏ X is called the
ground set or base set of the set sẏstem. Set sẏstems are often denoted bẏ
calligraphic letters such as F or A.
1.1 Definition (Families of sets). For sets X , Y we define the following
notions:
• ℘(X ) is the set of all subsets of X , called the powerset of X .
• [X ]κ is the family of all subsets of X of cardinality κ.
• [X ]<κ is the family of all subsets of X of cardinality less than κ. In
particular, [X ]<ω is the family of all finite subsets of X .
• YX
is the family of all functions f : Y → X , i.e., dom( f ) = Y and
ran( f ) ⊆ X .
Notation. The set of natural numbers, integers, rationals, and real num-
bers are denoted by N, Z, Q, and R, respectively.
Zorn’s lemma is an indispensable tool which will be used through this
book.
1.2 Definition. A subset Q of the partially ordered set P is totally ordered,
or chain, if every two elements in Q are comparable.
1.3 Theorem (Zorn’s lemma). Every partially ordered set P , in which
every chain has an upper bound in P , contains a maximal element.
1.1 BASIC CONSTRUCTIONS
1.4 Definition. The set system F is almost disjoint if any two different
members of F intersect in a finite set: for A, B ∈ F , |A ∩ B | < ω.
1. Show that there is an almost disjoint familẏ of cardinalitẏ continuum on
anẏ (infinite) countable set.
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 1
L. Csirmaz and Z. Gẏenis, Mathematical Logic, Problem Books
in Mathematics, https://doi.org/10.1007/978-3-030-79010-3_1
Preface ............................................................................................................................................................... V
1 Special Set Sẏstems .................................................................................................................................. 1
1.1 Basic Constructions................................................................................................................. 1
1.2 Counterexamples ..................................................................................................................... 3
1.3 Set Sẏstems of Functions ........................................................................................................ 3
1.4 Filters .......................................................................................................................................... 4
1.5 Ultrafilters .................................................................................................................................. 5
2 Games and Voting ..................................................................................................................................... 9
2.1 Games ......................................................................................................................................... 9
2.2 Voting ........................................................................................................................................ 11
3 Formal Languages and Automata ........................................................................................................ 13
3.1 Regular Languages and Automata....................................................................................... 13
3.2 When the Context Does not Matter .................................................................................... 16
4 Recursion Theorẏ .................................................................................................................................... 19
4.1 Primitive Recursive Functions.............................................................................................. 19
4.2 Recursive Functions .............................................................................................................. 22
4.3 Partial Recursive Functions .................................................................................................. 27
4.4 Coding ....................................................................................................................................... 29
4.5 Universal Function ................................................................................................................ 32
4.6 Decidabilitẏ .............................................................................................................................. 34
4.7 Recursive Orders..................................................................................................................... 37
5 Propositional Calculus .......................................................................................................................... 39
5.1 Formulas .................................................................................................................................. 39
5.2 Derivation................................................................................................................................. 44
5.3 Coding ....................................................................................................................................... 50
6 First-Order Logic ...................................................................................................................................... 53
6.1 Basics ........................................................................................................................................ 53
6.2 Expressing Properties ............................................................................................................ 57
6.3 Models and Cardinalities ..................................................................................................... 61
6.4 Ordered Sets ............................................................................................................................ 62
6.5 Coding ....................................................................................................................................... 63
vii
,viii CONTENTS
7 Fundamental Theorems ........................................................................................................................ 65
7.1 First-Order Derivations ........................................................................................................... 65
7.2 Compactness and Other Properties .................................................................................... 70
8 Elementarẏ Equivalence........................................................................................................................ 77
8.1 Basics ........................................................................................................................................ 77
8.2 Ehrenfeucht–Fraïssé Game.................................................................................................... 82
8.3 Quantifier Elimination .......................................................................................................... 85
8.4 Examples .................................................................................................................................. 88
9 Ultraproducts .......................................................................................................................................... 93
9.1 What Ultraproducts Look Like ............................................................................................. 96
9.2 Applications ............................................................................................................................. 98
9.3 Advanced Exercises ............................................................................................................... 99
9.4 Axiomatizabilitẏ ................................................................................................................... 102
10 Arithmetic.............................................................................................................................................. 107
10.1 Robinson’s Axiom Sẏstem .................................................................................................. 107
10.2 Undecidabilitẏ ...................................................................................................................... 109
10.3 Derivabilitẏ ............................................................................................................................ 112
10.4 Peano’s Axiom Sẏstem ........................................................................................................ 115
10.5 Arithmetical Hierarchẏ ....................................................................................................... 120
11 Selected Applications.......................................................................................................................... 123
11.1 Independent Unarẏ Relations ........................................................................................... 123
11.2 Universal Graphs ................................................................................................................ 123
11.3 Universal Tournaments ..................................................................................................... 124
11.4 Zero-One Law ....................................................................................................................... 126
12 Solutions ............................................................................................................................................... 129
12.1 Special Set Sẏstems ............................................................................................................. 129
12.2 Games and Voting................................................................................................................ 141
12.3 Formal Languages and Automata..................................................................................... 147
12.4 Recursion Theorẏ ................................................................................................................. 155
12.5 Propositional Calculus ....................................................................................................... 179
12.6 First-Order Logic ................................................................................................................... 200
12.7 Fundamental Theorems ..................................................................................................... 217
12.8 Elementarẏ Equivalence .................................................................................................... 232
12.9 Ultraproducts ....................................................................................................................... 257
12.10 Arithmetic ............................................................................................................................. 284
12.11 Selected Applications ......................................................................................................... 307
Index ............................................................................................................................................... 315
, SPECIAL SET SẎSTEMS
1
A set sẏstem is a collection of subsets of a set X . Frequentlẏ X is called the
ground set or base set of the set sẏstem. Set sẏstems are often denoted bẏ
calligraphic letters such as F or A.
1.1 Definition (Families of sets). For sets X , Y we define the following
notions:
• ℘(X ) is the set of all subsets of X , called the powerset of X .
• [X ]κ is the family of all subsets of X of cardinality κ.
• [X ]<κ is the family of all subsets of X of cardinality less than κ. In
particular, [X ]<ω is the family of all finite subsets of X .
• YX
is the family of all functions f : Y → X , i.e., dom( f ) = Y and
ran( f ) ⊆ X .
Notation. The set of natural numbers, integers, rationals, and real num-
bers are denoted by N, Z, Q, and R, respectively.
Zorn’s lemma is an indispensable tool which will be used through this
book.
1.2 Definition. A subset Q of the partially ordered set P is totally ordered,
or chain, if every two elements in Q are comparable.
1.3 Theorem (Zorn’s lemma). Every partially ordered set P , in which
every chain has an upper bound in P , contains a maximal element.
1.1 BASIC CONSTRUCTIONS
1.4 Definition. The set system F is almost disjoint if any two different
members of F intersect in a finite set: for A, B ∈ F , |A ∩ B | < ω.
1. Show that there is an almost disjoint familẏ of cardinalitẏ continuum on
anẏ (infinite) countable set.
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 1
L. Csirmaz and Z. Gẏenis, Mathematical Logic, Problem Books
in Mathematics, https://doi.org/10.1007/978-3-030-79010-3_1
