-- ============================================================
-- Homework 7
--
-- Math 4680/5680, "Topics in Logic and Computation"
-- Fall 2026
--
-- Due: November 17, 2026
--
-- Group members (up to 3):
--
-- _______________________
--
-- _______________________
--
-- _______________________
--
-- ============================================================
-- Do not use AI to do this homework. You may use AI to teach you
-- things, but not to do the homework for you.
--
-- ============================================================

import Mathlib

set_option linter.style.header false
set_option autoImplicit false
set_option linter.unusedVariables false

namespace Homework7

-- This homework is mainly about practicing tactics
-- (and a few other things). Many of the problems can
-- be solved by using a single-line automated tactic
-- from the following list:
--
--   `rfl`        - equal by computation
--   `decide`     - decidable propositions, small search space
--   `omega`      - linear arithmetic on `Nat` and `Int`
--   `norm_num`   - numerical computation (numbers, no variables)
--   `simp`       - rewriting with lots of lemmas
--   `exact?`     - the library already has the lemma; find it
--   `ring`       - identities in a commutative ring
--   `linarith`   - linear arithmetic over ordered fields
--   `nlinarith`  - some nonlinear arithmetic, usually with hints
--   `field_simp` - clear denominators
--   `positivity` - prove `0 < x`, `0 ≤ x`, or `x ≠ 0`
--
-- The other tactics:
--
--   Lecture 13: `exact`, `assumption`, `intro`, `apply`, `apply?`,
--               `constructor`, `obtain`, `left`, `right`, `rcases`,
--               `rw`, and `#print` to see the proof term a tactic
--               proof built
--   Lecture 14: `exact ⟨_, _⟩` and `use` for `∃`, `contradiction`,
--               `rw [lemma args]`, `rw ... at h`
--   Lecture 15: `simp?`, `simp only`, `induction`, `cases`, `have`,
--               `calc`, `rintro`, `refine`, `specialize`,
--               `by_cases`, `by_contra`, `push Not`, and the
--               combinators `<;>`, `try`, `repeat`,
--               `first | _ | _`, `all_goals`
--   Lecture 16: `simp [h]`, `field_simp at h`, `contrapose`

-- ============================================================
-- 1. [Foundations]

example (x : ℝ) : (x - 1) * (x^2 + x + 1) = x^3 - 1 := by
  sorry

-- ============================================================
-- 2. [Foundations] Prove this by asking Lean to
-- suggest a lemma, then paste in the Lemma Lean
-- suggested.
example (A B : Set ℕ) : A ∩ (A ∪ B) = A := by
  sorry

-- ============================================================
-- 3. [Foundations] This is a tautology of classical
-- logic, but not of intuitionistic logic.

example (p q : Prop) (h : p → q) : ¬p ∨ q := by
  sorry

-- ============================================================
-- 4. [Foundations] Note that `Fin 6` is a finite type, so a
-- statement quantified over all of it is still a finite check.

example : ∀ n : Fin 6, n.val * n.val ≤ 25 := by
  sorry

-- ============================================================
-- 5. [Foundations] This one is a named theorem in the library. Find
-- it rather than proving it.

example (a b : ℝ) : |a| - |b| ≤ |a + b| := by
  sorry

-- ============================================================
-- 6. [Foundations] Two problems in which the goal is fine as it is,
-- and it is a *hypothesis* that needs work.

-- 6.1 Rewrite `h` until it is literally the goal. Note that a
-- rewrite with a bare `Nat.add_comm` does not do what you want: try
-- it, and look at what it did. Then fix it.

example (f : ℕ → ℕ) (a b c : ℕ) (h : f (a + (b + c)) = 10) :
    f (a + (c + b)) = 10 := by
  sorry

-- 6.2 This time it is the division in `h1` that is in the way.

example (x y : ℝ) (hy : y ≠ 0) (h1 : x / y = 3) (h2 : x + y = 8) : y = 2 := by
  sorry

-- ============================================================
-- 7. [Foundations]

example (f : ℕ → ℕ) : id ∘ f = f := by
  sorry

-- ============================================================
-- 8. [Proficiency] The arithmetic at the end is easy, but no
-- arithmetic tactic will instantiate the `∀` in `h` for you. Get the
-- two instances of `h` you need into the context first. (There is a
-- catch if you do this the obvious way.)

