What is discrete mathematics?

It is also known as Mathematics for computer science. Sometimes finite mathematics, or concrete mathematics.

Discrete mathematics is the study of numerable sets, it is distinct from others. – such as integers, graphs, and statements in logic.

• Numerable. From Latin numerābilis.
  • (mathematics) In one to one correspondence with the set of natural integers.

Collins Dictionary

Wiki

https://www.merriam-webster.com/dictionary/numerable

https://www.dictionary.com/browse/numerable?s=t

https://wikidiff.com/countable/numerable#:~:text=As adjectives the difference between,able to be counted%3B countable.

Discrete. "separate, distinct from others," late 14c., from Old French discret, discre, and directly from Latin discretus "separated;" see discreet. Related: Discretely; discreteness. https://www.etymonline.com/word/discrete

Resources

Requisites

• Minimum formal math.

• Logic.

Nice to have

• Calculus

• Coding skills

Foundations topics

• Philosophical logic and Philosophy of logic

• Set theory

  • Sets

• Mathematical logic

• Combinatorics

  • Combinations

  • Permutations

  • Partitions

• Graph theory

  Graphs

  Networks

• Number theory

  • Integers

  • Transcendental numbers

  • Diophantine approximation

  • p-adic analytics

  • Function fields

• Algebraic structures

  • Boolean algebra

  • Relational algebra

  • Algebraic coding theory

  • Formal languages

• Discretization

  • Numerical analysis

Applications

• Discrete calculus

  • Sequences

  • Recurrence relation

• Discrete probability

• Discrete geometry

  • Discrete collections

• Operations research

  • Linear programming

  • Optimization

  • Queuing theory

  • Scheduling theory

  • Network theory

  • Continous-time Markov process

• Game theory

  • Decision theory

  • Utility theory

  • Social choice theory

  • Game theory

• Topology

  • Combinatorial topology

  • Topological graph theory

• Information theory

  • Coding theory

  • Analog coding

  • Analog signals

  • Analog encryption

• Theoretical computer science

  • Automata theory

  • Formal languages

  • Computational geometry

Sets

Definitions

Level 1.

Collection. A group of objects of one type that have been collected by one person or in one place. Oxford dictionary.

Object. The objects are sometimes referred to as elements or members. Elements are unique.

Level 2.

Group. A number of people or things that are located close together or are considered or classed together. Oxford dictionary.

Level 3.

Number - The content of a statement of number is an assertion about a concept. [source: The Foundations of Arithmetic, §55, Engl.transl. page 67].

How to use sets?

$\text{TAG is the set of all elements such that element checks properties}$.

Finite sets. E.g. $A=\{\text{1,2,3,4}\}$

Either infinite or large finite sets. E.g. $A=\{x|x\text{ is positive, even integer} \}$

Number sets

Worked examples

• Show that $A=\{1\}\times \{1,2\}\subseteq B=\{1\}\times\{1,2,3\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  By inspection

  $A=\{(1,1),(1,2)\}$, $B=\{(1,1),(1,2),(1,3)\}$

  $A\subseteq B$ since every element of $A$ is an element of $B$.

• Show that $A=\{2n|n\in Z^+\}\subseteq B=\{n|n\in Z\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  Let $x\in A$, $x\in Z^+$ because $Z^+$ is closed under the operation
  of multiplication.
  $x\in Z$ since $Z^+\subseteq Z$ .

• Show that $A=\{1,2,3\}\nsubseteq B=\{\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  but $\{\}$ iff $\forall x.x \notin \{\}$, so the consequent always is $False$, hence $A\nsubseteq B$.

• Show that $A=\{1,2,3,4\}\nsubseteq B=\{n|n\in A \land n+m=8 \text{ for some } m\in C\}$, $C=\{5,6,7,8\}$

  By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$

  $1\in A \implies 1\notin B$, so $A\nsubseteq B$.

• What is the correct option $Z \in R$ or $Z \subset R?$

• In a group of students, each student is taking a mathematics course or a computer science course or both. One-fifth of those taking a mathematics course are also taking a computer
  science course, and one-eighth of those taking a computer science course are also taking a mathematics course. Are more than one-third of the students taking a mathematics course?
  

  $C:\text{computer science students}$, $M:\text{mathematics course students}$

  We know $\dfrac{|C\cap M|}{|C|}=\dfrac{1}{5}$, $\dfrac{|C\cap M|}{|M|}=\dfrac{1}{8}$ (1), but

  $|U|=|C\cup M|=|C|+|M|-|C\cap M|$

  $1=\dfrac{|C|}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|C\cap M|}{|U|}$ (2)

  By 1

  $\dfrac{1}{5}|C|=\dfrac{1}{8}|M|$

  $|C|=\dfrac{5}{8}|M|$

  We’ll substitute in (2)

  $1=\dfrac{5|M|/8}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|M|/8}{|U|}$

  $1=\dfrac{12|M|/8}{|U|}$

  $\dfrac{|M|}{|U|}=\dfrac{8}{12}=\dfrac{2}{3}\ge\dfrac{1}{3}$

• Let C be a circle and D be the set of all diameters of C. What is ∩ D? (Here, by “diameter” we mean a line segment through the center of the circle with its endpoints on the circumference
  of the circle.)
  

  If

  $D=\{\{p_{11},p_{12},p_{13},...,Center,...\},\{p_{21},p_{22},p_{23},...,Center,...\},\{p_{31},p_{32},p_{33},...,Center,...\},...\}$

  then

  $\cap D=\{Center\}$

• Let P denote the set of integers greater than 1 ($P=\{x|x\in Z\land x>1\}$). For i ≥ 2, define $X_i=\{ik|k\in P\}$. Describe $P-\bigcup_{i=2}^\infty X_i$.

  $$P-\bigcup_{i=2}^\infty X_i=\{2,3,4,...\}-\{2k|k\in P\}\cup\{3k|k\in P\}...\\ =\{2,3,4,...\}-\{4,6,8,10,12,...\}\cup\{6,9,12,15,...\}\cup\{8,12,16,20,...\}...$$

  $\bigcup_{i=2}^\infty X_i$ describes composite numbers since $X_i$ describes $i$ multiples, so

  $=P-\text{composite numbers}=\{x|(x\in Z \land x>1)\land x\notin\text{composite numbers} \}\\ =\text{prime numbers}$

The following exercise is from [1]

Let $A=\{i+{5 \choose i} |i\in \mathbb{Z} \land 0\le i \le 4\}$ and $B=\{3i|i\in\{1,2,4,5\}\}$.

• Evaluate $A\cap B$.

  What is the fastest way that you come up with a solution for three exercises? List all elements $A$ and $B$, and then apply them to the operations. You can find $5 \choose i$ with Pascal Triangle.

  $$A=\{0+{5 \choose 0},1+{5 \choose 1},2+{5 \choose 2},3+{5 \choose 3},4+{5 \choose 4}\}\\ =\{0+1,1+5,2+10,3+10,4+5\} \\ =\{1,6,12,13,9\}$$

  $$B=\{3,6,12,15\}$$

  So, $A\cap B= \{6,12\}$.

• Evaluate $|A\cup B|$

  $|A\cup B| =|A|+|B|-|A\cap B|=5+4-2=7$

• Evaluate $|A-B|$

  $|A-B|=|A|-|A\cap B|=5-2=3$

Mathematical logic

Key ideas

Logic is the basis of all reasoning.

Classical Propositional Logical

A proposition is a communicated declarative sentence that is either true or false, but not both. Remember structure no content.

• Don't use "preposition" as synonymous with "proposition". A preposition is a word such as 'by', 'for', 'into', or 'with' which usually has a noun group as its object. Collins.

• Other views of propositions. A proposition is the meaning expressed by statements.

• Some people use statements and propositions interchangeably.

• The following statements are propositions

  • $2+3=5$

  • $1+1=3$

  • P=NP This is either true or false (but not both), but you don't know.

  • for all $x\in R$, $x>0$ then $x^2>0$

  • Sun leaves tomorrow.

  • $\dfrac{d}{dx}e^x=e^x$

  • She loves him.

  • Whenever Juney barks, Ralph gets mad.

  💡

  Actually, whether sentence is a preposition while the sentence matches the definition.

• Moreover, the definition excludes statements such as

  • Read 'Cogito ergo sum' in Discourse on the Method. (command)

  • Let's go to the beach tomorrow. (proposal)

  • God'll help you! (exclamation)

  • $2+3=5?$ (question)

  • $P(x):=x+4=6$ (indeterminate declarative sentence). It's a predicate.

  • if $x>0$, then $x^2>0$

  • $f(x)=x^2$ (indeterminate declarative sentence)

  • This sentence is false. A paradox is not a statement.

You gonna use variables to represent prepositions, thus as you use letters in algebra. e.g.

The Connectives of Propositional Logic. In short, Logical formulas

Definition.

Let $p$ and $q$ be propositions.

Grammar

Perhaps you’ve never seen before this language formalization.

<S> := P | P is P | P are P
<Proposition> := <Proposition> and <Proposition>
<Proposition> := <Proposition> or <Proposition>
<Proposition> := <Proposition> xor <Proposition> | either <Proposition> or <Proposition>
<Proposition> := not <Proposition>
<Proposition> := <Proposition> => <Proposition>
<Proposition> := (<Proposition>)
<Proposition> := <p> | True | False

<p> is whatever string (including numbers) that doesn’t be a reserved word. In this grammar order is important, it indicates precedence order when they have the same precedence level they are equals.

Note that True and False are propositions. Either-or mean XOR. In Spanish, we can use “o … o …”.

Does "either-or " mean XOR or OR? (2022, December 13). Retrieved from https://math.stackexchange.com/questions/1906242/does-either-or-means-xor-or-or

When people claim something, it means they want it to be true.

Representations

Worked examples

• Write the negation of the proposition.
  • Ten heads were obtained when you flip 10 times a coin.

    $P(\text{flipped coin} )=\text{flipped coin is a head}$

    $\lnot P(\text{flipped coin} )=\text{flipped coin is a tail}$

    By Morgan Law

    $\lnot(\forall \text{flipped coin } P(\text{flipped coin} ))= \exists \text{flipped coin } \lnot P(\text{flipped coin})$

    In plain English, the following propositions are equivalent

    Ten heads were not obtained.

    Some flipped coins were not head.

    Some flipped coins were tail.

    At least one flipped coin was tail.

  • Some heads were obtained when you flip 10 times coin.

    $P(\text{flipped coin} )=\text{flipped coin is a head}$

    $\lnot P(\text{flipped coin} )=\text{flipped coin is a tail}$

    By Morgan Law

    $\lnot (\exists \text{flipped coin } P(\text{flipped coin}))= \forall\text{flipped coin } \lnot P(\text{flipped coin})$

    In plain English, the following propositions are equivalent

    At least one head was not obtained.

    Some heads were not obtained.

    All the flipped coins were not heads.

    No flipped coin was head.

    All the flipped coins were tail.

  • Some heads $H$ and some tails $T$ were obtained.

    The above proposition is equivalent to

    $U=\{x|x\in H \text{ or } x\in T\}$

    $H\cup T=U$ Because the flipped coins are either head or tail.

    $H\cap T=\empty$ Because the coin is either head or tail, but not both.

    So by complement law

    $H\cup T=T^\complement\cup T=U$

    The negation of the proposition is

    $U^\complement=\empty$ Since 0/1 laws.

  • At least one was obtained.

    No head was obtained.

    All the flipped coins were tails.

  • For some positive integer $n$, $19340=n\cdot 17$

    No positive integer $n$, $19340=n\cdot 17$

    All positive integers $n$, $19340\neq n\cdot 17$

  • Every even integer greater than 4 is the sum of two primes.

    Every even integer greater than 4 is not the sum of two primes.

    At least one integer greater than 4 is not the sum of two primes.

• Determine whether each is true or false.
  • $5<9$ and $9<7$

    $true\land false$

    $false$

  • $5<9$ and $9<7$ are not the case.

    $\lnot false=true$

  • $5<9$ or $5<7$ and $9<7$ are not the case.

    $true\lor whatever=true$

• Formulate the symbol expression in words using $p:\text{Lee takes computer science.}$ $q:\text{Lee takes mathematics.}$
  • $\lnot p$

    Lee doesn’t take computer science.

  • $p\lor\lnot q$

    Lee takes computer science or no mathematics.

  • $p\land q$

    Lee takes computer science and mathematics.

  • $p\land \lnot q$

    Lee takes computer science, but no mathematics.

  • $\lnot p\land \lnot q$

    Lee takes neither computer science nor mathematics.

• Formulate the symbolic expression in words using $p:\text{Today is Monday}$. $q:\text{It is raining.}$ $r:\text{It is hot.}$
  • $p\lor q$

    Today is Monday or raining.

  • $\lnot(p\lor q)\land r$

    Today is neither Monday nor raining, but it is hot.

  • $(p\land(q\lor r))\land(r\lor(q\lor p))$

    Today is Monday and it’s raining or hot, but it’s hot, raining, or Monday.

• At one time, the following ordinance was in effect in Naperville, Illinois: “It shall be unlawful for any person to keep more than three [3] dogs and three [3] cats upon his property within the city.” Was Charles Marko, who owned five dogs and no cats, in violation of the ordinance? Explain. https://www.chicagotribune.com/news/ct-xpm-1990-10-12-9003250777-story.html

  Yes.

  Informally, if you have five dogs, then you’re keeping more than three dogs.

  Formally $dogs,cats\in N$

  $is\_lawful(dogs,cats)=dogs\le3 \land cats\le3$

  $is\_lawful(5,0)=dogs\le3 \land cats\le3 =false\land true=false$

  Maybe Charles Marko thought government counts in total such that

  $is\_lawful(dogs,cats)=dogs+cats\le6$

  but his ordinance interpretation fails; the government doesn’t say it explicitly, and we don’t assume anything from the text.

  Although attorney argues that is possible to change $and$ to $or$, if you follow connectives of propositional strictly; it is a mistake.

  $is\_lawful(dogs,cats)=dogs\le3 \land cats\le3 \neq dogs\le3 \lor cats\le3$

• Is “A statement that is either true or false.” a statement?

  It is a statement.

Suppose that Smartphone A has 256 MB RAM and 32 GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions.

smartphone(a, ram(256), rom(32), cam(8)).
smartphone(b, ram(288), rom(64), cam(4)).
smartphone(c, ram(128), rom(32), cam(5)).

a) Smartphone B has the most RAM of these three smartphones.

