Skip to content# [WIP] Mathematics for Computer Science - Notes

## Chapter 1: What is a proof

### Proposition:

### Predicates:

### The Axiomatic Method

— notes — 2 min read

- A
**proposition**is a statement (communication) that is either true or false. - The symbol ":=" is defined to read "equal by definition", and is used to define letters or symbols used to refer to commonly occurring objects. Statements involving the symbol ":=" are always assumed to be true. There is a subtle, but important difference between the symbols ":=" and "=". For example, we may first write "a:=4". This defines the symbol 'a' to equal 4, which is then assumed to be true. Then "a=5" and "a=4" are statements, the first of which is false and the second true.
- In general, you can’t check a claim about an infinite set by checking a finite sample of its elements, no matter how large the sample.
- $\forall n \in ℕ. \; p(n) \; is \; prime$
Here the symbol $\forall$ is read “for all.”
The symbol
**ℕ**stands for the set of nonnegative integers. The symbol $\in$ is read as “is a member of". The period after the**ℕ**is just a separator between phrases. - Euler (pronounced “oiler”)
- A conjecture is a conclusion or a proposition which is suspected to be true due to preliminary supporting evidence, but for which no proof or disproof has yet been found.
- $\forall \; a, \; b, \;, c, \; d \in \mathbb{Z}^+ . \; a^4 + b^4 + c^4 = d^4$ Here, $\mathbb{Z}^+$ is a symbol for the positive integers.

- A Predicate is a proposition that may be true or false depending on the values of its variables.
- Eg:
**“n is a perfect square”**describes a predicate, since it is either true or false depending on the value of**n**. - Predicates are named with letters, often with function notation. Eg: p(n) ::= "n is a perfect square" The output is either true or false. This is in contrast to ordinary functions where the output is a numerical value.

An axiom or postulate is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments.

A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question.

There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work:

i. Important true propositions are called theorems. ii. A lemma is a preliminary proposition useful for proving later propositions. iii. A corollary is a proposition that follows in just a few logical steps from a theorem.

Euclid’s axiom-and-proof approach, now called the axiomatic method.