CODEWITHSUNDEEP
scalafunctional-programminglogic
More Than Five
More Than Five

Reputation: 10419

Universal and Existential Quantifiers of First-Order Logic

I am taking a Scala programming course. At one point the instructor said:

Functions blah and bladdy are the universal and existential quantifiers of first-order logic.

Could someone translate "universal and existential quantifiers of first-order logic" into English please?

Upvotes: 33

Views: 10604

Answers (3)

john_science
john_science

Reputation: 6551

That sentence is full of jargon. You can find a description of universal and existential logical quantifiers here.

  1. A Universal Quantifier is a logical statement that applies to all elements of a set.
  2. An Existential Quantifier is a logical statement that applies to at least one element of a set.

You can also look here for a quick description of first-order logic. The term is meant to separate first-order from higher-order logic:

  1. First-order logical statements are the usual ones; they act on members of a set.
  2. Higher-order logical statements act on other logical statements; think of them as meta-logic.

Upvotes: 45

Ben
Ben

Reputation: 71515

To fully appreciate that statement, you'd probably have to study some logic. But here's the basic gist:

"Quantifiers" are how you give meaning to variables in statements of logic. If I say "{something about x}", that doesn't really have much meaning on its own. You'd have to know what x is to say whether it's a true or false statement. But if I quantify the variable x by saying "for all x {something about x}" or "there exists an x such that {something about x}" then I'm making a single statement that is either true or false.

In the "for all x" case I'm saying that "{something about x}" is true for any x you could pick; that's universal quantification. For example "for all x, x is an even number" is a false statement.

In the "there exists an x such that" case I'm saying that there is a possible choice for x so that "{something about x}" is true (I'm not saying what that choice is, just that there is one). This is existential quantification. As an example "there exists an x such that x is an even number" is a true statement.

They are duals in that "for all x {something about x}" means the same thing as "it is NOT true that there exists an x such that it is NOT true that {something about x}", and also "there exists an x such that {something about x}" means the same thing as "it is NOT true that for all x it is NOT true that {something about x}". Hopefully that seems intuitively justified if you think about it.

If you told us what the functions blah and bladdy are, we could explain the way in which they correspond to the universal and existential quantifiers, which might be more helpful in helping you understand the instructor's point.

Upvotes: 3

Brian
Brian

Reputation: 20285

The textbook Language Proof and Logic provides these English expressions for the universal and existential quantifiers that Professor Odersky referred to.

The universal quantifier ∀

is used to express universal claims, those we express in English using quantifed phrases like everything, each thing, all things, and anything.

The existential quantifier ∃

is used to express existential claims, those we express in English using such phrases as something, at least one thing, a, and an.

The mention of these terms was probably related or lead into operations on collections using higher order functions. In Scala, the transition from logic to code is quite natural with the forall and exists operations on a collection. These are analogous to the universal and existential definitions given above. Some simple examples are helpful to show this:

scala> val l = 1 to 10
l: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> l.forall(x => x > 0)
res0: Boolean = true

scala> l.forall(x => x > 1)
res1: Boolean = false

These two forall statements are simply asking do all elements of this collection meet the criteria.

scala> l.exists(x => x < 1)
res2: Boolean = false

scala> l.exists(x => x < 2)
res3: Boolean = true

These two exists statements are simply asking do any elements of this collection meet the criteria.

Upvotes: 18

Related Questions