用户: Scavenger/Recording Some Facts/Basics for Logic

We record some basic constructions of Logic here. In particular, we construct the ZFC system for set theory. A material for reference is, for example, [1].

We will use the notion of “naive set”, which is basically the first thing you have in mind while looking at this phrase. It admits no formal definition, since sadly there has to be something that cannot be defined, and we deliberately choose it to be this notion. We will use the word “set” to mean naive set, which can easily be recognized in the context, and hopefully this won’t cause much confusions. All the naive sets we will be considering are “naive” enough in nature, so hopefully this won’t cause any logical incorrectness.

1Propositional Logic

We begin with the construction of the propositional logic as an illustration of how things work in the theory of Logic.

Definition 1.1. The propositional logic consists of the following data (or formal symbols, if you prefer):

(i) A (specified) contably infinite set ${\mathrm{At}}_0$ of propositional variables $p_0,p_1,...,p_i,...$ ($i\in {\mathbb{Z}}_{\ge 0}$).

(ii) The logical connectives $\neg$ (negation), $\wedge$ (conjunction), $\vee$ (disjunction) and $\to$ (conditional).

(iii) Parentheses (and ).

The propositional logic is denoted ${\mathcal{L}}_0$.

Definition 1.2. The set $\mathrm{Frm}({\mathcal{L}}_0)$ of formulas of the propositional logic is the smallest subset of the set of all words of finite length consisting of symbols of the form $p_i$ ($i\in {\mathbb{Z}}_{\ge 0}$), $\neg$, $\wedge$, $\vee$, $\to$, (and ) such that:

(i) $p_i\in \mathrm{Frm}({\mathcal{L}}_0)$ ($i\in {\mathbb{Z}}_{\ge 0}$). (These are called the atomic formulas).

(ii) If $\varphi \in \mathrm{Frm}({\mathcal{L}}_0)$, then $\neg \varphi \in \mathrm{Frm}({\mathcal{L}}_0)$.

(iii) If $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$, then $(\varphi \wedge \psi )\in \mathrm{Frm}({\mathcal{L}}_0)$.

(iv) If $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$, then $(\varphi \vee \psi )\in \mathrm{Frm}({\mathcal{L}}_0)$.

(v) If $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$, then $(\varphi \to \psi )\in \mathrm{Frm}({\mathcal{L}}_0)$.

Let $x$ and $y$ be two words of finite length, we write $x\equiv y$ if they are exactly the same.

Theorem 1.3 (Unique Readability). Every element of $\mathrm{Frm}({\mathcal{L}}_0)$ is generated by a unique rule of Definition 1.2 in a unique fashion. More precisely, every element of $x\in \mathrm{Frm}({\mathcal{L}}_0)$ satisfies exactly one of the following conditions:

(i) $x$ is an atomic formula.

(ii) There exists $\varphi \in \mathrm{Frm}({\mathcal{L}}_0)$ such that $x\equiv \neg \varphi$.

(iii) There exists $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$ such that $x\equiv (\varphi \wedge \psi )$.

(iv) There exists $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$ such that $x\equiv (\varphi \vee \psi )$.

(v) There exists $\varphi ,\psi \in \mathrm{Frm}({\mathcal{L}}_0)$ such that $x\equiv (\varphi \to \psi )$.

Moreover, the $\varphi$ and $\psi$ in conditions (ii), (iii), (iv), (v) are unique.

Proof. The proof is easy.

$\square$

References

[1]	“Open Logic Project”, https://openlogicproject.org/