MATH 3265 Class Notes 01-27-2025

notelogic

Terminology About Trees

A tree is a partially ordered structure with a unique least element (called the root) such that for every node $x$ in the tree, the set of elements $\{y\mid y\le x\}$ is finite and linearly ordered.

Root: the node at the top of the tree (in picture). Predecessors: nodes above something (in picture). Successors: nodes below something (in picture). Leaves: nodes with no successors. Branch: a maximal linearly ordered subset.

Trees needn’t be finite. This will particularly arise once we begin to work with modal logic.

In a finite tree, every branch is uniquely determined by a leaf.

Example: Recursive Definition

Give a recursive definition for $V(\alpha )=\#$ variables occurring in $\alpha$. (Count all occurrences … $V(((p⟹\neg p)\vee q))=3$).

Base: $V(v_i)=1$.

Inductive: $V(\neg \phi )=V(\phi )$, $V(\phi \ast \psi )=V(\phi )+V(\psi )$.

Thus the final definition is,

$$V(\alpha )=\{\begin{array}{ll}1& \text{ if }\alpha \text{ is }{v}_i,\\ V(\phi )& \text{ if }\alpha \text{ is }\neg \phi ,\\ V(\phi )+V(\psi )& \text{ if }\alpha \text{ is }(\phi \ast \psi ).\end{array}$$

Unique Readability of Formulas

For each formula $\alpha$, exactly one of the following holds:

1. $\alpha$ is a proposition variable, which is uniquely determined.
2. $\alpha$ has form $\neg \phi$ for a unique formula $\phi$.
3. $\alpha$ has form $(\phi \ast \psi )$ where $\phi$, $\psi$, and $\ast$ are uniquely determined.