001_genesis.Rmd

---
title: "Genesis"
date: 2020-04-26 10:30:23
output:
  html_document:
    code_folding: hide
    df_print: paged
    highlight: tango
    number_sections: yes
    theme: flatly
    toc: yes
    toc_depth: 2
bibliography: beginners_guide_mathematical_logic.bib
link-citations: yes
---

<style>

body {
text-align: justify}

</style>

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo      = TRUE, 
                      warning   = FALSE, 
                      message   = FALSE,
                      fig.align = "center")
```

```{r libraries}

library(tidyverse)
library(ggforce)
```

# Genesis

This section is based on [@smullyan_beginners_2014, Chapter 1]

## What is mathematical logic?

In [@russell_mysticism_2007, Chapter 2, Section 5] Bertrand Russell talks about pure mathematics and its relation with formal logic or what we know as mathematical logic given us a general definition:

_"Pure mathematics consists entirely of assertions to the effect that, if such and such a proposition is true of anything, then such and such another proposition is true of that thing. It is essential not to discuss whether the first proposition is really true, and not to mention what the anything is, of which it is supposed to be true. Both these points would belong to applied mathematics. We start, in pure mathematics, from certain rules of inference, by which we can infer that if one proposition is true, then so is some other proposition. These rules of inference constitute the major part of the principles of formal logic. We then take any hypothesis that seems amusing, and deduce its consequences. If our hypothesis is about anything, and not about some one or more particular things, then our deductions constitute mathematics. Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. People who have been puzzled by the beginnings of mathematics will, I hope, find comfort in this definition, and will probably agree that it is accurate."_

However there is not a simple definition that make you understand what mathematical logic is all about. Only if you study it its nature will become apparent. Also mathematical logic has many purposes, but again, you will understand them after studying it. Anyway there is a purpose that we can understand now even if we don't have studied mathematical logic:

- One of its purpose is to make precise the notion of proof

__Problem 1__ "Good food is not cheap" and "Cheap food is not good" say different things or the same thing?

- We can use propositional logic to understand this two statements. Let

    + $p = \text{Food is good}$
    
    + $q = \text{Food is cheap}$
    
    + $p \implies \neg q: \text{Good food is not cheap}$
    
    + $q \implies \neg p: \text{Cheap food is not good}$
    
        + Later you will see that $p \implies \neg q$ and $q \implies \neg p$ are equivalent so we can point out that those two statements say the same thing in the context of propositional logic
        
        + According to Raymond Merrill Smullyan logically the two statements say the same thing but psychologically they convey diiferent things
        
            + $\text{Good food is not cheap}$ creates the image of expensive food that is good
            
            + $\text{Good food is not cheap}$ creates the image of cheap food that is rotten
            
- It is important to understand the difference between a _valid_ argument and a _sound_ argument

    + An argument is _valid_ if and only if whenever the premises are all true then the conclusion is true. For example:
    
        + Premises (In this case the first premise is false): 
        
            + $\text{I am human and a bird}$ 
            
            + $\text{I am human}$
        
        + Conclusion (In this case the conclusion is a logical consequence of the premises): 
        
            + $\text{I am a bird}$
    
    + An argument is _sound_ if and only if it is valid and all its premises are true. For example:

        + Premises (In this case all premises are true): 
        
            + $\text{I am human and not a bird}$
            
            + $\text{I am human}$
        
        + Conclusion (In this case the conclusion is a logical consequence of the premises):
        
            + $\text{I am not a bird}$
            
## Set theory

The beginnings of mathematical logic went pretty much hand in hand with the nineteenth century development of _set theory_ and particularly the theory of _infinite sets_ founded by George Cantor. Some elements of basic set theory are described below

- A set is any collection of objects whatsoever

    + The basic notion of set theory is that of _membership_
    
        + The standard notation for membership is the symnol $\in$ and the expression _$x$ is a member of $A$_ is abbreviated $x \in A$
        
    + A set $A$ is said to be a _subset_ of $B$ if every member of $A$ is also a member of $B$
    
        + The phrase _$A$ is a subset of $B$_ is abbreviated $A \subseteq B$
        
        + Don't confuse $\in$ with $\subseteq$
        
            + If $H$ is the set of humans, $W$ is the set of women and $\text{Maria}$ is a woman then
            
                + $W \subseteq H$
                
                + $\text{Maria} \in W$
                
                + However it is not the case that
                
                    + $W \in H$ because the set of women is not a human
                    
                    + $\text{Maria} \subseteq H$ because $\text{Maria}$ is not a subset of humans
                    
      + A set $A$ is the same as the set $B$ if and only if they contain exactly the same elements
      
          + This is equivalent to $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$
          
      + A set is called _empty_ if it contains not elements at all
      
          + The $\emptyset$ is abbreviated $\emptyset$
      
          + There can only be one empty set
          
          + This set has a strange characteristic if you encounter it for the first time
          
              + For any property $P$, all elements of the empty set have property $P$
              
                  + This characteristic is related to the use of the logical connective $\implies$ in mathematical logic where $p \implies q$ is false only when $q$ is falseand true in any other case 
                  
                      + $(\forall P)(\forall x)(x \in \emptyset \implies P(x))$
                      
                      + Alternatively, if $x \in \emptyset$ then $x$ has the property $P$ 
                      
                          + $x \in \emptyset$ is false so $x \in \emptyset \implies P(x)$ is true
                          
__Problem 2__ Is the empty set a subset of every set?

What we want to answer is if this statement is true:

$$(\forall A)(\forall x)(x \in \emptyset \implies x \in A)$$
If we accept the use of the logical connective $\implies$ in mathematical logic then the above statement is true. Therefore $\emptyset$ is a subset of every set:

- In particular $\emptyset \subseteq \emptyset$

- Furthermore the only subset of $\emptyset$ is $\emptyset$ because if $A \neq \emptyset$ and if there exist some $x$ such that $x \in A$ then the statement $x \in A \implies x \in \emptyset$ is false 

## Boolean operation on sets

### Unions

For any pairs of sets $A$ and $B$ the union of $A$ and $B$, denoted $A \cup B$, is meant the set of all things that belong to either $A$, $B$ or both.

__Problem 3__ Which, if any, of the following statements are true?

- If $A \cup B = B$ then $B \subseteq A$

    + $B = \{ 0, 1 \}$, $A = \{ 0 \}$, $A \cup B = \{ 0, 1 \} = B$ and $B \nsubseteq A$
    
- If $A \cup B = B$ then $A \subseteq B$

    + $A \subseteq A \cup B \implies A \subseteq B$

- If $A \cup B$ then $A \cup B = B$

    + $B \subseteq B \cup A$
    
    + $A \subseteq B \land B \subseteq B \implies A \cup B \subseteq B$
    
- If $B \subseteq A$ then $A \cup B = A$

    + $A = \{ 0 \}$, $B = \{ 0, 1 \}$, $A \cup B = B$ but $B \neq A$ so $A \neq A \cup B$
    
We can think of $A \cup B$ as the result of adding the elements of $A$ to the set $B$

- This is the same of as adding the elements of $B$ to the set $A$ so $A \cup B = B \cup A$

- Also we have that $A \cup (B \cup C) = (A \cup B) \cup C$ because adding the elements of $A$ to the set $B \cup C$ is equivalent to adding the elements of $A \cup B$ to the set $C$

- Furthermore $A \cup A = A$ because we are adding the same elements to $A$ so we end up with the same elements

- Finally $A \cup \emptyset = A$ because we are not adding elements to $A$

### Intersections

For any pairs of sets $A$ and $B$ the intersection of $A$ and $B$, denoted $A \cup B$, is meant the set of all things that are in both $A$ and $B$. Therefore we have that

- $A \cap A = A$

    + All the common elements between $A$ and $A$ are those that are in $A$

- $A \cap B = B \cap A$

    + The common elements between $A$ and $B$ are the same common elements between $B$ and $A$ 

- $A \cap (B \cap C) = (A \cap B) \cap C$

    + The common elements between $A$ and $B \cap C$ are the same common elements between $A \cap B$ and $C$

- $A \cap \emptyset = \emptyset$

    + Remeber that $\emptyset$ has no elements so $\emptyset$ has no common elements with any set

__Problem 4__ Which, if any, of the following statements are true?

- If $A \cap B = B$ then $B \subseteq A$

    + $\begin{split}
       x \in B & \implies x \in A \cap B \\
       & \implies x \in A \land  x \in B \\
       & \implies x \in A
       \end{split}$
    
- If $A \cap B = B$ then $A \subseteq B$

    + $B = \{ 0 \}$, $A = \{ 0, 1 \}$, $A \cap B = \{ 0 \} = B$ but $A \nsubseteq B$

- If $A \subseteq B$ then $A \cap B = B$

    + $A = \{ 0 \}$, $B = \{ 0, 1 \}$, $A \cap B = \{ 0 \} = A$ but $A \nsubseteq B$
    
- If $A \subseteq B$ then $A \cap B = A$

    + $A \cap B \subseteq A$

    + $\begin{split}
       x \in A & \implies x \in B \\
       & \implies x \in A \land  x \in B \\
       & \implies x \in A \cap B
       \end{split}$
       
__Problem 5__ Suppose $A$ and $B$ are sets such that $A \cap B = A \cup B$. Does it necessarily follow that $A$ and $B$ must be the same set?

- $\begin{split}
   x \in A & \implies x \in A \cup B \\
   & \implies x \in A \cap B \\
   & \implies x \in B \\
   \end{split}$
        
- $\begin{split}
   x \in B & \implies x \in B \cup A \\
   & \implies x \in A \cup B \\
   & \implies x \in A \cap B \\
   & \implies x \in A \\
    \end{split}$
    
- $A \cap B = A \cup B \implies A = B$ is true.

    + Furthermore $A = B \implies A \cap B = A \cup B$ is true
    
    + Therefore $A = B \iff A \cap B = A \cup B$ is true

### Complementation

In this part we are going to consider a set $I$, which we call _the universe of discourse_

- The set $I$ will vary for one application to another

    + In plan geometry $I$ is the set of all points in the plane
    
    + In number theory $I$ is the set of whole numbers
    
- For any $A \subseteq I$, by its complement relative to $I$ we meant the set of all elements of $I$ that are not in $A$

- The complement of a set $A$ is denoted $A^{'}$, $\overline{A}$ or $\widetilde{A}$

- We have that $A = A^{''}$
    
__Problem 6__ Which, if either, of the following statements is true?

- If $A \subseteq B$ then $A^{'} \subseteq B^{'}$

- If $A \subseteq B$ then $B^{'} \subseteq A^{'}$

    + $\begin{split}
       x \in B^{'} & \iff x \notin B \\
       & \iff x \notin A \\
       & \iff x \in A^{'}
       \end{split}$
       
    + Therefore $A \subseteq B \implies B^{'} \subseteq A^{'}$ is true
    
The operations of union, intersection and complementation are the fundamental boolean operations on sets. For example $A - B = A \cap B^{'}$
    
## Venn diagrams

Boolean operations on sets can be graphically illustrated by what is known as _Venn Diagrams_, in which:

- The universe of discourse $I$ is represented by the set of all points in the interior of a square

- Subsets of $I$, $A, B, ...$, are represented by circles within the square

- Boolean operations are represented by shading appropriate portions of the circle

```{r}

