This course covers the fundamentals of discrete mathematics with a focus on proof methods. Topics include: propositional and predicate logic, notation for modern algebra, naive set theory, relations, functions and proof techniques.
The number of elements of the set $X$, written $|X|$, is its cardinality.
From the definition, $|{1,2,3}|=3$. Also, $|\varnothing|=0$.
Definition 1.2 1. Given sets $X$ and $Y$, we say $X$ is a subset of $Y$ if every element of $X$ is also an element of $Y$. We write $X \subseteq Y$, and refer to the symbol $\subseteq$ as inclusion.
- If there is an element of $Y$ that is not an element of $X$, we say that $X$ is a proper subset of $Y$, written $X \nsubseteq Y$. Note that if $X \varsubsetneqq Y$, then we also have that $X \subseteq Y$.
Example $1.2$ The set
$$
{1,3,4} \subseteq{1,2,3,4}
$$
and it is also the case that
$$
{1,3,4} \varsubsetneqq{1,2,3,4}
$$
These are two equations in two unknowns, and we solve them below
Subtracting (1.4) from (1.3), we obtain
$$
V_{1}(H)-V_{1}(T)=\Delta_{0}\left(S_{1}(H)-S_{1}(T)\right)
$$
so that
$$
We may put sets together using several operations.
Definition $1.6$ Let $X$ and $Y$ be sets in a universe $U$.
- The intersection of $X$ and $Y$, written $X \cap Y$, is the set consisting of elements in both $X$ and $Y$. We write
$$
X \cap Y={u \in U: u \in X \text { and } u \in Y}
$$ - The union of $X$ and $Y$, written $X \cup Y$, is the set consisting of elements in $X$ or $Y$. We write
$$
X \cup Y={u \in U: u \in X \text { or } u \in Y}
$$ - The difference of $X$ with $Y$, written $X \backslash Y$, is the set consisting of elements in $X$ but not in $Y$. We write
$$
X \backslash Y={u \in U: u \in X \text { and } u \notin Y}
$$ - The complement of $X$, written $X^{c}$, is the set of elements of $U$ not in $X$. We write
$$
X^{c}={u \in U: u \notin X}
$$
CMTH110 COURSE NOTES ：
Definition 1.1. A statement (or proposition) is a sentence that is either true or false but not both.
Examples of statements:
- $p=$ “Alice is 12 years old”,
- $q=$ “Bob ate pizza for dinner yesterday”,
- $r=” 3 \cdot 3=9$ “,
- $s=” 2 \cdot 4=9 “$.
Examples of non-statements: - “Is the sky blue?” (question)
- ” $x^{2}+y^{2}=13 “$ (for some values of $x$ and $y$ the proposition is true, whereas for others it is false).
Compound Statements
We can make new statement from old ones using operators like “not”, “and”, “or”, “if then”. There are a few simple examples: - “Alice is not 12 years old” $(\sim p)$,
- “Bob ate pizza for dinner yesterday and $3 \cdot 3=9$ ” $(q \wedge r)$.
Compound statements (since they are (regular) statements as well) must have well-defined truth values – they must be either true or false. We can write down a table of truth values for compound statements based on the truth values of component statements.
Definition 1.2. The negation of a statement $p$ (denoted $\sim p$ ) is true if $p$ is false. If $p$ is true, then $\sim p$ is false.