Re: SUO: Theory Query
On Fri, Apr 19, 2002 at 02:41:37AM -0400, John Sowa wrote:
> Yes, I admit that I meant aleph-1, since the set of all subsets of
> formulas is indeed uncountable (and yes, I am assuming the continuum
> hypothesis).
Just FYI, most set theorists seem to think CH is false (since the
universe with CH is intuitively much sparser than it is without it). It
is almost never assumed unless one is specifically investigating its
consequences.
> In comparing the size of the two lattices -- the lattice of all subsets
> of formulas and the lattice of all deductively closed sets of formulas,
> I meant that for every one of the latter, there are infinitely more
> (in fact, uncountably more) of the former:
Well, again, that is not an accurate way to put it, since "infinitely
more" here is simply relative to one particular mapping. The two
lattices have the same cardinality, and so, relative to a 1-1 mapping
between the two, for every member of your lattice L there is *exactly
one* member of the power set lattice P. And indeed there will be 1-many
mappings from P to L relative to which, for every member of P, there
will be *uncountably many* more members of L. What you are pointing out
is simply that there is a particularly "natural" 1-many mapping from L
to P with the analogous property, viz., the one that maps each
deductively closed set S to the (uncountably many) members of P that
have S as their deductive closure, one that has you in its clutches,
apparently:
> 1. Every deductively closed set S is infinite, since if it contains p,
> it also contains p and p, p or p, p and (p or p), p or (p and P)...
Of course.
> 2. Any subset of these formulas can be deleted from S and the remainder
> would still have S as its deductive closure.
That is true.
> 3. Since there are uncountably many such possible deletions, the
> number of sets that have S as their deductive closure must be
> uncountably infinite.
Quite so.
> 4. Therefore, for every element S of the lattice of all deductively
> closed sets, there are infinitely many elements of the lattice of
> all subsets -- all of which have S as their deductive closure.
Right; this is the "natural" mapping noted above. But, once again,
there is also a mapping from the power set lattice P to your lattice L
relative to which, for every set of sentences there are uncountably many
deductively closed sets --- though I can only give you a simple
cardinality argument for this, rather than a construction analogous to
the one you give.
> 5. In fact, the lattice of all deductively closed sets is isomorphic
> to the set of all equivalence classes of the set of all subsets of
> formulas under the condition that U and V are in the same equivalence
> class if they have the same deductive closure.
Sure thing.
> Point #5 characterizes the lattice of all deductively closed sets as a
> quotient space.
Yep.
> CM> The relation that gives rise to your lattice is then simply the
> > subset relation.
>
> No, because you can delete uncountably many sentences from any element
> of the lattice while still staying within the same equivalence class.
I meant that the relation on YOUR lattice L is simply the subset
relation.
> On the question of the proper use of the term "tautology":
Yeah yeah, ok, just so long as you acknowledge that there is a
substantive distinction between the truths of propositional logic and
those of predicate logic generally. You want to use the word
"tautology" for the latter -- go right ahead, but *given* that this is
out of step with current usage, and hence confusing, I don't really
understand your insistence upon retaining a now archaic usage. The
important thing is that there is a distinction there, and we need words
to name it. Refusing to use "tautology" in this context strikes me as
somewhat perverse.
Highest regards,
-chris