[HN Gopher] Why does all() return True if the iterable is empty?
___________________________________________________________________
Why does all() return True if the iterable is empty?
Author : vikrum
Score : 80 points
Date : 2023-08-25 17:01 UTC (5 hours ago)
(HTM) web link (blog.carlmjohnson.net)
(TXT) w3m dump (blog.carlmjohnson.net)
| whoopdedo wrote:
| def all(L): for i in L: if not L:
| return False return True
|
| Seems quite clear when presented that way. Same with `any`.
|
| > In logic, this is called the principle of bivalence: there are
| only two values that a proposition can have, true or false. But
| Python has None, many other programming languages have null or
| nil, and Zen has mu. Maybe adding another value would help?
|
| If `all` were in Python v1 it would have thrown an exception when
| called with an empty list. (Said jokingly, or is it?)
| dragonwriter wrote:
| Yes, that's an implementation of all() that produces the
| current result.
|
| What the article explains is why the thing that produces the
| current result has the name "all()".
|
| While both can be answers to different senses of "Why does
| all() behave the way it does?", they are fundamentally answers
| to very different questions that English, being ambiguous in
| the way natural language tends to be, allows to be expressed in
| the same words, the implementation explanation is not a clearer
| answer to the _same_ question answered by the examination of
| the history of philosophy and predicate logic, and presenting
| it as if it were is fundamentally misunderstanding the question
| being answered by the longer piece.
| Buttons840 wrote:
| We could have just used: all(L) if L else True
| ajross wrote:
| This is the essence of the issue. All the pontification about
| (sigh) periods of western logic is missing the point.
|
| The object isn't question isn't a statement of philosophical
| logic[1]. It's a computer program. And, yeah, it's implemented
| by iterating over the list and returning false if it finds
| anything false. If it gets to the end, it returns true. _And
| that is all that needs to be said, because it is an algorithm
| and not a statement about the world._ Maybe it 's wrong. In
| which case, file a bug. But the bug isn't about philosophy
| either, it's about "I want to solve a problem and all() is
| giving me the wrong answer".
|
| [1] Not to be confused with _actual mathematics_ , of course.
| Math doesn't have semantic arguments like this because it
| starts from a stance of defining terms and axioms such that no
| one gets confused over words. Sigh, again.
| cpgxiii wrote:
| This and the parent are mistaking the "how" all([]) is True
| for the why. The code is the "how", but it doesn't just
| _exist_. It could just as easily end in
| return len(L) > 0
|
| instead, which would obviously have different behavior. The
| code is the embodiment of a particular design, the "why",
| which has a more complex history.
| ajross wrote:
| There's no treatment about any "complex history of the
| design of all()" though. The article is a bunch of
| nattering about philosophical semantics.
|
| And I'm saying that's just plain dumb. This is an
| engineering discipline. If there's a "why", then the author
| of the code is the resource, not (sigh) philosophers. Go
| ask Guido, or check the commit messages. Don't ask
| Aristotle, he can't hack.
|
| And the proof (that's right, proof) that I'm right is this:
| imagine Guido (or whoever) had indeed chosen the opposite
| convention for all(). It's easy to imagine. And it's
| equally easy to imagine people getting confused about it
| and asking about it. And you could reply _with exactly this
| same article_ trying to explain the "why" behind it as
| part of two traditions of philosophy.
|
| That's right: the same words explain the opposite
| convention too. That's not an explanation for "why", is it?
| This whole discussion is _QUITE LITERALLY_ providing zero
| insight into the question you 're imagining it's answering!
| It's like asking someone "Why did you paint your house
| blue?", and them answering "Well, you see, I could have
| painted it blue, or red."
| rickboyce wrote:
| I think the analysis is really interesting, but I suspect it's
| quite possible that this behaviour is just a result of optimising
| the implementation than GVR taking sides in a 2,500 year old
| philosophical debate.
|
| Both implementations of all() and any() short-circuit by
| returning as soon as a fasly element in all or a truthy element
| in any is iterated over.
|
| The origin of these two functions seems to be this post:
| https://www.artima.com/forums/flat.jsp?forum=106&thread=9819...
|
| Guido makes no comment on empty iterables, but does comment on
| the final implementation needing to be efficient. It's possible
| this behaviour is just the engineering trade off made for a
| slightly more efficient implementation.
|
| The initial commit of these two functions -
| https://github.com/python/cpython/commit/96229b191814556622b... -
| is exactly as Guido's suggestion, but does include a test case
| for empty iterables for both functions so we know it wasn't
| overlooked.
| Minor49er wrote:
| Why try to reduce assertions made against something that doesn't
| exist down to a boolean result? Clearly the answer is undefinable
| neuromanser wrote:
| The assertion is against the set (list in the TFA).
| rwmj wrote:
| It makes recursion easier. For example:
| [?](head::tail) = head [?] [?](tail)
|
| if [?]([]) is defined as true then this works for the single
| element list.
| IshKebab wrote:
| It's easily definable. all(x) is true iff none of the elements
| in x are false. This is really the only sane option. To do
| anything else would be a weird special case for []. Like
| defining len([]) == None. There's no point; it just makes
| everything more complicated and worse.
| neuromanser wrote:
| > In logic, this is called the principle of bivalence: there are
| only two values that a proposition can have, true or false. But
| Python has None, many other programming languages have null or
| nil, and Zen has mu. Maybe adding another value would help?
|
| Hoare labeled his invention of null a "billion dollar mistake".
| SQL NULL can't be far behind. Boolean logic has 4 unary and 16
| binary operators, ternary logic has 27 and 19683, respectively.
| That's not helpful, that's intractable!
|
| I cannot recommend C. J. Date's books enough.
| jewel wrote:
| > SQL NULL can't be far behind.
|
| SQL's NULL is far more useful though, since NULL != NULL. That
| lets you do things like join two tables with a column and not
| have the NULLs match.
|
| Consider, for example: select * from users
| where id = null;
|
| That will give 0 results, even if somehow you have a user with
| a null id.
|
| It's also really nice for non-ID, non-reference fields to
| represent N/A. For example, user.birthdate can be NULL if the
| birthdate is not known.
|
| SQL also lets you choose when you want NULL to be allowed for a
| column, so it's less likely to be a gotcha.
| tomp wrote:
| For anyone wondering how to fix the above query so that it
| works for arbitrary X (which can be NULL or non-NULL):
| SELECT * FROM users WHERE status IS NOT DISTINCT FROM $x
| neuromanser wrote:
| > Consider, for example: > select * from users where id =
| null; > That will give 0 results, even if somehow you have a
| user with a null id.
|
| Why is it useful? Can you elaborate?
| neuromanser wrote:
| > SQL's NULL is far more useful though, since NULL != NULL.
|
| That's not true! (Nor is it false.) NULL = NULL _IS NULL_ ,
| NULL != NULL _IS NULL_. I can 't overstate this: as soon as
| either (or both) operand of any binary relational operator is
| NULL, the whole expression is NULL!
|
| I'm not being an asshole, this is the exact mistake that
| makes SQL NULL the other billion dollar sink!
|
| This is really funny, because i wasn't aware of laying such a
| beatiful trap.
| Karellen wrote:
| > as soon as either (or both) operand of any binary
| relational operator is NULL, the whole expression is NULL!
|
| Isn't _is_ a binary operator?
|
| Because "NULL is NULL" is True (not NULL).
| jerf wrote:
| SQL NULL has to be the quintessential example of why
| programming can't just blindly follow math. The NULL truth
| table makes all the sense in the world in a mathematical
| context.. and it is a _total pain_ to program with. Letting
| NULL == NULL be "true" and NULL == anything else be
| "false" might be slightly less principled, but it would be
| _soooo_ much safer and have prevent so very many bugs.
|
| (And it's not like that's some sort of mathematical
| nonsense either. It makes perfect sense to not create a
| special value that represent "outside my universe of
| values" and then refuse to equate any two of them. It makes
| perfect sense to declare a distinguished "outside my
| universe of values" and let it be equal to any other such
| value on the grounds that it is mathematically impossible
| to witness any differences between them anyhow so _within_
| the system they are indeed equal.)
| Smaug123 wrote:
| The mistake of `null` is _not_ that it exists at all - it's
| often the case that you can't answer a question, and it's
| extremely useful to be able to model your inability to answer a
| question! The mistake of `null` is instead that it forces every
| reference type to be an optional. This is a mistake because
| some things can in fact be known. In practice, when everything
| is optional, it's so boilerplate-heavy to enforce the condition
| "this is known" at runtime for every property that everyone
| inevitably ends up not enforcing that condition most of the
| time; the bugs arise when one side of a boundary assumes for
| expediency that the other side has enforced it.
|
| It is in general very reasonable for a function to return an
| optional bool; think of `List.tryHead [false, true, false]`.
| What is unreasonable is for all boolean functions to return
| optional bools.
| feoren wrote:
| Humans have trouble with this because our brains cannot let go of
| the context surrounding a question. For example, a logician may
| find it funny to walk up to a police officer and say "all of the
| hookers in my trunk are dead." That is technically true, even
| though there are no bodies in his trunk. But the brain of the
| police officer is awash with why someone would be talking about
| dead hookers _at all_. Surely something is going on! I would not
| expect that logician to have a great day.
|
| So we read things about bags with no marbles and bearded kings of
| France and pink goblins and we think someone is taking the piss
| out of us, because we can't let go of the context behind those
| statements. Why are we talking about goblins _at all_?
|
| All models are wrong. Some models are useful. If you're getting
| hung up on how it just _doesn 't make sense_ that "A -> B" is
| always true when A is false (which is really the same issue), you
| have to realize that it's not meant to be intuitive, it's meant
| to be _useful_. And the theory of predicate logic where ALL([])
| == TRUE is _much_ more useful than the one where it 's FALSE or
| even NULL. It's more useful because TRUE is the identity element
| of the monoid AND and ALL is the unary set-aggregation of AND.
| There really cannot be any other choice if you want your theory
| to fit in with the rest of mathematics and logic, which a useful
| theory must. It's internally consistent, useful, and really does
| make deep sense if you are able to let go of context-laden real-
| world examples.
|
| You should not rely on English sentences making sense to be a
| good metric of whether a model is useful or not. Consider:
| Dogs must be carried on escalators.
|
| You don't have a dog. Are you allowed on the escalator? Of course
| you are. This is, in fact, a perfect example of why
| Your_Dogs.All(is_carried) must be TRUE if Your_Dogs is empty.
| Hard hats must be worn in work areas.
|
| You don't have a hard hat. Are you allowed in the work area? No!
| How can you tell the difference between these two situations?
| Only from context. Yet you can see how easy it would be to form
| the 2nd sentence as an (erroneous) example of
| "Enforce(HardHats.All(are_worn))", but it's _not that_. It 's
| more like
| "Enforce(People.Where(in_work_areas).All(have_hard_hat_on))" --
| if there is someone in a work area, then they must have a hard
| hat on. But if there's nobody in the work area, no rule is being
| broken! Again we actually see ANY([]) having to be true here.
|
| When you come up with weird-sounding examples where you're sure
| All([]) must be False, you're just poisoning your intuition with
| unhelpful context.
| adameasterling wrote:
| I had to deal with this problem in our product, which has a
| visual programming language. I opted to throw an exception if,
| for whatever reason, "all()" receives an empty list! I had
| forgotten I'd done that. There's no explanation for it in the
| code.
|
| As I sit here justifying my own reasoning, though, it sort of
| makes sense. For ordinary people (for whom this product is
| supposed to be for), I figure if they put in nothing, that was
| probably just a mistake.
| waffletower wrote:
| I miss using the Midje testing library for Clojure, as it has the
| 'truthy' and 'falsey' functions. It reduced these variously
| bivalent and trivalent conditions into binary in a way that would
| do Stephen Colbert proud
| (https://web.archive.org/web/20150121223555/http://www.merria...)
| Of course you or I can add such to what ever language we are
| using that supports actual functions -- or smash some abstraction
| of truthiness into those that don't.
| cheald wrote:
| It helps to think in terms of `any` first:
| any([], predicate) => false
|
| This is plainly obvious, because it is illogical to say "the
| predicate is true for at least one member of the empty set".
|
| If we can agree on that, then all([], predicate) must be true,
| because the complement of all(list, predicate) is any(list,
| predicate')
|
| The naive assumption is that the complement of all(list, p) is
| all(list, p'), but this is demonstrably false, because in the
| case of an empty list: all([], e => e) and all([], e => !e) would
| both return the same value. > [[], [true],
| [false]].map(s => s.every(e => e) == !s.every(e => !e)) [
| false, true, true ]
|
| Instead, its proper complement is any(list, p'), which means that
| all(list, p) = !any(list, p') > [[], [true],
| [false]].map(s => s.every(e => e) == !s.some(e => !e)) [
| true, true, true ]
|
| So, for all([], p) to be false, any([], p') would have to be
| true, which makes even less sense than all([], p) => true.
| dkersten wrote:
| "Are there any items in this list that are true? No? Ok, then
| False"
|
| I don't care about any fancy philosophy. What's important is what
| kind of operation you want for when implementing algorithms, and
| False is what I always want in cases where I do "all".
| stop50 wrote:
| You can define all() as "is there any False item?" Which is
| False for an empty list, but true for any list with an false
| item. all(list) == anyfalse(list)
| shawnz wrote:
| You're describing the "any" function, which actually does
| return false in that case already.
| kadoban wrote:
| > "Are there any items in this list that are true? No? Ok, then
| False"
|
| There's no particular reasoning that this is any more
| compelling than: "Are there any items in this list that are
| false? No? Ok, then True"
| jamilton wrote:
| "is any item in this list true" is any(), which is different
| from all().
| robot_no_421 wrote:
| > What's important is what kind of operation you want for when
| implementing algorithms, and False is what I always want in
| cases where I do "all".
|
| Why would you want "all" to produce results that are
| inconsistent with logic and mathematics? Consider this
| tautology, which is a result of De Morgan's laws: for any list
| L, we have that
|
| all(L) == ~any([~x for x in L]).
|
| In other words, if all([]) == False, then you would also
| logically need to accept that:
|
| False == all([]) == ~any([~x for x in []]) == ~any([])
|
| which means that we'd require any([]) == True. And that's
| definitely an illogical result.
| CJefferson wrote:
| Can you give a couple of examples where you want False for an
| empty all? I'd be interested to see them, as I've found I
| always want True.
| edflsafoiewq wrote:
| all = foldr and True any = foldr or False
| hiAndrewQuinn wrote:
| So glad I know this language
| xcdzvyn wrote:
| Man I love Haskell.
| ptx wrote:
| > _in the new logic, you can't soundly argue that "all dogs are
| mammals; all mammals have fur; therefore, all dogs have fur"
| because one person shaving their dog suddenly makes "all mammals
| have fur" untrue._
|
| Isn't this just a problem with an unclear definition of "having
| fur"? Is the article saying that the old logic would hand-wave
| this problem away because it's about "universals and essences"?
| aportnoy wrote:
| 1 is the multiplicative identity
|
| 0 is the additive identity
|
| all([]) is True
|
| any([]) is False
| NoToP wrote:
| A man goes into court not sure how he got there or what he's
| accused of. The judge starts saying the opening formalities. "If
| and only if every member of the jury is convinced you are guilty
| then this court will convict you." The man looks around. "Your
| honor, there are no members of the jury." The judge slams the
| gavel hard. "Guilty". That's the trivial case.
| [deleted]
| nwah1 wrote:
| The codebase of Apache Kafka must be littered with this.
| shadowgovt wrote:
| FTA:
|
| > But it is interesting how even extremely practical twenty-first
| century programming can get drawn into millennia old
| philosophical controversies, intentionally or not.
|
| This turns out to happen a lot. I can't find the source right
| now, but there was a good essay I read ages ago about how
| questions that are abstract and hand-waveable in day-to-day life
| become cornerstones of architecture rapidly in computer science
| and software engineering. The cow in the field epistemological
| puzzle [http://www.philosophical-investigations.org/2021/09/the-
| cow-...] maps directly to the nature of proving code is "correct"
| by testing (and any practicing coder has a story of false-
| positive or false-negative tests, as well as times they
| identified one of those by a "gut check" telling them "That
| result... doesn't feel right; I should investigate further").
| Similarly, the philosophical question of "sameness" or "equality"
| ends up concretized over and over again in language design;
| there's a reason languages end up with so many ways to say
| 'equals', and it's because the underlying question of what it
| means for two things to be the same thing is legitimately
| philosophically complicated!
| michaelteter wrote:
| The problem isn't with all([]) -> True, the problem is the if []
| -> False.
|
| [] exists. It happens to be empty, but it is neither a False nor
| a None. Therefore it should be a True if applying truthiness to
| it. IMO, any expression which does not result in an actual False
| or None should be judged as True.
|
| - edit -
|
| On second thought, all([]) -> True is also a poor choice, same in
| Ruby. The idea of judging an empty collection as having all items
| being any value is flawed, since there are no items to measure.
| It is on par with 1 / 0.
|
| This is fun: in both Ruby and Python...
|
| [].all? -> true
|
| all([]) -> True
|
| [].any? -> false
|
| any([]) -> False
|
| So both languages agree that all elements of any empty collection
| are true, but if you ask them if any of the elements are true,
| they deny it. So they are all true while also not having any true
| elements.
| kstrauser wrote:
| I disagree. An empty string is False. Any empty set is False.
| An empty dict is False. Basically, in Python emptiness implies
| falseness. This has practical benefits: users =
| database.fetch_users() if not users:
| print("Didn't find anyone.")
|
| and name = input() if not name:
| print("You didn't enter a name.")
|
| Of course you could work around those like `if len(users) == 0`
| or `if not len(users)` or `if name != ""`, but each of those is
| uglier.
|
| `if not users` translates very nicely to English: "if there are
| not any users...". I'm glad Python defined `bool(list)` that
| way.
| x3n0ph3n3 wrote:
| That's exactly how Ruby behaves.
| michaelteter wrote:
| Ruby and Python agree on the all/any functions, but they
| disagree on the if. And in the "if", I think the Ruby result
| is better.
| mabbo wrote:
| I think a key point is that (correct me if I'm wrong here) in
| predicate logic you can rewrite [?]x Fx
|
| As Not [?]x (not Fx)
|
| Ie: "for all x, f(x)" implies the opposite of "there exists an x
| where not F(x)".
|
| People seem to have less of a problem with Not
| [?]x (not Fx)
|
| when the universe is x is empty.
|
| I usually explain it to junior developers by telling them to
| imagine it's a for loop over a list that returns true/false if it
| finds a value that doesn't match what's expected, and the
| opposite of it reaches the end of the list.
| kubb wrote:
| Every one (all) of the set of zero elements is true. It's not
| counterintuitive or inconsistent, this is the only way that makes
| sense.
|
| The complement is also consistent. None of the set of zero
| elements are true. So there aren't _any_ true 's.
|
| They're symmetrical cases, and negation turns them into each
| other. Not-any-true is equivalent to all-false, and not-all-true
| is equivalent to any-false.
| justin_oaks wrote:
| Regardless of whether you thing the return value should be True
| or False, this behavior violates the Principle of Least
| Astonishment [0] for a significant number of people.
|
| Such violations in software inevitably lead to bugs that could
| have been avoided. The real question in my mind isn't what the
| return value should be. The question is "How can this problem be
| wholly avoided?"
|
| Some have suggested requiring a default return value when the
| iterator argument is empty. Others have suggested throwing an
| error. Perhaps others will suggest the all() function shouldn't
| exist, although that may be throwing the baby out with the
| bathwater.
|
| [0]
| https://en.wikipedia.org/wiki/Principle_of_least_astonishmen...
| kstrauser wrote:
| I disagree.
|
| If lst = [True, True]; all(lst) is True
|
| is True, and lst = [True]; all(lst) is True
|
| is True, I'd be very surprised by lst = [];
| all(lst) is False
|
| Basically, all(lst) is the same as `not any(not item for item
| in lst)`. If we inverted the value of `all([])`, I'd argue that
| we'd also have to invert the value of `any([])`, which today
| evaluates as False. `any([]) is True` would be beyond bizarre
| to me.
| H8crilA wrote:
| What's an example realistic problem/piece of code that could be
| buggy because of this definition of all()?
| justincredible wrote:
| [dead]
| dylan604 wrote:
| In any discussion on languages like this, I feel the Wat
| discussion is always appropriate:
| https://www.destroyallsoftware.com/talks/wat
| H8crilA wrote:
| This video is over 10 years old. I felt very old all of a
| sudden. (BTW, it's hilarious, go watch it)
| travisjungroth wrote:
| Think often when people want/expect this to be false, they're
| combining two checks: that there's an item and all items are
| true. This covers doing an operation on "ready" items. Instead:
| if items and all(items):
| the-alchemist wrote:
| Clojure does the same thing: > clj
| Clojure 1.11.1 user=> (every? true? []) true
| user=> (every? false? []) true user=> (every? true?
| nil) true user=>
|
| Also: user=> (true? []) false
|
| In English, an empty list is `false`, but any predicate on an
| empty list is `true`.
|
| So I believe the logic is the same as Python.
|
| Logic article on this in Wikipedia:
| https://en.wikipedia.org/wiki/Vacuous_truth
| aib wrote:
| It's the identity element of the monoid, no?
|
| Similarly, the product of an empty list should be 1.
| Nevermark wrote:
| The sum of no numbers is 0.
|
| The product of no numbers is 1.
|
| The union of no areas (sets, ...) is the empty area.
|
| The intersection of no areas (sets, ...) is the universal area.
|
| The commonality here, is what element z can you add or remove
| from a list which won't change the result?
|
| We call the element that makes no change to the result, the
| "identity element".
|
| For y = sum of {x1,x2, ... Xn, z},
|
| We know z must be 0, if it has no impact on y. So the identity
| element for sum is 0.
|
| So if y = sum of {}, we know we can insert the identity element
| without changing the result, and we know the sum of {0} is 0. The
| identity element itself.
|
| _So operations applied across lists return that operation's
| identity element for an empty list._
|
| ---
|
| Ergo:
|
| the identity element of "all" is "true".
|
| The identity element of "any" is "false".
|
| ----
|
| More fun:
|
| The identity element for the resistance sum across parallel
| resistors, is the infinite ohm resister.
|
| The identity element for the vector distance sum of a child
| making a sequence of jumps is the in-place jump.
|
| ---
|
| Getting meta with, oh hell, monads:
|
| The identity element for C, the concatenation operator over
| lists, is the empty list {}.
|
| Since all lists are concatenations of lists (down to empty &
| unitary lists), we can view any operation Q over lists also as an
| operation over the concatenation of lists.
|
| So any Q acts like a monad over list concatenation operations.
|
| If Q = sum, then it is the monad that transforms concatenations
| of lists of numbers into the sum of those numbers.
|
| If Q = all, then it is the monad that transforms concatenations
| of lists of truth values to the conjunction of the truth values
| in those lists.
|
| With that view in place, we can see another reason why the
| identity of any operation Q is Q on an empty list Q{}
|
| Because as a monad, Q applies over C, the concatenation of lists.
| The identity of C is {}, so the identity of Q must be Q{}.
|
| Voila!
|
| So we really shouldn't define sum{} as 0, but define 0 as sum{}.
|
| "0" is just a symbol. Sum{} is what it _is_.
|
| 0 _is_ the sum of nothing.
|
| _So "True" IS the conjunction of nothing. It's meaning IS all{}.
| It is the truth of "no requirements"._
| [deleted]
| klysm wrote:
| > The identity element for the resistance sum across parallel
| resistors, is the infinite ohm resister.
|
| I really like this example, because it has an intuitive
| physical analog and is more tangible than than the example I
| typically reach for: lists.
| layer8 wrote:
| One corollary is that a zero-dimensional array has exactly one
| element, whereas a 1-dimensional array can have zero elements
| (can have length zero). It took me a while to wrap my head
| around this.
| Nevermark wrote:
| Yes! Dimensions are multipliers on each other.
|
| The cross points, over multiple points on segments in
| different dimensions is a product.
|
| And the product across an empty list is 1.
|
| The number of ways you can roll a dice "no" times is also 1.
|
| Cross combinations of all kinds are products.
| itishappy wrote:
| Whoah...
|
| Does this imply there's a sixth of a way to unroll a dice?
| feoren wrote:
| To be pedantic:
|
| TRUE is the identity element of "and", not "all". "All" is not
| a binary operator, it is the (unary) aggregation of "and". That
| is, S.all() == S.aggregate((prev, next) => prev && next, TRUE).
|
| FALSE is the identity element of "or". "any"/"some" is the
| aggregation of "or". S.any() == S.aggregate((prev, next) =>
| prev || next, FALSE).
|
| 0 is the identity element of addition, and "sum" is the
| aggregation of addition. S.sum() == S.aggregate((prev, next) =>
| prev + next, 0).
|
| 1 is the identity element of multiplication, with "product" the
| aggregation.
|
| Given a monoid M<T> { combine(a: T, b: T) => T, identity: T },
| you can define an aggregation operation the same way:
| S.aggregate((prev, next) => M.combine(prev, next), M.identity)
| Nevermark wrote:
| TRUE can be the identity element both for the conjunction of
| 2 Boolean values, and of an operator that extends 2-value
| Boolean operations to lists of N-elements.
|
| Being an identity is a property. A given mathematical object
| can be an identity for more than one relation.
|
| It can also be the identity element for general logical
| propositions or relations.
|
| The reason being, the former is just a special case of the
| Boolean relations of AND and ALL.
|
| So TRUE can consistently be the identity for many classes of
| logical operations of varying generality or complexity.
|
| The raw identity relation and concept of identity element
| form the "tops" of ladders, whose specializations can hold
| over large classes of relations.
| feoren wrote:
| My goal was to add more context to your (excellent and
| upvoted) original post, which in my opinion is basically
| the fundamental "proof" of why All([]) must be TRUE, and I
| find beauty in this two-dimensional analogy:
| add | sum multiply | product and
| | all or | any concat | "flatten"
| (arguable name here)
|
| I also find beauty in the fact that the existence of a
| monoid on the left is sufficient for producing the
| aggregation on the right that behaves in the way we want. I
| see the monoid as the simple building block from which we
| produce more interesting and complicated structures. I
| enjoy the continued, unbroken thread of rigorous logic that
| connects everything.
|
| When you say that TRUE can be the identity of "an operator
| that extends 2-value Boolean operations to lists of
| N-elements", I just don't see the unbroken thread of
| rigorous logic behind that statement. Maybe it's there! But
| I don't see it. I can write down exactly what it means for
| some element _i_ to be an identity of a binary operation @.
| It means i@x == x == x@i for all x in the set over which @
| is defined. Whatever the rules of "identity" are that
| you're talking about, they're not this, so I'm just kinda
| struggling to accept it. I wonder whether maybe what you're
| thinking of deserves a different name than "identity".
|
| Does any of this matter? It does to me, because I actually
| use Monoids all the time in programming, where you can't
| afford any ambiguity at all. So again: maybe you see that
| unbroken chain of rigorous logic and know exactly what you
| mean when you say TRUE is the identity of "an operator that
| extends 2-value Boolean operations to lists of N-elements",
| but I'd need to see the exact laws that an element must
| follow to be such an operator or such an identity of that
| operator. I gave an example of how to turn associative
| binary operations with identity into a unary operator on
| lists of elements, but unary operators don't really have
| identity elements. _Some_ unary operators have fixed points
| and eigenvalues, which are similar to identity, but such
| operators must have the same domain and codomain, and
| aggregate operators like SUM and ALL do not. So there 's
| not really anything you define to be SUM's identity, since
| it does not accept 0 as an input.
| Nevermark wrote:
| Ha! I agree, you are right.
|
| TRUE for a monoid can exist independently from any
| aggregator defined over that monoid.
|
| My bad :)
|
| The fractal lines between what is mathematically true,
| vs. what is practical or useful to be true, in coding are
| worth paying attention to!
|
| Thank you!
|
| And perhaps these relations can always hold, "without
| loss of generality".
|
| In which case we need to formally define these monoid-
| aggregator relations so we all know when they are assumed
| to be in effect.
|
| --
|
| On the beauty side, I love how 0 = sum{} captures the
| semantic difference between zero and other numbers, with
| the syntax of nothing between two braces.
| feoren wrote:
| I do think there was something interesting about the idea
| that adding the element to the input array doesn't change
| the result. It's a little tricky to formalize though.
|
| If we define an "aggregation" _agg_ over some set S as a
| function from S* (the "Kleene star", AKA the free monoid
| over S, AKA really just simple arrays of S) to S, and we
| identify some element _i_ such that
| agg([i] concat X) == agg(X) == agg(X concat [i])
|
| for all X in S*, that does feel very "identity-ish". It's
| a little bit like saying [i] is an identity of _concat_
| under the equivalence relation on S* that X~Y iff agg(X)
| == agg(Y)? In the same way that 7 is an identity of +
| under the equivalence relation "mod 7" (paraphrasing).
|
| But note that: sum([-2, 2] concat X) ==
| sum(X) == sum(X concat [-2, 2])
|
| for all X as well. You could say "well obviously, because
| sum([-2, 2]) == sum([0]) and [0] is our identity element"
| but then we're implicitly assuming that agg(X concat Y) =
| agg(X) @ agg(Y) for some operator @. Which in turn is
| basically assuming we've built _agg_ up from a monoid to
| begin with, and the novelty here would be what happens
| when we _don 't_ do that. There may be some interesting
| (if not useful) stuff here.
|
| _if_ there exists some operator @: (S, S) - > S such
| that: agg(X concat Y) == agg(X) @
| agg(Y)
|
| For all X, Y in S*, and if : agg([i]
| concat X) == agg(X) == agg(X concat [i])
|
| for all X in S*, then must agg([i]) be an identity
| element of @? Certainly that's true if agg is onto (i.e.
| we can find every element of S via agg of some S*). But
| it can't really be true in general, because we could make
| degenerate _agg_ functions like
| ignore(X) := 0
|
| Now every element of S meets this condition:
| ignore([s] concat X) == ignore(X) == ignore(X concat [s])
|
| So we have every element of S as this weird kind of
| "identity" of the "ignore" function. And we can find
| functions on S* with no "identity" of this kind: "count",
| for instance. Although that's cheating because it only
| works when S happens to be the natural numbers (otherwise
| agg is not a function from S* -> S).
| Nevermark wrote:
| Yes I think you hit it on the nail.
|
| My logic depended on the aggregator being a recursive
| monoid, with:
|
| 1) Special handling for a unit list, where the unitary
| element is returned, and
|
| 2) Special handling for an empty list, where the identity
| element of the monoid is returned OR we get explicit that
| the case of the empty list is simply already it's
| simplest form, and we choose to define that equivalent to
| the monoid's identity
|
| So i skipped a step by "finding" the identity from the
| aggregator's behavior, instead of directly from the
| monoid it is based on.
|
| ----
|
| Alternatively, I am liking the idea of defining this list
| vs pair, aggregator vs monoid relations more tightly.
|
| Empty braces unify the syntax for "zero" with the
| semantics "nothing" between the braces.
|
| How else can you join those semantics and syntax?
|
| Likewise, starting with unary natural numbers,
| syntactically and semantically, a list of 1's is the
| number.
|
| So which comes first? A unary monoid addition of 2 lists
| of ones (n-way concatenations of unitary 1), or an n-way
| sum-concatenation that each unary number actually
| consists of?
|
| I think they are more tightly bound definitions than our
| typical syntax suggests, when we get down to the
| semantics = syntax level.
| black_knight wrote:
| To be even more pedantic! Unit elements are not limited to
| binary operators. In fact, in a monoid (or group) there is
| naturally an n-ary operation for each n. Or if you want a
| single operation from lists of elements to a single element.
| It is just that we usually present it using a unit and a
| binary operation + associativity. But one can split that cake
| in other ways. Thus, in some sense any and all are even more
| natural or "objective" (as Lawvere would put it) than and and
| or.
| feoren wrote:
| What is your definition of an identity of a ternary
| function? Say _i_ is the identity of _f_. Must it hold that
| f(i, a, b) == f(a, i, b) == f(a, b, i)?
|
| For all a, b in f's domain? The seems like the obvious
| choice, and certainly holds for ternary functions "built
| up" from associative binary ones, but I've just never seen
| such a thing. Is there a case where it's useful to talk
| about the identity of a 3-valued function?
|
| I think the thing I find weird about this is that a binary
| operator _op2_ over some set S is defined as S^2 - > S. So
| we can sensibly say: op2(a, i) == a ==
| op2(i, a)
|
| But the extension of this to a 3-valued function from S^3
| -> S cannot have that middle condition, because it has too
| many "free variables". We can't say:
| op3(a, b, i) == op2(a, b)
|
| Without establishing a relationship between op3 and op2,
| but must there be a sensible "decomposition" of op3 into
| some op2? Surely not. I guess I just don't know what it
| means to be an identity of a 3-valued function.
|
| As an example, consider mult3(a, b, c) := a * b * c. Then,
| mult3(0, a, b) == mult3(a, 0, b) == mult3(a, b, 0)
|
| for all a and b. We intuitively know that 0 is not behaving
| like an identity. Can we write down an identity rule that
| must hold for a generic op3 that excludes 0 as the identity
| of that function? Without relying on some oracle to provide
| us an appropriate decomposed op2?
|
| Edit: I would also like to point out this function over
| R^3: f(a, b, c) := a*b + a*c + b*c
|
| Note that _every value in R_ meets the condition:
| f(a, x, y) == f(x, a, y) == f(x, y, a) == ax + ay + xy
|
| For all x and y. Is every number an identity of this
| function? In fact, this is trivially true for any
| completely associative function. I guess I just need to see
| the definition of an identity of a ternary operator.
| evertedsphere wrote:
| monoid, not monad
|
| ---
|
| a monoid is a set A with an associative binary operator @ on
| it: that is, for any a, b, c
|
| a @ (b @ c) = (a @ b) @ c
|
| and it also has an "identity" element I, that is, for any a:
|
| a @ I = I @ a = a
|
| common monoids: integers under addition (i.e. @ is addition,
| the identity is 0), nonzero real numbers under multiplication,
| lists under concatenation, booleans under AND (identity is
| True), booleans under OR (what's the identity?), ...
|
| now, when you have a mathematical structure, you often want to
| study functions between two of them. so you might ask what a
| reasonable notion of functions between monoids is
|
| one nice way is if, given two monoids, M with operation @ and
| unit I, and N with operation ^ and unit J, we had a function f
| for which:
|
| f(I) = J
|
| f(a @ b) = f(a) ^ f(b)
|
| this is loosely described as the function "respecting the
| structure" of the monoids, and such functions are called monoid
| homomorphisms or just homomorphisms if the context is clear
|
| --
|
| with that background, we see that `all` should really be be a
| homomorphism from the monoid of lists (under concatenation,
| with the empty list as the identity element) to the monoid of
| booleans under AND (with True as the identity)
|
| this means that
|
| all(concat(list1, list2)) = and(all(list1), all(list2))
|
| or, in python,
|
| all(a + b) = all(a) and all(b)
|
| and, of course, all([]) = True!
|
| the value here is that now you can reason about the all() of
| two lists by thinking about the all() of sublists, and the
| conditions required for a homomorphism guarantee that the empty
| list is not an edge case:
|
| all([T, F]) = all([]) and all([T, F]) = all([T]) and all([F]) =
| ...
|
| and that it doesn't matter how you cut up a list into sublists
| and what order you apply the concatenations in to reconstruct
| it
| Nevermark wrote:
| I was referring to monad, as used in programming, as a
| transform that can be applied to the elements of a structure.
|
| For instance, a transform that wraps each joining operator,
| in an expression tree, with a new operator that applies the
| original operator if all its inputs are defined, but returns
| a null if any input is null.
|
| The expression tree structure hasn't changed, but it now
| consistently (anvoiding error) responds to null values by
| propagating them.
|
| In my example, a monad converts the list combining operation
| of concatenation into other list combining operations.
|
| The result was that the identity of concatenation (the empty
| list) formed the basis for the new list operator's identity.
|
| --
|
| Both concepts are indeed relevant.
|
| A "monoid-to-aggregator" monad could convert 2-element
| operations into recursively applied list operations (which
| also return the single element for unitary lists, and the
| identity element for empty lists).
|
| Then a structure of monoids processing pairs of values could
| be transformed into a structure that processes lists.
| slaymaker1907 wrote:
| You could also argue that any({}) is really not defined because
| first order logic generally excludes empty sets. The reason for
| said exclusion is because weird stuff starts to happen when you
| allow an empty domain when talking about if a formula is true
| in all domains. For example, "exists x, P(x) or !P(x)" is true
| for every domain unless you allow an empty domain since "exists
| x ..." is always false. The same is true of all({}) because you
| have an equivalent weirdness in the form of "!(forall x, P(x)
| and !P(x))". These seem innocuous, but there are many rules of
| inference that are excluded once you allow the empty domain.
| [deleted]
| schoen wrote:
| Maybe I'm too used to Coq's higher-order theory now, but I
| think it's not really that bad to say that we have to be
| careful about whether statements have existential import.
|
| https://en.wikipedia.org/wiki/Syllogism#Existential_import
| Nevermark wrote:
| If we are defining ANY as an n-element LIST operator, in a
| programming language, which recursively applies the 2-operand
| AND taking literal Boolean values, there are no ambiguities.
|
| Note that this is inherently a _constructible_ relation,
| which avoids many pratfalls of more general mathematics.
|
| But if ANY & ALL are being defined as general mathematical
| relations over all EXISTING members of a class (whose
| members' construction, consistency or completeness, may be
| unknown or even unattainable), then there are other issues.
| tromp wrote:
| If all marbles in a bag are black, and you take one marble out,
| are all marbles in the bag still black?
|
| The only logical answer is yes. It would be rather absurd to make
| an exception for the case where you start with one marble in the
| bag. That would make logical reasoning extremely cumbersome, for
| no benefit whatsoever.
| bowsamic wrote:
| > If all marbles in a bag are black, and you take one marble
| out, are all marbles in the bag still black?
|
| > The only logical answer is yes.
|
| The only "logical answer" is "there are no marbles in the bag".
| If this must be cast to a boolean somehow, the only "logical
| answer" is no. There should be a discontinuity as the last
| black marble is removed. That isn't absurd at all
| jimmaswell wrote:
| Look into formal boolean logic, specifically the "therefore"
| operator. (T->T)=T,(T->F)=F, but starting with a false
| premise always results in true. There's good reason for it
| and it makes other things work out how you'd expect.
|
| A marble is in the bag -> the marble is black = True, even if
| there are no marbles in the bag. You can consider the "all"
| method as asking for the truth value of "A marble is in the
| bag -> the marble is black"
| bowsamic wrote:
| Why should I consider the all function to be like that,
| rather than actually answering the question "are all the
| marbles black"?
|
| Also, why am I getting downvoted? I'm starting to realise
| that HN is not the place to come for intellectual
| discussion anymore if you have anything to say that isn't
| immediate agreement. I guess dang has set a flag on my
| account that encourages others to downvote me, because I'm
| not sure what other explanation there is for how my
| comments have been treated recently
| stOneskull wrote:
| i think it's a 'black marble bag'. you want to make sure
| it only ever has black marbles in it. so you do checks on
| it.. does the bag only contain black marbles? you want to
| check there's no non-black marbles.
| shadowgovt wrote:
| With deepest respect: I can't speak to any other comments
| you've made, but on this thread the downvotes are almost
| certainly because you've stepped into a philosophical
| debate that has gone on for over 2,000 years in Western
| philosophy and more-or-less asserted "If this must be
| cast to a boolean somehow, the only 'logical answer' is
| no." I believe the community is interpreting that as a
| bit dismissive both of the contents of the post and
| philosophy in general; one of the field's goals is to get
| past what we feel ought to be the answer to establish
| some kind of framework where that _must_ be the answer,
| and your assertion is a bit dismissive of the other
| viewpoint (which, FWIW, happens to be the modern
| orthodoxy; IIUC your preferred answer is the old
| orthodoxy that leads to logical paradoxes and has
| therefore been put on the shelf as less useful).
| wan23 wrote:
| Without knowing how many marbles are in the bag, if you say
| that not all the marbles in the bag are black, then I'm going
| to ask you to show me a non-black marble to prove it.
| Alternatively, I can prove that all the marbles are black by
| showing you n marbles that are black where n is the number of
| marbles in the bag. Here you go, zero black marbles!
| Someone wrote:
| An alternative way to see why that's the most logical viewpoint
| is, that, if you assume not all marbles in an empty bag are
| black, you can have the following:
|
| - Take a bag for which "all marbles in this bag are black" is
| false
|
| - Add a black marble to that bag
|
| - After that, "all marbles in the bag are black" becomes true
|
| As is often the case in mathematics/logic [1] with these kind
| of things, you can hold an alternative view where "are all
| marbles in this bag black" doesn't make sense for an empty bag
| or one where it has the answer "yo", but if you do that, you'll
| find that many proofs get more cumbersome because you have to
| handle that case differently from all other cases.
|
| [1] other examples are the convention that 00 = 1 and the
| convention that 1 isn't a prime number (that's an example where
| mathematicians (eventually) decided that having 3 kinds of
| positive integers (prime numbers, composite numbers, and 1) is
| the better choice)
| marktani wrote:
| edit: totally misunderstood parent, my bad. disregard the
| following.
|
| > - Take a bag for which "all marbles in this bag are black"
| is false
|
| > - Add a black marble to that bag
|
| > - After that, "all marbles in the bag are black" becomes
| true
|
| This reasoning is not correct. If the bag contains exactly a
| red marble at the start, "all marbles in this bag are black"
| is false as you required, but it breaks the claim at the end
| that "all marbles in the bag are black".
|
| There is in fact no bag that fulfills your reasoning, even
| the empty bag wouldn't (when starting to write my reply I had
| erroneously assumed so)
| saurik wrote:
| If a bag contains exactly one red marble at the start then
| all marbles in this bag are black is in fact false, but
| when you throw in a black marble the value does NOT
| suddenly become true, as the red marble still exists, which
| is exactly the point of the scenario: adding a black marble
| to a bag where that claim is false shouldn't make the bag
| suddenly become true, and it still didn't in your
| example... it would, though, if the empty bag were defined
| to be false (which it should not be based on this
| argument).
| marktani wrote:
| thanks, I see my misunderstanding now
| SkyPuncher wrote:
| The answer should be no. Though, it's understandably ambiguous.
|
| Black is a property of a marble. Without a marble, black cannot
| evaluate to true. Therefore zero marbles equals "no"
| pharrington wrote:
| There are zero marbles. All zero of the marbles are black.
| All zero of the marbles are white. There are zero marbles.
| kstrauser wrote:
| Alternatively, there are no marbles that are not black.
| feoren wrote:
| All cell phones must be turned off before the movie will
| begin.
|
| Oh wait, nobody in the audience has a cell phone. Can the
| movie begin?
|
| > Without a marble, black cannot evaluate to true. Therefore
| zero marbles equals "no"
|
| "Is_Black" cannot evaluate to false either, therefore zero
| marbles equals "yes". But that's wrong too, because it is
| _never evaluated_ , because there are no marbles to evaluate
| it on. TRUE is the identity of AND, and ALL is the
| aggregation of AND, so ALL([]) == TRUE. Put another way:
|
| If you start from a bag with N black marbles and split it up
| between M bags, can you say that for each new bag, all the
| marbles in it must be black? Yes, you can. That is, if you
| find a marble in the bag, it will be black. This still holds
| even if one bag doesn't happen to get any marbles.
| fasterik wrote:
| Your proposal would break all of logic and mathematics.
|
| "All marbles in the bag are black" is equivalent to "For all
| x, if x is a marble and x is in the bag, then x is black".
| Since the antecedent is false if the bag is empty, the
| statement is true by material implication.
| NoThisIsMe wrote:
| That's not the question. The question is: If there are no
| marbles in a bag, are all marbles in the bag black?
| Smaug123 wrote:
| I think you've misunderstood. The question you posed has an
| answer implied by the parent's question with n=1.
| twiceaday wrote:
| Sounds weird when you ask the question that way, but if you
| ask "is there a non-black marble in the bag?" the answer is
| clearly no. So the question is more like: Should "all marbles
| in the bag are black" be exactly equal to "not(is there a
| non-black marble in the bag)".
| jayd16 wrote:
| Isn't this like complaining about division by zero? Why make an
| exception? Well...because its exceptional.
|
| So it's consistent to say that a bag can contain all red and
| all black marbles at the same time?
| Eldt wrote:
| That's not an exception, that's a different situation...
| jackbrookes wrote:
| not really marbles = (BlackMarble() for _
| in range(random.randint(0, 10))) all(isinstance(m,
| BlackMarble) for m in marbles)
|
| Surely should always be true
| cedilla wrote:
| Is it?
|
| If that case is so different, than the case with two marbles
| is also different - because removing the second-to-last
| marble will change will change the bag to be in that
| situation. But then, the case with three marbles is also
| different, and by induction you are left with only special
| cases.
|
| On the other hand, see the related statement "If all marbles
| in a bag are black, adding a red marble will result in a
| mixed bag" clearly fails for the empty bag.
|
| This isn't really a question of logic or mathematics.
| Mathematicians just use systems which are useful. And
| predicate logic, which has proven invaluable, would allow
| OP's claim.
| pixl97 wrote:
| Eh, wouldn't the induction reduce to 0, 1, infinity?
| dkarl wrote:
| Translating it to idiomatic natural language makes it less
| clear, because the natural language statement "all marbles in
| the bag are black" implies that there are marbles in the bag.
| The question is, why do we interpret it differently in a
| logical/mathematical context?
|
| As with anything mathematical, we picked the way that yields
| useful and elegant mathematics. The notion of "all" would be
| awkward to work with if it did not apply to the empty set (bags
| without marbles) so we extended it in a way that is consistent
| with what it means over non-empty sets (bags with marbles.)
|
| One very nice thing about this definition of "all" is that it
| gives this simple relationship between logical "all" and
| logical "none":
|
| "for all x, P(x) is true" is equivalent to "there is no x for
| which P(x) is false"
|
| I.e., if there is no marble in the bag that is not black, then
| all marbles in the bag are black... so to speak.
|
| This yields elegant and useful mathematics, and (as you would
| expect) that tends to mean elegant and useful code as well.
|
| For example, suppose you had an enormous dataset of records
| that included zip codes and wanted to know: "Are all the zip
| codes in this dataset in the continental United States?" One
| approach would be to split the data into smaller shards, answer
| the question for each shard, and "and" all the answers
| together. What if you chose a bad way of sharding the data and
| one of the shards was empty? What result would you want
| returned for that shard?
| dragonwriter wrote:
| If all marbles in a bag are black, and you take one marble out,
| are all marbles in the bag white?
|
| The only logical answer is no. It would be rather absurd to
| make an exception for the case where you start with one marble
| in the bag... and yet: marbles = ["black"]
| marbles.pop() all(m=="white" for m in marbles) # => True
| p1mrx wrote:
| > If all marbles in a bag are black, and you take one marble
| out, are all marbles in the bag white?
|
| The logical answer is "maybe."
| Thiez wrote:
| Yes, you took out the last marble that wasn't white, and
| now all marbles that remain are white.
| bandyaboot wrote:
| Though it feels strange to write this, the fact that all the
| marbles are white doesn't change the fact that they're all
| black...and transparent, and not marbles at all, etc...
| dragonwriter wrote:
| Right, my point was pointing out a weakness in the style of
| explanation--that the same structure can be applied with
| similar intuitive appeal to reject the behavior of
| all()--not to actually disagree with the correctness of
| all() in implementing universal quantification, or the
| correctness of the design that it should implement
| universal quantification.
| neves wrote:
| my pragmatic view is that it should be false.
|
| A common error would be a programming mistake in the
| selection of the list element return an empty list. The
| returned list would, unexpectedly, comes empty. Trying to
| check if everything is black would return True and the code
| would follow on. It would be very hard to debug
| chongli wrote:
| The mistake you're making here is by treating the statement
| "all marbles are white" as the negation of "all marbles are
| black" and claiming that this violates the law of the
| excluded middle.
|
| But we are operating under predicate logic. The negation of
| "all marbles in the bag are black" is "there is a marble in
| the bag which is not black". Then, clearly the latter
| statement is false in the case of an empty bag.
|
| In fact, we can confidently claim falsity for any given
| statement of the form "there is a marble in the bag such
| that..." when the bag is empty. Therefore, by the law of the
| excluded middle, its negation is true, so statements of the
| form "all marbles in the bag are..." are vacuously true when
| the bag is empty.
| jayd16 wrote:
| Its interesting that "for all <is true?>" seems to imply a
| non-empty set, whereas "for any <is false?>" seems to not
| make the same implication.
|
| It's certainly misleading in every day speech. On the
| bright side, all my papers have been published and all of
| my research funding has been granted.
| Dylan16807 wrote:
| > "for any <is false?>"
|
| What do you mean here?
|
| "some element doesn't have the attribute" _requires_ a
| non-empty set.
|
| If you mean "it is false that some element has the
| attribute", then you need to write that very differently,
| which makes it much less of a surprise that it has
| different implications from the "all" statement.
| VonGallifrey wrote:
| I don't think he was treating "all marbles are white" as
| the negation of "all marbles are black".
|
| The comment he replied to was claiming that any question
| that is true for n = 1 should also be true for n = 0, but
| this comment shows that it is obvious nonsense.
|
| The comment above basically claimed:
| marbles = ["black"] all(m=="black" for m in marbles)
| # => True marbles.pop() all(m=="black" for m in
| marbles) # => True
|
| If that is the case then the following would also need to
| be true: all(m=="white" for m in marbles) #
| => True all(m=="green" for m in marbles) # => True
|
| What color is the marble?
|
| Just because the question "there is a marble in the bag
| such that..." is false does not mean you can just negate it
| and say "all marbles in the bag are..." if the actual
| answer is that the question is not applicable.
| fasterik wrote:
| Your proposal would break all of logic and mathematics.
|
| "All marbles in the bag are white" is equivalent to "For all
| x, if x is a marble and x is in the bag, then x is white".
| Since the antecedent is false if the bag is empty, the
| statement is true by material implication.
| [deleted]
| VonGallifrey wrote:
| Are those statements really the same?
|
| "For all x, if x is a marble and x is in the bag, then x is
| white"
|
| I would question if nothingness is a marble. Or would you
| say that the following statement is also true? I would say
| that x is a marble and therefore can be neither even or odd
| because it is not a number?
|
| "For all x, if x is a marble and x is in the bag, then x is
| even"
|
| That is just a nonsense question same as asking if all the
| non-existing marbles are of a particular color.
| fasterik wrote:
| According to the rules of logic, we can always replace (P
| -> Q) with (~P v Q). In other words, if P is false then
| (P -> Q) is always true. This is known as a vacuous
| truth.
|
| https://en.wikipedia.org/wiki/Vacuous_truth
|
| Agreed, sometimes this leads to true statements that
| sound like nonsense. One example from the article is "if
| Tokyo is in France, then the Eiffel Tower is in Bolivia".
| This is a true statement because Tokyo is not in France.
|
| _> "For all x, if x is a marble and x is in the bag,
| then x is even"_
|
| We can rewrite this as "For all x, x is not a marble or x
| is not in the bag or x is even". We can see that this is
| true if "x is not in the bag" is true for all x. It's not
| really nonsense because we can quantify over all objects,
| so some of them will be marbles, some of them will be
| even, etc.
| bandyaboot wrote:
| Ultimately I agree with the conclusion, but the logic of how
| you're getting there seems flawed in that the question you're
| asking doesn't add any value. The fundamental question is
| whether all marbles in a bag of n black marbles are black for
| all values of n including 0. If the answer to that question is
| yes, then the answer to your question is yes. If the answer is
| no, then the answer to your question is "yes except if it
| results in n=0".
| saurik wrote:
| The point was (explicitly) that it would be awkward to add
| the n=1->0 corner case.
| gouggoug wrote:
| I'm a bit confused by this:
|
| > "All stonemen are made of stone" is true by definition, but "no
| men are made of stone" is also true and seems to contradict it.
|
| I don't see how "no men are made of stone" contradicts "All
| stonemen are made of stone".
|
| "stonemen" are not the same as "men".
|
| English isn't my first language so maybe I don't know what a
| stoneman is (and google failed me), but I assumed it is a statue?
| Smaug123 wrote:
| The originator of that quote was writing in the 12th century.
| The quote is cited without a source at
| https://en.wikipedia.org/wiki/Square_of_opposition , where the
| phrase is "Omnis homo qui lapis est" ("every man who is a
| stone"). I haven't dug any further than that. But the phrase
| literally is intended to indicate a contradiction.
| Jtsummers wrote:
| A stoneman would be a man made of stone, not a stone shaped
| like a man.
|
| It comes down to a philosophy of logic issue. A universal
| quantifier ("for all x P(x)") is ambiguous when there are no
| x's. You can take it as false, true, or indeterminant, your
| system of logic will determine which interpretation should be
| used.
|
| In modern predicate logic, that statement is true if there are
| no x's. In syllogistic logic it's considered false because
| there's a second presumption which must be satisfied: That
| there are any x's to talk about.
| ptx wrote:
| Shouldn't this question fail at the parsing stage then,
| before it has even been asked? Q: All
| stonemen are ... A: ERROR: Undefined operation.
| Stonemen do not exist.
| Jtsummers wrote:
| That's certainly one option. In a way, that's what the
| colloquial understanding of the expression would entail.
|
| In colloquial use if you were to say, "All unicorns are
| blue" no one can meaningfully contradict nor confirm the
| statement, the statement is neither true nor false because
| there are no unicorns (this all assumes we're not
| discussing in a context where unicorns "exist", like about
| a particular fantasy setting or animated series). In
| syllogistic logic it becomes false because of the
| foundation of that logic (centered on reality, what exists
| and can be defined, not on fiction). Nothing true can be
| said about all of some non-existent thing because, well, it
| doesn't exist, so the statement must be false. In modern
| predicate logic it's considered true, because even though
| there are no unicorns we (someone) decided that it should
| be true by convention when the set is empty (turns out to
| have useful properties if we permit this).
|
| These are just the rules that we've used for our logic, a
| choice we made. We're generally, in programming, operating
| under the modern logical rules, using neither colloquial
| rules nor syllogistic rules, so our programs are consistent
| with that last interpretation.
| assbuttbuttass wrote:
| I'm guessing, a stoneman means a man made out of stone
| billpg wrote:
| I posted in a political thread once...
|
| "Re-joining the EU would give the UK all the benefits of EU
| membership as well as all the benefits of Brexit too."
| gizajob wrote:
| True
| Waterluvian wrote:
| I feel like I'd just make a poll and pick the least surprising
| option if there's a clear winner.
|
| But maybe that's why I'm not a language developer.
| rightbyte wrote:
| > all([]) True > any([]) False
|
| Not very consistent philosophy in that case. Surely if 'all' is
| True then 'any' got to be too?
| [deleted]
| CJefferson wrote:
| It is consistent, and in practice this is the only definition
| that ends up being sensible, if you play with lots of examples.
| I have done this as a, I believe, surprisingly fun thing with
| older school children, where we think about all the things we
| want to be true about all, and any, and then figure out what
| the answers are.
|
| Some examples are "if something is true for 'all students', it
| should be true for any group of students", and if "all students
| have a hat" is true, then it should not be true that "any
| student had no hat", etc.
| Sohcahtoa82 wrote:
| Think of it this way...
|
| You're logging incoming web requests and then gathering
| statistics in 5 minute intervals.
|
| During one interval, you get no requests.
|
| You check to see...did "all" of the requests get processed
| without errors? The answer is Yes, because to say No would
| imply there were errors.
|
| Did "any" of the requests cause an error? The answer is No,
| because to say Yes would imply at least one error.
| thewakalix wrote:
| `any` corresponds to the existential quantifier, not the
| universal.
| Arnavion wrote:
| any(collection, predicate) == not(all(collection,
| not(predicate))). Or in English, "It is true that there is an
| even number in this list." is the same as "It is false that all
| the numbers in this list are odd."
| zem wrote:
| think of "any" as "we can find an element for which this is
| true", and "all" as "we cannot find an element for which this
| is false"
| knappa wrote:
| I would read all more formally as: for each element in this
| list, the element is true. Then you get a vacuous truth. (Think
| about the negation: there is an element in the list which is
| false. That's obviously false.)
|
| Any would be more formally: there is an element of the list
| which is true. But the list doesn't have any elements, so
| that's false.
|
| Looks logical to me. Plus you get that `not any( map(lambda x:
| not x, l) )` is the same as `all(l)` for any list `l`.
| rightbyte wrote:
| > Any would be more formally: there is an element of the list
| which is true. But the list doesn't have any elements, so
| that's false.
|
| It is just a matter of convention and I see no logic behind
| why any convention would be worse or wrong. But I believe if
| 'any' implies 'at least one' so should 'all' otherwise they
| use different conventions.
|
| In practice I get it was arbitrary choices and this is just
| how you end up when doing the obvious implementation.
| def all(l): for e in l: if not e:
| return False return True def any(l):
| for e in l: if e: return True
| return False
| dragonwriter wrote:
| > But I believe if 'any' implies 'at least one' so should
| 'all' otherwise they use different conventions.
|
| The conventions they use are not an arbitrary choice, and
| are those of predicate logic. any() is the "for any"
| (existential quantification) operator, while all() is the
| "for all" (universal quantification) operator.
|
| They are deeply connected: "all items in _xs_ are true" is
| "there are not any items in _xs_ that are not true", or, in
| code terms, all(xs) == not any(not x for x in xs).
|
| And, vice versa, any(xs) == not all(not x for x in xs)
| rightbyte wrote:
| Sure thinking about it the 'all ([]) => True', 'any ([])
| => False' might be more intuitive.
| shawnz wrote:
| How could they both have the same answer? They must have
| opposite answers because of De Morgan's law: asking "is any
| item true" is the same as asking "are NOT all items NOT true"
| petesergeant wrote:
| To prove "do all x satisfy y" you need to find an example that
| is not.
|
| In order to satisfy "does any x satisfy y" you need find an
| example that does.
| orf wrote:
| Going by the example in the post, "all unicorns are blue" seems
| truthy whereas "are any unicorns blue" seems falsey in a world
| with no unicorns?
| JadeNB wrote:
| > Surely if 'all' is True then 'any' got to be too?
|
| No. `any([])` means "some element of [] is true", which is
| false because there aren't any elements. `all([])` means "all
| elements of [] are true", which is true because it's
| (classically, anyway) got to be true or false, and being false
| would require that there be some element of [] that isn't true,
| which there isn't.
|
| More generally, `!all([!x for x in xs])` (or whatever the
| syntax is; I'm not a Python programmer)--meaning "it's not the
| case that the negation of every element of xs is true"--is
| `any(xs)`, so `!all([])` is `any([])`.
| mrkeen wrote:
| No need for philosophy. any (<5) [6,7,8]
| any (<5) ([6,7,8] ++ []) (any (<5) [6,7,8])
| || (any (<5) []) False || True
| True
| mrkeen wrote:
| I like `all = foldr and True` as others have pointed out.
|
| But I think I have a more convincing example of why it can't be
| the other way around: all (>5) [6,7,8]
| all (>5) ([6,7,8] ++ []) (all (>5) [6,7,8]) && (all (>5)
| []) (True && False) False
| manlobster wrote:
| Given: all(xs + ys) == (all(xs) and all(ys))
|
| And: xs == xs + []
|
| We have: all(xs) == all(xs + []) == all(xs) and
| all([])
|
| Which implies: all([]) == True.
| toxik wrote:
| I like this variant, it also works to show why any([]) is
| False.
| Smaug123 wrote:
| Although it's presumably much less controversional that
| `any([])` is false. After all, most people presumably think
| of an existential statement as being satisfied precisely when
| there's a witness to that statement, and of course an empty
| list contains no witnesses to any statement.
| devmunchies wrote:
| I actually used this in my F# code yesterday. The forall function
| does the same and it was exactly what I needed.
|
| https://fsharp.github.io/fsharp-core-docs/reference/fsharp-c...
| rgovostes wrote:
| all([x]+x)
| gizajob wrote:
| The present king of France is bald.
| ptx wrote:
| Does that work, though? If you're talking about a set of kings,
| then the set can be empty. But "the king" - isn't that more
| like Kotlin's _single()_ method, which throws an exception if
| the number of elements is not 1?
| [deleted]
| [deleted]
___________________________________________________________________
(page generated 2023-08-25 23:01 UTC)