example (f : ℕ → ℕ) (h : ∀ n, f n ≤ n) : f 3 + f 5 ≤ 8 := by
  sorry

-- ============================================================
-- 9. [Foundations]

example (a b : ℤ) (h1 : a % 2 = 1) (h2 : b % 2 = 1) : (a + b) % 2 = 0 := by
  sorry

-- ============================================================
-- 10. [Proficiency] A natural number is either `0` or a successor.
-- Here, one of those two cases is impossible, and the other needs a
-- witness.

example (n : ℕ) (h : n ≠ 0) : ∃ k, n = k + 1 := by
  sorry

-- ============================================================
-- 11. [Proficiency] Naming conventions.
--
-- Each line below is the statement of a Mathlib lemma. Using the
-- conventions from Lecture 16, guess its name and write your guess
-- in the blank. Then check your guess by filling it into one of the
-- `#check` commands below and seeing whether Lean recognizes it.
--
-- Guess first, and write down your guess even when it turns out to
-- be wrong. A reasonable wrong guess is worth as much as a right one
-- here; what we want to see is that you can read the conventions.
--
--   11.1  a ≤ b → c ≤ d → a + c ≤ b + d        ________________
--   11.2  0 ≤ a - b ↔ b ≤ a                    ________________
--   11.3  a < b → a ≤ b                        ________________
--   11.4  0 ≤ a → |a| = a                      ________________
--   11.5  a * b = b * a                        ________________
--   11.6  b < a → a ≠ b                        ________________
--   11.7  min a b ≤ a                          ________________
--   11.8  0 < a → 0 < b → 0 < a * b            ________________

-- Uncomment and fill in:
-- #check @
-- #check @
-- #check @
-- #check @
-- #check @
-- #check @
-- #check @
-- #check @

-- ============================================================
-- 12. [Foundations] The hypothesis `h` is not in the library, so you
-- will have to hand it to the tactic yourself.
--
-- Prove this twice: once with a single automation tactic, and once
-- using only `rw` -- but without writing the same rewrite more than
-- once.

example (f : ℕ → ℕ) (h : ∀ x, f x = 2 * x) : f (f 1) = 4 := by
  sorry

example (f : ℕ → ℕ) (h : ∀ x, f x = 2 * x) : f (f 1) = 4 := by
  sorry

-- ============================================================
-- 13. [Proficiency] Try `decide` on this first, and see what
-- happens. Then find a tactic that does work, and in a comment say
-- in one sentence what the difference between the two is.

example : Nat.Prime 104729 := by
  sorry

-- ============================================================
-- 14. [Proficiency] Prove this theorem. Use `constructor` to split
-- the `↔`, and then exactly one `rintro` in each direction to take
-- the hypothesis apart completely; after that, each remaining case
-- should be a one-liner.
--
-- Then `#print` the theorem, and find in the printed proof term the
-- places where your two `rintro` patterns took apart an `∧` and an
-- `∨`. (Nothing to write; just look.)

theorem and_or_distrib (p q r : Prop) : (p ∨ q) ∧ r ↔ (p ∧ r) ∨ (q ∧ r) := by
  sorry

-- #print and_or_distrib

-- ============================================================
-- 15. [Proficiency] `linarith` will not use a hypothesis of the form
-- `a ≠ b`. Turn the problem around so that the `≠` becomes the goal
-- instead, and then it is easy. (For an example, see the
-- section on `field_simp` in Lecture 16.)

example (x : ℝ) (h : x^2 ≠ 1) : x ≠ 1 := by
  sorry

-- ============================================================
-- 16. [Proficiency] This is a one-liner, but write it as a `calc`
-- chain instead: `a ≤ 2 * b ≤ 2 * 3 = 6`. The point is to practise
-- the syntax, and to notice that the three steps want three
-- different justifications.

example (a b : ℝ) (h1 : a ≤ 2 * b) (h2 : b ≤ 3) : a ≤ 6 := by
  sorry

-- ============================================================
-- 17. [Proficiency] Three goals in one, each wanting a different
-- tactic. Split the goal into its three conjuncts with a single
-- `refine` with holes. Then finish the proof in two different ways:
--
--   (a) in the same line, with `<;>` and a combinator that tries
--       several tactics in turn;
--   (b) on separate lines: first apply one tactic to every goal,
--       ignoring the goals where it fails, and then finish what is
--       left.

