17.4 Quantified Statements

Words that describe an entire set, such as “all”, “every”, or “none”, are called universal quantifiers because that set could be considered a universal set. In contrast, words or phrases such as “some”, “one”, or “at least one” are called existential quantifiers because they describe the existence of at least one element in a set.

Something interesting happens when we negate – or state the opposite of – a quantified statement.

When we negate a statement with a universal quantifier, we get a statement with an existential quantifier, and vice-versa.

Note

Negating a quantified statment

The negation of “all A are B” is “at least one A is not B”.

# EDIT this little world: does each child learn English in school?
CHILDREN = {"Anna": True, "Bjorn": True, "Katrin": True, "Dagur": True}

def universal(world, claim):
    truth = all(world.values())
    print(f'"{claim}"  ->  {truth}')
    print('   negation: "at least one is not"  ->  ' + str(not truth))
    bad = [k for k, v in world.items() if not v]
    if bad:
        print(f"   ONE counterexample settles it: {bad[0]}"
              f"   (you do not have to show that nobody does)")
    else:
        print(f"   to disprove it you would need just one counterexample - "
              f"all {len(world)} check out, so none exists")

universal(CHILDREN, "All Icelandic children learn English in school.")

print()
CARTONS = [False, False, False, False, False, False]     # EDIT: which cartons leak?
truth = any(CARTONS)
print(f'"One of these six cartons of milk is leaking."  ->  {truth}')
print(f'   negation: "no carton is leaking"  ->  {not truth}')
print(f"   to DISPROVE it you must check all {len(CARTONS)} cartons; checking one proves nothing")
leaks = [i + 1 for i, v in enumerate(CARTONS) if v]
print(f"   leaking cartons: {leaks if leaks else 'none'} - "
      f"{'the claim stands' if leaks else 'the claim is false'}")

print()
def is_prime(k):
    return k > 1 and all(k % d for d in range(2, int(k ** 0.5) + 1))
primes = [k for k in range(2, 40) if is_prime(k)]
evens = [p for p in primes if p % 2 == 0]
print('"There are no prime numbers that are even."  ->  ' + str(not evens))
print('   negation: "at least one prime number is even"  ->  ' + str(bool(evens)))
print(f"   witness: {evens}")

print("\nthe four negation rules, in one place")
rules = [("all A are B", "at least one A is NOT B", "one counterexample"),
         ("no A are B", "at least one A IS B", "one example"),
         ("at least one A is B", "no A are B", "check every A"),
         ("at least one A is not B", "all A are B", "check every A")]
print(f"{'statement':<28}{'its negation':<28}what it takes to disprove")
for a, b, c in rules:
    print(f"{a:<28}{b:<28}{c}")

The negation of “no A are B” is “at least one A is B”.

The negation of “at least one A is B” is “no A are B”.

The negation of “at least one A is not B” is “all A are B”.

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.