7.2. Logical Predicates - JulTob/Mathematics GitHub Wiki

Propositions

A $\color{Silver}Proposition$ is a declarative sentence that is either $\color{Lime}true$ or $\color{Tomato}false$

To put it simply, ambiguous sentences that produce different reactions depending on whom you ask are not propositions.

Implication

In situations where we know that “if P then Q” is true, but don't know anything about its converse “if Q then P”

we say that “P entails Q” and that “Q could entail P.”

\color{Gold}
P⇒Q

flowchart LR
    P --> |True|Q
    Q --> |Not necessarily True|P

Equivalence

\color{Goldenrod}
P⇔Q

flowchart LR
    P --> |True|Q
    Q --> |True|P

Predicate Logic in Set Theory

Predicate logic extends the exploration of sets by introducing predicates $𝑷(𝑥)$, $𝑸(𝑥)$, …
that describe properties of elements within a Universal set $𝕌$. These predicates facilitate the formation of sub-sets based on logical conditions, illustrating the nuanced relationships within and between sets.

Negation

The negation of a predicate defines a set excluding elements that satisfy $𝑷(𝑥)$.

\color{tomato}
¬𝑷(𝑥)

Conjunction

The logical OR combines sets under predicates $P$ and $Q$.

\color{gold}
𝑷(𝑥) ∨ 𝑸(𝑥)

Implication

Implies a logical progression from $P$ to $Q$

\color{violet}
𝑷(𝑥) ➞ 𝑸(𝑥)

A set $𝔹$ defined by

\color{cyan}
𝔹  = ｛ 𝑥 ∊ 𝔸 ∣ 𝑷❨𝑥❩ ∧ ¬𝑷❨𝑥❩ ｝= ∅

illustrates the application of predicates to determine membership based on specified properties.

Natural Numbers and the Axioms of Peano

Natural numbers

\color{gold}
ℕº=｛0,1,2,3,4,5,.,.｝

\color{silver}
ℕ⁺=｛1,2,3,4,5,.,.｝

are foundational in mathematics, described by the Axioms of Peano:

Axioms of Peano

Zero is a natural number: $0={}=∅$
- Zero is the First Element
Every natural number $𝑛$ has a successor $𝑛+1$
- $\color{salmon} 1 = ｛∅｝ = ｛0｝$
- $\color{salmon} 2 = ｛∅, ｛∅｝｝ = ｛0,1｝$
- $\color{salmon} 𝑛+1 = ｛0,1,2.,.n｝$
Is Orderly:
- If $\color{tomato} n+1 = m+1 ➞ n = m$
Induction
- If a property holds for zero.
- If it holds for $n$, then implies it holds for $n+1$
∴ Then it holds for all Natural Numbers.

Mathematical Induction

Mathematical induction allows the proof of properties across natural numbers.

The structure of induction follows this steps:

𝑷₀
𝑷ₙ￫𝑷ₙ₊₁
- ⁖ 𝑷ₙ

\color{silver}
\begin{align}
\text{Step} &&    \text{Formula}                      && \text{Description}  \\

1    &&    \sum \frac{n}{2^n} = 2 - \frac{(n+2)}{2^n}  && \text{Sum formula for series}\\
2    &&    n=0                                         && \text{Base case evaluation }\\
2.1  &&   \frac{0}{2^0} = 2 - \frac{(0+2)}{2^0}        && \text{Substituting 0 into the formula}\\
2.2  &&   0 = 2 - \frac{2}{1} = 0                      && \text{Simplifying the expression }\\ 
3    &&   \sum \frac{n+1}{2^{n+1}} = 2 - \frac{(n+3)}{2^{n+1}}  && \text{Sum formula for } (n+1) \\ 
3.1  &&   \sum \frac{n}{2^n} + \frac{n+1}{2^{n+1}}     && \text{Separating} (\frac{n+1}{2^{n+1}}) \text{from the series for n} \\ 
3.2  &&   2 - \frac{(n+2)}{2^n}) + \frac{n+1}{2^{n+1}}      && \text{Utilizing the original sum formula} \\ 
3.3  &&   2 - \frac{ 2 (n+2) - n - 1 }{ 2^{n+1}}      && \text{Combining terms under a common denominator} \\ 
3.4  &&   2 - \frac{ 2n + 4 - n -1 }{ 2^{n+1} }      && \text{Simplifying the numerator} \\ 
3.5  &&   2 - \frac{ n + 3 }{ 2^{n+1} }      && \text{Further simplification} \\ 
3.6  &&   2 - \frac{ (n + 1) + 2}{2^{n+1}}      && \text{Final form of the expression} \\ 
4  &&   \text{Quod erat demonstrandum}     && \text{Conclusion} \\ 

\end{align}

Quantifiers in Set Theory

In the realm of mathematics, particularly within the universe of set theory, quantifiers act as the bridge between the abstract and the specific. They are the mathematical equivalent of existential ponderings and universal truths.

We consider a Set $𝔸$, with element $𝑥$, with a predicate $𝑷$ :

When we say an element ($𝑥$) belongs to a set ($𝔸$), we're describing a relationship where ($𝑥$) is one of the objects that make up the set ($𝔸$), denoted as ($𝑥∈𝔸$).

A predicate ($𝑷$) in this context is a condition or property that elements of the set may or may not satisfy. Predicates are functions that return a boolean value, true or false, depending on whether the element in question satisfies the given condition. For instance, a predicate might be defined to test whether numbers in a set are even, prime, greater than a certain value, and so on.

Universal Quantifier: $∀$

Imagine walking into a vast library, each book representing an element of set ($𝔸$). The statement ($∀𝑥∈𝔸:𝑷(𝑥)$) is akin to declaring, "Every single book in this library is a masterpiece." The universal quantifier $∀$ speaks to every element without exception, imposing a blanket statement of truth across the entire set.

∀𝑥 ∊ 𝔸 : 𝑷(𝑥)

This can be interpreted as "For every element ($𝑥$) within set ($𝔸$), property ( $𝑷(𝑥)$ ) holds true."

All ($𝑥$) in ($𝔸$) is ($ 𝑷(𝑥) $)
For all 𝑥 in 𝔸, 𝑷(𝑥)

∀𝑥 : 𝑷(𝑥)

All 𝑥 is 𝑷
For All 𝑥, property 𝑷 holds

 ⇒  𝔸 = {∀𝑥 : 𝑷(𝑥) } 
 ⇒  𝑷(𝑥₁) ∧ 𝑷(𝑥₂) .∧. 𝑷(𝑥ₙ) …

This statement asserts that every element ($𝑥$) in the domain under consideration satisfies the property ($𝑷$). It's a universal claim about the elements in question, implying a broad applicability of ($𝑷$).

Existential Quantifier: $∃$

Contrast this with the existential quantifier ($∃$), which takes a more nuanced approach. It suggests the presence of at least one element within the set that satisfies a given property. Using the library analogy, ($∃𝑥 ∈ 𝔸 : 𝑷(𝑥)$) is like saying, "Within this vast collection, there exists at least one book that will change your life."

∃𝑥 ∊ 𝔸 : 𝑷(𝑥)

There exists an $𝑥$ in $𝔸$ that is $𝑷(𝑥)$

This translates to "There exists an element ($𝑥$) within set ($𝔸$) for which property ($𝑷$) is true."

Imagine searching for a book written by an author born on February 29. Finding just one such book confirms the existence statement: ($∃book : \text{author was born on a leap day}$) .

∃𝑥 : 𝑷(𝑥)

"There exists an ($𝑥$) such that $𝑷(𝑥)$ is true."

"Some ($𝑥$) is $𝑷(𝑥)$."

"It exists an ($𝑥$) such as $𝑷(𝑥)$."

This statement asserts that there is at least one element ($𝑥$) within the domain under consideration for which the property ($𝑷$) holds. It does not claim that ($𝑷$) holds for all elements, just that at least one such element exists.

∃𝑥 ∈ 𝔸 : 𝑷(𝑥)

Let ($𝔸$) be any set for which there exists an ($𝑥$) such as ( $𝑷(𝑥)$ )

𝑷{𝔸}≠∅

The subset of 𝔸 that satisfies 𝑷 is not empty

𝑷𝑥₁ ∨ 𝑷𝑥₂ .∨. 𝑷𝑥ₙ …

At least one element's existence proves the statement.

Example: Even Numbers (𝟚ℕ)


\begin{aligned}
\text{Pares:} && 𝟚ℕ & \\
 && = & \{ 𝑥∊ℕ ∣ ∃𝑘 ∊ ℕ : 𝑥 = 𝟐𝑘 \} \\
 && = & \{ 𝟐𝑘 ∣ 𝑘∊ℕ  \}
\end{aligned}

This defines the set of all even natural numbers. An even number is any number that can be expressed as ($𝟐𝑘$) where ($𝑘$) is a natural number ($ℕ$). This definition uses the concept of existential quantification ($∃$) to express that for any even number ($𝑥$), there exists a natural number ($𝑘$) such that ($𝑥 = 𝟐𝑘$).

\begin{aligned}
∀𝑥∈ℝ : &&  \\
  && 𝑥²-1 = (𝑥+1)(𝑥-1) 
\end{aligned}

This statement says that for all real numbers $𝑥$ ($ℝ$), the expression ($x^2−1$) can be factored into ($(x+1)(x−1)$). It demonstrates a universally true algebraic identity, applying universally across the real numbers ($∀$).

Example: Solution to a Linear Equation

\begin{aligned}
∃𝑥∈ℝ:              &  \\
&  𝑥+5=3               \\
\end{aligned}

This example states that there exists a real number ($𝑥$) that solves the equation ($𝑥+5=3$). The implication is that such an ($𝑥$) exists, and solving the equation yields ($𝑥 = 2$) satisfying the existential quantifier ($∃$) by showing at least one solution exists within the real numbers.

\begin{aligned}

∀x ∈ \text{Crows},Black(x) && \text{All crows are black}    \\
\{∃Swans\}Black && \text{Some swans are black}   \\

\end{aligned}

𝑷𝑥=𝑸𝑥 ⟺ ∀𝑥∈𝔸: 𝑷𝑥⟷𝑸𝑥

Negaciones

¬(∀𝑥: 𝑷𝑥) ⇔ ∃𝑥 : ¬𝑷𝑥
¬({∀𝑥}𝑷𝑥) ⇔ {∃𝑥}¬𝑷𝑥

¬(∃𝑥: 𝑷𝑥) ⇔ ∀𝑥: ¬𝑷𝑥
¬({∃𝑥}𝑷𝑥) ⇔ {∀𝑥}¬𝑷𝑥

Demostración por contraejemplo

Complemento

𝕌⊆𝔸
¬𝔸 =𝔸͞ = 𝕌-𝔸
   = { 𝑥∈𝕌 ∣ 𝑥∉𝔸 }
   = { 𝑥∈𝕌: ¬𝑷𝑥}

Ej: Impares:

𝕀 = ¬ℙ = ¬𝟚ℕ
   = { 𝑥∊ℕ ∣ ∃𝑘∊ℕ : ¬(𝑥=𝟐𝑘) }
   = { 𝑥∊ℕ ∣ ∃𝑘∊ℕ : 𝑥=𝟐𝑘+𝟏 }

Particiones

𝓟❨𝔸❩ 
   ={∀𝔹: 𝔹⊂𝔸}

∅∈𝓟❨𝔸❩ 
𝔸∈𝓟❨𝔸❩

Ejemplo:

𝔸={1,2}
⇒ 𝓟❨𝔸❩ = {∅,{1},{2},{1,2} }

Sentential Logic

all and every

some, there is, and there exists

an intersection. For example, when you say, “Some of my teachers are nice,” you mean that there’s an intersection between the set of your teachers and the set of nice things.

no, there is no, and none

if...then    and    but    or
not    unless    though    every
all    every    each    there is
there exists    some    there is no    none

Argument

The premises are the facts of the matter: The statements that you know (or strongly believe) to be true. In many situations, writing down a set of premises is a great first step to problem solving.

an argument also includes intermediate steps that show how the premises lead incrementally to that conclusion.

The conclusion is the outcome of your argument.

After you’ve built an argument, you need to be able to decide whether it’s valid, which is to say it’s a good argument.

hidden premise called an enthymeme

Uncovering hidden premises in real-world arguments is more related to rhetoric, which is the study of how to make cogent and convincing arguments.

The law of identity states that every individual thing is identical to itself.

x is x
x=x

The law of the excluded middle The law of the excluded middle states that every statement is either true or false. Rather, in logic, every statement is either completely true or completely false.

𝕃 : {0,1} = {False,True} : Boolean

type Boolean is (False, True);

------

Flag : Boolean := True

and
or
not
xor
/=
=

and then  --Stops when a false is found
or else   --Stops when a true is found

in   -- Belongs to a set type

The law of non-contradiction states that given a statement and its opposite, one is true and the other is false.

p and not p = false

Other Logics

Boolean logic Modern logic Quantifier logic Classical logic Multi-valued logic Quantum logic Formal logic Non-classical logic Sentential logic Fuzzy logic Predicate logic Syllogistic logic Informal logic Propositional logic Symbolic logic