example (x : ℝ) (hx : 0 < x) : 0 < x ∧ x ≤ x + 1 ∧ 0 ≤ x^2 + 1 := by
  sorry

example (x : ℝ) (hx : 0 < x) : 0 < x ∧ x ≤ x + 1 ∧ 0 ≤ x^2 + 1 := by
  sorry

-- ============================================================
-- 18. [Proficiency] This will not go through on the bare tactic. It
-- needs one extra fact thrown into the pot, of the form
-- `sq_nonneg (? - ?)`. Your job is to find which square.

example (a b : ℝ) (ha : 0 < a) (hb : 0 < b) (h : a * b = 1) : a + b ≥ 2 := by
  sorry

-- ============================================================
-- 19. [Proficiency] In class, we proved a theorem
-- about the sum of the first `n` odd numbers. The
-- following is about the sum of the first `n` even
-- numbers.

example (n : ℕ) : ∑ i ∈ Finset.range n, (2 * i) = n*(n-1) := by
  sorry

-- ============================================================
-- 20. [Proficiency] Why does the tactic fail?
--
-- Each of the four statements below is true, and in each case the
-- commented-out line is a plausible first attempt that does *not*
-- work. For each one:
--
--   (a) uncomment the attempt and look at the error;
--   (b) comment it out again, and explain in the space provided why
--       that tactic cannot do this goal -- not "it failed", but what
--       about the goal puts it outside that tactic's fragment;
--   (c) prove the statement with a tactic that does work.

-- 20.1
-- example (x y : ℝ) : (x + y)^2 ≥ 0 := by linarith
--
-- WHY IT FAILS:
--
--
example (x y : ℝ) : (x + y)^2 ≥ 0 := by
  sorry

-- 20.2
-- example : (2 : ℝ) + 2 = 4 := by decide
--
-- WHY IT FAILS:
--
--
example : (2 : ℝ) + 2 = 4 := by
  sorry

-- 20.3
-- example (x : ℝ) (h : 2 * x = 6) : x = 3 := by omega
--
-- WHY IT FAILS:
--
--
example (x : ℝ) (h : 2 * x = 6) : x = 3 := by
  sorry

-- 20.4
-- example (x y : ℝ) (h : x ≤ y) : x + 1 ≤ y + 1 := by ring
--
-- WHY IT FAILS:
--
--
example (x y : ℝ) (h : x ≤ y) : x + 1 ≤ y + 1 := by
  sorry

-- ============================================================
-- 21. [Mastery] A step that occurs constantly in analysis: a number
-- that is below every positive number is not positive. No tactic
-- does this directly. Suppose the conclusion is false, and then pick
-- a suitable `ε` to get a contradiction. (Expect three or four
-- lines.)

example (x : ℝ) (h : ∀ ε > 0, x ≤ ε) : x ≤ 0 := by
  sorry

-- ============================================================
-- 22. [Mastery] No single tactic does this one. Here is the skeleton
-- of a proof that works; fill it in.
--
--   rw [ge_iff_le, ← sub_nonneg]     -- goal becomes `0 ≤ x + 1/x - 2`
--   have key : x + 1/x - 2 = ?       -- rewrite it as a single fraction
--   rw [key]
--   positivity
--
-- The missing step is to see that `x + 1/x - 2` is equal to
-- `(x - 1)^2 / x`, which `positivity` can then handle on sight.
-- Prove the `have` by clearing denominators and then doing the
-- algebra.
--
-- Having done that, say in a comment why `nlinarith [sq_nonneg (x -
-- 1)]` is *not* enough here, even though problem 18 had the same
-- shape. (Look at where the division is.)

example (x : ℝ) (hx : 0 < x) : x + 1 / x ≥ 2 := by
  sorry

-- ============================================================
-- 23. [Mastery] This one *is* a one-liner, but it needs three hints
-- rather than one. Note also that there are no positivity
-- assumptions: the statement holds for all reals, including negative
-- ones.

example (a b c : ℝ) : a^2 + b^2 + c^2 ≥ a * b + b * c + c * a := by
  sorry

-- ============================================================
-- 24. Structures and type classes (Lectures 11 and 12).
--
-- Here is a structure for rectangles. Both fields have default
-- values. (`deriving Repr` lets `#eval` print rectangles.)

structure Rect where
  width : ℕ := 1
  height : ℕ := 1
  deriving Repr

