Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I'm not sure I follow the definition of $K'$. What is $x$? – Asaf Karagila Dec 16 '12 at 20:05
up vote 4 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Seriously? 12 seconds? :-) – Asaf Karagila Dec 16 '12 at 20:15
@Asaf: It would have been a good minute the other way if I hadn’t done an Amazon Look Inside to see what notation Enderton was using! – Brian M. Scott Dec 16 '12 at 20:17
Well, it would have been a good minute in my favour if I hadn't had to get up and tend the cat for a moment! :-) – Asaf Karagila Dec 16 '12 at 20:18
@Asaf: Ah, but I didn’t mention the trip out to the living room to see whether my old Enderton was close enough to the current edition to be useful! :-) (It wasn’t.) – Brian M. Scott Dec 16 '12 at 20:19
And I didn't mention my trip to the bar which I am going to take in a few minutes, because it hadn't occurred yet and has nothing to do with this question! :-) – Asaf Karagila Dec 16 '12 at 20:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.