Chapter 5: Logic

Question 1

What is a statement?

Answer 1

A statement is a sentence or mathematical expression that is either true or false

• Note that:
  
  • Every theorem/proposition/lemma/corollary is a true statement
  • Every conjecture is a statement (of unknown truth value)
  • Every incorrect calculation is a (false) statement)

Question 2

What is an open sentence?

Answer 2

A related notion is that of an open sentence, which are sentence or mathematical expressions which (1) do not have a truth value, (2) depend on some unknown, like a variable x or an arbitrary function f, and (3) when the unknown is specified, then the open sentence becomes a statement (and so has a truth value). Their truth value
depends on which value of x or f one chooses.

Question 3

What notation do we typically use for statements or open sentences?

Answer 3

• Remember or in maths in “inclusive” (A or B or both).

Question 4

Examples of Statements using the usual notation?

Answer 4

Question 5

What is the notation for implication?

Answer 5

• The first is defined as a conditional statement whereas the second is a biconditional.

Question 6

What are some subtly different ways to say “P implies Q”?

Answer 6

Question 7

What are some subtly different ways to say “P if and only Q”?

Answer 7

Question 8

What is the converse of P –> Q?

Answer 8

Question 9

How can the logic statements be applied to set unions and intercept notation?

Answer 9

Question 10

How can the logic statements be applied to set complement notation?

Answer 10

Question 11

How can the “imply” logic statements be represented in set notation?

Answer 11

Question 12

How can we represent P ∧ Q on a Truth table?

Answer 12

Question 12

How else can the “not” logic symbol be written?

Answer 12

Question 13

How can we represent P v Q on a Truth table?

Answer 13

Question 14

How can “not P” be represented on the truth table?

Answer 14

Question 15

What are the truth values of ( P v Q) ∧ (~P ∧ Q) and how are they represented in a truth table?

Answer 15

Question 16

What are De Morgan’s Logic Laws?

Answer 16

Since the final columns are the same, if one is true, the other is true; if one is false, the
other is false; that is, there is no way to select P and Q without these two agreeing.
When two statements have the same final column in their truth tables, like in the
the example above, they are said to be logically equivalent (one is true if and only if
the other is true), which we denote with an “⇔” symbol

Question 17

How else can De Morgan’s logic law be written?

Answer 17

Question 18

How are implications added to Truth Tables?

Answer 18

• For if n =2, n is even
• So WHY is the implication true if the assumption, P, is false?
  
  • Because it is vacuously true: Is kind of like we said that “If x ∈ ∅, then x is a purple elephant that speaks German –> if there is nothing in the set then you can claim what you want about x as there is nothing in the set you can use to prove it wrong.
  • So in a universe where P is not true, it claims nothing and hence P –> ! it vacuously true
• Another way to think about it is if P –> Q is false if P –> Q is a lie
  
  • IF a said get A (final) –> A (class), if you get a B in the final and a B in class you can say my implication is wrong, equal if you got a B on the final but a A(class) you also wouldn’t say I lied to you either.

Hence the last two cases in the implication table are true

Question 19

What does the truth table look like for “P if and only if Q”?

Answer 19

Question 20

What is a quantifier?

Answer 20

• A quantifier is an expression which indicates the number (or quantity) of our objects
• These are used to turn a sentence like “n is even” into a statement (e.g. “by saying If n=5, then n is even”) which turns the sentences into something that is either true or false

Question 21

What are two of the most important quantifiers in maths and what are their symbols?

Answer 21

• The symbol ∀ means “for all” or “for every” or “for each”, and is called the
  universal quantifier
• The symbol ∃ means “there exists” or “for some”, and is called the existential
  quantifier

Question 22

Example of negations?

Answer 22

Question 23

What are the rules of thumb for negating statements?

Answer 23

• neggation would be “someone in the NBA is unable to dunk.” Indeed, in order to show
  “Every NBA player can dunk” is false, you would have to show that “someone in the
  NBA is unable to dunk” is true. Using quantifiers more explicitly, the negation of
  “For all players p in the NBA, player p can dunk” would be “There exists an NBA
  player p such that p can not dunk.”