? smartphone(b, ram(X), _, _), smartphone(Y, ram(Z), _, _), Y \= b, X > Z.
true

b) Smartphone C has more ROM or a higher resolution camera than Smartphone B.

? smartphone(c, _, rom(RomC), cam(CamC)), smartphone(b, _, rom(RomB),cam(CamB)), (RomC > RomB; CamC > CamB).
true

c) Smartphone B has more RAM, more ROM, and a higher resolution camera than Smartphone A.

d) If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera.

e) Smartphone A has more RAM than Smartphone B if and only if Smartphone B has more RAM than Smart-phone A.

Fuzyy logic.

happy(fred, 0.8).
happy(jonh, 0.4).

not(happy(_, Y), Z) :- Z is 1-Y.
and(happy(_, X), happy(_, Y), Z) :- Z is min(X,Y).

Lógica computacional, Enrique Paniagua Arís et al., Ed. Thomson, 2003.

Elementos de lógica formal, Calixto Badesa et al., Ed. Ariel, 2003.

Truth tables

• Created by Charles Sanders Peirce. Popularized by Ludwig Wittgenstein in his Tractatus Logico-Philosophicus.

See "truth"

Truth table generator

When you wish to provide a conclusion (or proof in mathematics), you must use chain statements throughout logical consequences (or connectives, methods, and pieces of evidence) from a base set of previous results – such as axioms, theorems, and definitions.

value judgment

Environment

A particular row or instance in the truth table is an environment, world, or model.

Natural Language into Formal Language. Natural Logic.

2

Argument

Arguing or proving something is not the same as explaining it. So, if you prove something, you are not saying anything noting how the result or proof is coming up. This difference is useful when you ask since sometimes you want to learn the underlying patterns or the process.

Rules of Inference

Worked examples

Formulate the following arguments symbolically and determine whether each is valid.

Let

p: I study hard.

q: I get A’s.

r: I get rich.

• If I study hard, then I get A’s. I study hard. Therefore, I get A’s.

  $p\implies q$

  $p$

  $\therefore q$

  It’s a valid argument because the argument uses the modus ponens.

• If I study hard, then I get A’s. If I don’t get rich, then I don’t get A’s. Therefore, I get rich.

  $p\implies q$

  $\lnot r\implies \lnot q$

  $\therefore r$

  From $\lnot r\implies \lnot q$ contrapositive, we may use Hypothetical syllogism to conclude $r$. Thus the conclusion $r$ follows from the hypotheses and the argument is valid.

  $p\implies q$

  $q \implies r$

  $\therefore r$

• I study hard if and only if I get rich. I get rich. Therefore, I study hard.

  Argument (I)

  $p\iff r$

  $r$

  $\therefore p$

  By Disjunctive syllogism

  $(p\implies r) \land (r\implies p)$

  $\lnot(p\implies r)$

  $\therefore r \implies p$

  By Modus ponens, (1) is valid

  $r \implies p$

  $r$

  $\therefore p$

• If I study hard or I get rich, then I get A’s. I Get A’s. Therefore, If I don’t study hard, then I get rich.

  The argument becomes

  $p\lor r \implies q$

  $q$

  $\therefore \lnot p \implies r$

  It’s invalid because $(p\lor r \implies q)\land q$ is equivalent $q$, and it’s not the conclusion.

• If I study hard, then I get A’s or I get rich. I don’t get A’s and I don’t get rich. Therefore, I don’t study hard.

  $p\implies q \lor r$

  $\lnot q \land \lnot r$

  $\therefore \lnot p$

  It’s a valid argument since modus tollens application

  $p\implies q \lor r$

  $\lnot (q \lor r) \implies \lnot p$

Notes

https://en.wikipedia.org/wiki/List_of_rules_of_inference

https://calcworkshop.com/logic/rules-inference/

http://logic.stanford.edu/intrologic/glossary/rule_of_inference.html

http://intrologic.stanford.edu/chapters/chapter_04.html

https://www.cs.sfu.ca/~ggbaker/zju/math/inference.html

Predicates

A predicate can be understood as a proposition whose truth depends on the value of one or more variables.

$x\in D, P(x)$: let x is in D, we claim $P(x)$

Example: $P(x)$

Quantifiers

$\forall x \in D, P(x)$ , for all x in D we claim $P(x)$

$\exists x$

Negation. The negation of $\forall x ,P(x)$ is that there exists at least one value for which the statement is not true.

Nested Quantifiers

Exercises

Formulate the leap year definition as a predicate. If you achieve this, you don’t need to nest “if” clauses in your program.

on every year that is evenly divisible by 4
  except every year that is evenly divisible by 100
    unless the year is also evenly divisible by 400

Predicate

$x\in Years, LeapYear(x) : x(\text{mod } 400)==0 \text{ or } (x(\text{mod } 4)==0 \text{ and } x(\text{mod } 100)!=0)$

The last rule has more priority, so if $x(\text{mod } 400)==0$ is true, $x$ is a leap year.

Proofs

Mathematical systems and the Axiomatic method

What is suitable proof?

Uninformative and informative proofs

Direct proofs

Proof by contradiction

Proofs of equivalence

Prove the Morgan Law with .

Problem Set

Proofs

What is the proof?

