An example:

Text version:

Are there numbers with the following property: tripling it and adding 3 gives the same result as squaring it?

Using a placeholder:

Is there is a set of number \(x\) with the following property: doubling \(x\) and adding 3 gives the same result as squaring \(x\)?

Collecting the mathematical terms:

\[\left\{\forall x \mid 2x + 3 = x^2\right\}\] Reading the equation:

A Set of numbers for all values of \(x\) where \(3x + 3\) equals \(x\) squared.

Solving the equation:

\[\eqalign{(x-3)(x + 1) &=& x^2-2x -3 &=& 0\\ x &=& \{3,-1\}\\ }\]

2. The Language of Sets:

\[\begin{matrix}\quad \LaTeX\quad & \rm Symbol &\quad\rm Description\quad\\ \hline \backslash\tt forall & \quad\forall\quad & \rm For\ all,\ Every\\ \backslash\tt exists & \quad\exists\quad & \rm There\ exists\\ \backslash\tt mid & \quad\mid\quad & \rm Given,\ Where,\ Such\ that \\ \backslash\{\backslash\} &\{\ \}& \rm A\ set\ (Unordered)\\ \backslash\tt dots & \dots & \rm And\ so\ on\\ \backslash\tt in & \in &\rm Element\ in;\ Member\ of\\ \backslash\tt notin & \notin & \rm Not\ a\ member;\ Not\ in \\ \backslash\tt subset & \subset & \rm Subset\ of\\ \backslash\tt subseteq & \subseteq & \rm Subset\ or\ equal\ to \\ \backslash\tt neq & \neq & \rm Negate;\ Not\\ \backslash\tt emptyset& \emptyset & An empty set\\ \end{matrix}\]

Types of statements

• statement: any declarative sentence which is either true or false
• atomic statement: basic statement that cannot be divided into smaller statements
• a molecular statement: a composite statement made from substatements

Example:

• The moon is made of cheese.

• 42 is a perfect square.

• Every even number greater than 2 can be expressed as the sum of two primes.

• \(3 + 7 = 12\)

• Would you like some cake?

• The sum of two squares.

• \(1 + 3 + 5 + 7 + \dots + 2n + 1\)

• Go to your room!

• \(3 + x = 12\)

Statements vs Non-statements

1. Some say the end is near, and some say we’ll see Armageddon soon.
2. Mom’s coming ’round to put it back the way it ought to be.
3. Learn to swim.
4. Everybody can be fooled sometimes.
5. Every natural number greater than 1 is either prime or composite.
6. Go to your room!
7. The Broncos will win the Super Bowl, or I’ll eat my hat.
8. This shirt is not black.

An example

Let \(P(x,y)\) be the predicate where Person \(x\) can be fooled at Time \(y\).
Match each statement with its representation in symbols

• A. Some people can be fooled all of the time.
• B. Everyone can be fooled sometimes.
• C. It is always true that some people can be fooled.
• D. Sometimes everyone can be fooled.
• E. Someone is never fooled.
• F. Everyone is never fooled.
• G. Someone is not fooled sometimes.
• H. Everyone is not fooled sometimes.

Solutions

• A: \(\quad \forall y \exists x \mid P(x,y)\)
• B: \(\quad \exists y \forall x \mid P(x,y)\)
• C: \(\quad \forall y \exists x \mid P(x,y)\)
• D: \(\quad \exists y \forall x \mid P(x,y)\)
• E: \(\quad \forall y \exists x \mid \neg P(x,y)\)
• F: \(\quad \forall y \exists x \mid \neq P(x,y)\)
• G: \(\quad \exists y \exists x \mid \neq P(x,y)\)
• H: \(\quad \exists y \forall x \mid \neq P(x,y)\)

Standard sets:

