Hacker News Reader

Comment by celias | Hacker News Reader

all([]) returns True but any([]) returns False, which seems like a contradiction.

It follows from exactly the same logic. The following are theorems, at least as long as x and y are lists of Booleans:

    all(x + [True]) == all(x)
    any(x + [False]) == any(x)
    all(x + y) == (all(x) and all(y))
    any(x + y) == (any(x) or any(y))
    not all(x) == any(not xi for xi in x)
    not any(x) == all(not xi for xi in x)

Any other values for all([]) and any([]) would cause some or all of these theorems to be correct for all values of x and y except the empty list. In practice this would mean you would have a bug in your program on most occasions where the argument of one of these functions was empty, unless you included a special case for empty sequences.

For example, suppose you're processing a request that includes some tasks and some attachments. You might write something like this:

    if any(task.is_failed() for task in request.tasks):
        raise TaskFailed(request)

    if any(x.is_too_large() for x in request.attachments):
        raise AttachmentTooLarge(request)

Clearly for this code to do the right thing in the case where a request has tasks or attachments but not both, we need any([]) to be false. And the corresponding requirement applies to all([]) if our task interface is a little different:

    if not all(task.is_succeeded() for task in request.tasks):
        raise TaskFailed(request)

Now, there are occasionally programs where you do need a special case for empty sequences; for example, if you have three search results, you might want to return a page containing just those results, but if you have zero, you probably don't want to just return an empty page — the user might think the software is just broken. And in the above example, if there are neither any tasks nor any attachments, it might or might not be useful to report that the user accidentally submitted an empty request. But it is unusual for such a special case to just fall out of a possible alternative semantics of all() and any().

The way I think about it is the base case of a recursive function to evaluate the two. In order to preserve folding Boolean AND across a list your base case must be true. Folding Boolean OR across a list only works if your base case is false.

False is the identity element for Or, similar to how Zero is the identity element for addition.

True is the identity element for And, similar to how One is the identity element for multiplication.

Hardly. As described in the article `all([])` is equivalent to `∀x Fx` or "all unicorns are blue". `any([])` is equivalent to `∃x Fx` or "a blue unicorn exists".

How so? Any means "at least one is true" and all means "all in the array are true".

all: "there is none in the array that is false".

>> all means "all in the array are true"

> all: "there is none in the array that is false"

You... are aware that those statements are exactly the same, right?

They're not. In fact, that's what this entire article is about.

I don't know what to say to this. They are exactly the same. It's not a controversial point. You could write an article on the theme "why apples fall upward in the winter", but that wouldn't make apples fall upward in the winter.

See e.g. https://en.wikipedia.org/wiki/Universal_quantification#Negat...

> It's not a controversial point.

I wouldn't have thought so personally, but alas, here we are ;)

Perhaps you two are not using precise enough language?

The common definitions for 'all' and 'any' as used in math are certainly on thaumasiotes' side. But English as a natural, every-day language is a bit more fuzzy.

Correct. That is the point this article is making.

"all in the array are true" is not specific about how the empty case ought to be interpreted. That's not at all to say all([]) ought to be False; the wording is simply under-specified.

Where as "there is none in the array that is false" is clearly True when all([]) is encountered.

Thus the statement cannot be simplified to the English statement "all in the array are true", without introducing ambiguities.

As a general rule, this is why we don't perform mathematics (or programming) in English.

