This is part 3 of a multi-part series aimed at increasing mathematical literacy and logical thinking by teaching the background for and then the process of proving mathematics theorems. But this is important for more than just mathematicians: the ability to think logically is the backbone of making strong arguments and is vital for every aspect of life.

https://i.ytimg.com/vi/d33o0y_ASPs/maxresdefault.jpg
*source: [Youtube](https://www.youtube.com/watch?v=d33o0y_ASPs)*

Previous parts of this series:
[Part 1](https://steemit.com/mathematics/@daut44/an-introduction-to-mathematical-proofs-part-1-basic-logic-and-truth-tables)
[Part 2](https://steemit.com/mathematics/@daut44/an-introduction-to-mathematical-proofs-part-2-conditionals-deduction-biconditionals-proofs-of-equivalence)

# Summary of what was covered in parts 1 and 2:
-**Propositions** are sentences that are either true or false.
-**Compound propositions** are finitely many propositions connected by logical symbols
-**Propositional forms** are expressions involving finitely many logical connectors and letters.
-a **paradox** is a sentence that leads to a self-contradictory conclusion.
-Use letters such as P, Q, R, S to shorthand propositions
-"P and Q" = P^Q, referred to as **conjunction**
-"P or Q" = P v Q, referred to as **disjunction**
-"not P" = ~P, referred to as **negation**
-truth tables with N propositions have 2^N lines
-When two compound propositional forms have identical truth tables they are **equivalent**
-**Tautologies** are always true regardless of truth assignments to individual propositions, i.e. P v ~P
-**Contradictions** are the negation of tautologies. i.e. ~(P v ~P)
-**conditionals** have the form “if P then Q”
-**antecedent** refers to the proposition P, or what is assumed.
-**consequent** refers to the proposition Q, or what is deduced.
-**Modus Ponens** is the first deductive logic rule, which states that if we know P and P=>Q then we can deduce Q. This sets up our first future proof technique, **The Direct Proof**.
-the **converse** of P=>Q is Q=>P, and it is **not equivalent** to the conditional.
-the **contrapositive** of P=>Q is ~Q => ~P, and it is **equivalent** to the conditional P=>Q. This sets up our second future proof technique, **The Proof by Contraposition**.
-**biconditional** sentences have the form “P if and only if Q”
-**De Morgan’s Laws** are two famous equivalences:
~(P^Q) is equivalent to (~P) v (~Q)
~(PvQ) is equivalent to (~P) ^ (~Q)
-**The distributive Laws are two famous equivalences:
P^(QvR) is equivalent to (P^Q) v (P^R)
Pv(Q^R) is equivalent to (PvQ) ^ (PvR)


# Quantifiers
Consider the sentence “x > 10”. This is not a proposition: without a particular value of x assigned, this statement is neither true nor false. For some values of x this is true and for some values of x this is false. Until it has a particular value assigned, x is a **variable**. 

## Definitions
**Open Sentence**: a sentence containing at least one *variable*, which becomes a proposition only when the variables are replaced by particular objects. Another word for open sentence is **Predicate**. 
*Mathematicians denote open sentences using P and the variables inside x1, x2, …, xN., i.e. P(x1,x2,...,xN)*

Example: The sentence “x1 minus x2 is greater than x3 minus x4” is an open sentence with four variables. If we denote this sentence by P(x1,x2,x3,x4), then the specific proposition P(5,2,6,4) is true because (5-2) > (6-4) but proposition P(5,4,6,3) is false because (5-4) < (6-3).

**Universe**: the complete set of objects that are available to substitute for variables.
**Truth Set**: the collection of objects within that universe that make an open sentence a true proposition. 

Recall the following number definitions:
> **Integer:** whole numbers, or numbers that can be written without fractional components.
**Natural Number:** Positive integers (1,2,3,...)
**Rational Number:** Any number that can be represented as the fraction of two integers, p/q. For instance 3/2
**Irrational Number:** Numbers that cannot be represented as the fraction of two integers. For instance the square root of 2 or π
**Real Number:** The set of all rational and irrational numbers together. Both 1.5 and π are real numbers.

Example: Consider the open sentence "x² = 4". If our universe is defined as integers, then the truth set is {-2,2}. If our universe is instead defined to be the natural numbers then our truth set is {2}. 

**Equivalent**: given the same universe, open sentences P and Q are equivalent if and only if they have the same truth set.



Example: Let P be the sentence "10x = 50" and Q be the sentence "x=5". These sentences are equivalent in any universe, while  "x² = 4" and "x=2" are not equivalent if the universe is integers, but is equivalent if the universe is positive integers.


## Universal and Existential Quantifiers 
**Universal Quantifier**: The universal quantifier, denoted by the symbol **∀**, is equivalent to "for all". Given an open sentence P(x) with variable x, the sentence (∀x)P(x) is "for all x, P(x)" in English, and is true when the truth set for P(x) is the entire given universe. To show (∀x)P(x) is not true, we must find just one counter example in the universe where it doesn't hold, but to show it is true, we must show that it holds for everything in the universe.

For the following examples, let the universe be all real numbers:
1. (∀x)(x > 10) is false because there are many real numbers where this doesn't hold. For instance, x=5.
2. (∀x)(2x > x) is false because when x is negative, 2x is less than x. For instance, -2 < -1. 
3. (∀x)(x+2 > x) is true, because no matter what real number we choose, when 2 is added to that number it is greater than x.

**Existential Quantifier**: The existential quantifier, denoted by the symbol **∃**, is equivalent to "there exists". Given an open sentence P(x) with variable x, the sentence (∃x)P(x) is "there exists x such that P(x)" in English, and is true whenever there is at least one example of P(x) being true in a universe, or in other words, the truth set for P(x) is not empty. To show (∃x)P(x) is false, we must show that it is false for everything in the universe. 

For the following examples, let the universe be all real numbers:
1. (∃x)(x > 10) is true, because there are many real numbers where this holds. For instance 11>10 is true, so there exists a number greater than 10.
2. (∃x)(2x > x) is true, because there are many real numbers where this holds. For instance 2>1.
3. (∃x)(x² = -1) is false, because there are no real numbers which satisfy this equation. 

## Translating sentences in English to symbolic form
#### Translating universal quantifier sentences
Consider the sentence "All integers are rational numbers". This will be quantified with ∀ since we refer to all of something, but what does the proposition look like? Let I(x) represent "x is an integer", and R(x) represent "x is a rational number" in the universe of real numbers. 

Which of the following is the correct symbolic representation?
1. (∀x)[I(x) ^ R(x)]
2. (∀x)[I(x) => R(x)]

The first one says "For every object x in the universe, x is an integer and x is a rational number". This isn't what we intend to say because there are things in the universe that aren't integers, for instance irrational numbers are real numbers that aren't integers. 
The second one says "For all objects x in the universe, if x is an integer then x is a rational number", which is correct. 

In general, a sentence of the form  "All P(x) are Q(x)" should be symbolized by (∀x)[P(x) => Q(x)]

#### Translating existenial quantifier sentences
Now consider the sentence "Some rational numbers are integers". This will be quantified with ∃, because the sentence says "some" and not "all". Just as above, let R(x) represent "x is a rational number" and I(x) represent "x is an integer" in the universe of all real numbers.

Which of the following is the correct symbolic representation?
1. (∃x)[R(x) ^ I(x)]
2. (∃x)[R(x) => I(x)]

The first sentence says "There is an object x such that x is a rational number and x is an integer". This is the correct translation.
The second sentence says "There is an object x such that if it is a rational number then it is an integer".  This is incorrect because it doesn't guarantee the existence of a rational number which is an integer, also being a rational number does not imply something is an integer. 

In general, sentences of the form "Some P(x) are Q(x)" should be symbolized (∃x)[P(x) ^ Q(x)]

## De Morgan's Laws with Quantifiers
**Theorem: If P(x) is an open sentence with variable x, then**
1. **~(∀x) P(x)** is equivalent to **(∃x) ~P(x)**. ("Not for all x, P(x)" is equivalent to "there exists not P(x)")
2.  **~(∃x) P(x)** is equivalent to **(∀x) ~[P(x)**. ("There does not exist P(x)" is equivalent to "for all x not P(x)")

These are similar to De Morgan's Laws of conjunction and disjunction:
~(PvQ) = ~P ^ ~Q
~(P^Q) = ~P v ~Q

https://img1.steemit.com/0x0/https://www.liquidpoker.net/staff/Daut/Math/demorgan.png


Let's walk through the logic behind part 1. Proving part 2 is similar.
*Assume ~(∀x) P(x) is true. This means that (∀x) P(x) is false. But (∀x) P(x) is false if and only if the truth set of P(x) is not the entire universe, or on the flip side, the truth set of ~P(x) is non empty. The truth set of ~P(x) being non empty is equivalent to the existence of an x such that ~P(x). In symbolic form this is (∃x) ~P(x). Thus ~(∀x) P(x) is equivalent to (∃x) ~P(x).*

These equivalences allow us to easily find **denials** (another word for negation) of propositions. For instance consider the proposition “All primes are odd”. If we want to find a denial of this formally, we would have to step through and find equivalences:
1. **~(∀x) (x is prime => x is odd)** is equivalent to **(∃x) ~(x is prime => x is odd).**
2. **(∃x) ~(x is prime => x is odd)** is equivalent to **(∃x) ~(x is not prime or x is odd).**
3. **(∃x) ~(x is not prime or x is odd)** is equivalent to **(∃x) (x is prime and x is not odd)**

But now we have a shortcut using our rule ~(∀x) P(x) is equivalent to (∃x) ~P(x):
A denial of "all primes are odd" is "there exists a prime that is not odd". 

## Unique Existence Quantifier
The **unique existence quantifier**, denoted by the symbol **∃!**, is equivalent to "there exists a unique x such that P(x)". This is true whenever there is exactly one example of P(x) being true in a universe. To show (∃!x) P(x) is false, we must either show that it is false for everything in the universe or that there are multiple and unique x in the universe for which it is true.

Examples:
1. (∃!x)(x is prime and x is not odd) is true, since the truth set contains only one number: 2. 
2. (∃!x)(x² = 4) is true when the universe is the natural numbers, but is false when the universe is the integers.

In symbolic terms, a useful equivalent for (∃!x) P(x) is **(∃x) (P(x) ^ (∀y)[P(y) => x=y])**
Basically, if there are two x that satisfy P(x) then they are the same. Otherwise unique existence is not fulfilled.

As an exercise, what is the denial of (∃!x) P(x)?
1. **~(∃x) (P(x) ^ (∀y)[P(y) => x=y])** is equivalent to **(∀x) ~ ((P(x) ^ (∀y)[P(y) => x=y]))**
2. **(∀x) ~ ((P(x) ^ (∀y)[P(y) => x=y]))** is equivalent to **(∀x)(~P(x) v ~ (∀y)[P(y) => x=y])**
3. **(∀x)(~P(x) v ~ (∀y)[P(y) => x=y])** is equivalent to **(∀x)(~P(x) v (∃y) ~[P(y) => x=y])**
4. **(∀x)(~P(x) v (∃y) ~[P(y) => x=y])** is equivalent to **(∀x)(~P(x) v (∃y) ~[(~P(y)) v (x ≠ y)])**
5. **(∀x)(~P(x) v (∃y) ~[(~P(y)) v (x ≠ y)])** is equivalent to **(∀x)(~P(x) v (∃y) [P(y) ^ x ≠ y])**

Thus via the chain of equivalence, **~(∃x) (P(x) ^ (∀y)[P(y) => x=y])** is equivalent to **(∀x)(~P(x) v (∃y) [P(y) ^ x ≠ y])**.

In other words, (∃!x) P(x) is false when, for every x in the universe, either P(x) is false or if P(x) is true, then there exists y that is different from x such that P(y) is true too.

## Summary of Part 3
-**Open Sentence** is a sentence containing at least one variable, which becomes a proposition only when the variables are replaced by particular objects.
-**Universe**: the complete set of objects that are available to substitute for variables.
-**Truth Set**: the collection of objects within that universe that make an open sentence a true proposition. 
-Open sentences P and Q are **equivalent** if and only if they have the same truth set for a given universe. 
-"for all x, P(x)" = (∀x)P(x), the **universal quantifier**
-"there exists x such that P(x)" = (∃x)P(x), the **existential quantifier**
-In general, a sentence of the form  "All P(x) are Q(x)" should be symbolized by (∀x)[P(x) => Q(x)]
-In general, sentences of the form "Some P(x) are Q(x)" should be symbolized (∃x)[P(x) ^ Q(x)]
-**De Morgan's Laws for Quantifiers**:
1. ~(∀x) P(x) is equivalent to (∃x) ~P(x)
2.  ~(∃x) P(x) is equivalent to (∀x) ~[P(x)

-"there exists a unique x such that P(x)" = (∃!x) P(x), the **unique existence quantifier**


### We now have the necessary background built up to jump right into proof techniques next time!

___________________________________________________________________________________________________

My name is Ryan Daut and I would love to have you as a follower. [Click here](https://steemit.com/@daut44) to go to my profile page, then click [<img src="https://img1.steemit.com/0x0/http://i.imgur.com/oq3c1oq.png
">](https://steemit.com/@daut44) in the upper right corner if you would like to see my blogs and articles regularly. 

https://scontent-sjc2-1.xx.fbcdn.net/v/t1.0-9/12079621_10109514445317204_9079744146490914101_n.jpg?oh=82830933979d962a712322f57cc3c27f&oe=583BA554

My interests include poker, fantasy sports, football, basketball, MMA, health and fitness, rock climbing, mathematics, astrophysics, cryptocurrency, and computer gaming. 

You can also [follow me on twitter](https://twitter.com/rcdaut).