Proof. A finite sequence of statements (called well-formed formulas in the case of a formal language), each of which is a previous result -axiom, an assumption, experiments, or theorems- in the sequence by a rule of inference.

Axiom. Simple postulate or assumption based on a priori knowledge and free contradictions.

Theorems. Important true statements.

Lemma. Preliminary statements.

Corollary. Statements that follow a few logical steps from the theorem.

https://mathoverflow.net/questions/18352/theorem-versus-proposition

Writing code and mathematics

• State your game plan.

• Keep a linear flow.

• The proof is an essay, not a calculation.

• Avoid excessive symbolism.

• Revise and simplify.

• Introduce notation thoughtfully.

• Structure long proofs.

• Be wary of the “obvious.”

• Finish.

Notes

https://math.mit.edu/~poonen/papers/writing.pdf

Logical Verification 2019–2020. (2022, December 13). Retrieved from https://lean-forward.github.io/logical-verification/2019

Theorem Proving in Lean — Theorem Proving in Lean 3.23.0 documentation. (2021, October 02). Retrieved from https://leanprover.github.io/theorem_proving_in_lean

Natural number game. (2021, May 27). Retrieved from https://www.ma.imperial.ac.uk/~buzzard/xena/natural_number_game

Logic and Proof — Logic and Proof 3.18.4 documentation. (2021, December 04). Retrieved from https://avigad.github.io/logic_and_proof/index.html

Mathematical Writing by Knuth, Larrabee, and Roberts, https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf

Guide to Proofs, Stanford https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/handouts/070 Guide to Proofs.pdf

Proofwriting Checklist, Stanford https://web.stanford.edu/class/cs103/proofwriting_checklist

Some Remarks on Writing Mathematical Proofs by John M. Lee

https://www.youtube.com/watch?v=B0acu5nhG0w&ab_channel=StanfordOnline

https://math.stackexchange.com/questions/424854/1-0-by-integration-by-parts-of-tanx/424855#424855

Translating from English into Predicate Logic with Identity (Unit 10.1). (2015, February 17). Retrieved from https://dornsife.usc.edu/assets/sites/548/scripts/LogicWebExercises/bwr-exercises/unit10.1.html

Tammet, T. (2021, September 04). Logictools. Retrieved from https://logictools.org/index.html

Tree Proof Generator. (2022, December 13). Retrieved from https://www.umsu.de/trees

Most ambiguous and inconsistent phrases and notations in maths

What are some examples of notations and words in maths which have been overused or abused to the point of them being almost completely ambiguous when presented in new contexts? For instance, a fun...

https://math.stackexchange.com/questions/1024280/most-ambiguous-and-inconsistent-phrases-and-notations-in-maths

Methods

Direct proof

Worked examples

• Prove that for all integers m and n, if m and n are even, then m + n is even.

  Let $m,n \in \mathbb{Z}$ such that $m$ is even and $n$ is even, by even definition we know

  $2k_1=m$ and $2k_2=n$ where $k_1,k_2\in \mathbb{Z}$.

  So, $m+n=2k_1+2k_2=2(k_1+k_2)$ is even since $k_1+k_2\in Z$.

Proof by perfect induction o Proof by exhaustion

Proof of a Boolean theorem through perfect induction.

Simple induction

We know by Modus Ponens:

The principle of induction says

$\forall n P(n+1)$ use $\forall n P(n)$ when $\forall n P(n)\implies \forall n P(n+1)$ but the same to simple $P(n+1)$if always is true then $P(n)$ is always true.

Strong induction

https://www.youtube.com/watch?v=9w20J4j5-0Y&ab_channel=AtticPhilosophy

Worked example.

• $\forall n \text{ }n\in N \text{, } P(n):\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}$

  $$\text{Base case:}P(0):0 =0\\ \text{Inductive Hypothesis: Assume that }P(n):\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2} \text{ is true}\\ \text{Inductive step: We need to prove }P(n+1):\sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2}$$

  $$\forall n [\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}]\implies \\\forall n [\sum_{i=0}^{n+1}i=\\ \sum_{i=0}^{n}i+(n+1)=\\\dfrac{n(n+1)}{2}+(n+1) =\\ \dfrac{(n+1)(n+2)}{2} ]\\$$

  Therefore

  $$\forall n [\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}]\implies \forall n [\sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2} ]\\ \text{ iff } \sum_{i=0}^{n+1}i=\dfrac{(n+1)(n+2)}{2}$$

