Mathematical-Logic1

Before: 数理逻辑CS2950是ACM班大一下要求修的一门课，这门课本质上还是一门数学课，一般也是数学系的同学可能会上的（而不是计算机系🤣）。Prof是Yin Qiang，Yijia Chen的学生。后续会更新这门“抽象”的课的Lecture Notes❤️

Methematical Logic 1 Introduction & The Syntax of First-order Logic

Course Introduction

Four Problems mainly

• What is a mathematical proof
• What makes a proof correct
• Is there a boundary of provability
• Can computers find proofs

Q1.What is a mathematical proof

Based on first-order logic

Q2.What makes a proof correct

Gödel Completeness Theorem

Q3.Is there a boundary of provability

Gödel’s First Incompleteness Theorem

Q4.Can computers find proofs

Any computer program cannot decide whether an arbitrary input mathematical statement has a proof.
Turing’s undecidability of the halting problem.(图灵停机问题不可判定)

Below is A Proof of Q4:
φP,x has a proof | P will eventually halt on input x
1.construct the mathematical statement φx,x
2.call the program T on input φx,x
3.if T(φx,x) = yes then run forever else halt

Then we can get that H(H) haltss iff H(H) does not halt.(Using what we know up)

The Syntax of First-order Logic 一阶逻辑语法

Alphabets 字母表

an nonempty set of symbols 非空符号的集合

Word 词

A word w over A(an Alphabet) is a finite sequence of symbols in A,i.e,
$$
w = w_1w_2…w_n
$$
$
w_i \in A
$
$A^*$ denotes the set of all words over A

Countable Set

There exists an injective function(单射) α from N onto M
At most countable: if M is either finite or countable

Two lemmas
1.These three equivalent:
(1)M is at most countable
(2)an surjective function f:N -> M
(3)an injective function f:M -> N
2.A is most countable,then $A^*$ is countable.

Terms 项

Variable Constant are both S-terms.
And if f is a n-ary function symbol in S,then f(S-terms) is also a S-term.

Formula 公式

The set $L^S$ of S-formulas contains precisely those words in $A^∗_S$ which can be obtained by applying the following rules finitely many times.

Variables 变量

Let t be a S-term, then var(t) is the set of variables in t.

Free Variables 自由变元

We say that an occurrence of x in φ is free if it is not in the scope of any ∀x or ∃x.
只有出现在约束范围内的变量才算是约束出现的

Sentence 句子

If free(φ) is ∅,then it’s a sentence. 没有自由变元
Reflect Mathematical characteristics.
$L_N^S$:= {φ | φ an S-formula with free(φ) ⊆ {v0, . . . , vn−1}}.