Prove: there is no set of first order sentences such that the negation of König’s lemma is satisfied

62 Views Asked by At

Prove that there does not exist a set $\Delta$ of first-order sentences such that the negation of König’s lemma is satisfied.

Negation:
For each directed graph $T$ if $T\models\Delta$ then either $T$ is not tree or $T$ doesn't contain infinite path.

My trial
Let’s suppose that such $\Delta$ exists. Then, let’s extend language by two constant vertices $u,v$ and add to $\Delta$ sentences $\phi_k:$ neither $u$ nor $v$ is reachable from the other in less than $k$ edges. Using the compactness theorem let’s consider any finite subset $\Delta_0\subseteq\Delta$. It is of course satisfiable - it is sufficient to get a finite chain (path) of appropiate length.

So thanks to the compactness theorem $\Delta$ is satisfiable. As you can see here, I don't manage to reach a contradiction. I show where I got stuck in order to show you my reasoning and (no)skills.

Be forgiving for me, please :) Try to explain me it in possiblily easy way and try to sell intuition please!

1

There are 1 best solutions below

8
On BEST ANSWER

What you've concluded is that there is a model of $\Delta$ which is not connected as a graph - so, it satisfies König's lemma, since in particular it is not a tree!

I suspect you are misunderstanding what an infinite path is. An infinite path in a graph is a sequence of vertices $v_1, v_2, . . .$ such that $v_1Ev_2Ev_3E...$. Two vertices infinitely far apart do not constitute an infinite path; in particular, an infinite path has no "end".

In fact, I think you've copied the problem incorrectly. Let $\Delta$ say "There are exactly two vertices, and no edges at all." Then any model of $\Delta$ is not a tree. I think the problem you're supposed to solve is:

Show that there is no $\Delta$ such that the models of $\Delta$ are exactly the trees with no infinite paths.

Note the iff: if $T$ is a tree with no infinite paths, then $T\models \Delta$.

Here's a hint for this problem. Consider the expanded language with new constant symbols $c_1, c_2, c_3, . . . $, and the theory $$\Delta'=\Delta\cup \{c_iEc_{i+1}: i\in\mathbb{N}\}.$$ Do you see why $\Delta'$ has a model? And do you see what that model has to do with the original problem?