• $\forall n \text{ }n\in N \text{ }n>0 \text{, } P(n):n^3\le n^2$

  $$\text{Base case: }P(1):1\le1 \\ \text{Inductive Hypothesis: Assume that }P(n):n^3\le n^2 \text{ is true }\\ \text{Inductive step: We need to prove }P(n+1):(n+1)^3\le (n+1)^2$$

  Because $n^3\ge 0,1\ge1,3n^2\ge2n^2$, $3n\ge2 n$

  $$\forall n [n^3\le n^2]\implies \forall n [n^3+3n^2+3n+1\ge n^2+2n+1]\\ \implies \forall n [(n+1)^3\ge (n+1)^2]\\$$

  Our theorem is false since

  $$\forall n [n^3\le n^2] \implies \forall n [(n+1)^3\ge (n+1)^2]\\ \text{iff } (n+1)^3\le (n+1)^2$$

  our argument is always false.

• $\forall n \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=n!x^{k-n}$

  $$P(0):\dfrac{d^0}{dx^0}x^k=x^k\\ P(n):\dfrac{d^n}{dx^n}x^k=n!x^{k-n}\\ P(n+1):\dfrac{d^{n+1}}{dx^{n+1}}x^k=(n+1)!x^{k-(n+1)}\\ \dfrac{d^n}{dx^n}x^k=n!x^{k-n}\implies \\\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{d}{dx}\dfrac{d^{n}}{dx^{n}}x^k=\dfrac{d}{dx}(n!x^{k-n})=n!(k-n)x^{k-n-1}$$

  $$\forall n [\dfrac{d^n}{dx^n}x^k=n!x^{k-n}] \implies \forall n [\dfrac{d^{n+1}}{dx^{n+1}}x^k=n!(k-n)x^{k-n-1} ]\\ \text{iff } \dfrac{d^{n+1}}{dx^{n+1}}x^k=(n+1)!x^{k-(n+1)}$$

  Our argument is valid, but it is always false.

• $\forall n,k, \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}$

  $$P(0):\dfrac{d^0}{dx^0}x^k=\dfrac{k!}{(k-0)!}x^k=x^k\\ P(n):\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}\\ P(n+1):\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}\\ \dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}\implies \\\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{d}{dx}\dfrac{d^{n}}{dx^{n}}x^k=\dfrac{d}{dx}\dfrac{k!}{(k-n)!}x^{k-n}=\dfrac{k!}{(k-n)!}(k-n)x^{k-(n+1)}=\\\dfrac{k!}{(k-n)(k-n-1)!}(k-n)x^{k-(n+1)}=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}$$

  As

  $$\forall n [\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}] \implies \forall n [\dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}]\\ \text{iff } \dfrac{d^{n+1}}{dx^{n+1}}x^k=\dfrac{k!}{(k-(n+1))!}x^{k-(n+1)}$$

  Our argument is valid and it happen be always true.

https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf

https://math.stackexchange.com/questions/2926239/when-we-can-use-mathematical-induction-and-when-we-cant

https://www.purplemath.com/modules/inductn2.htm

Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction

https://www.youtube.com/watch?v=z7QCT8cgsR4&ab_channel=FrankStajanoExplains

Zermelo-Fraenkel Axioms

Our Axioms

Mathematical data types

Symbols

$=$ vs $::=$

FAQ

Is a definition a proposition?

Please Explain Kuratowski Definition of Ordered Pairs. (2022, December 22). Retrieved from https://math.stackexchange.com/questions/1767604/please-explain-kuratowski-definition-of-ordered-pairs

Why would definition not be proposition? (2022, December 22). Retrieved from https://philosophy.stackexchange.com/questions/1074/why-would-definition-not-be-proposition

