-
Yesterday we encountered a very useful logical equivalence which I call a partial contrapositive. But before stating a partial contrapositive let us state two important equivalences related to an implication: the negation of an implication and the equivalence of an implication and its contrapositive.
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \Rightarrow q) \ \ \Leftrightarrow \ \ p \wedge (\neg q) }$ This is the negation of an implication. To understand why this equivalence makes sense, think of what setting would make the implication: "If it rains (on campus), then the Red Square is wet." false. For a formal proof of this equivalence construct its truth table.
- $\bbox[lightgreen, 4px, border:2px solid green]{ p \Rightarrow q \ \ \Leftrightarrow \ \ (\neg q) \Rightarrow (\neg p) }$ The contrapositive is equivalent to the original implication. The easiest way to prove this equivalence is to look at the negations: the negation of the original implication is $p \wedge (\neg q)$, while the negation of the contrapositive is $(\neg q) \wedge p$. The last two propositions are clearly equivalent since the conjunction is commutative.
- $\bbox[lightgreen, 4px, border:2px solid green]{ (p \wedge q) \Rightarrow r \ \ \Leftrightarrow \ \ \ (p \wedge \neg r) \Rightarrow (\neg q) }$ I call this equivalence a partial contrapositive. To prove it, just look at the negations of each side of the equivalence.
- $\bbox[lightgreen, 4px, border:2px solid green]{ p \Rightarrow ( q \lor r ) \ \ \Leftrightarrow \ \ \ (p \wedge \neg q) \Rightarrow r }$ This equivalence is closely related to the partial contrapositive. Its structure is similar to the contrapositives of each side of equivalence in the partial contrapositive. To prove this equivalence, look at the negations of each side of the equivalence.
-
Since we are listing logical equivalences, let us review three more equivalences. As above, I use $\Leftrightarrow$ to mean "is equivalent to."
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( \neg p ) \ \ \Leftrightarrow \ \ p }$ This is the double negation law
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \wedge q) \ \ \Leftrightarrow \ \ (\neg p) \vee (\neg q) }$ This is De Morgan's law
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \vee q) \ \ \Leftrightarrow \ \ (\neg p) \wedge (\neg q) }$ This is De Morgan's law
- I updated the class lecture notes by fixing typos and adding the nicknames to the Axioms of the Real numbers.
- Sunday, October 16, 2022
-
-
How to negate a logical statement with two quantifiers? I claim that logical operations are not "randomly" made up rules which are here for us to learn and apply; logical operations are formalizations of how mind works. Therefore, I believe that a good way to internalize how logical operations work is to test them on everyday statements.
- It is an open problem to find a good everyday statement on which we could test the above claim. (The problem with my claim might be that the phrases "for every" and "there exists" are not often use in everyday language. However, I belive that if we keep trying we can find a statement on which we can test understanding of quantifiers that exists as common sense.)
- What is the negation of the statement: In every class at WWU, there exists a student who likes chocolate.
- Is the answer to the preceding question common knowledge? I would like to think that it is. I am hoping that a lot of people would answer: There exists a class at WWU in which all students do not like chocolate; or some equivalent version of this statement.
- Now I will put the quantified statement from above in a more formal setting. First we determine two universes of discourse which are present in the statement. The first universe of discourse is \(C\), the set of all classes at WWU and the second is \(S\), the set of all students at WWU. The propositional function that we are discussing is \(P(x)\) which means: \(x\) likes chocolate. Here \(x\in S\). Then, the above statement is \[ \forall\mkern 1mu c \in C \quad \exists \mkern 1mu x \in S \quad \text{such that} \quad x \in c \, \land \, P(x) \] The negation is \[ \exists\mkern 1mu c \in C \quad \text{such that} \quad \forall \mkern 1mu x \in S \quad x \notin c \, \lor \, \lnot P(x) \] An alternative (equivalent) formal version is \[ \forall\mkern 1mu c \in C \quad \exists \mkern 1mu x \in c \quad \text{such that} \quad P(x) \] The negation is \[ \exists\mkern 1mu c \in C \quad \text{such that} \quad \forall \mkern 1mu x \in c \quad \lnot P(x) \] I find the first version a little nicer since it is very clear about the second universe of discourse. The second version is not so clear about the second universe of discourse.
-
I suggest another practice for quantified statements: consider grids consisting of randomly colored black and white squares.
- Let $B(j,k)$ be the following propositional function: "The square in the $j$-th row and $k$-th column is colored black". Here we assume that the rows are counted from top to bottom and the columns are counted from left to right.
-
Consider grids which consist of black and white cells. For example consider the following four grids:
Grid 1 Grid 2 Grid 3 Grid 4 
-
Further, consider the following four propositions:
- Proposition 1. $\forall j \, \exists k \ B(j,k)$
- Proposition 2. $\exists k \, \forall j \ B(j,k)$
- Proposition 3. $\exists j \, \forall k \ \neg B(j,k)$
- Proposition 4. $\forall k \, \exists j \ B(j,k)$
- Your task here is as follows: For each grid identify the propositions that are true for that grid. For each grid identify the propositions that are false for that grid. State the negations of Propositions 1 through 4.
-
How to negate a logical statement with two quantifiers? I claim that logical operations are not "randomly" made up rules which are here for us to learn and apply; logical operations are formalizations of how mind works. Therefore, I believe that a good way to internalize how logical operations work is to test them on everyday statements.
- Tuesday, October 11, 2022
-
-
Today we discussed Exercise 3.1.2(d) and Exercise 3.2.2(g). In the proof of Exercise 3.2.2(g) we needed as a Background Knowledge the following statement: Let \(a \in \mathbb{R}\). If \(a \gt 0\), then \(1/a \gt 0\). Without consulting the
class lecture notes I tried to prove this statement in class. On the spot, the proof that I came up with was a proof by contradiction. That proof goes as follows:
- The Background knowledge for this proof are Axioms MO, MR, OE, OM, Exercise 3.1.2(b), Exercise 3.2.2(e) and Exercise 3.1.2(i). In fact we will use the contrapositive of the implication \[ a = 0 \ \lor \ b=0 \quad \Rightarrow \quad ab=0. \] The contrapositive is \[ ab \neq 0 \quad \Rightarrow \quad a \neq 0 \ \land \ b\neq 0. \]
- We will prove the implication If \(a \gt 0\), then \(1/a \gt 0\) by contradiction. We will prove that \[ a \gt 0 \ \land \ \lnot ( 1/a \gt 0 ) \quad \Rightarrow \quad \mathsf{F}. \] In this proof we use the following symbols for the logical operations: \(\land\) for the conjunction, \(\lor\) for the disjunction, \(\lnot\) for the negation and \(\Rightarrow\) for the implication.
- Assume \(a \gt 0\) and \(\lnot ( 1/a \gt 0 )\).
- We first explain that it is "legal" to use the reciprocal of \(a\). By Axiom OE we have \(a\neq0\). By Axiom MR there exists the reciprocal of \(a\), which we denote by \(1/a\), such that \(a (1/a) = 1\).
- By Axiom MO \(1\neq 0\). Hence \(a (1/a) \neq 0\). By Exercise 3.1.2(i) we deduce that \(1/a \neq 0\). Since \(1/a \neq 0\) the assumption \(\lnot ( 1/a \gt 0 )\) and Axiom OE yield \(1/a \lt 0\).
- Now we have \(a \gt 0\) and \( 1/a \lt 0\). By Axiom OM we deduce \(a(1/a) \lt a\cdot 0\). By Exercise 3.1.2(b) we have \(a\cdot 0 = 0\) and by Axiom MR \(a(1/a) = 1\). Hence we proved \(1 \lt 0\). Since in Exercise 3.2.2(e) we proved \(0 \lt 1\), by Axiom OE, the statement \(1 \lt 0\) is false. Thus, we proved \[ a \gt 0 \ \land \ \lnot ( 1/a \gt 0 ) \quad \Rightarrow \quad \mathsf{F}. \]
- Since I do not like proofs by contradiction, in the class notes I proved If \(a \gt 0\), then \(1/a \gt 0\) (this is Exercise 3.2.2(f)) by deducing this statement from Exercise 3.2.2(c). I proved the relevant implication in Exercise 3.2.2(c) by proving its contrapositive. You can see that I went through some trouble to avoid a proof by contradiction. I always try that since I find that seeking a direct proof of the contrapositive enhances my learning experience.
-
Today we discussed Exercise 3.1.2(d) and Exercise 3.2.2(g). In the proof of Exercise 3.2.2(g) we needed as a Background Knowledge the following statement: Let \(a \in \mathbb{R}\). If \(a \gt 0\), then \(1/a \gt 0\). Without consulting the
class lecture notes I tried to prove this statement in class. On the spot, the proof that I came up with was a proof by contradiction. That proof goes as follows:
- Monday, October 10, 2022
-
- Where do proofs come from? Where do proofs start? Proofs start from axioms. The main object of study in this class are real numbers. Therefore we introduce the Axioms for the Real Numbers. The standard notation for the set of all real numbers is $\mathbb{R}.$
- High school algebra is based on the Axioms for the Real Numbers. If you ever wondered how rules of high school algebra are proved, the answer is: one would start from the 16 Axioms listed in the Axioms for the Real Numbers. I am not sure if the issue of proving basic algebra rules is addressed in our curriculum at all. Therefore, in the class lecture notes I prove some of the basic rules of high school algebra in Exercises 3.1.2, 3.2.2, 3.2.6 and I leave some other basic rules for you to prove.
- Thursday, September 29, 2022
-
- I wrote a webpage dedicated to rigorous definition of a Function. Everething that we covered in class is on this page, and there is more. In particular, I think that studying the examples on this page will give you an overview of what you learned scattered in various math courses.
- We continued with Section 2.2: Functions in the class lecture notes. There are three exercises for which proofs are given in the notes: Exercises 2.2.3, 2.2.5, and 2.2.13. Proofs for Exercises 2.2.4, 2.2.6, 2.2.7, and 2.2.8 use the definitions. In Exercise 2.2.9 you can use Exercises 2.2.7 and 2.2.8. Exercises 2.2.11 and 2.2.12 use definitions related to functions combined with definitions related to sets.
- Wednesday, September 28, 2022
-
-
As I mentioned in class on Tuesday, a proof should begin with the following sentence: "In this proof, I use the following facts from background knowledge.''
For example, I should have started the proof of Proposition stated on Sunday, September 25, 2022, by the following statement:
In this proof, I use the following facts from background knowledge:
- The implication $p\Rightarrow q$ is equivalent to its contrapositive $\lnot q\Rightarrow \lnot r.$
- The negation of the statement $a \geq 0$ is the statement $a \lt 0.$ (This property of real numbers follows from the axioms of order of real numbers. We will talk more about it when we introduce the axioms of real numbers.)
- In this proof I use the concept of the maximum of a set of three real numbers.
- There are two solutions for Exercise 2.1.8 posted in Canvas Discussions. I commented on each of the proofs.
- On Tuesday we talked about Section 2.2: Functions in the class lecture notes. There are three exercises for which proofs are given in the notes: Exercises 2.2.3, 2.2.5, and 2.2.13. Proofs for Exercises 2.2.4, 2.2.6, 2.2.7, and 2.2.8 use the definitions. In Exercise 2.2.9 you can use Exercises 2.2.7 and 2.2.8. Exercises 2.2.11 and 2.2.12 use definitions related to functions combined with definitions related to sets.
-
- Monday, September 26, 2022
-
- Today we talked about Section 2.1: Sets in the class lecture notes. There are three exercises with statements that you can prove: Exercise 2.1.8, Exercise 2.1.10, and Exercise 2.1.15.
- Sunday, September 25, 2022
-
- We finished discussing Brief Review of Mathematical Logic. We will continue with the discussion of Chapter 2: Sets and functions in the class lecture notes.
-
On Friday I proved Proposition 5.1 from Brief Review of Mathematical Logic.
Proposition. For all real numbers $a, b, c$ the following equivalence holds \[ \forall\mkern+1mu x \in \mathbb{R} \quad ax^2 + b x+ c \geq 0 \qquad \Rightarrow \qquad a \geq 0. \]
- The proof that I offered on Friday might be simpler than the proof in the notes.
-
I used the following strategies to prove this proposition.
- It is easier to prove the contrapositive of the implication given in the proposition \[ a \lt 0 \qquad \Rightarrow \qquad \exists\mkern+1mu x \in \mathbb{R} \quad \text{such that} \quad ax^2 + b x+ c \lt 0. \]
- Notice that $a,b,c \in \mathbb{R}$ are given real numbers. When I use colors, I color such numbers green. In the implication in the preceding item the number $x \in \mathbb{R}$ needs to be constructed using the numbers $a,b,c \in \mathbb{R}$. I color such numbers red.
- Working with three given numbers $a,b,c \in \mathbb{R}$ seems hard. Therefore I first consider much simpler special case $a = -1,$ $b \geq 0,$ and $c = 0$ and I prove \[ \exists\mkern+1mu x \in \mathbb{R} \quad \text{such that} \quad -x^2 + b x \lt 0. \] In this case $x$ will depend only on $b.$ To find a desired $x$ I observe that the parabola $y = -x^2 + b x$ is concave down and intersects the $x$-axis at $0$ and $b.$ Therefore, the value of this parabola at $x = b+1$ will be negative. Let us check this: \[ -(b+1)^2 + b (b+1) = -b^2 - 2 b - 1 + b^2 + b = - b - 1 \lt 0. \] Since $b \geq 0$ we have $-b-1 \lt 0.$
-
Now comes the most difficult part of the proof.
I still keep $a=-1,$ but use arbitrary $b,c \in \mathbb{R}.$ We need to discover a certain number $b' \geq 0$ such that \[ -x^2 + b x + c \leq -x^2 + b' x. \] It is not very likely that the above inequality can hold for all $x \in \mathbb{R}.$ However, it is sufficient that the above inequality holds for all large positive values of $x,$ for example $x \geq 1.$
Assume that $x \geq 1.$ Set $d = \max\{b,c,0\}.$ Then \[ b \leq d, \qquad c \leq d \qquad 0 \leq d. \] Therefore \[ b x \leq d x, \qquad c \leq d x. \] Therefore \[ -x^2 + b x + c \leq - x^2 + d x + d x = -x^2 + 2d x. \]
What we did in this and the preceding item shows that with $x = 2d+1$ we have \[ -(2d+1)^2 + b (2d+1) + c = -4 d^2 - 4 d - 1 + 2 bd + b + c =- 2 d^2 - 2d(d-b) - 2 d - (d-b) - (d-c) - 1 \lt 0. \]
- Now assume that $a \lt 0.$ Then $-a \gt 0$ and \[ a x^2 + b x + c = (-a) \left( - x^2 - \frac{b}{a} x - \frac{c}{a} \right). \] Based on what we did in the preceding item, after some algebra we can deduce that with \[ x = 1 - 2 \frac{d}{a} \qquad \text{where} \qquad d = \max\{b,c,0\} \] we have \begin{align*} a \left(1 - 2 \frac{d}{a}\right)^2 + b \left(1 - 2 \frac{d}{a}\right) + c & = a - 4 d + 4 \frac{d^2}{a} + b - 2 \frac{bd}{a} + c \\ & = a - 2 d - (d-b) - ( d - c ) + 2 \frac{d^2}{a} + 2 \frac{d}{a} (d- b) \lt 0. \end{align*} The last expression is strictly less than $0$ since \[ a \lt 0, \quad - 2 d \leq 0, \quad - (d-b) \leq 0, \quad - ( d - c ) \leq 0, \quad 2 \frac{d^2}{a} \leq 0, \quad 2 \frac{d}{a} (d- b) \leq 0, \quad. \]
- Thursday, September 22, 2022
-
- We talked about Mathematical Logic. Thank you for your contributions to today's class. The relevant reading is in the first three sections (1. Logic, 2. Propositional calculus, 3. Implications) of my essay Brief Review of Mathematical Logic.
- For the next class read Section 4: Propositional functions and Section 5: Examples in my essay Brief Review of Mathematical Logic. As a big example of how to do proofs with quantifiers you can read my webpage Mathematical Rigor in the Context of Quadratic Functions.
- Tuesday, August 9, 2022 (updated)
-
- The information sheet
- In this class we present a rigorous approach to basic theorems in calculus. Since rigorous reasoning in Mathematics is based on Mathematical Logic, we will start with a Brief Review of Mathematical Logic. After reading Brief Review of Mathematical Logic you can read my webpage Mathematical Rigor in the Context of Quadratic Functions.
- The class lecture notes.
- Some useful Wikipedia links: