any(), all() and empty iterable

[Chris Rebert]

On Sat, Apr 11, 2009 at 9:00 PM, John O'Hagan <mail at johnohagan.com> wrote:
> Hi,
>
> I was getting some surprising false positives as a result of not expecting
> this:
>
> all(element in item for item in iterable)
>
> to return True when 'iterable' is empty.
>
> I guess it goes into hairy Boolean territory trying to decide if an element is
> in an item that doesn't exist (if that's what's happening), but I would have
> thought not. It seems inconsistent with the behaviour of
>
> any(element in item for item in iterable)
>
> which returns False when 'iterable' is empty.
>
> Sorry if this has come up before, but 'any' and 'all' make for fruitless
> googling!
>
> Any light to be shed?

This is justified in formal logic by the concept of vacuous truth. See
http://en.wikipedia.org/wiki/Vacuous_truth

all(P(x) for x in y) #Original Python statement
∀x∈y. P(x)  #equivalent in formal logic
¬¬[∀x∈y. P(x)]  #apply Double Negation
¬[∃x∈y. ¬P(x)]  #negate Universal Quantifier

English interpretation: There does not exist a counterexample `x` in
the set `y` which fails to satisfy predicate `P`.
Comment: Indeed, in the case the set `y` is empty, there is no
counterexample to be had, and thus both the final statement and the
initial equivalent one are vacuously true. Yes, this may seem
unintuitive at first. Logic is like that sometimes.

Python equivalent to final statement: not any(not P(x) for x in y)
Comment: Likewise, in the case of a empty `y`, any() returns False, so
the code simplifies to `not False`, which obviously simplifies further
to just True.

So, if you agree with the behavior of any(), you must logically agree
with the behavior of all(). ;-)

Discrete mathematics FTW!

Cheers,
Chris

-- 
I have a blog:
http://blog.rebertia.com