Logic and Sets

Logic

To talk about math properly, we need to define foundations. We have seen in the basic algebra, how these operators work at a "intuitive" level, but without much formalism behind it.

We first define language used in math. Since words are not able to express easily mathematical concepts in a concise manner, mathematicians invented a "sublanguage" using symbols, in order to convey meaning quickly and without misunderstanding.

We first define what is a set. In layman's terms, a set is a collection of elements. These elements have to be all different from each other. I am going to present what is called first "naive set theory", as there's very little restriction about what's an element, and how a set is formed.

Let's talk about elements first. What is an element? Since naive set theory does not define it, it can be anything, from a simple number, to a set, to any kind of mathematical construct.

What is an example of a set? Usually sets are defined by curly braces, { for opening, } for closing a set definition. For example, the set $\{\}$ corresponds to the empty set. The set $\{a,b,c\}$ corresponds to a set that contains the three distinct elements a,b,c. Even better, we can do sets of sets, just like this $\{\{a\},\{b\},\{c\}\}$, that set contains three separate elements, which are themselves sets. Remember that the "distinct" clause works recursively, that is, if the two elements/sets were to be equal, then the container set would not be a set.

Some symbols

Let's add some symbols to the mix, after all just retyping all of that every time gets tedious.

Equality

$=$ is the symbol representing equality. If an expression is stated $a=b$, then the element "a" is fundamentally the same as the element "b". Before, when explaining all the intermediate steps during the operators, I used the $\rightarrow$ symbol, as a way to describe a "this form becomes the form after the arrow". That usage of the $\rightarrow$ symbol is not really correct in logic, so the more proper notation is to use the $=$ symbol instead.

As an example, $5=3+2=1+4=5*1$. While this is a bit of a spoiler, the equality is a symbol we always apply for last, always "grouping" everything else. So rather than thinking $4+1=5$ as $4+(1=5)$, it should always be grouped as $(4+1)=5$. Also, the equality symbol does not really give back a number, so when writing an expression, it does not make sense to write things like $(1=3)+(2=4)$.

Variables