What is the difference between proofs and arguments?

What's the difference between an argument and proof? (2022, December 22). Retrieved from https://www.quora.com/Whats-the-difference-between-an-argument-and-proof

How do I know if my mathematical proof is actually a proof or just a convincing argument? (2022, December 22). Retrieved from https://www.quora.com/How-do-I-know-if-my-mathematical-proof-is-actually-a-proof-or-just-a-convincing-argument

Counting

Counting is finding the finite set’s cardinality. We prefer reasoning over enumerate the set.

Foundations rules

The sum rule.

If two sets are disjoint, $|A\cup B|=|A|+|B|$

The product rule.

$|X\times Y|=|X||Y|$

Cardinality Rules

The Bijection Rule

Bijection := one-to-one correspondence

Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

What does it mean to write |A| = n?

It means that there is a bijection f : A → {1, . . . , n}

MIT OpenCourseWare. 2016. 3.3.3 Counting with Bijections: Video. YouTube. Retrieved May 25, 2021 from https://www.youtube.com/watch?v=n0lce1dMAh8‌

The Bijection Rule or Equinumerosity

Let S and T be two finite sets. If there exists one-to-one correspondence (or bijection) between them, from S to T, if and only if $|S|=|T|$ i.e. S and T have the same number of elements. This is taken as the definition.

https://www.cs.colostate.edu/~cs220/summer19/slides/16_bijection_rule.pdf

Counting Sequences

Multiplication Principle or Product Rule

$P_1\times P_2\times ... \times P_n=\{(p_1,p_2,...p_n)|p_1\in P_1,p_2 \in P_2,...,p_n\in P_n\}=\text{all sequences}$ called Cartesian product.

Thus, if $P_1,P_2,\cdots ,P_n$ are finite sets, then

For example, if $A=\{x,y,z\}$ and $B=\{1,2,3\}$

$A\times B=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)\}$

$|A\times B|=|A|\cdot|B|=3 \cdot 3=9$

Key ideas

• When we're counting since cardinality $|A|$ is more important than the set $A=\{a_0,a_1,...,a_n\}$. We will ignore writing it.

• No decision might be part b of the set. When your problem says about optional something. $A=\{a_0,a_1,...,a_n,noA\}$

• If repetitions are allowed, $|A|^{repetitions}$

• If repetitions are not allowed, You'd remove the last used element such that $|A|\cdot(|A|-1)\cdot(|A|-2)...$

• $|U|=|A|+|A^c|$

Product Rule Worked examples

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer and one beverage?

  $|Appetizers|=2$, $|Beverages|=4$

  $|Dinners|=2\cdot4=8$

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of an optional appetizer, one main course, and an optional beverage?

  $|Main\text{ } courses|=3$

  $|optional \text{ } appetizers|=|appetizers|+|no\text{ }appetizer|=2+1=3$

  $|optional \text{ }bevarages|=|bevarages|+|no \text{ }bevarage|=4+1=5$

  $|Dinners|=|main\text{ } courses| \cdot |optional \text{ } appetizers| \cdot |optional \text{ }bevarages|=3\cdot3\cdot5=45$

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer, one main course, and an optional beverage?

  $|Main\text{ } courses|=3,$$|Appetizers|=2,$ $|Beverages|=5$

  $|Dinners|=3\cdot2\cdot5=30$

• A man has eight shirts, four pairs of pants, and five pairs of shoes. How many different outfits are possible?

  $Outfit=\{(shirt,pair\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes)|shirt\in Shirts,pair\text{ } of\text{ }pants \in Pairs\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes \in Pair\text{ } of\text{ }shoes\}$

  $|Shirts|=8$, $|Pairs\text{ } of\text{ }pants|=4$ and, $|Pairs\text{ } of\text{ }shoes|=8$

  $|Outfit|=|Shirts|\cdot|Pairs\text{ } of\text{ }pants|\cdot |Pairs\text{ } of\text{ }shoes|=8\cdot 4\cdot5=160$