-- 24.1 [Foundations] Define the following three rectangles. Do not
-- use `Rect.mk` or the anonymous constructor `⟨_, _⟩`, and specify
-- as few fields as possible.
--
--   `unitSquare` is 1 × 1;
--   `wide` is 5 × 1;
--   `tall` is like `wide`, except that its height is 7. Define it
--   in terms of `wide`.

def unitSquare : Rect := sorry
def wide : Rect := sorry
def tall : Rect := sorry

-- #eval tall    -- should print { width := 5, height := 7 }

-- 24.2 [Foundations] Define the area of a rectangle by
-- pattern matching directly on the record notation
-- `{ width := _, height := _ }`.

def Rect.area : Rect → ℕ := sorry

-- 24.3 [Proficiency] Here is a type class for things
-- that have an area.

class HasArea (α : Type) where
  area : α → ℕ

open HasArea

-- Give three instances: rectangles have their usual area; a pair
-- has the sum of the areas of its components; and a list has the
-- sum of the areas of its elements.

instance : HasArea Rect where
  area := sorry

instance {α β : Type} [HasArea α] [HasArea β] : HasArea (α × β) where
  area := sorry

instance {α : Type} [HasArea α] : HasArea (List α) where
  area := sorry

-- Now this should be provable by a one-liner. (Which tactic?)

example : area (wide, [tall, unitSquare]) = 41 := by
  sorry

-- 24.4 [Proficiency] Uncomment the following two
-- lines. The first one asks Lean which instance it
-- uses for `HasArea (Rect × List Rect)`; the second
-- one fails. In a comment, explain what Lean was
-- trying to do for the second line, and why it could
-- not.

-- #synth HasArea (Rect × List Rect)
-- #eval area (wide, "hello")

-- ============================================================
-- 25. Decidability (Lecture 14).
--

#print Decidable

-- In this problem, you can pretend that `Decidable p` in Lean's
-- library is defined like `DecidableX` in `Attempt2` of Lecture 14,
-- with functions
--
--   `isTrue : p → Decidable p`  and  `isFalse : ¬p → Decidable p`,
--
-- While the actual underlying definition of `Decidable` has changed
-- in a recent Lean version, the mechanism described in class still
-- works. Recall that the `decide` tactic works on a proposition `p`
-- whenever it can find an instance of `Decidable p`.

-- 25.1 [Foundations] Define a `Decidable` instance for the following
-- predicate. Then use `decide` to prove the two examples.
--
-- Hint: equality on `ℕ` is already decidable. The function
-- `Nat.decEq a b : Decidable (a = b)` decides it, and you can
-- `match` on its result, just as Lecture 14 matched on `is_even n`.

def IsSquare (r : Rect) : Prop := r.width = r.height

instance (r : Rect) : Decidable (IsSquare r) := sorry

example : IsSquare { width := 4, height := 4 } := by
  sorry

example : ¬ IsSquare tall := by
  sorry

-- 25.2 [Mastery] Here is an inductive predicate for divisibility by
-- 3. Write a decision procedure for it, in the style of `is_even` in
-- `Attempt2` of Lecture 14, and make it into an instance. First
-- prove the three helper lemmas; you will need them. Then the two
-- examples at the end should go through by `decide`.

inductive Div3 : ℕ → Prop where
  | zero : Div3 0
  | step : ∀ {n}, Div3 n → Div3 (n + 3)

theorem not_div3_one : ¬ Div3 1 := sorry
theorem not_div3_two : ¬ Div3 2 := sorry
theorem div3_of_step {n : ℕ} : Div3 (n + 3) → Div3 n := sorry

def div3Dec : (n : ℕ) → Decidable (Div3 n) := sorry

instance (n : ℕ) : Decidable (Div3 n) := div3Dec n

example : Div3 27 := by
  sorry

example : ¬ Div3 100 := by
  sorry

-- 25.3 [Proficiency] Two questions; answer each in a comment.
--
--   (a) `decide` proved problem 4, which is about all `n : Fin 6`.
--       Why can it not prove `∀ n : ℕ, Div3 (3 * n)`?
--
--   (b) In `Attempt1` of Lecture 14, we could accidentally write a
--       wrong decider `is_evil`, and Lean did not notice. Could you
--       write a `div3Dec` that compiles (without `sorry`) but gives
--       the wrong answer for some `n`? Why or why not?

end Homework7
