Eli5 what are these symbols and what’s their use in Tuple Relational Calculus (TRC)? ¬,∀,Ǝ

87 views
0

Eli5 what are these symbols and what’s their use in Tuple Relational Calculus (TRC)? ¬,∀,Ǝ

In: 4

– ¬ is a logical negation symbol. It means “not.”
– ∀ is a universal quantifier. It means “For all” (but sometimes it makes more sense to translate as “for any,” “for every” or “for each” because English is weird)
– Ǝ is an existential quantifier. It means “There exists.”

Some other symbols you didn’t ask about but might see:

– ∈ means “is an element of” or “in”
– ε is epsilon, a Greek letter sometimes used for a variable, that is very confusingly and unfortunately similar looking to ∈
– ℕ is the set of natural numbers {1, 2, 3, …} (some textbooks include 0 in ℕ as well)
– ℤ is the set of integers {…, -3, -2, -1, 0, 1, 2, 3, …}
– ℚ is the set of rational numbers (ℤ plus all fractions, positive or negative)
– ℝ is the set of real numbers (ℚ plus non-repeating non-terminating decimals like e, π, and √2)
– ℂ is the set of complex numbers (ℝ plus imaginary numbers is a complex number)

So here’s a piece of mathematical shorthand you might see; I put commas in for readability. Let’s call this statement S1:

∀ x ∈ ℕ, ∃ y ∈ ℕ, y > x

You read this as “for any element x in the set of natural numbers, there exists an element y in the set of natural numbers such that y is greater than x.” Or more concisely, “for any natural number x, there exists a natural number y such that y is greater than x.” This is a true statement.

The order in which the quantifiers appear is important. For example if we flip the quantifiers statement like this (call this S2):

∃ x ∈ ℕ, ∀ y ∈ ℕ, y > x

You read this as “there exists a natural number x, such that for all natural numbers y, y is greater than x.” Or a little more naturally “there exists some natural number x such that any natural number y is greater than x.”

S1 is a true statement, but S2 is not a true statement. (Regardless of which number x you pick, it’s at minimum not going to be greater than itself!)

These quantifiers are related. In general you can rewrite ¬∀ to Ǝ¬ and rewrite ¬Ǝ to ∀¬. (You should probably spend some time thinking about why this is logically sound.)

A minute ago, we proved that S2 is false. Now think about what happens if we add a “not” symbol in front of S2 to get this:

¬∃ x ∈ ℕ, ∀ y ∈ ℕ, y > x

We proved S2 is false, so the negation of S2 must be true. (In standard logic, every statement must be either true or false, this is known as the “law of the excluded middle.”)

If we want to use the rewrites I mentioned above, we flip the quantifiers and negate the statement inside, like this:

∀ x ∈ ℕ, ∃ y ∈ ℕ, ¬y > x

Of course ¬y > x is equivalent to y ≤ x so our statement becomes:

∀ x ∈ ℕ, ∃ y ∈ ℕ, y ≤ x

This statement (which should be true, since it’s logically equivalent to a statement we’ve already said is true) is: “For every natural number x, there exists a natural number y such that y is less than or equal to x.”

If none of that made sense to you, you need to find an online “introduction to mathematical proof” course and follow it.