Question

Let \(\sigma^{s}\) be the Skolem form of \(\sigma\). Consider only sentences. (i) Show that \(\Gamma \cup\left\\{\sigma^{s}\right\\}\) is conservative over \(\Gamma \cup\\{\sigma\\}\). (ii) Put \(\Gamma^{s}=\left\\{\sigma^{s} \mid \sigma \in \Gamma\right\\}\). Show that for finite \(\Gamma, \Gamma^{s}\) is conservative over \(\Gamma\). (iii) Show that \(\Gamma^{s}\) is conservative over \(\Gamma\) for arbitrary \(\Gamma\).

Short answer

For all cases, Skolemization preserves conservativity.

Step-by-step solution

Understand the Concept of Skolemization

Skolemization is a process used in logic to eliminate existential quantifiers by introducing new function symbols. When \(\sigma\) is a sentence and \(\sigma^{s}\) is its Skolem form, this conversion preserves satisfiability—the property that if a formula is satisfiable, its Skolem form is also satisfiable and vice versa in a specific context.

Proving Conservativity for Part (i)

To show \(\Gamma \cup \{\sigma^{s}\}\) is conservative over \(\Gamma \cup \{\sigma\}\), we need to demonstrate that if \(\Gamma \cup \{\sigma\}\) is consistent (i.e., has a model), then \(\Gamma \cup \{\sigma^{s}\}\) is also consistent, and any sentence provable from \(\Gamma \cup \{\sigma^{s}\}\) is already provable from \(\Gamma \cup \{\sigma\}\). Skolemization specifically doesn't change the satisfiability of the original theory; it just gives a different representation. Hence, their extensions do not affect continuity: any model of \(\Gamma \cup \{\sigma\}\) can be adapted to fit \(\Gamma \cup \{\sigma^{s}\}\), ensuring no additional theorems are introduced.

Show Conservativity for Finite Set in Part (ii)

For a finite set \(\Gamma\), \(\Gamma^{s} = \{\sigma^{s} | \sigma \in \Gamma\}\) should also be conservative over \(\Gamma\). Since each formula is Skolemized independently, each maintains the properties of conservativity similar to Step 2. Once more, it suffices that each Skolemized formula \(\sigma^{s}\) preserves the satisfiability from \(\sigma\). In a finite set, the theory modeled by \(\Gamma\) extends seamlessly to \(\Gamma^{s}\), and no new information gets added inadvertently.

Extend Conservativity Proof to Arbitrary Set in Part (iii)

For the infinite case of arbitrary \(\Gamma\), we argue similarly as with finite, using the fact that Skolem functions are added uniformly without changing original dependencies and satisfiability. Since any finite subset of \(\Gamma\) shows conservativity, by compactness theorem in logic, the entire set does too. Thus, if any sentence is provable from \(\Gamma^{s}\), it is also provable from \(\Gamma\) since \(\Gamma^{s}\) does not introduce new dependencies beyond skolemized representations.

Key concepts

Conservativity in Logic

Conservativity in logic refers to the idea that extending a theory with additional axioms or rules does not lead to new theorems that contradict the original theory. In simple terms, when you add something new to your current theory, it shouldn't change the original truths of that theory.

In the context of Skolemization, when we take a theory, say \( \Gamma \), and Skolemize it to form \( \Gamma^{s} \), conservativity ensures that \( \Gamma^{s} \) does not prove any new sentences that were not already consequences of \( \Gamma \).

• If \( \Gamma \) is consistent, meaning it has a model (or a way that all sentences in it can be true together), then \( \Gamma^{s} \) is also consistent.
• Every consequent of \( \Gamma^{s} \) is already a consequent of \( \Gamma \). So, even though we change the form, we don't change the logical consequences.

This concept is crucial in logic because it helps maintain the original integrity and truth of a theory, even after modifications.

Satisfiability Preservation

Satisfiability preservation refers to a property of logical transformations where if a statement or theory is satisfiable, its transformation remains satisfiable as well. In simpler terms, we want to ensure that if a theory has a model (a way to make all its statements true), it still does after we transform it.

When it comes to Skolemization, this transformation specifically focuses on eliminating existential quantifiers by adding functions. Importantly, Skolemization maintains the satisfiability of the original formulas - this means if the original formula is true in some interpretation, so is the Skolemized form.

• If \( \sigma \) has a model, \( \sigma^{s} \) will also have a model in a similar structure.
• This preservation is vital to ensure logical transformations don't break the initial condition of truth.

This preservation is essential because it allows us to manipulate formulas while keeping their original truth value intact.

Compactness Theorem

The compactness theorem is a key principle in logic stating that if every finite subset of a set of sentences is satisfiable, then the entire set is satisfiable.

In simpler language, as long as you can make smaller parts of your theory true, the whole theory can also be true. This theorem proves very useful when dealing with infinite theories.

• The theorem reassures us that if a formula holds for every part of a model, it holds for the whole.
• It helps in proving that if each finite subset of a Skolemized theory \( \Gamma^{s} \) is conservative over \( \Gamma \), then the whole theory is conservative.

Use of compactness in logic helps streamline proofs and manage infinite processes in a finite manner. The compactness theorem assures us of the logical stability of the theories when extended.

Elimination of Existential Quantifiers

Eliminating existential quantifiers means converting statements in logic that use phrases like "there exists" into an equivalent form that doesn't require them. This often involves introducing new function symbols – a process called Skolemization.

When you see a logical statement of the form "for every x, there exists a y...", the goal is to replace the existential part with a Skolem function.

• It helps in simplifying complex logical statements and eliminations. For example, turning \( \exists x \) into a function like \( f(y) \), removing the need for existential quantifiers.
• Elimination is crucial because it generally leads to simpler expressions easier to work with during logical derivations and proofs.

By eliminating existential quantifiers, we maintain equivalence in satisfiability which leads us to an easier form to apply logical theories and proofs. Skolemization ensures that even without existential quantifiers, the logical meaning remains.