Glossary

GLOSSARY VLORBIK

1. Glossary absorbing element (n.) For S a set with operation ◦, an element a ∈ S is called absorbing if for every s ∈ S, one has a ◦ s = s ◦ a = a. For example, zero is an absorbing element for multiplication, and t (true) and f (false) are absorbing elements for the operations of disjunction and conjunction respectively. and (n.) The logical operation formally known as “conjunction” and abbreviated by ∧. Thus the compound statement “p ∧ q” is pronounced “p and q” and is true when both of the statements represented by the variables are true. antecedent (n.) The “if part” of a conditional statement; for example “p” in “p ⇒ q” (the “then part”, “q”, is the consequent). arithmetic operation (n.) An operation on (a set of) numbers. The best known examples of arithmetic operations are addition and multiplication. associative (adj.) An operation ◦ on the set S is said to be associative if the equation x ◦ (y ◦ z) = (x ◦ y) ◦ z (the “associative law”) holds for all possible values of x, y, and z in S. base (n.) A number system that uses n different face values and whose place values are determined by the powers of n is said to be a base n system (and n is called the base of the system). Numbers are usually written in a base ten (decimal) number system, but bases two, eight, and sixteen are also useful in computing (binary, octal, and hexadecimal systems). binary (adj.) Having two parts. Base two numbers are referred to as binary numbers and are written using the two face values 0 and 1. Binary operations combine two elements of a set. bit (n.) A single digit in a binary number system. The usual notations for the two possible values of such a digit are 0 and 1. Other useful notations include off and on, t and f, and + and −. boolean algebra (n.) The arithmetic of formal logic. Variables are used to represent statements and hence have two possible values (usually denoted true and false). Variables and logical operations are combined to produce well-formed formulas. These in turn can be manipulated by various rules (for example, DeMorgan’s Laws) to produce other formulas representing equivalent statements. check digit (n.) A symbol used in an error-detecting code (for example, the ISBN) to introduce redundant information. 1

2

VLORBIK