tibble(x      = c(-0.5, 0.5),
       y      = c(   0,   0),
       labels = c('A', 'B')) %>% 
    ggplot() +
    geom_circle(aes(x0 = x, y0 = y, r = 1, fill = labels),
                alpha       = .5, 
                size        = 1, 
                color       = 'grey',
                show.legend = FALSE) +
    geom_rect(aes(xmin = -2, xmax = 2, ymin = -2, ymax = 2), 
              fill  = "#C77CFF",
              color = 'grey',
              alpha = 0.1) +
    annotate(geom = "text", x =   -1, y =  1,   label = "A") +
    annotate(geom = "text", x =    1, y =  1,   label = "B") +
    annotate(geom = "text", x = -1.5, y =  1.5, label = "I") +
    labs(fill = "") +
    coord_fixed() +
    theme_void()
```

## Boolean equations

- We will use the capital letters $A, B,...$ with or without subscripts to stand for arbitrary sets

- We call this capital letters _set variables_

- By a _term_ we mean any expression constructed according to the following rules:

    + Each set variable standing alone is a term
    
    + For any terms $t_1$ and $t_2$ the expressions $t_1 \cup t_2$, $t_1 \cap t_2$ and $t_1^{'}$ are again terms
    
Examples of terms are:

- $(A \cup (B \cap C^{'}))$
    
- $(A^{'} \cup (B \cap A^{''}))$

Where sometimes we can drop some parentheses when their isn't ambiguity like:


- $A \cup (B \cap C^{'})$
    
- $A^{'} \cup (B \cap A^{''})$

However sometimes dropping parentheses create an ambiguity like

- $A \cup B \cap C^{'}$

In this case we don't know if the above expression is $(A \cup B) \cap C^{'}$ or $A \cup (B \cap C^{'})$

By a _boolean equation_ we mean an expression of the form $t_1 = t_2$ where $t_1$ and $t_2$ are boolean terms. For example:

- $A \cup B = B \cup A$

- $A \cup B = A \cap B$

A boolean equation is valid if it is true no matter what sets the set variables represent. For example  $A \cup B = B \cup A$ is valid but $A \cup B = A \cap B$ is not valid  

### Testing boolean equations

- Is there a systematic way of testing whether or not a given boolean equation is valid?

    + One way is by using Venn diagrams
    
    + Another way is the method of indexing
    
In the plot below $I$ is divided into four sets:

- $A \cap B$ indexed as $1$

- $A \cap B^{'}$ indexed as $2$

- $A^{'} \cap B$ indexed as $3$

- $A^{'} \cap B^{'}$ indexed as $4$

    + These four regions are know as the _basic regions_ 

```{r}

tibble(x      = c(-0.5, 0.5),
       y      = c(0,  0),
       labels = c('A', 'B')) %>% 
    ggplot() +
    geom_circle(aes(x0 = x, y0 = y, r = 1, fill = labels),
                alpha       = .5, 
                size        = 1, 
                color       = 'grey',
                show.legend = FALSE) +
    geom_rect(aes(xmin = -2, xmax = 2, ymin = -2, ymax = 2), 
              fill  = "#C77CFF",
              color = 'grey',
              alpha = 0.1) +
    annotate(geom = "text", x =   -1, y =  1,    label = "A") +
    annotate(geom = "text", x =    1, y =  1,    label = "B") +
    annotate(geom = "text", x = -1.5, y =  1.5,  label = "I") +
    annotate(geom = "text", x =   -1, y =  0,    label = "2") +
    annotate(geom = "text", x =    0, y =  0,    label = "1") +
    annotate(geom = "text", x =    1, y =  0,    label = "3") +
    annotate(geom = "text", x =    0, y =  -1.5, label = "4") +
    labs(fill = "") +
    coord_fixed() + 
    theme_void()
```

We can identify any union of the basic regions with its set of indices. For example

- $A = (1,2)$

- $B = (1,3)$

- $A \cup B = (1,2,3)$

- $A \cap B = (1)$

- $A \cup A^{'} = (1,2,3,4)$

    + Take into account that $A \cup A^{'} = \emptyset$
    
If we want to verify if $(A \cup B)^{'} = A^{'} \cap B^{'}$ is valid we find the indices of $(A \cup B)^{'}$ and $A^{'} \cap B^{'}$ to see if they are equal. 

- $A \cup B = (1,2,3)$

- $(A \cup B)^{'} = (4)$

    + We select the numbers that are not in $(1,2,3)$ 

- $A^{'} = (3,4)$

- $B^{'} = (2,4)$

- $A^{'} \cap B^{'} = (4)$

    + We select the numbers that are common to $(3,4)$ and $(2,4)$
    
Therefore $(A \cup B)^{'} = A^{'} \cap B^{'}$ is valid

In the case of an equation with three sets $A, B$ and $C$ we have that $I$ is divided into eight basic regions:

```{r}

