logoalt Hacker News

aabhay • 12/09/2024 • 2 replies • view on HN

The puzzle is referring to the concept of a vacuous truth (https://en.wikipedia.org/wiki/Vacuous_truth).

In most logic frameworks, the All function (upside down A in standard logic notation) is true if and only if no statement within the set is false (i.e. All his hats are green if he has no hats). This is for several reasons:

- it allows for more coherent empty set functions. For example if we take the power set of a set, that power set has the same All value as the standard set (since the power set includes the empty set)

- it allows for early stopping on false statements. So you can define the statement as a lazy executor of all child conditions

Replies

predictand • 12/09/2024

I learned about Vacuous Truth the hard way recently when I found out that `every` method in JavaScript returns `true` for empty arrays as well.

➕ show 4 replies
feoren • 12/09/2024

As a programmer, my favorite way to think about Vacuous Truth is to think about the relationship between binary operators and their corresponding sequence operators. Think about taking an operator like "plus" and extending it to sequences or lists of things. What properties would we like those extensions to have? Let's start with a simple example:

Sum is the "sequence extension" of Plus.

    Sum([a, b, c]) = a + b + c -- basically our definition

    Sum([a, b, c]) = Sum([a, b]) + Sum([c]) -- distributive

    Sum([]) = 0 -- identity
Let's keep things simple by assuming our operator is associative and has an identity (i.e., it is a monoid). We can take any monoid and extend it to sequences. Assume @ is some monoid. We define the sequence aggregate "Agg" as:

    [0] Agg([a, b, c]) = a @ b @ c == ((a @ b) @ c) == (a @ (b @ c)) -- definition + associativity

    [1] Agg([a, b, c]) = Agg([a, b]) @ Agg([c]) -- distributive

    [2] Agg([]) = Identity(@)
Note that property 2 is required if we want Agg([]) to have a value at all, since Agg([]) == Agg([] concat []) == Agg([]) @ Agg([]). If Agg([]) doesn't have a value, then it's not really properly distributive, since Agg([a]) == Agg([a] concat []) == Agg([a]) @ Agg([]) == ???. So we see that if we have an identity for the operator, it really should be the same as Agg([]).

So let's extend AND and OR to sequence operators. The extension of AND can be called "Every", and it operates on sets of booleans. In particular, Every([]) == Identity(AND). The Identity of AND is "true", so Every([]) == True. The extension of OR can be called "Any", and Any([]) == Identity(OR) == False.

This is the easiest way for me to remember the truth values of Every([]) and Any([]): they must be the identities of the corresponding boolean operators.

Any([Your name is Bob, you can fly]) == Any([Your name is Bob, you can fly] concat []) == Any([Your name is Bob]) OR Any([You can fly]) OR Any([]) == (Your name is Bob) OR (You can fly) OR (False). Any([]) == False.