Dominik Farhan

Orders and trees

Definition. A tree is a set T whose elements are partially ordered by

<_T

with a unique least element called root in which the predecessors of every node are well ordered by $<_T$.

Definition. A sucessor of a node

x

in a tree

T

with the ordering

<_T

is a node

y

such that

x \leq_T y

y

is an immediate sucessor if there exists no node

z

such that

x <_T z <_T y

and

z \neq x

Definition. A level of a tree. The zeroth level of a tree consists only of the root. The

k+1

level consists of immediate sucessors of nodes on the level

k

Lemma. Every node in a tree is on exactly one level

Proof. Suppose that there exists a node that is on at least two different levels

x, y

. Then this node has an immeditate predecessor that must be also on two levels. We can iterate this construction until we arrive to the root. Root is only on the zeroth level (this comes trivialy from the definition of levels) and thus all its sucessors are also only on one level. Which is contradiction.

Definition. A path of

T

is a miximal lineary ordered subset of

T

Theorem (König's lemma). If a finitely branching tree is infinite, it has an infinite path.

Proof. By induction. The first element in the path, the root, has infinitely many sucessors by the assumption that the tree is infinite. Let now have a path where each node was choosen so that it has infinitely many sucessors. Now denote

x_{n-1}

the last node on this path. By the assumtion that the tree is finitely branching this node has only finitely many immediate sucessors. Because

x_{n-1}

has infinitely many sucessors there exists at least one node in the set of sucessors of

x_{n-1}

that has infinitely many sucessors. We choose any such node to be

x_n

on our path and we can continue constructing the path like this indefinetely.

Theorem (Compactness theorem). Set of first order sentences has a model if and only if every finite subset has a model.

For the propositional (zeroth-order) logic this can be proven using the theorem above.

Definition. A formation tree is a finite tree

T

of binary sequences whose nodes are labeled with propositions that satisfies the following conditions:

The leaves are labeled with propositional letters
Root is $\varnothing$
If a node $\sigma$ is labeled with a proposition of the form $(a \land b), (a \lor b) (a \rightarrow b) (a \leftrightarrow b)$ its immediate successors, $\sigma^0, \sigma^1$ are labeled with $a, b$ .
If a node $\sigma$ is labeled with proposition $\neg a$ its unique immediate sucessor is labeled with $a$

Definition. A support of a proposition is the set of propositional letters that occur as labels of the leaves of the associated formation tree.

Theories and models

Definition. A propositional theory

T

over language

\mathbb{P}

is a set of propositions from

VF_{\mathbb{P}}

. We call these propositions axioms of

T

Definition. An assignment

v

is a model of

T

if all axioms of

T

are true in

v

Definition. Let

T

be a theory over language

\mathbb{P}

and

\varphi

some proposition from

\mathbb{P}

, we say that the proposition

\varphi

is valid in

T

if it is true in every model of

T

Definition. A

\delta (T)

of consequences of

T

is a set of all propositions that are true in

T

Definition. An

T

over

\mathbb{P}

is an anextension of

T'

over

\mathbb{P}'

\delta(T') \subset \delta(T)

T

is a conservative extension if

\phi('T) = \delta{T} \cap VF_{\mathbb{P'}}

. Extensions are simple if they are over the same language. Theories are equivalent if one is extension of the other and vice versa.

Dominik Farhan

A few notes on propositional logic

Annoying definitions one keeps forgetting

Orders and trees

Theories and models