tibble(x      = c(-0.5, 0.5, 0),
       y      = c(   0,   0, -1),
       labels = c('A', 'B', 'C')) %>% 
    ggplot() +
    geom_circle(aes(x0 = x, y0 = y, r = 1, fill = labels),
                alpha       = .5, 
                size        = 1, 
                color       = 'grey',
                show.legend = FALSE) +
    geom_rect(aes(xmin = -2.5, xmax = 2.5, ymin = -2.5, ymax = 2), 
              fill  = "#C77CFF",
              color = 'grey',
              alpha = 0.1) +
    annotate(geom = "text", x =   -1, y =  1,    label = "A") +
    annotate(geom = "text", x =    1, y =  1,    label = "C") +
    annotate(geom = "text", x =    1, y =  -2,   label = "B") +    
    annotate(geom = "text", x = -1.5, y =  1.5,  label = "I") +
    annotate(geom = "text", x =   -1, y =  0,    label = "4") +
    annotate(geom = "text", x =    0, y =  0.4,  label = "3") +
    annotate(geom = "text", x =    1, y =  0,    label = "7") +
    annotate(geom = "text", x =    0, y =  -1.5, label = "6") +
    annotate(geom = "text", x =  1.5, y =  1.5,  label = "8") +
    annotate(geom = "text", x = -0.5, y = -0.75, label = "2") +
    annotate(geom = "text", x =  0.5, y = -0.75, label = "5") +
    annotate(geom = "text", x =    0, y = -0.4,  label = "1") +
    labs(fill = "") +
    coord_fixed() +
    theme_void()