When we introduce a random non-capital letter, (that hopefully isn't greek), we usually want to define a variable. This is useful in longer work and proofs, where rather than constantly writing the full expression, we could rather use a shortcut. For the computationally aware, these variables do not ever change. The value a variable has is simply to replace a full expression (that we may not even know!).

The simplest example is along the lines of $x=5$. This can be interpreted in two ways:

• When we see "x" in any subsequent formula within the same context, we can freely replace it with "5".

• The "previously unknown" value of the x (as in, what expression did it replace), is finally found, and has value "5".

The latter interpretation is used when "obfuscating" what the "x" actually means, and the math work consists in "reverse engineering" what the "x" could be so that the "=" symbol actually tells us the truth. Also, an expression that involves the "="/equality symbol, is called equation.

A simple example:

$$x+5=9$$

The value of the "x" isn't exactly apparent, as we only have the "x+5" value being set as "9". Of course, simple math/intuition tells us the solution is "4", but what steps did we do exactly to reach that conclusion? The answer is that we actually applied quite a few rules of maths. For example, we know that the opposite "symbol" to "+", is "-", so since we had a "+5" we had to add a "-5". But then, exactly like balance scales, if we were to add it only to one side, we would "break" the "=" symbol. So we applied the "-5" to the other side too.

$$x+5-5=9-5$$

While the "9-5" makes "4" is obvious, the "+5-5" leaves a "zero", as "x+0".

$$x+0=4$$

We know thankfully (intuitively) that, adding 0 to something does not change it, so we rewrite it as

$$x=4$$

Since we have an equation where one side is made up by the single variable, while the opposite has no instances of it (this is especially important, if there was some writing of "x" on both sides, like $x=5-x$, we could not fully replace the "x" without removing its reference), we know fully that the value of "x" is "4".

Now if we preemptively knew that the value of "x" was 4, and we came across the equation

$$x+5=x+x+1$$

(in the same context), we could replace every "x" with 4 and still be correct.

$$4+5=4+4+1$$ $$9=9$$

And in the previous equation

$$4+5=9$$

---

Some exercises: Find values of x (think about whether there's none or multiple, and why):

$$x+10=0$$ $$x+3=4$$ $$x-3=6$$ $$x*3=3$$ $$x/5=2$$ $$x*3=2$$ $$5/x=1$$ $$x/x=1$$ $$x*x=4$$ $$x*x=5$$

Enough preamble, time for the sets:

As we introduced them before, sets are simply collections of distinct elements. If we had a set $A=\{a,b,c\}$, we can introduce the notation $\in$ to write statements like:

$$x \in A$$

The above $\in$ symbol means "belongs to set". In logical writing, it is for delimiting what possible values can the variable can take, in order to write a True statement. In this case, "x" can take one of the values between "a","b", or "c", but not all at the same time. It also doesn't take the entirety of the set as the value or part of it, but just one of the elements the set is composed of.

If set A were to be empty, then the notation $x\in A$ would be a false statement, a "failure" of enumerating the statement with a value of "x", since there are no possible values "x" can take. Whether this is good or bad, depends on the statement we're evaluating, and sometimes the fact there might not be even a value could be in our favour.

We denote the set of "natural" number with the letter $\mathbb{N}$ (yes, that fancy). So if we say $a \in \mathbb{N}$, we can say that the variable "a" is taking a value from the natural numbers. It could be 5, it could be 8, we just know it's inside of that set.

A bit of clarification then: natural numbers are the numbers we can count, and that we associate to a positive quantity. That means, things like 4,9, even 0, are naturals, but things like "-4" aren't. Strictly speaking, a natural number is defined as:

• zero or

• a successor of a natural number.

The notation used to define this is varied, both in maths and the computer science field. We're going to use a similar definition as theorem provers (software specific to proving logical statements about programs).

For example, "4" could be defined as "s(s(s(s(zero))))", that is, zero and then counting up four times. Other numbers are made by a differing number of "s(...)", so our "s(...)" is nothing more than a "+1" operation. In this framework we can see the glaring issue: what happens when we subtract too much?

Since there's no number "below" the zero, our mental model of subtraction breaks. Why is that? Because in natural numbers, we can do subtraction very easily, just remove each "s" from both numbers until zero remains. For example, in "5" - "3"

5	-	3
s(s(s(s(s(zero)))))	-	s(s(s(zero)))
s(s(s(s(zero))))	-	s(s(zero))
s(s(s(zero)))	-	s(zero)
s(s(zero))	-	zero

That kind of means that "5 - 3" is the same as "4 - 2" and then "3 - 1" and then "2 - 0", but we know that removing zero does not change the result, so 2 remains. (How would the addition with s work? Will it be similar to our group of xs notation?). If we try to do the opposite "3-5" we instead run in the problem of "zero - s(s(zero))", which is sadly impossible in our mental model.

Therefore we introduce a new set! The integers! The important thing about this set is:

• it is denoted by a cool $\mathbb{Z}$

• it is made up of integers both positive and negative.

Now, sadly our fun s(s(....)) kind of breaks, so we go back to our "group of xs" notation. We could possibly try to extend the notation with n(n(zero)) as we just count down from zero, but we need to be careful not to mix up the s and n, as seen in the example before, they act exactly as the "x and -x" particles of the previous notation and therefore cancel out.

The set of $\mathbb{Z}$ can also be declared logically. I am going to throw a bit of notation and then explain it:

$$\mathbb{Z} = \{ x | x \in \mathbb{N} \lor -x \in \mathbb{N}\}$$

Don't panic! First of all, we introduce here the "set declaring" notation, where instead of listing every possible element, we just kind of describe what properties the elements composing the set have.

$$A = \{ x | x \text{ is a fruit} \}$$

The "|" just separates the "element structure" of the set (in our case just x), from the declaration following in logical language. The important thing here to note is that the "x | ..." can also not be just a single variable.

For example, we declare:

$$B = \{ 2*x | x \in \mathbb{N} \}$$

This means that the B set is composed by elements that are made by picking a "random" element in the naturals (so just pick your favourite natural number, like 7), but then we substitute 2*x instead (which in our case would make 14). So, if we try to pick ALL the possible elements in $\mathbb{N}$ (a big task I know), we will always replace them with their double. This defines a set that would be like $\{0,2,4,6,.....\}$ (Can 5 be there? Why not?)

And from the example before, "A" could be a set like $\{\text{apple}, \text{banana}, \text{mango}, \text{tomato}...\}$.

Back to our cool $\mathbb{Z}$! When trying to read the "definition", we read that "x" has to be in the natural set, and that's fine, but then we encounter a weird symbol. Logic time! Again!

Logic... again.

First of all, let's talk about propositions. A proposition is a statement stating a "fact", that can be given a value of truth or false. Either the statement is true, and what is says is correct, or the statement is false and what the statement says is completely bogus. (It's important to state that if a statement says multiple things, and it's false, we always take the statement as a whole. "I can do addition and rain is made of chocolate" as a whole is false, but hopefully only the "rain is made of chocolate" statement is false, it does not invalidate the rest).

We can assign statements to letters. A declaration could take the following form: "A = this is a good tutorial about logic", and then we can discuss whether A is True or False. In the same context, we can also assign a second letter B, and declare a statement like "B = the device I am reading this on is active and working" has also a truth value, which is probably True in this case. The statements "A" and "B" don't need to necessarily have the same truth value, and can be True or False on a statement by statement basis.

A possible issue arising from the notation is that when looking at the letter "A" now, we might not be sure if it is a set or a statement, since both use uppercase letters (unlike the previously introduced variables, which usually take the form of lowercase letters), and the only way we can tell those apart is from remembering what is the current context of declarations we have. A declaration of set "A" for example, will not be "long-standing", and will probably be erased in the example after, where that same letter "A" could instead take the value of a set.

To remind us from the set notation before:

$$A = \{ x | x \text{ is a fruit} \}$$

We are stating that A as a set is made up of elements that make that "second part of the description (after the |)" actually True. (This is huge) It's a way to categorically define a set of all the elements that satisfy that "property" without having to describe each one.

Since our statement above is:

$$\mathbb{Z} = \{ x | x \in \mathbb{N} \lor -x \in \mathbb{N}\}$$

we focus on the $x \in \mathbb{N} \lor -x \in \mathbb{N}$ part.

The $\lor$ symbol means Logical OR. That is, in a statement of the form $A \lor B$, if A and B are also statements (or better called prepositions), with their own true or false values, the statement as a whole is only True if any of the two is true. In Logic Table notation:

$A$	$B$	$A \lor B$
F	F	F
F	T	T
T	F	T
T	T	T

Conversely, the $\land$ symbol stands for Logical AND and is only True if both statements are also True.

$A$	$B$	$A \land B$
F	F	F
F	T	F
T	F	F
T	T	T

An extra operator is $\lnot$, the logical not. This operator only takes a single "preposition" argument.

$A$	$\lnot A$
F	T
T	F

In our previous definition then, we split the statement in both parts, and look at "$x \in \mathbb{N}$" first. This only means it's in the naturals, ergo zero or a positive number. The "$-x \in \mathbb{N}$" is a bit more complicated. As it means that we take numbers of the form "-x" that are also in the naturals. But didn't we say all numbers in the natural set are positive? If taking a number like 5, we would get "-5" and that is not the naturals, the condition is not satisfied.

What if we were to take a negative number then? What does "--5" mean? While intuitively you can understand it's probably "5", mathematically is not really taken for granted, because our "-" symbol is just applied as a "modifier" we use to 5, to denote the negative part. What happens when we double negative? Let's try to think of it in addition terms. We know that -5 is what we reach when we subtract 5 from zero.

$$x = 0 - 5$$

We want to find what "-x" is. If we were to add 5 to both sides of the equation....

$$x + 5 = -5 + 5$$ $$x + 5 = 0$$

Now we might want to add "-x" to both sides...

$$x + 5 - x = - x$$ $$5 = -x$$

Since "x - x" is "0", we can remove it safely, and we finally get that "-x" is "5", finally demonstrated. Extrapolating, every "--x" number can be reduced back to "x".

Back to our definition then.

$$\mathbb{Z} = \{ x | x \in \mathbb{N} \lor -x \in \mathbb{N}\}$$

• $x \in \mathbb{N}$ is straightforward, as it means "take a natural number".

• $-x \in \mathbb{N}$ where we take any possible value that x could take (every possible number form ever), and if by the operation of "negating it", we end with some form of $-(-7)$ (or other values of course), we can simplify it back to $7$ which is a natural number instead (and is part of the set $\mathbb{N}$).

So $\mathbb{Z}$ is made up by numbers that are either in the natural set $\mathbb{N}$, or their negative ($-x$) is in $\mathbb{N}$. Therefore only positive and negative integer numbers end up making up the set $\mathbb{Z}$.

Sets! ...... again

Now that we have a set notation down, we can introduce some friendly "operators" that work on sets. Rather than doing $\{a,b\}+\{c,d\}$, as "+" does not really "count up" in sets, we use the notation $\cup$. So $\{a,b\}\cup\{c,d\} = \{a,b,c,d\}$.

What if elements are repeated?

$$\{a,b\}\cup\{b,c\} = \{a,b,c\}$$

The operator of $\cup$ (union) makes a bigger set only out of the common elements.

Conversely, if we have union, we have a similar operation in $\cap$ (intersection).

$$\{a,b\}\cap\{b,c\} = \{b\}$$

We only keep the common elements between the two sets. What if there's none?

$$\{a\}\cap\{b\} = \{\}$$

We have a set with no elements, therefore the empty set mentioned above.

We have actually more operations we could do on sets, but I am going to introduce only one extra for now:

$$\{a,b\} \setminus \{b,c\} = \{a\}$$

This is the "set difference" operator. We define it as removing the common elements from the first set of the operation.

As a final "hmm" to give, what happens when we swap the order of those two sets in the above example (34) ? Is it the same result? Why not? Does the intersection also change when swapping the order?