Math 2710

Aug 26-28

Course Info

Grading

Homework

1.1 What is this course about?

Mathematics as a discipline

This course is about

The actual mathematics we will learn in this course is less important than the approach

A very simple example

Assertion: The sum of two even numbers is an even number.

Goal: find a mathematical proof of this fact.

Mathematical Proof

A mathematical proof of this assertion is an argument that starts from known facts and definitions and establishes the the truth of the assertion using the tools of logic.

A proof in formal logic starts from explicit hypotheses or axioms and applies the rules of deductive logic to reach a conclusion. Proofs of even simple facts in formal logic are extremely long and mostly not readable by humans.

In principle, a mathematical proof contains enough information to produce a formal logical proof.

Good Mathematical Proofs

A good mathematical proof is

Example, continued

To construct a proof of this assertion, we need:

Discussion

Key Vocabulary

  • theorem
  • lemma
  • proposition
  • corollary
  • example
  • algorithm
  • definition
  • proof
  • statement
  • proposition
  • converse
  • contrapositive
  • conditional statement

1.2 Logic

Statements

A statement is a sentence that is either True or False

Compound statements are built up using logical operators AND, OR, NOT, and others.

The truth of a compound statement depends on the individual statements and the properties of the operators.

AND, OR, NOT

P Q AND
T T T
T F F
F T F
F F F
P Q OR
T T T
T F T
F T T
F F F
P NOT
T F
F T

Implications/Conditionals

A great deal of reasoning is about conditional statments.

The truth of an implication depends on the Truth/Falsehood of BOTH components. But if the first clause is FALSE, the statement is TRUE. So the interesting cases are when the first clause is TRUE.

For discussion: Compare how other disciplines think about implications such as those above with how mathematicians do. Which of the statements above might be susceptible to proof in “real life”?

Truth Tables for conditionals

P Q \(\implies\)
T T T
T F F
F T T
F F T

Alternate formulations

Equivalence

The claim that two statements are equivalent is the claim that they are either both True or both False.

P Q \(\Longleftrightarrow\)
T T T
T F F
F T F
F F T

Example Computation

(X and (Y or Z)) \(\Longleftrightarrow\) ((X and Y) or (X and Z))

X Y Z Y or Z X and (Y or Z) X and Y X and Z ((X and Y) or (X and Z))
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T F F F F

(X and (Y or Z)) have the same truth values as ((X and Y) or (X and Z)) and so the statements are equivalent.

Discussion

Problems Originally posted to piazza

Definition: An integer x is 5-ish if there is an integer y so that x=5y.

  1. Write the definition for a number that is NOT 5-ish.
  2. Is 37 a 5-ish number? How do you know?

Definition: An integer x is “purple” if there is a integer y so that x=5y+1.

Which of the following statements are true?

  1. If x is purple, then x is not 5-ish.
  2. If x is 5-ish, then x is not purple.
  3. There is a number z that is neither purple nor 5-ish.

1.3 Sets

Sets

We rely on a “naive” notion of set, meaning a collection of objects. For example:

For a discussion of why this is naive, see Russell’s paradox.

Subsets

We can construct sets by selecting elements of another set, yielding a subset of the original set.

Explicit specification

\(A=\{1,3,5,8,9\}\), a subset of the integers.

Selection by a property

Suppose \(P\) is the set of people. Then \[\{p\in P: \textrm{$p$ is a legal resident of Chicago}\}\] is shorthand for the set consisting of people \(p\) for which the statement “\(p\) is a legal resident of Chicago” is True.

Set operations

If \(A\) and \(B\) are both subsets of some huge (and usually unmentioned) set \(U\), then:

More set operations

Discussion 1

Suppose \(A\) and \(B\) are two sets contained in some big set \(U\). Prove the following by a truth table:

Hint: Start with the statements \(X=(x\in A)\) and \(Y=(x\in B)\). Then \(A\subset B\) is \(X\implies Y\). Express the left hand side similarly and work out the truth table.

Discussion 2

What is the truth table associated to the proposition about any three sets \(A, B, C\):

\[ A\cup (B\cap C) = (A\cup B)\cap (A\cup C) \]

Is the proposition true?