```

Thus:

$$\begin{split}
  A & = \{ 1,2,3,4 \} \\
  B & = \{ 1,2,5,6 \} \\
  C & = \{ 1,3,5,7 \} \\
  \end{split}$$

Suppose we wish to show that $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

- $B \cap C = (1,5)$

- $A \cup (B \cap C) = (1,2,3,4,5)$

- $A \cup B = (1,2,3,4,5,6)$

- $A \cup C = (1,2,3,4,5,7)$

- $(A \cup B) \cap (A \cup C) = (1,2,3,4,5)$

Therefore $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ is valid

What do we do if we have more than three sets, like $A, B, C$ and $D$?

- According to [@ruskey_search_2006] it is not possible to draw circles when we have more than three sets.

    + To know more about Venn diagrams check out [@ruskey_survey_2005]

- However for the case of four sets we can divide $I$ into 16 basic regions and number them such that:

$$\begin{split}
  A & = \{ 1,2,3,4,6,7,8 \} \\
  B & = \{ 1,2,3,4, 9,10,11,12 \} \\
  C & = \{ 1,3, 5,6, 9,10, 13,14 \} \\
  D & = \{ 1,3,5,7,9,11,13,15 \}
  \end{split}$$

In general for any $n \geq 2$ the sets $A_1, ..., A_n$ divide $I$ into $2^n$ basic regions and we can assign an index to each of these regions in the following way:

- $A_1$ will be the first half of the integers $1, ..., 2^n$

- $A_2$ will be every other quarter starting with the first

- $A_3$ to be every other eight

- And so forth

    + For example if $n = 5$ then
    
        + $\begin{split}
           A_1 & = (1-16) \\
           A_2 & = (1-8, 17-24) \\
           A_3 & = (1-4, 9-12, 17-20, 25-28) \\
           A_4 & = (1-2, 5-6, 9-10, 13-14, 17-18, 21-22, 25-26, 29-30) \\
           A_4 & = (\text{All odd numbers from 1 to 32})
           \end{split}$
           
__Exercise 1__ By the method of indexing, prove the following boolean equation to be valid $(A \cup B)^{'} \cap C = (C \cap A^{'}) \cup (C \cap B^{'})$

- $A \cup B = (1,2,3,4,5,6)$

- $(A \cup B)^{'} = (7,8)$

- $(A \cup B)^{'} \cap C = (7)$

- $A^{'} = (5, 6, 7, 8)$

- $C \cap A^{'} = (5,7)$

- $B^{'} = (3, 4, 7, 8)$ 

- $C \cap B^{'} = (3,7)$

- $(C \cap A^{'}) \cup (C \cap B^{'}) = (7)$ 

Therefore $(A \cup B)^{'} \cap C = (C \cap A^{'}) \cup (C \cap B^{'})$ is valid

Some other boolean operations are:

- $A \rightarrow B$ which refers to $A^{'} \cup B$

- $A \equiv B$ which refers to $(A \cap B) \cup (A^{'} \cap B^{'})$

__Exercise 2__ By the method of indexing, prove that the following equations are valid

- $A \rightarrow B = (A - B)^{'}$

    + $A^{'} = (3,4)$
    
    + $A \rightarrow B = (1,3,4)$
    
    + $A - B = (2)$
    
    + $(A - B)^{'} = (1,3,4)$
    
- $A \equiv B = (A \rightarrow B) \cap (B \rightarrow A)$

    + $A \cap B = (1)$
    
    + $A^{'} \cap B^{'} = (4)$
    
    + $A \equiv B = (1,4)$
    
    + $B^{'} = (2,4)$
    
    + $B \rightarrow A = (1,2,4)$
    
    + $(A \rightarrow B) \cap (B \rightarrow A) = (1,4)$
    
- $A \cap (A - B)^{'} = \emptyset$

    + $A \cap (A - B)^{'} = (1)$
    
        + Therefore this boolean equation is not valid
        
- $A \equiv A \rightarrow B = A \cap B$

    + $A \cap A \rightarrow B = (1)$
    
    + $A^{'} \cap (A \rightarrow B)^{'} = \emptyset$
    
    + $A \equiv A \rightarrow B = (1)$
    
    + $A \cap B = (1)$

# Bibliography