In article <[EMAIL PROTECTED]>,
Paul Rubin <http://[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] writes:
> > Ah, thanks... and does "comprehension" have any special computer
> > science meaning?
>
> It is from mathematical set theory. If you write something like
>
> { p | [some logical expression indicating that p is prime] }
>
> then that denotes a set (the set of all prime numbers). That every
> such formula names a set is called the axiom of comprehension. The
> above notation is sometimes called set-builder notation.
>
> Frege's original system of logic (late 19th century), now called
> "naive set theory" had "unrestricted comprehension" which meant
> you could say anything at all where the logical expression went.
> This made the system inconsistent, because of Russell's paradox
> ("c is the class of all classes that are not members of themselves.
> So is c a member of itself?").
>
> Axiomatic set theory has a restricted axiom of comprehension that
> requires the logical expression to be a first order formula with
> a certain syntax, to avoid such paradoxes.
Not that it matters, but the fix is not by using a first-order
formula with a certain syntax. The comprehension itself is
not
{p | p satisfies some condition},
it's
{p in S | p satisfies some condition},
where S is some set. You're not allowed to ask for _everything_
satisfying a certain condition, just for the elements of
some given set satisfying the condition.
The paradox doesn't come from being allowed to say anything
at all. If you write
(*) c = {x | ~(x e x)}
(where ~ means "not" and "a e b" means "a is an element of b")
you get Russell's paradox: if c is an element of c then it follows
that c is not an element of c, while if c is not an element of c
then it follows that c is an element of c. The problem is not
with the formula ~(x e x); given a set S, there's no problem
with the set {x in S | ~(x e x)}, for example. "restricted"
versus "unrestricted" does not refer to some restriction on
that formula - the "restriction" in restricted comprehension
is the "x in S" part - we're restricting things to elements
of a given set S.
Writing informally people often omit the "in S" part when the
S in clear from the context. For example, your original
{p | p is prime} should officially be {p in N | p is prime},
where N is the set of natural numbers - the first form is
often written because the "in N" is implicit in "prime".
> Anyway, list comprehensions in programming languages got their
> name because of their resemblance to set-builder notation that
> invoked the axiom of comprehension.
--
David C. Ullrich
--
http://mail.python.org/mailman/listinfo/python-list