…. If the universe of people I’m talking about are NBA players, then the negation remains in that universe. Getting back to our original example withR, if the universe of x-values that I am referring to is R, then the negation remains n that universe. That’s why the negation is “∃ x ∈ R,” rather than “∃ x 6∈ R.”

Question 24

How does negation apply to implications?

Answer 24

Question 25

How is the Contrapositive defined and what does its truth table look like?

Answer 25

Question 26

What does the contrapositive truth table look similar to?

Answer 26

The final column of the truth table of P –> Q

Question 27

THEOREM: What is logical equivalence to an implication?

Answer 27

Question 28

How do you prove an existense statement?

Answer 28

• To prove an existence statement, it suffices to exhibit an example satisfying the criteria.
• For example, in the opening pages of this book we proved that “there exists a perfect covering of a chessboard,” and we did so by drawing one out.
• Likewise, if you were asked to prove that “there exists an integer with exactly three positive divisors,” you could just find an integer which satisfies this; 4 is such an integer

Question 28

What are constructive and non-constructive proofs?

Answer 28

• The above strategy is called constructive proof — you literally construct an example. There are also non-constructive ways to prove something exists. Often (but not always!) non-constructive proofs make use of some other theorem.

Question 28

What is an example of a non-constructive proof?

Answer 28

Question 31

What is a Universal Proof?

Answer 31

• To prove a universal statement, it suffices to choose an arbitrary case and prove it works there
• For example, if you were asked to
  prove that “For every odd number n, it follows that n+ 1 is even,” your proof wouldn’t explicitly check 1 and 3 and 5 and so on
• Proving something holds for an arbitrary element of a set, proves that it in turn holds for every element in that set.
  The field of real analysis has a lot of definitions which make good use of quantifiers.

Question 32

Example of a universal proof used in real analysis?

Answer 32

Question 32

What is a paradox?

Answer 32

• The term is used in several distinct ways
  
  • One being that it is used to mean something is “counterintuitive” but the logic is being bent or broken
    *Some are like the magic trick sort of variety Like the picture attached.
• Others are where logic doesn’t break but due to faulty definitions we can get into loops where something is defined by itself but it says not to contain or be defined by itself.
  
  • e.g. the set R = {x : x ∉ x}
• The remaining “paradoxes” in math are of the false-at-their-core type.39 There is
  some fundamental flaw which is causing the inconsistency, like the basic misuse of an idea or object

Question 33

What are autological words?

Answer 33

a word that is an example of itself:
* For instance, a word is a word, and unhyphenated has no hyphens. Here are some more:
* A pentasyllabic word is one having five syllables, and the word itself has five
syllables.
**The word oxymoron refers to a term that is self-contradicting. The word has
two parts to it:
* The ‘oxy’ part comes from a Greek word meaning ‘sharp’, and the ‘moron’ part means ‘dull’. The word itself is self-contradicting, so it is an oxymoron!

Question 34

What is the paridoxical set R = {x : x ∉ x}
?

Answer 34

• Symbolically, there was no reason to disallow such a set definition, but yet you can work out the strange contradiction that R ∈ R if and only if R ∉ R; indeed, if R is not a member of itself, then according to its definition it must be a member of itself, and if it does contain itself, then it contradicts its own definition. How unsettling!
• Russell’s paradox demonstrated a hole in our theory, but that hole is now patched.

*In the above example, it was natural to assume that since the set R was able to
be succinctly defined, that it must exist. But this was false, and no such R exists.
* The issue comes down to the fact that the set’s definition, in some way, referred back to itself.
No word in the dictionary uses itself in its definition but in a less direct way
language can also fall into this trap

Question 35

What is the definition of converges concerning sequences?

Answer 35

Question 36

What is the outline to prove a sequence converges?

Answer 36

Question 37

PROOF: Let (a_n) be the sequence where a = 1/n. Then, a_n → 0

Answer 37

Question 38

PROOF:Let (a_n) be the sequence where a_n = 2 −(1/n²). Then, a_n → 2.

Answer 38

Question 39

PROOF:Let (a_n) be the sequence where a_n = (3n+1)/(n+2). Then, a_n → 3.

Answer 39