Shreyas’ Notes

# COMP 409

Liar’s paradox: “This sentence is false”

Excluded middle: Nothing between true and false (philosophically sus).

Digital abstraction: High/Low state.

Transitivity of implication:

1. If $p$, then $q$ ($p \implies q$)
2. If $q$, then $r$ ($q \implies r$)
3. Therefore if $p$, then $r$ ($p \implies r$)

Set of symbolic proposition. Set of truth values.

Connecting propositional connectives to logical operations. Let $P$ be the set of propositions. $F$ is the smallest set such that:

1. $P \subseteq F$
2. [closure] If $\psi \in F$, then:
• $\neg \psi \in F$
• $\psi \circ \psi \in F$

$F' := \bigcap \{W : W \text{ is a set of expressions that contain } P \text{ and satisfy closure} \}$

Theorem: $F'$ is the smallest set that contains $P$ and satisfies closure.

Alternative definition:

1. $F_0 = P$
2. $F_{i + 1} = F_i \cup \{(\neg \psi) : \psi \in F\} \cup \{(\phi \circ \psi) : \psi, \phi \in F\}$

Claim: $F'$ contains $P$ and satisfies closure.

Theorem: $F' = F$