Math MSC 0 Logic

0.
Logic
Mathematics for Economists
Francesc Dilmé
University of Bonn
1 / 15
Logic, notation
I These slides are far from complete (see SB A1.3, dlF 1.2).
I Some more complete notes on how to write proofs and
first-order logic are:
I https://web.stanford.edu/class/archive/cs/cs103/cs103.1202/
I https://math.berkeley.edu/~hutching/teach/proofs.pdf
I http://math.loyola.edu/~loberbro/ma421/BasicProofs.pdf
I https://sites.millersville.edu/bikenaga/math-proof/math-proof-notes.html
I https://www.birmingham.ac.uk/Documents/college-eps/college/stem/
Student-Summer-Education-Internships/Proof-and-Reasoning.pdf
I Formal languages and computer-verified proofs: http://www.cs.ru.nl/~freek/100/#1
2 / 15
Logic, notation
I ∈ : “belongs to” or “is in” (∈

/ is “does not belong”).
I ∃ (∃!) : there exists (a unique) (@ is “does not exist”).
I ∀ : for all.
I | or “s.t.” : such that.
I Basic Greek letters: alpha (α), beta (β), delta (δ), epsilon
(ε, ε), gamma (γ), kappa (κ), lambda (λ), mu (µ), nu (ν),
omega (ω), phi (φ, φ), pi (π), psi (ψ), rho (ρ), sigma (σ ), tau
(τ) and theta (θ). Also Delta (∆), Gamma (Γ), Omega (Ω),
Pi (Π), Phi (Φ), Psi (Ψ), Sigma (Σ) and Theta (Θ).
3 / 15
Logic, statements
I A statement p is a claim that some fact is true.

I Ex.: p = “2 is bigger than 1” or “there are infinite prime
numbers”.
I The claim itself is either True or False.
I ¬p is the negation of p: If p is True then ¬p is False, if p

is False then ¬p is True.
I Note: ¬(¬p) = p.
I It is an example of a logical operator, which transform

(groups of) statements into (new) statements.
4 / 15
Logic, properties
I A statement p may depend on some variable x (that
belongs to some collection of relevant elements X ).
I In this case p is called a property.
I Ex.: p(x) = “x is greater or equal than 1”.
I p or p(·) denotes the generic property.

I It is not True or False until it is evaluated at some x.
I p(x) denotes the generic property evaluated at some x.

I It is True or False, depending on x.
I If p(x) is True then “x has the property p”.
I Ex.: p(2) is True, but p(0) is False.
5 / 15
Logic, quantifiers
I The symbol ∀ is a shorthand for “for all”.

I Given a property p the statement q = “∀x p(x)00 is True if
there is no x ∈ X such that p(x) is False.
I Phrases: “for all/any x ∈ X ”, “every x ∈ X ”, “given/take
x ∈ X ”, “if x ∈ X then”, “whenever x ∈ X ”,...
I The symbol ∃ is a shorthand for “exists” or “there is”.

I Given a property p the statement q = “∃x s.t. p(x)00 is True
if there is x ∈ X such that p(x) is True.
I Phrases: “there exists x ∈ X ”, “x ∈ X exists”, “for some
x ∈ X ”,...
6 / 15
Logic, quantifiers
I Let p(·) be a property. In this case

I If q = “∀x p(x)00 then ¬q = “∃x s.t. ¬p(x)00 .
I If q = “∃x s.t. p(x)00 then ¬q = “∀x ¬p(x)00 .
I Let p(·, ·) be a property. In this case

I If q = “∀x∀y p(x, y )00 then ¬q = “∃x s.t. ∃y s.t. ¬p(x, y )00 .
I If q = “∀x∃y s.t. p(x, y )00 then ¬q = “∃x s.t. ∀y ¬p(x, y )00 .
I If q = “∃x s.t. ∀y p(x, y )00 then ¬q = “∀x∃y s.t. ¬p(x, y )00 .
I If q = “∃x s.t. ∃y s.t p(x, y )00 then ¬q = “∀x∀y ¬p(x, y )00 .
7 / 15
Logic, conditions
I A property p is a necessary condition for another

property q if, for all x, q(x) is True only if p(x) is True.
I “q only if p”, or “p ⇐ q”.
I “for all x, q(x) is True only if p(x) is also True.”
I also: “for all x, if q(x) is True then p(x) is also True.”
I Ex.: p(x) = “x is positive”, q(x) = “x is greater than 2”.
I Note: Necessary conditions are useful to prove that x

does NOT satisfy some property q(x). Indeed, if p(x) is
False then q(x) is False.
8 / 15
Logic, conditions
I A property p is a sufficient condition for another property

q if, for all x, q(x) is True when p(x) is True.
I “if p then q”, or “p implies q” or “p ⇒ q”.
I “for all x, if p(x) is True then q(x) is also True.”
I Ex.: p(x) = “x is divisible by 4”, q(x) = “x is divisible by 2”.
I Note: Sufficient conditions are useful to prove that x

satisfies some property q(x). Indeed, if p(x) is True then
q(x) is True.
9 / 15
Logic, conditions
I A property p which is necessary and sufficient condition

for q is also denoted as:
I “p if and only if q”, or “p iff q”, or “p ⇔ q”, or “p is
equivalent to q”.
I Ex.: p(x) = “x is even”, q(x) = “x’s last digit is even”.
I Note: Necessary and sufficient conditions are useful to

