3

Also known as Enderton 1.2.10.c. I'm struggling with this question so much. It has been asked and answered on here. I have also read the solution from other sources, but just cannot grasp the main idea. I know that it cannot be the subset of the original infinite set.

As for now, I am following the solution from University of Pennsylvania. I have encountered two main problems.

  1. Why are there two separate cases for $\Delta_n$? Specifically, a case in which $\Delta_n$ $\models$ $\sigma_n$, another which $\Delta_n$ $\not\models$ $\sigma_n$.
  2. Are $\Sigma$ and $\Sigma_n$ two separate sets? If I understand it right, the first one contains a series of sentence symbol, while the second one contains one symbol only.
Bedivere
  • 81
  • 2
    You have described the general picture pretty well yourself. You could improve your question greatly by explaining what happens when you go line-by-line through one the proofs that you link to, and explain where and how you get stuck. – Lee Mosher Aug 20 '21 at 16:23
  • What don’t you understand about the answer in the first link? I’d guess “layman’s terms” are really not useful here, because these are technical terms, and the “trick” in the answer doesn’t reveal much underlying it. – Thomas Andrews Aug 20 '21 at 16:27
  • I’d add this proof is not constructive. If you have a recursively enumerable sequence $\sigma_n$ you get a new sequence $\rho_n$ of the form you’ve described, but then you have to exclude the $\rho_n$ which are provable, and that exclusion is not constructive. – Thomas Andrews Aug 20 '21 at 16:34
  • @LeeMosher The answer in the third link (University of Pennsylvania) is the most detailed, so I will go with it. When the proof introduce $\Delta_n$, I don't understand why they have to introduce two separate cases: One for $\Delta_n$ $\models$ $\sigma_n$, and the other for $\Delta_n$ $\not\models$ $\sigma_n$. The second problem I have is that why do the proof specify $\Sigma$ and $\Sigma_n$ as two separate sets? Is it because the first one contains a series of sentence symbols, while the second one contains only one symbol (a singleton)?

    I hope you don't mind me asking more questions.

     – Bedivere Aug 20 '21 at 17:50
  • @ThomasAndrews For the first link, I don't even understand what is set enumeration. I think it is some kind of bijection established between two sets? And I lost it when the answer introduces the set \textit{$T$}, that is basically \textit{$T_0$} without tautologies, without specifying why they do so. For now, I will be grateful if you can help me answer the same questions I have posed to LeeMosher. Thank you. – Bedivere Aug 20 '21 at 17:56
  • Add that to your question, not in comments. Comments are not part of the question. Until you edit the question, it is an insufficient question. – Thomas Andrews Aug 20 '21 at 17:58
  • As for removing tautologies, ask yourself: Can an independent set of axioms have a tautology? – Thomas Andrews Aug 20 '21 at 17:59

1 Answers1

1

First regarding your question "Are $\Sigma$ and $\Sigma_n$ two separate sets? If I understand it right, the first one contains a series of sentence symbol, while the second one contains one symbol only.", clearly they're different and $\Sigma_n$ doesn't necessarily contain only one sentence symbol from the definition in your reference:

Let $\Sigma$ = {$\sigma_0$, $\sigma_1$, . . .}. Let $\Sigma_n$ = {$\sigma_i$| i < n}.

So $\Sigma$ is an infinite set of wffs (sentences), while $\Sigma_n$ contains only $n$ such formulas (indexed from $0$ to $n-1$).

Regarding your question "Why are there two separate cases for $\Delta_n$? Specifically, a case in which $\Delta_n$ $\models$ $\sigma_n$, another which $\Delta_n$ $\not\models$ $\sigma_n$."

Here in the proof $\Delta_n$ appears in the general inductive step which is assumed to be tautologically independent and equivalent to $\Sigma_n$, but this by no means $\Delta_n$ $\models$ $\sigma_n$ or $\Delta_n$ $\not\models$ $\sigma_n$ (remember from above that $\Sigma_n$ contains only $n$ such formulas indexed from $0$ to $n-1$). So we have to proceed with two cases. The first case ($\Delta_n$ $\models$ $\sigma_n$) simply means $\Sigma_n$ $\models$ $\sigma_n$ by inductive hypothesis and thus $\Delta_{n+1}$ = $\Delta_n$ is equivalent to $\Sigma_{n+1}$. So we just find such a construction using $\Delta_n$ itself. Another case we need to construct $\Delta_{n+1}$ according to some specific Horn clause algo as shown in your reference as $\Delta_{n+1}$ = $\Delta_n$ ∪ {$\delta_n$ → $\sigma_n$} where $\delta_n$ is defined as $\alpha_0$ ∧ · · · ∧ $\alpha_k$ each of which is a member of $\Delta_n$. Your another Math Exchange reference mainly discussed this second case since that reference constructed $\Delta_n$ in a more specific way.

cinch
  • 1,648
  • 1
  • 4
  • 12
  • I have understood your explanation. However, I still have trouble with the proof from UPenn, so I hope you can reply back. I am confused with the case $\Delta_n$ $\not\models$ $\sigma_n$, in which if $\Delta_{n + 1}$ $\models$ $\alpha$, then $\Sigma_{n + 1}$ $\models$ $\alpha$. The proof contains only one line: "Conversely, if $\Sigma_{n + 1}$ $\models$ $\delta_n$ $\rightarrow$ $\sigma_n$, so ... $\Delta_{n + 1}$ $\models$ $\sigma$." Why is the first clause assumed? Because this means the two sets are equivalent only if we accept the assumption, which is not how it works. – Bedivere Aug 21 '21 at 16:36
  • Also, how can we construct $\Delta_{n + 1}$ from the assumption that $\Delta_n$ $\not\models$ $\sigma_n$? For example, if $\Delta_0$ $\not\models$ $\sigma_0$, then $\Delta_1$ = $\Delta_0$ $\cup$ {$\delta_0$ $\rightarrow$ $\sigma_0$} = $\emptyset$ $\cup$ {$\emptyset$ $\rightarrow$ $\sigma_0$}. How do I go on simplifying this expression? – Bedivere Aug 21 '21 at 16:43
  • @Rampage "Conversely..." is the proof of the other direction for the equivalence of $\Delta_{n+1}$ and $\Sigma_{n+1}$ which is the final goal of the inductive step for the second case outlined in my answer. So to proceed with the other direction, $\Sigma_{n+1} \models \delta_n \rightarrow \sigma_n$ is simply true (not assumed) since $\delta_n$ is true in $\Delta_n$ and $\sigma_n$ is also true in $\Sigma_{n+1}$. As for your second comment question, you cannot further simplify the set of wffs, the added conditional is the only added independent wff during the inductive construction step. – cinch Aug 22 '21 at 03:14