circular definition (n.) See infinite loop. commutative (adj.) An operation ◦ on the set S is said to be commutative if the equation x ◦ y = y ◦ x (the “commutative law”) holds for all possible values of x and y in S. complement (n.) The complement of the set S is denoted by S 0 (this is usually pronounced “S-complement” or “S-prime”) and consists of all the elements of the universal set that are not elements of S. The corresponding logical operation is negation. compound statement (n.) A statement formed by joining two or more simple statements (or, loosely, by negating a single simple statement). For example, “I will pay my taxes or I will go to jail” is a compound statement formed of the simple statements “I will pay my taxes” and “I will go to jail”. At the symbolic level, statements are combined using logical operations; the most common of these are or, and, implies, and not. conclusion (n.) A statement in an argument said to follow from the premises of the argument. The form of the argument is valid if the conclusion must be true whenever all the premises are true. conditional statement (n.) A statement of the form “If p, then q”, or “p implies q” (abbreviated “p ⇒ q” in either case). The statement represented by the variable p is called the antecedent of the conditional statement; the statement represented by q is the consequent. conjunction (n.) The logical operation commonly known as “and” and abbreviated by ∧. The corresponding operation for sets is intersection. The conjunction of two statements is true when both of the statements are true. consequent (n.) The “then part” of a conditional statement; for example “q” in “p ⇒ q” (the “if part”, “p”, is the antecedent). contradiction (n.) A statement that cannot possibly be true (for any values of its variables). The so-called “law of non-contradiction” asserts that p ∧ ∼p (“p and notp”) is a contradiction—p cannot simultaneously be true and false. The negation of a contradiction is a tautology. contrapositive (n.) The (direct) conditional statement p ⇒ q is logically equivalent to the statement ∼q ⇒ ∼p; the second statement is called the contrapositive of the first. converse (n.) The statement q ⇒p obtained from the (direct) conditional statement p ⇒ q by reversing the rˆ oles of the antecedent and the consequent is called the converse of the direct statement. The direct statement and its converse are not logically equivalent. decimal (1) (adj.) Based on the number ten; base ten. The most common system of notation throughout the world for several centuries has been the decimal system (1, 2, 3, . . . , 9, 10, 11, . . . , 98, 99, 100, 101, . . . ): a place value system with base ten. (2) (n.) A number written in base ten notation. In everyday speech, the usual reference is 1 1 plus four times 100 ). to a decimal fraction like 0.14 (one times 10 DeMorgan’s Laws (n.) The pair of logical equivalences ∼(p ∧ q) ≡ ∼p ∨ ∼q and ∼(p ∨ q) ≡ ∼p ∧ ∼q. These facts can also be written using the set equations (X ∩ Y )0 = X 0 ∪ Y 0 and (X ∪ Y )0 = X 0 ∩ Y 0 .

GLOSSARY

3

direct statement (n.) A conditional statement (say, p⇒q) as considered in contrast to its converse (q ⇒ p) or its contrapositive (∼q ⇒ ∼p). disjunction (n.) The logical operation commonly known as “or” and abbreviated by ∨. The corresponding operation for sets is union. The disjunction of two statements is true when at least one of the statements is true. Disjunction is sometimes called “inclusive or” for this reason (“exclusive or” is then the operation yielding a true statement when exactly one of its operands is true — an operation also known as “symmetric difference”). distributive law (n.) A (left–) distributive law for a pair of operations ◦ and ? on the set S is an equation of the form a ◦ (x ? y) = (a ◦ x) ? (a ◦ y), true for all possible values of a, x, and y in S. (A right-distributive law takes the analogous form (x?y)◦a = (x◦a)?(y ◦b).) The operation ◦ is said to be “distributive over” ?. The best-known example: multiplication is distributive over addition—a(x+y) = ax+ay (and also (x+y)a = xa+ya). Distributive laws also occur in boolean algebra: in fact p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (and its rightdistributive analogue) and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (and its right-distributive analogue) are true. divide (vt.) For natural numbers n and m, we say n divides m, and write n|m, when m n is a natural number. For example, 4|12 and 5 6 | 12. divisor (1) (n.) The phrase “n is a divisor of m” has the same meaning as “n divides m”. Thus, the set of divisors of 12 is {1, 2, 3, 4, 6, 12}. (2) (n.) In the equation a ÷ b = c, some authors refer to a as the dividend, b as the divisor, and c as the quotient. element (n.) A member of a set. The symbol “∈” is used to denote set membership; x ∈ S is pronounced “x is an element of S” (or simply “x is in S”). For example 5 ∈ {2, 3, 5, 7, 11} and 9 6∈ {2, 3, 5, 7, 11}. empty set (n.) The set { } contanining no elements. The standard notation for the empty set is “Ø”. This symbol should not be confused with zero. Because of the resemblance between “Ø” and the Greek letter φ, the empty set is sometimes referred to as “phi”. This usage should be regarded as slang. equivalent (adj.) Two elements of a set are said to be equivalent with respect to a given partition of the set when both elements belong to the same class in the partition. For examples, see logically equivalent and equivalent (mod n). equivalent (mod n) (adj.) For n a natural number greater than or equal to 2, the natural numbers a and b are called equivalent (mod n) when they have the same remainder on division by n (otherwise inequivalent). The symbol ≡n denotes equivalence (mod n); thus, for example, 5 ≡3 23 and 5 6≡4 23. face value (n.) The quantity represented by a digit without regard to its place value; for example, the “8” in 187 has a face value of eight. factor (1) (n.) The phrase “n is a factor of m” has the same meaning as “n divides m”. Thus, the set of factors of 12 is {1, 2, 3, 4, 6, 12}. (2) (vt.) To write as a product of primes. Thus, the answer to the exercise “Factor 120” is “120 = 23 · 3 · 5”. false (adj.) Abbreviation: f. Not true; one of the possible values of a boolean variable or the possible types of statement.

4

VLORBIK

finite (adj.) Limited in extent. A set is finite if it is possible (at least in principle) to list its elements in order from first to last. Thus, for example, {1, 2, 3, . . . , 1, 000, 000, 000} is a finite set but { 12 , 31 , 14 , . . .} is not. See infinity. hex (adj.) Short for hexadecimal. hexadecimal (adj.) Base sixteen. Because 16 = 24 , “hex” notation translates easily to and from binary (one hex digit ↔ four bits). identity element (n.) For S a set with operation ◦, an element e ∈ S is called absorbing if for every s ∈ S, one has e ◦ s = s ◦ e = s. For example, zero is an identity element for the operation of addition, 1 is an identity element for multiplication, and t (true) and f (false) are elements for the operations of conjunction and disjunction respectively. implication (n.) (1) The operation defined at implies. (2) A conditional statement. implies (n.) The logical operation (also known as “implication”) denoted by ⇒. Thus “p ⇒ q” is pronounced “p implies q” (another common pronunciation is “if p then q”). This compound statement is true unless q is false while at the same time p is true. infinite (adj.) Not finite; without end. infinite loop (n.) See circular definition. integers (n.) The set Z = {. . . − 2, −1, 0, 1, 2, 3, . . .}. intersection (n.) The intersection of sets X and Y is denoted by X ∩ Y and consists of all the elements of X that are at the same time also elements of Y . The corresponding logical operation is conjunction. invalid (adj.) Not valid. ISBN (n.) The International Standard Book Number used by publishers throughout the world to identify books. An example of an error-detecting code based on equivalence mod eleven. lexicographer (n.) A harmless drudge, according to Samuel Johnson. Examples include Ambrose Bierce, Josepha Heifetz Byrne, Sir James Murray, and Voltaire. lexicographic (adj.) A generalization of “alphabetic” as applied to ordering the objects of a set. logically equivalent (adj.) Two statements are logically equivalent when every possible assignment of the values true and false to the boolean variables of the statements makes the truth values of the two statements match (both true or both false). In other words, statements are equivalent if they “have the same truth table”. logical operation (n.) An operation on statements. Examples include conjunction, disjunction, implication, and negation. mod (adv.) Given a natural number n > 1, the natural numbers a ≤ b are said to be equivalent (mod n), and we write a ≡n b, when n divides b − a (this amounts to the same thing as saying that a and b have the same remainder on division by n). modular (adj.) Involving a modulus. modulus (n.) The number n in the mod n equivalence a ≡n b is called the modulus of the equivalence.

GLOSSARY

5

natural numbers (n.) The set N = {0, 1, 2, 3 . . .}. Some texts refer to the set {1, 2, 3, . . .} (the counting numbers or the positive integers) as the natural numbers, so particular care is required on this point. Throughout this text, the convention is that zero is a natural number. negate (vt.) To form the negation of (a statement). negation (n.) The logical operation commonly known as “not” and abbreviated by ∼. The corresponding operation for sets is complement. The negation of a statement is true when the original statement is false and false when the original statement is true. not (n.) The logical operation formally known as “negation” and abbreviated by ∼. Thus “∼p” is pronounced “not p” and is true when p is false (and false when p is true). numeral (n.) A written or typographic symbol representing a number. For example “3”, “III”, and “112 ” are numerals representing the number three in Hindu-Arabic, Roman, and binary notations. octal (adj.) Base eight. Because 8 = 23 , octal notation translates easily to and from binary (one octal digit ↔ three bits). operand (n.) An “input” to an operation on a set. operation (n.) An operation on a set can be thought of as a device taking a certain number of elements of the set as “input” and producing an element of the set as “output”. The “input” elements are known as operands. An example of a unary (one operand) operation is logical negation: this operation on the set of statements turns true inputs into false outputs and false into true. Examples of binary operations (two operands) include the familiar arithmetic operations (+, −, ·, ÷) on sets of numbers, set operations (∩, ∪,0 ) on sets of sets, logical operations (∧, ∨, ∼, ⇒) on sets of propositions, and many others. or (n.) The logical operation formally known as “disjunction” and abbreviated by ∨. Thus the compound statement “p ∨ q” is pronounced “p or q” and is true when at least one of the statements represented by the variables is true. parity (n.) The parity of the natural number n is even or odd (depending, of course, on whether 2 divides n or not). partition (1) (n.) A splitting-into-parts. Given a set S, a collection of subsets of S is called a partition of S provided that (i) none of the subsets is empty and (ii) every element of S belongs to exactly one of the subsets. The sets of a partition are sometimes referred to as equivalence classes. (2) (vt.) To form a partition of (a set). pixel (n.) (Derived from picture element). The location for a single “dot” in a computer graphic output device. place value (n.) A base n positional notation system uses the rightmost digit for “ones”, the next digit to the right for “n’s”, and so on — multiplying by n at each move to the left. For example, the “8” in 187 (= 18710 ) is in the tens place, and the “1” in 1000002 is in the thirty-twos place (32 = 25 ). Compare face value. premise (n.) A statement assumed to be true for purposes of argument. prime (adj.) The natural number n is prime if it has exactly two natural number factors: 1 and itself (note in particular that 1 is not prime). Thus the set of prime

6

VLORBIK

numbers is {2, 3, 5, 7, 11, 13, 17, . . .}. (2) (n.) The symbol 0 ; used to denote the complement of a set (For example. Also used in dozens of other notations throughout mathematics): thus X 0 (“ex prime”) denotes the complement of X. proposition (n.) See statement. set (n.) A collection of objects (the elements of the set) considered as a whole. Sets are usually denoted by capital letters or by displaying their elements between right and left set braces (“{” and “}”). Thus, A = {2, 3, 5, 7} is a (finite) set with four elements; this fact can be denoted #(A) = 4. Sets are determined by their elements without regard to order . Thus, with A = {2, 3, 5, 7} and B = {7, 5, 3, 2}, we have A = B. Examples include the empty set Ø = { }, the (infinite) set of natural numbers N = {0, 1, 2, 3, . . .}, and of course many others. The common set operations are union, intersection, and complement. See also subset, universal set. statement (n.) (1) A sentence (or other string of symbols [such as an equation]) with the property that it is either true or false. Compound statements are created by combining simple statements; simple statements are usually abbreviated in symbolic logic as variables (commonly p, q, r . . . ). (2) A well-formed formula of boolean algebra; thus, a representation in symbols of the form of a “natural language” statement as defined in (1). string (n.) A sequence of items taken in one-at-a-time order. For example, “abcdefg” may be viewed as a string of letters. Notice that the string “apple” is to be considered as an ordered collection of letters: “a, p, p, l, e” (not as the English word for the edible pome fruit). Computer systems represent everything — numbers, words, pictures, sounds, . . . everything! — as strings of bits. subscript (n.) A symbol written below another; for example, “8” and “10” in 7648 = 50010 . Commonly used to denote the base of a number. Not to be confused with superscripts (which usually denote exponentiation [as in “32 = 9”]). subset (n.) The set X is said to be a subset of the set Y when every element of X is also an element of Y . “X is a subset of Y ” is abbreviated by “X ⊂ Y ”. In the same situation, one may also write “Y ⊃ X” and say that Y is a superset of X. In particular A ⊂ A and Ø ⊂ A for any set A (Ø denotes the empty set). Also A ⊂ U for a universal set U . tautology (n.) A statement that must always be true (for any values of its variables). The so-called “law of the excluded middle” asserts that p∨∼p (“p or not-p”) is a tautology— p must be either true or false. The negation of a tautology is a contradiction. trinary (adj.) Having three parts. Base three numbers are referred to as trinary numbers and are written using the three face values 0, 1, and 2. trit (n.) A single digit in a trinary number system. true (adj.) Abbreviation: t. One of the two possible values of a boolean variable; one of two types of statement (the other value or type is, of course, false). Strictly speaking, both terms are undefined — as some terms must be if we are to avoid circular definitions. “What is truth?” is a question for philosophy rather than for mathematics (famously asked by Pontius Pilate [John 18:38] — no reply is recorded).

GLOSSARY

7

truth table (n.) A display showing the result of every possible substitution of values for the boolean variables of a statement or sequence of statements. union (n.) The union of sets X and Y is denoted by X ∪ Y and consists of all of the elements of X together with all of the elements of Y . The corresponding logical operation is disjunction. universal set (n.) A universal set U for a particular context is a set containing every element of interest for that context. One advantage of defining a universal set is that for an arbitrary set S one may then speak of the set of things not in S (the complement of S, denoted by S 0 ). valid (adj.) . An argument form is valid provided that whenever the premises are true, the conclusion will also be true. Not to be confused with “true” — it is possible for a valid argument to have a false conclusion (and for an invalid argument to have a true conclusion). validity (n.) “Correctness”. See valid. variable (n.) A typographical symbol used to represent an (arbitrarily chosen) element of a set. Common examples are arithmetic variables (representing numbers) and logical or boolean variables (representing statements or their logical values—true or false). well-formed formula (n.) A string of symbols that “makes sense” according to the rules of a particular system. Usually used in the context of the system of boolean algebra. wff (n.) Abbreviation for well-formed formula. Pronounced “woof”. zero (n.) The least natural number (no pun intended). The identity element for the operation of addition: x + 0 = x. The absorbing element of multiplication: x · 0 = 0. The rˆole of the numeral 0 as a face value in a base ten numeration system apparently originated in India in the second century b.c.e..