Skip to main content

Subsection 4.2.8 Equality

We just mentioned, as an example of the use of an infix predicate, the equality predicate. We will use equality in exactly the way in which you are used to using it. In particular:

Let P be any predicate. If x = y and P(x) is true, then we can conclude that P(y) is also true.

In other words, if x = y, then they can be substituted for each other in any logical expression.

Suppose that we know:

[1] Fragile(boxmailedbySamlastweek)

We then discover that boxonourdoorstep = boxmailedbySamlastweek

Then we can conclude:

[2] Fragile(boxonourdoorstep)

No surprises here. So why mention it at all?

Because EQ (or =) is fundamentally different from all the other predicates we are using. The system of predicate logic that we have been describing is called first-order logic because it allows quantification over variables (and thus the objects to which they refer) but not over predicates. But we want to say that if x = y, then ∀P, P is true of both x and y or neither of them. Oops.

On the other hand, higher-order logics do allow such quantification. But we don’t want to resort to them because they are logically and computationally very difficult to use.

So what to do? We can’t make do without equality. So we will compromise. We will use a system called first-order logic with equality. We can’t, in general, quantify over predicates. But we can assert equality and use it as we would expect.

We should mention here one thing that equality is particularly useful for: It lets us say that there exists a unique value that satisfies some predicate. The existential quantifier, ∃, asserts only that there exists at least one such object. There might be many. If we want to claim that there is exactly one, we can assert that there exists at least one, call it x, and then assert that any such one must be equal to x.

Suppose that we want to require that every employee have exactly one emergency contact. Then we could write:

[1] \(\forall\) x (Employee(x) \(\rightarrow \) \(\exists \) y (EmergencyContact(y, x) \(\wedge \) \(\forall\) z (EmergencyContact(z, x) \(\rightarrow \) (z = y))))

So we have that y is an emergency contact for x. The read the last line as, “and, for any z, if z is x’s emergency contact, then z must equal y.

Equality also lets us say that there are at least two (or three, or whatever) different things that possess some property.

Suppose that we want to require that, for our manufacturing plant, every critical raw material must have at least two suppliers. Then we could write:

[1] \(\forall\) x (RawMaterial(x) \(\wedge \) Critical(x) \(\rightarrow \) \(\exists\)y (\(\exists \) z (SupplierOf(y, x) \(\wedge \) SupplierOf(z, x) \(\wedge \) \(\neg \)(z = y))))

Without the last line, nothing prevents both z and y from being bound to the same supplier. In other words, nothing prevents z = y.

Exercises Exercises

1.

1. Suppose that you were axiomatizing the world in which we live. Which (one or more) of the following statements that exploit equality would you give as axioms/premises:

I. ∀x, y (Co-workers(x, y) → (socialSecurityNumber(x) = socialSecurityNumber(y)))

II. ∀x, y (Twins(x, y) → (age(x) = age(y)))

III. ∀x, y (Married(x, y) → weddingAnniversaryOf(x) = weddingAnniversaryOf(y))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Just I and II.

  5. Just II and III.

Answer.
Correct answer is E.
Solution.
Explanation: Of course, whether the two twins have the same age depends on whether we measure age in milliseconds or days, but assuming it’s not milliseconds, we’ll want to say that twins have the same age.

2.

2. Suppose that we want to represent our class requirement that every student work with another student on the class term project. Define:

Student(x): x is a student.

Partners(x, y): x and y are on the same team for the term project.

Consider the following claim:

∀x (Student(x) → ∃y (Student(y) ∧

Partners(x, y) ∧

¬(x = y)))

Which of the following statements is true:

  1. The claim, as stated, correctly describes the class requirement.

  2. The claim, as stated, is wrong. The existential quantifier should be replaced by a universal one.

  3. The claim, as stated, is too weak. There is at least one other thing that must hold for the y that must exist for any x who is a student.

  4. The claim as stated, is too strong. It claims too much about what must hold for the y that must exists for any x who is a student. We should remove one of the conjuncts inside the scope of the existential quantifier.

Answer.
Correct answer is A.

3.

3. Suppose that a, b, x, and y are integers and we have:

[1] x = y

[2] a = b

Assume the standard rules of arithmetic and the definition of equality that we gave above:

∀P (∀x, y (((x = y) ∧ P(x)) → P(y)))

For any integer n, define: successor(n) = n + 1.

Which of the following statements is/are true:

I. (successor(a) + 1) > successor(b)

II. (x > a) → (y > b)

III. (a ≠ x) → ((b > x) ∨ (b < x))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Exactly two of them

  5. All three of them

Answer.
Correct answer is E.
Solution.
Explanation: It’s easy to see each of them with appropriate substitutions of x for y and/or a for b. These substitutions are allowed since x = y and a = b .