Forbidden Induced Subgraphs and the Łoś–Tarski Theorem
Forbidden Induced Subgraphs and the Łoś–Tarski Theorem
Let <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś-Tarski Theorem from classical model theory implies that <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> is definable in first-order logic (FO) by a sentence φ if and only if <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</i> has a …