characterize x that satisfy some property q(x). Indeed, if
p(x) is True (False) then q(x) is True (False).
10 / 15
Logic, conditions
I Note that ⇒ (and ⇐) is a logical operator.

I True ⇒ True is True.

I True ⇒ False is False.
I if p is True and p ⇒ q is True then q is True.

I False ⇒ True is True (this is the least obvious).

I False ⇒ False is True.
I if q is False and p ⇒ q is True then p is False.
I Note: (p ⇒ q) ⇔ (¬q ⇒ ¬p).
11 / 15
Logic, and & or
I “and”, “∧” or “&” denote logical conjunction.

I p ∧ q is True if and only if both are True.
I Ex.: Note that p ⇔ q is equivalent to [(p ⇒ q) ∧ (p ⇐ q)].
I “or” or “∨” denote logical disjunction.

I p ∨ q is True if and only if at least one of them is True.
I Ex.: p ∨ ¬p is always True while p ∧ ¬p is always False.
I De Morgan’s law: ¬(p∧q) ⇔ ¬p∨¬q and ¬(p∨q) ⇔ ¬p∧¬q.
I Note: (p ⇒ q) ⇔ ¬p ∨ q.
12 / 15
Logic, definitions
I Necessary and sufficient conditions are commonly used to

make definitions.
I Ex.: “x is even if(f) x is divisible by 2”.1
I ≡ denotes “equal by definition” (also , or :=).
1
We will use “if” for definitions, even though some people prefer “iff”.
13 / 15
Logic, proofs
I Direct proof (deductive method): Prove that if x satisfies
some property, then it satisfies another property.
I Find a sequence of implications leading to the result.
I Proof by contradiction: Prove that a statement is true.

I Assume the contrary of the statement and show that this
leads to some fact known to be false.
I Proof by contrapositive: Prove that if x satisfies a
property p then it satisfies another property q.
I Assume there is y that satisfies p and ¬q and then reach a
contradiction.
I Proof by example (or counterexample): Prove that there
exists x satisfying some property.
I Find y that satisfies the property.
14 / 15
Logic, proofs
I Tips: Assume that x, y , z are (real) numbers. Then:

I z + x = z + y ⇔ x = y.

I zx =zy ⇔ x = y or z = 0 .

I x2 = y2 ⇔ x = y or x = −y .
I z + x ≥ z + y ⇔ x ≥ y.

I z x ≥ z y and z > 0 ⇒ x ≥ y .

I z x ≥ z y and z < 0 ⇒ x ≤ y .
15 / 15

Math MSC 0 Logic

Uploaded by

Copyright:

Available Formats

Math MSC 0 Logic

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Math MSC 0 Logic

Uploaded by

Copyright:

Available Formats

0.

I ∈ : “belongs to” or “is in” (∈

I ∃ (∃!) : there exists (a unique) (@ is “does not exist”).

I | or “s.t.” : such that.

I A statement p is a claim that some fact is true.

I ¬p is the negation of p: If p is True then ¬p is False, if p

I It is an example of a logical operator, which transform

I Ex.: p(x) = “x is greater or equal than 1”.

I p or p(·) denotes the generic property.

I p(x) denotes the generic property evaluated at some x.

I If p(x) is True then “x has the property p”.

I Ex.: p(2) is True, but p(0) is False.

I The symbol ∀ is a shorthand for “for all”.

I The symbol ∃ is a shorthand for “exists” or “there is”.

I Let p(·) be a property. In this case

I If q = “∃x s.t. p(x)00 then ¬q = “∀x ¬p(x)00 .

I Let p(·, ·) be a property. In this case

I If q = “∀x∃y s.t. p(x, y )00 then ¬q = “∃x s.t. ∀y ¬p(x, y )00 .

I If q = “∃x s.t. ∀y p(x, y )00 then ¬q = “∀x∃y s.t. ¬p(x, y )00 .

I If q = “∃x s.t. ∃y s.t p(x, y )00 then ¬q = “∀x∀y ¬p(x, y )00 .

I A property p is a necessary condition for another

I “for all x, q(x) is True only if p(x) is also True.”

I also: “for all x, if q(x) is True then p(x) is also True.”

I Ex.: p(x) = “x is positive”, q(x) = “x is greater than 2”.

I Note: Necessary conditions are useful to prove that x

I A property p is a sufficient condition for another property

I “for all x, if p(x) is True then q(x) is also True.”

I Ex.: p(x) = “x is divisible by 4”, q(x) = “x is divisible by 2”.

I Note: Sufficient conditions are useful to prove that x

I A property p which is necessary and sufficient condition

I Note: Necessary and sufficient conditions are useful to

I Note that ⇒ (and ⇐) is a logical operator.

I Note: (p ⇒ q) ⇔ (¬q ⇒ ¬p).

I “and”, “∧” or “&” denote logical conjunction.

I Ex.: Note that p ⇔ q is equivalent to [(p ⇒ q) ∧ (p ⇐ q)].

I “or” or “∨” denote logical disjunction.

I Ex.: p ∨ ¬p is always True while p ∧ ¬p is always False.

I De Morgan’s law: ¬(p∧q) ⇔ ¬p∨¬q and ¬(p∨q) ⇔ ¬p∧¬q.

I Necessary and sufficient conditions are commonly used to

I ≡ denotes “equal by definition” (also , or :=).

I Proof by contradiction: Prove that a statement is true.

I Tips: Assume that x, y , z are (real) numbers. Then:

You might also like