Chapter 11 Appendix: the basics of mathematical logic
11.1 Mathematical statements
Not every combination of mathematical symbols is a statement; we sometimes call it ill-formed or ill-defined. ill-formed statements are considered to be neither true or false.
Axiom every well-formed statement is either true or false, bur not both. (Though if there are free variables, the truth of a statement may depend on the values of these variables)
In fact, usually we call well-formed statement as statement, and ill-fomed statements are not considered statements at all.
Conjunction.
Disjunction.
Negation.
If and only if (iff).
11.2 Implication
What this statement “if \(X\), then \(Y\)” means depend on whether \(X\) is true or false. If \(X\) is true, then “if \(X\), then \(Y\)” is true when \(Y\) is true, and false when \(Y\) is false. If however \(X\) is false, then “if \(X\), then \(Y\)” os always true, regardless of \(Y\) is true or false. That is, when \(X\) is false, the statement “if \(X\), then \(Y\)” offers no information about whether \(Y\) is true or not; the statement is true, but vacuous.
The only way to disprove an implication is to show that the hypothesis is true while the conclusion is false.
11.4 Variables and quantifiers
Mathematical logic is the same as propositional logic but with the additional ingredient of variables added. A variable is a symbol, such as \(n\) or \(x\), which denotes a certain type if mathematical object.
Universal quantifiers.
Existential quantifiers.
11.5 Nested quantifiers
Swapping two “for all” quantifiers or “there exists” quantifiers has no effect; swapping a “for all” with a “there exist” makes a lot of difference.
11.6 Equality
Equality is a relation linking two objects \(x,y\) of the same type \(T\).For the purposes of logic we require that equality obeys the following four axiom of equality.
- (Reflexive axiom). Given any object \(x\), we have \(x=x\).
- (Symmetry axiom). Given any two objects \(x\) and \(y\) of the same type, if \(x=y\), then \(y=x\).
- (Transitive axiom). Given any three objects \(x,\ y,\ z\) of the same type, if \(x=y\) and \(y=z\), then \(x=z\).
- (Substitution axiom). Given any two objects \(x\) and \(y\) of the same type, if \(x=y\), then \(f(x) = f(y)\) for all functions or operations \(f\). Similarly, for any property \(P(x)\) depending on \(x\), if \(x=y\), then \(P(x)\) and \(P(y)\) are equivalent statements.