3
$\begingroup$

I am experiencing some honestly embarrassing confusion regarding the use of the logical quantifier $\forall$

When I have a statement such as $\forall a, b \in A, P(a,b)$ I interpret this statement as:

"For any two elements $a$ and $b$ in $A$, $P(a,b)$ is true"

where $P(a,b)$ is some predicate.

Does such a statement include $P(a,a)$ and $P(b,b)$?

That is would such a statement involve all possible combinations of elements in $A$ including combinations of elements with themselves? Or is the implication in such a statement that $a$ and $b$ are necessarily distinct?

I believe it would be the former, for example:

"For all People x and y in the World, if x likes y then x will buy y a gift"

Or to frame it logically: $\forall x,y \in W, P(x,y)$ where $P(x,y) = (L(x,y) \implies B(x,y))$

Surely this would be true of a person that likes themselves (the case where x = y)?

$\endgroup$
3
  • 6
    $\begingroup$ Does such a statement include $P(a,a)$ and $P(b,b)$? --- YES. $\endgroup$ Jan 25 at 21:38
  • 5
    $\begingroup$ I think your confusion arises from the fact that "for any two elements $a$ and $b$" might plausibly be read as "for any set $\{ a, b \}$ of cardinality two", but really it means "for any ordered pair $(a, b)$", which of course includes ordered pairs of the form $(a, a)$. $\endgroup$
    – Pilcrow
    Jan 25 at 21:52
  • 1
    $\begingroup$ @Pilcrow: Excellent comment. $\endgroup$ Jan 25 at 22:45

4 Answers 4

6
$\begingroup$

$\forall a,b \in A \ P(a,b)$ is really shorthand for $\forall a \in A \ \forall b \in A \ P(a,b)$

And now I think it's a little easier to see that for $b$ you can pick the same object as for $a$.

So, yes, $\forall a,b \in A \ P(a,b)$ implies $P(a,a)$

$\endgroup$
3
$\begingroup$

There's nothing embarassing about your question; you're clearly asking it because you were not taught clearly the semantics (i.e. meaning) of the quantifiers. I have nothing to add to Bram28's answer regarding your specific question, but I want to emphasize that the meaning we give to each piece of syntax is entirely our choice, though if we chose a semantics different from the standard one then we are going to get something less useful.

For example, we might want to say "every pair of positive integers has a greatest common divisor". With the standard semantics:

$∀k,m{∈}ℕ^+\ ∃d{∈}ℕ^+\ ( \ d \mid k,m ∧ ∀t{∈}ℕ^+\ ( \ t \mid k,m ⇒ t ≤ d \ ) \ )$,
where "$d \mid k,m$" is short for "$d \mid k ∧ d \mid m$"
and "$d \mid k$" is short for "$∃x{∈}ℤ\ ( \ d·x = k \ )$".

Notice that $k,m$ are allowed to be the same, otherwise this sentence would not be enough to cover that case. Moreover, $d$ is allowed to be equal to $k$ or $m$ too, otherwise it would fail.

Furthermore, if you take a look at any deductive system for FOL, such as this Fitch-style system, you will find that the rules are much much simpler when quantified variables can be equal in the intended semantics.

So the key point is that although we are free to invent alternative semantics for quantifiers, it would make the theorems that we want become more convoluted (in their logical expressions), and would require more convoluted deductive rules (in the formal proof). Thus we don't choose the standard semantics just because we like it, but because it is practically the best choice.

$\endgroup$
1
$\begingroup$

By saying for all $a$ in $A$ and all $b$ in $A$ $P(a,b)$ is true you definitely say $P(a,a)$ is true where $a$ now is an arbitrary element in $A$. It might be best to imagine by saying for all $a$ in $A$ that $a$ is not a concrete element of that set. It rather is a placeholder for any arbitrary element in the set. Probably, that is also why the question:

Does such a statement include P(a,a) and P(b,b)?

concluded. Well, it is hard to answer. Because technically $a$ and $b$ are no objects with a useful meaning. They just have been "abused" to act as some element And to answer this question:

would such a statement involve all possible combinations of elements in A

Yes, it would. Because again, the concept behind the symbol after the "forall quantifier" is to have a name for some arbitrary element. So, you could take any two element out of the set, we might call it $a$, and another one, we might call it $b$ or even $x,y,z,\phi,\lambda$. If they are some element in the same set you cannot rule out that they might be the same element.

I hope I helped in understanding this concept a little more.

$\endgroup$
1
$\begingroup$

I see that there are many correct Answers, including one Accepted Answer; but I wanted to chip in with some Points:

(1A) Consider Equivalence Relations:
Reflexivity : $\forall a \in A : \ P(a,a)$
Symmetry : $\forall a,b \in A : \ P(a,b) \implies \ P(b,a)$
Transitivity : $\forall a,b,c \in A : \ P(a,b) , \ P(b,c) \implies \ P(c,a)$

If a & b (& c) were not allowed to be the same element in Symmetry (and Transitivity), then the Arithmetic Equality Relation (=) over Integers or Reals would not apply here; To make Equality satisfy the Equivalence Relation Criteria, we have to allow "For All" to select same element too.

(1B) More to the Point, Consider Anti-Symmetry:
Anti-Symmetry : $\forall a,b \in A : \ P(a,b) , \ P(b,a) \implies a = b$
This works only because "For All" allows selection of same elements.

(2A) When we want Constraints on the Elements:
There are cases where we have to ensure certain Properties; We then have to mention that Explicitly:
Multiplicative Inverse : $\forall a \neq 0 \in A : a^{-1} = 1/a$
Multiplication In Inequality : $\forall a \ge 0 \in R : b \le c \implies ab \le ac $

(2B) When we want Distinctness on the Elements:
There are cases where we have to ensure Distinct Elements; We then have to mention that Explicitly:
Diagonal Matrix A with Size DxD : $\forall x, y (x \neq y) \in \{1,....,D\} : \ a_{xy} = 0$
Here, we have two Explicit Constraints on the Points:
Circle : $\forall a,b,c (Distinct Points, Non-Co-linear) \in Plane :$ Exactly 1 Circle Passes through a,b,c

Here, in each case, we have Explicitly provided additional constraints on the "For All" to get "True Statements"; Without the Constraints, these will be False because "For All" allows same elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.