Mathematical Logic

Some important ideas from Lectures on "Logic for Computer Science" by David Ben Shai.

Inductively defined Sets (Lecture 2)

Defintion 1. Given a set $A$ (core set) in a universe $X$ and a set of functions $P$ of arbitrary arities over $X$. Then $I(A,P)$ is defined as the minimal set (w.r.t inclusion) that contains the core set $A$ and is closed under $P$.

Defintion 2. Given a set $A$ (core set) in a universe $X$ and a set of functions $P$ of arbitrary arities over $X$. Then $I(A,P)$ is defined as: \begin{equation} \label{eq: IAP} \bigcap_{i}\{B | A \subseteq B \text{ and } B \text{ is closed under P }\} \end{equation} We wish to prove the equivalence of these definitions i.e.

Defintion 1. $\leftrightarrow$ Defintion 2.

Note that the minimality of $I(A,P)$ in the second definition is not completely trivial. Minimality w.r.t inclusion also leads to uniqueness.

An Auxiliary Result (Lecture 2)

Let us have a collection of sets $\{B_i\}_i$. Then for every $B_k \in \{B_i\}_i$ : \begin{equation} \label{eq: subset} \bigcap_{i}\{B_i\} \subset B_k \end{equation}

Structural Induction (Lecture 2)

Given an $I(A,P)$ and given a property $H$, our goal is to show that all members of $I(A,P)$ have the property $H$. A property is essentially a subset of $X$, hence, it is enough to show that $I(A,P) \subseteq H$.

Base Case: Show that $A \subseteq H$

Induction Step: Show that $H$ is closed under $P$

After the above steps, we have shown that $H$ is one of the $B$ in equation \ref{eq: IAP}. Using equation \ref{eq: subset}, we have that $I(A,P)\subseteq H$. Hence, Completing the proof.

Construction Sequence (Lecture 2)

Defintion 3. A Construction Sequence for a given $\alpha \in I(A,P)$ is the sequence $CS = \{\alpha_1,...,\alpha_n\}$, where $n \in \mathbb{N}$ such that for every $\alpha_i \in CS$, one of the following is true:

$\alpha_i \in A $

$\alpha_i = f(\alpha_{j_1},\dots,\alpha_{j_s})$, where $j_{q}$ are smaller than $i$ and $f \in P$.

A proof is a special type of construction sequence.

Claim: For every valid expression $\alpha$, $\alpha \in I(A,P)$ if and only if there exists a $CS$ for $\alpha$.

Showing that $\alpha \not \in I(A,P)$ (Lecture 2)

Key Idea: Identify syntactical properties $T$ (equivalently subsets of $X$) such that if $\alpha \in T \rightarrow \alpha \in I(A,P)$. Equivalently, identify $T$ such that $I(A,P) \subseteq T$. For showing that $I(A,P) \subseteq T$ use structural induction.

Showing that $\alpha \not \in I(A,P)$ for Propositional Logic (Lecture 3)

Key Ideas:

Identify $T$ syntactically such that it contains $A$ and is closed under $P$. Clearly, $T$ is a super set of $I(A,P)$ by definition.

T: If $\alpha \in PL$, where $PL$ stands for $I(A,P)$ for propositional logic, then $\alpha$ has the same number of left and right brackets

T: If $\alpha \in PL$, where $PL$ stands for $I(A,P)$ for propositional logic, then every proper initial segment of $\alpha$ has more left brackets than right brackets.

Construction Tree: Input: $\alpha$ Output: Decision wether WFF or not

1. Check if $\alpha \in A$

2. Check if it starts with a right bracket and ends with a left bracket else reject

3. Remove left bracket if the next symbol is $\neg$ i.e. (\neg \beta) then copy $\beta$, go to step 1. setting $\alpha = \beta$ else got to 4.

4. (Notice, a left bracket has been removed) Parse the expression from left till the number of right and left brackets is equal, remove the last left bracket. Split and got to step 1, for each of the branches.

Why is a construction Tree a proof of WFF? A Construction Sequence can be constructed by ordering the Construction tree from bottom up with respect to the levels.

Lecture 7

Review concepts:

$\Sigma$ is SAT if $\exists. v$ such that $v(\alpha) = \top$, $\forall \alpha \in \Sigma$

$\Sigma \models \alpha$ if $\forall v : \text{If} \Sigma \text{is SAT then}$ $v(\alpha)$ is SAT.

$\Sigma$ is complete

$\Sigma$ is maximally SAT $\Sigma \not\models \alpha \rightarrow \Sigma \cup \{\alpha\}$ is UNSAT

$\Sigma$ is SAT and complete iff $\Sigma$ is MAXSAT

$\Sigma \models \alpha$ iff $\Sigma \cup \{\neg \alpha\}$ is UNSAT.

$\Sigma \not \models \alpha$ iff $\Sigma \cup \{\neg \alpha\}$ is SAT.

Theorem [Finite Models]: For any $\Sigma$ such that $\Sigma \models \alpha$. Then $\exists$ $\Sigma_{\alpha}\subseteq \Sigma$ such that $\Sigma_{\alpha}$ is finite and $\Sigma_{\alpha} \models \alpha$.
Is $\alpha$ finite ?: He said $\alpha$ is finite, what if it is not finite ?

NAIVE IDEA. Restrict $\Sigma$ to the set of variables in $\alpha$
Problem in the idea : $\Sigma := \{(p_0 \lor p_i)\}_{i=1}^{\infty}$

Proof.
IDEA: $\alpha$ is finite restrict to propositional variables in $\alpha$ and create it's truth tables (say TT). We only need to worry about models in TT which are false. Because we only need to make sure that when they are FALSE then $\Sigma$ is FALSE as well. There are at most $2^{n}$ such models (n being propositional variables in $\alpha$). Consider one such assignment $v_i$, now because $\Sigma \models \alpha$, we know that $\Sigma$ can not be TRUE under $v_i$ i.e. there exists some $\alpha_i \in \Sigma$ $v_i(\alpha_i)$ is false. We can add the $\alpha_i$ to $\Sigma_{\alpha}$. We do this for all $\alpha_i$ for a given $v_i$ and then forall $v_i$. The obtained $\Sigma_{\alpha}$ is clearly finite because we only have finitely many models of $\alpha$. We need to show that it $\Sigma_{\alpha} \models \alpha$. Assume by contradiction that $\Sigma_{\alpha} \cup \neg \alpha$ is SAT. But this can not be the case because every $v$ such that $v(\neg \alpha)$ is TRUE i.e. $v(\alpha)$ is FALSE necessarily makes all formulas in $\Sigma_{\alpha}$ FALSE by construction. Hence, $\Sigma_{\alpha} \cup \neg \alpha$ is UNSAT. Hence,$\Sigma_{\alpha} \models \alpha$.

Defintion [Finite Satisfiability (FS)] $\Sigma$ is finitely $SAT$ iff $\forall \Sigma_0 \subseteq \Sigma$ then $\Sigma_0$ is SAT.

Theorem [Compactness] $\Sigma$ is SAT iff $\Sigma$ is FS (proved by Kurt Godel)
Proof. $$\text{Finite Models} \leftrightarrow \text{Compactness} $$ Compactness $\rightarrow$ Finite Models. Assuming the contrapositive i.e. $\neg$Finite Models i.e. $\forall \Sigma_{\alpha}$ such that $\Sigma_{\alpha}$ is finite then $\Sigma_{\alpha} \not \models \alpha$. Since, $\Sigma_{\alpha} \not \models \alpha$ then there exists $v$ such that $\Sigma_{\alpha}$ is SAT and $\alpha$ is UNSAT i.e. $v(\neg \alpha)$ is TRUE. Therefore $v(\Sigma_{\alpha} \cup \neg \alpha)$ is TRUE. Therefore $\Sigma_{\alpha} \cup \{\neg \alpha\}$ is SAT. But this is true for all $\Sigma_{\alpha} \subseteq \Sigma$. Hence, $\forall \Sigma_{\alpha} \subseteq \Sigma. \{ \Sigma_{\alpha}$ is SAT $\}$.Hence, due to compactness we have that $\Sigma$ is SAT.