\[\small\eqalign{\rm Sym&\rm Set names &\rm \hbox{Math definition}\\ \hline \emptyset &\hbox{empty set} & \emptyset = \{\}\\ \mathbb N & \hbox{all natural numbers} &\mathbb N = \{1, 2, \dots, \infty\} \\ \mathbb W & \hbox{all natural numbers} &\mathbb W = \{0, 1, 2, \dots, \infty\} \\ \mathbb Z & \hbox{all integers} & \mathbb Z = \left\{{-\infty\dots,-2,-1,\atop 0, 1, 2, \dots \infty}\right\}\\ \mathbb Q & {\hbox{all rational numbers}\quad\atop {}^\hbox{(quotients of integers)}}& \mathbb Q = \left\{\frac{\forall x}{\forall y} \mid x\in \mathbb Z, y \in \mathbb Z \right\}\\ \mathbb R & \hbox{all real numbers} &\mathbb R =\left\{{-\infty\dots,-2,-1,\atop 0,1,2,\dots\infty}\right\} \\ \cal U & \hbox{Universe} & \\ }\]

3. The Set-Roster and Set-Builder Notations:

\[\left\{x \in S \mid P(x)\right\}\] ### Using Set-Builder Notations

• \(\{x \in \mathbb R \mid -2 \le x \le 5\}\)
• \(\{x \in \mathbb Z \mid -2 \le x \le 5\}\)
• \(\{x \in \mathbb N \mid -2 \le x \le 5\}\)

4. Subsets:

If A and B are sets, then A is called a subset of B, written \(A \subset B\), if, and only if, every element of A is also an element of B.

\[A \subset B \mid (\forall a \in A) \in B\]

If \(A\) and \(B\) are sets, then \(A\) is called a subset of \(B\), written \(A \subset B\), if, and only if, every element of \(A\) is also an element of \(B\).

\[A \subset B \mid (\exists a \in A) \notin B\]

5. Cartesian Products: Between ordered sets

\[\eqalign{S&=& A \times B\\ &=& \left(\forall a\in A, \forall b \in B \mid (a,b)\right)\\ &=& \left(\begin{matrix}(1,4), (2,4), (3,4),\\ (1,5), (2,5), (3,5)\end{matrix}\right)\\}\]

If \(n = |A|\) and \(m= |B|,\quad \therefore \quad n\cdot m = |A \times B|\)

6. Strings:

Let n be a positive integer. Given a finite set A, a string of length n over A is an ordered n-tuple of elements of A written without parentheses or commas.

The elements of A are called the characters of the string.

• The null string over A is defined to be the “string” with no characters. It is often denoted \(\lambda\) and is said to have length 0.

• If \(A = \{0, 1\}\), then a string over A is called a bit string

Example:

Let \(A = \{a, b\}\). List all the strings of length 3 over A with at least two characters that are the same.

\[aab, aba, baa, aaa, bba, bab, abb, bbb\]

7. The Language of Relations:

• often act as black boxes that cause or reject a relationship to form between codomains (input).

• Can be represented as a variable \(R\)

\[\eqalign{Given\ A &=& \{1, 2\};\ B = \{1, 2, 3\};\ \{(x,y)\} \subset A \times B;\ \forall (x,y) \in R;\ \mid \\ && R = \left(\frac{x + y}{2}\right) mod\ 2 = 0\\ \\ A \times B &=& \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)\}\\ (x,y) \in R &=& \{(1,1), (1,3), (2,2)\}\\ (x,y) \notin R &=& \left\{(1,2),(2,1)\right\} }\]

\[(x,y) \in R \mid x - y\]

8. Functions

A relation F from A to B is a function if, and only if:

1. Every element of A is the first element of an ordered pair of F.
2. No two distinct ordered pairs in F have the same first element.

NonFunctions

Functions

Reversible

Non-reversible

10. The Logic of Compound Statements:

An Example

• A: \(\quad\) If Florence eats her vegetables, then she can have a cookie.
• B: \(\quad\) Florence must eat her vegetables to get a cookie.

Application question

• When Florence eats her vegetables, does she get a cookie?

Answer

• Statement A: Florence gets a cookie.
• Statement B: Florence might not get a cookie. (Other conditions may be required)

Standard Logic Relationships

\[\eqalign{LaTeX &\quad&\rm Sym&\quad& \hbox{Logic operator}\\ \hline \backslash\tt lor &&\lor &\quad& \hbox{OR}\\ \backslash\tt land &&\land&&\hbox{AND}\\ \backslash\tt otimes &&\otimes&&\hbox{XOR}\\ \backslash\tt neg &&\neg&&\hbox{NOT}\\ }\]