4 ms·
What is a trivial existential quantifier and what property identifies them?
by marcosdumay 7y ago
What is a trivial existential quantifier and what property identifies them?
- empath75 7y agoI’m not sure what a trivial existential quantifier is, but an existential quantifier is the statement ‘there exists’, usually written ∃.
- marcosdumay 7y agoThe 'for all' statement is also an existential quantifier, as is the 'this one value' statement implicit on the imperative statements. The entire meat of the article depends on this concept of "non-trivial" quantifier.
- bawolff 7y agoUmm, isnt the universal quantifier by definition not the existential qualifier?
- disconcision 7y agoFrom the comments, it seems likely that the author doesn't have a precise definition of non-trivial. But the framework still feels potentially useful as a way to precisely parameterize disagreements about whether or not a given semantics is declarative. That said, I'm also having some trouble with the concept. Take for example the rule: there exists x such that succ(x) = y ⊢ dec(y) = x. If we're used to operational semantics which include pattern matching, this feels trivial. But otherwise we have to be clever to avoid exhaustive search. I'm a bit out of my depth here, but it sort-of feels like 'non-trivial' here means 'I can't immediately/uniquely produce a corresponding well-moded operational semantics'. Whether this lends any clarity might be a matter of taste...
- JadeNB 7y ago> The 'for all' statement is also an existential quantifier, as is the 'this one value' statement implicit on the imperative statements. If you're making a technical claim, rather than some informal claim whose meaning I'm missing, then "for all" is a universal, not an existential, quantifier. The truth of universal quantification over an empty set is an important part of predicate logic.
- tel 7y agoI think, loosely, an existential quantifier is "trivial" if you can immediately discharge it. I don't know that there's a very formal approach to this, but there's definitely a way to dream up completely trivial existential quantifiers. The only obvious one that comes to mind is an existential quantifying over a singular domain. If Unit is the type containing the single value (), then `exists (x: Unit) . P x` is trivially P (). Even a tiny extension of this (e.g. exists (x: Boolean) . P x) is enough to make this no longer trivial as it at least indicates a search process and can be used to encode arbitrary expansion as long as you can nest existentials. So that's the other way I could imagine it being trivial: if existentials aren't allowed to index very powerful statements, if the Ps above cannot themselves include quantified statements.