1
$\begingroup$

On Page 28, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed),

Say that a set $\Sigma_1$ of wffs(short for well-formed formulas) is equivalent to a set $\Sigma_2$ of wffs iff for any $\alpha$ wff, we have $\Sigma_1 \vDash \alpha$, iff $\Sigma_2 \vDash \alpha$. A set is independent iff no member of $\Sigma$ is tautologically implied by the remaining members in $\Sigma$. Show that the following hold.

(b) An infinite set need not have an independent equivalent subset. (c) Let $\Sigma = \{\sigma_0, \sigma_1, . . .\}$; show that there is an independent equivalent set $\Sigma'$. (By part (b), we cannot hope to have $\Sigma' \subseteq \Sigma $, in general.)

I don't know why an infinite set need not have an independent equivalent subset? Here's my attempt to find one with the help of axiom of choice.

$\Sigma$ is a set, so is its power set $P(\Sigma)$. Thus, $K =\{x \in P(\Sigma): \exists y,y \in x, y \text{ is tautologically implied by } x-\{y\}\}$ and $K'=\{x' \subseteq x \in K: \forall y,y \in x', y \text{ is tautologically implied by } x-\{y\}\}$are also sets. Let $g : K \to K'$ such that $g(x) \subseteq x$ By axiom of choice, there exists a choice function $h$, such that for any $x \in K'$, $h(x)\in x$. So we have $f = h \circ g$, such that $h(g(x)) \in x' \in K'$ and $x \subseteq x'$

Let $\sigma'_0 = f(\Sigma)$. Given all $\sigma'_j (j < k)$, $\sigma'_{k}=f(\Sigma - \{\sigma'_j: j < k\})$, provided that $g(\Sigma - \{\sigma'_j: j < q\}) \in K'$ for all $q \le k$.

Such process will stop at or before some ordinal $\lambda$, because $K'$ is a set.So we have $\Sigma - \{\sigma'_j: j \le \lambda \}$ or $\Sigma -\{\sigma'_j: j < \lambda \}$ as an independent equivalent subset of $\Sigma$.

EDIT: Finally I realized that there is no guarantee that $\Sigma - \{\sigma'_j: j \le \lambda \}$ or $\Sigma -\{\sigma'_j: j < \lambda \}$ is non-empty.

  • 0
    I'm not sure I follow the definition of $K'$. What is $x$?2012-12-16

2 Answers 2

4

Consider the following case: $\Sigma$ is an infinite independent set, $\{\sigma_n\mid n\in\omega\}$. Let $\varphi_n=\bigwedge_{i\leq k}\sigma_i$, then $\Phi=\{\varphi_n\mid n\in\omega\}$ is an infinite set, and it is not hard to see that $\Phi$ and $\Sigma$ are equivalent.

But what happens? If $\varphi\in\Phi$ is any wff, then $\varphi=\varphi_n$ for some $n\in\omega$ and clearly $\varphi_{n+1}=\varphi_n\land\sigma_{n+1}$. Therefore $\varphi_n$ is implied by $\varphi_k$ whenever $k>n$. So there is no infinite independent subset which is equivalent to $\Phi$. In fact the only independent subsets of $\Phi$ are singletons.

4

What if $\sigma_n\to\sigma_{n+1}$ for each $n\in\omega$? For instance, what if $\sigma_n$ is the wff $\mathbf{A}_0\land\ldots\land\mathbf{A}_n$? No subset containing more than one of the $\sigma_n$’s is independent.

  • 0
    @Asaf: Okay: you win! I’m only going out to the kitchen for more coffee.2012-12-16