EDIT: Just to clarify why this is ambiguous, in case anyone reading is still not following (although I'd suggest reading the article!)

English is an (informally) consensus based language. Understanding boolean logic is not a precursor to being able to interpret common language, in particular English. Just because one has knowledge of logic (mathematics) and we happen to have given some operation the English name "all", that does not mean the English word "all" in general speech refers to this logical operation. Especially since, as the article describes, the mathematical consensus for this logic has only largely shifted to be interpreted this way in the last several hundred years. The English word "all" predates the current mathematical consensus (which isn't even universal) by thousands of years.

Additionally, if for some reason you are interpreting the written word "all" (no matter the context) as the logical operation, then "all in the array are true" is not a viable definition for this word, it's self-referential and thus ambiguous. "there is none in the array that is false" on the other hand is clear in its meaning (if not slightly grammatically incorrect).

Mostly agreed about the vernacular. Though a minor nitpick: mathematics has been around for longer than English.

As for eg Python: when in doubt, going with the mathematical usage of the term is the Right Choice here.

For another interesting example: the negation of must and may in English vs their German equivalents.

In English 'You must not do X.' means that refraining from X is obligatory. In German the equivalent 'Du musst nicht X-en.' means that engaging in X is not obligatory.

Both usages make sense in their respective languages. And both usages have translations into formal logic. Just different ones.

> The English word "all" predates the current mathematical consensus (which isn't even universal) by thousands of years.

This is at the edge of possibility, but it's certainly not a slam dunk. "All" is not an indo-european word; it's restricted to Germanic languages.

> Just because one has knowledge of logic (mathematics) and we happen to have given some operation the English name "all", that does not mean the English word "all" in general speech refers to this logical operation.

This isn't a good argument; all you and the article are saying is that people have vocally objected to the meaning of "all" for a long time. They still do. But this isn't sufficient to claim that the objections reflect a disagreement over the meaning of "all". If you carefully explain to people how you want them to interpret sentences like "every cat is in a box", and then you show them pictures and ask them whether or not every cat is in a box, most people will screw it up. That's not because they didn't understand you; it's because they are very bad at the task.

It is quite clear that the vernacular meaning of the English word "all" coincides with the formal meaning of the logical universal quantifier. You can poll any number of people and they'll give you a definition that just so happens to match the logical quantifier. People don't object to all([]) being true after thinking about what "all" means to them -- they object before thinking about it.

If you poll people asking for a definition of "all", you're doing it wrong. Instead, you should ask them to use the word to describe various cases, and derive the actual definition from that.

I doubt it'll match formal logic.

> It's not a controversial point

It's not important to the discussion at hand, but I enjoyed your wording here, because even though you're right, in a sense this is one of the most controversial points in mathematics: https://en.m.wikipedia.org/wiki/Constructivism_(philosophy_o...

They are not. If there’s adres zero entries, the first one isn’t true.

This is also consistent with Boolean algebra where the empty sum is 0 (any), and the empty product is 1 (all).

I think of it as: the minimum of an empty set is +inf as the min of a union must be the min of the mins. Similarly, the max of empty must be -inf.

Those will get you the right result if you use them as an initial value in a fold and the set is not empty. They're not correct on their own; an empty set has no minimum or maximum.

It depends. You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system.

But eg Python's minimum and maximum functions don't do that. They throw an error by default.

In mathematical terms, if you have a lattice https://en.wikipedia.org/wiki/Lattice_(order) you can always just arbitrarily introduce a least and greatest element, and all the relevant laws stay valid.

Whether that's a good idea for your application or not, is a different question.

In programming, types often give you trouble. Eg the integers don't have least or greatest element, but you want your minimum function over list of integers to return an integer. So throwing an error is the only choice, if you can't represent something like minus infinity in your return type.

> You _can_ define minimum and maximum over empty sets exactly as described and get a consistent mathematical system.

You can define infimum and supremum that way. But I was under the impression that wherever the concept of a "minimum element" of a set is used, the minimum element of any set must be an element of that set.

So e.g. the positive reals have an infimum, 0, but no minimum. The page you link doesn't do much to dispute this idea; it uses "minimum" and "maximum" to talk about the largest and smallest elements of the lattice, but never to talk about a property that a subset of the lattice might have.

I guess you are right.

Of course, the Python function named 'min' could very well implement an infimum in this case, and it would be OK.

In general, there's some conventions, like using the words 'minimum' vs 'infimum'. Or stressing the property 'result of min should be an element of the input set' vs 'min on lists should behave like repeated application of min on two arguments starting with the neutral element'.

The right choice depends on context. In lots of programming context, I find stressing the connection with the minimum monoid was useful.

> Of course, the Python function named 'min' could very well implement an infimum in this case, and it would be OK.

Using min(∅) = +inf and max(∅) = -inf would violate the otherwise valid constraint that min(x) ≤ max(x). I'd be a little uncomfortable with it for that reason.

> The right choice depends on context.

Definitely.

> Using min(∅) = +inf and max(∅) = -inf would violate the otherwise valid constraint that min(x) ≤ max(x). I'd be a little uncomfortable with it for that reason.

Excellent point!

Funny enough, we have the same with 'any' and 'all':

For most lists of booleans: all(l) ≤ any(l). Or equivalently all(l) implies any(l).

But that property is broken for empty lists.

Hmm, I think I might understand the case for `all([]) == False` a bit better now. Though I still disagree with it.

Read up on DeMorgan’s law.

De Morgan's law isn't the right one for this. You want the identity ∀x.P(x) ⟺ ¬∃x.¬P(x).

∀x.P(x) is obviously true when the universe is empty -- no counterexamples exist. ∃x.P(x) is obviously not true in that case -- no examples exist.

That is De Morgan if you expand the quantifiers.

You have to make some assumptions if you want to "expand the quantifiers". In particular, you have to assume that the universe is non-empty, which is a really bad idea if you're commenting in this thread.

Reply on news.ycombinator.com