CSC165 Cases, multiple quantifiers, limits

Week #6

Topic: Cases, multiple quantifiers, limits

I found really interesting both the proof by cases and the proof about limits; therefore, I would like to use this space to practice and enhance the knowledge about these two interesting proofs.

Proof by cases

I realized that in this kind of proofs we are considering all the natural numbers by dividing them in odd and even numbers.

In other words: ℕ = {x: ∃ k ∈ ℕ, x = 2k + 1} U {x: ∃ k ∈ ℕ, x = 2k}

Now, let’s try to proof that ∀ n ∈ ℕ, 3n² + n +15 is odd

Definitions: n is odd when ∃ k ∈ ℕ, n = 2k + 1 and n is even when ∃ k ∈ ℕ, n = 2k

Assume n ∈ ℕ #Typical

            Case1: Assume n is odd, n = 2k + 1

                         Then 3n² + n +15 = 3(2k + 1)² + (2k + 1) + 1

                                                          = [3(4k² + 4k +1)] + 2k + 2

                                                          = 12k² + 12k + 3 +2k + 2

                                                          = 12k² +14k + 5

                                                          = 12k² +14k + 4 + 1 # 5 = 4 + 1

                                                          = 2(6k² +7k + 2) + 1

                        Then ∃ k₀ ∈ ℕ, n = 2 k₀ + 1 # k_{0 =} 6k² +7k + 2

                        Then 3n² + n +15 is odd #by definition

            Case2: Assume n is even, n = 2k

                         Then 3n² + n +15 = 3(2k)² + (2k) + 1

                                                          = [3(4k²)] + 2k + 1

                                                          = 12k² + 2k + 1

                                                          = 2(6k² + k) + 1

                        Then ∃ k₀ ∈ ℕ, n = 2 k₀ + 1 # k_{0 =} 6k² + k

                        Then 3n² + n +15 is odd #by definition

            Then 3n² + n +15 is odd #since in both cases this was true

Conclude ∀ n ∈ ℕ, 3n² + n +15 is odd

Now, let’s try to prove that  the limit of 3x - 1 as x approaches 2 is 5

In this case, we apply a concept very similar to the delta-epsilon proof.

∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x - |<d ⇒ |(3x - 1) - 5| < e

Assume e ∈ ℝ #Generic x

            Pick  d = e/3

                        Assume |x - 2|<d

                        Then |(3x - 1) - 5| = |3x - 6| = |3 (x - 2)| < 3d = e   # |x - 2|<d

   # |(3x - 1) - 5| < e

                        Then ∀ x ∈ ℝ, |x - 2|<d ⇒ |(3x - 1) - 5| < e

            Then ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x - 2|<d ⇒ |(3x - 1) - 5| < e

Conclude ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x - 2|<d ⇒ |(3x - 1) - 5| < e

CSC165 Contradiction, existence, sequences

Week #5

Contradiction, existence, sequences

We started doing proofs this week. It is interesting to notice that we can structure our proofs in the same way we structure code. We can see it better by looking at an example.

In the code below, the structure and indexation is very important to understand how the code is executed.

for i in range(10):

    if i <= 5:

        print(pow(i, 3))

    else:

        print(pow(i, 1/2))

Similarly, the structure of a proof is of great importance to understand the process of the proof and to guarantee a proper use of variables and quantifiers.

∀ x ∈ ℕ, ∀ y ∈ ℕ, ∃ z ∈ ℕ, x + y = z

Assume x ∈ ℕ

            Assume y ∈ ℕ

                        Let z = x + y                        #x and y are any ordinary natural numbers

                        Then x + y = z

                        Then ∃ z ∈ ℕ, x + y = z                   

            Then ∀ y ∈ ℕ, ∃ z ∈ ℕ, x + y = z                 # Include ∀

Then ∀ x ∈ ℕ, ∀ y ∈ ℕ, ∃ z ∈ ℕ, x + y = z             # Include ∀

To sum up, precision and ingenuity are the key factors to create a good proof.

I would like to include a link to a proof that I especially like:

https://www.youtube.com/watch?v=mX91_3GQqLY

CSC165 Implication/disjunction, mixed quantifiers, proof

Week #4

Implication/disjunction, mixed quantifiers, proof

I really enjoyed this week’s material. As Professor Heap pointed out, algebra comes into play when dealing with logic. Perhaps, thinking of the predicates as algebraic expressions, and of the logical operators as algebraic operators made it easier to understand the material. I realized that the key point for this part of the course is to understand the logic behind the concepts, instead of just learning by heart the properties.

In terms of tutorials, I found that the questions really tackled the use of logical operators (¬, ∧, ∨, ⇒, ⇔). By the way, I found an easier solution for one of the problems that I would like to show here.

Prove that ((P ⇒ Q) ⇒ R) ⇒ S is equivalent to (¬ R ∧ ¬ P) ∨ (¬ R ∧ Q) ∨ S

RHS ⇔ ¬ ((P ⇒ Q) ⇒ R) ∨ S ⇔

⇔ ¬ (¬ (P ⇒ Q) ∨ R) ∨ S ⇔

⇔ ¬ (¬ (¬ P ∨ Q) ∨ R) ∨ S ⇔

⇔ (¬ P ∨ Q) ∧ ¬ R) ∨ S ⇔

⇔ (¬ R ∧ ¬ P) ∨ (¬ R ∧ Q) ∨ S ⇔ LHS

Implication, DeMorgan’s laws and distributive law were applied in this exercise.

Something that may be tricky sometimes, is implication, especially when it involves a negation operator. One example of this is the following:

P ⇒ ¬ Q ⇔ ¬ P ∨ ¬ Q

In this case, we really need to know how the implication works because we could easily miss the negation. Something useful is to think about the rule we are going to use, see how it works, and then apply it.