Lecture 4 (11.11.96)

Previous lecture: Lecture 3 , Overview , Course home page ,

How to Prove Non-definability ? (Continuation)

Repetition: Back and Forth Games or Ehrenfeucht-Fraisse Games in many variations.
We solved the exercise of the previous lecture on winning strategies.

We looked at more examples to understand the game.
Examples: We analized the cases of the

empty vocabulary;
vocabularies with a finite number of unary predicates;
finite linear orders.

THEOREM Planarity is not first order definable on unordered graphs.

We discussed the role of linear orders.

THEOREM Evenness is not first order definable on ordered graphs.

THEOREM Connectivity is not first order definable on ordered graphs.

To show that order matters we introduced TCL, the logic with a built in transtive closure operator.

Proposition Connectivity is TCL definable on unordered graphs.

Proposition Evenness is TCL definable on ordered graphs.

Next lecture: Lecture 5