Section B.6 Notation from Set Theory and Logic
In set theory, it is common to deal with statements involving one or more elements from the universe as variables. Here are some examples:
- For \(n\in\posints\text{,}\) \(n^2-6n+8=0\text{.}\)
- For \(A\subseteq[100]\text{,}\) \(\{2,8,25,58,99\}\subseteq A\text{.}\)
- For \(n\in \ints\text{,}\) \(|n|\) is even.
- For \(x\in \reals\text{,}\) \(1+1=2\text{.}\)
- For \(m,n\in \posints\text{,}\) \(m(m+1)+2n\) is even.
- For \(n\in \posints\text{,}\) \(2n+1\) is even.
- For \(n\in \posints\) and \(x\in\reals\text{,}\) \(n+x\) is irrational.
These statements may be true for some values of the variables and false for others. The fourth and fifth statements are true for all values of the variables, while the sixth is false for all values.
Implications are frequently abbreviated using with a double arrow \(\Longrightarrow\text{;}\) the quantifier \(\forall\) means “for all” (or “for every”); and the quantifier \(\exists\) means “there exists” (or “there is”). Some writers use \(\wedge\) and \(\vee\) for logical “and” and “or”, respectively. For example,
\begin{equation*}
\forall A,B\subseteq[4]\quad \bigl((1,2\in A) \wedge |B|\ge 3)\bigr)
\Longrightarrow\bigl((A\subseteq B)\vee (\exists n\in A\cup B,
n^2=16)\bigr)
\end{equation*}
The double arrow \(\iff\) is used to denote logical equivalence of statements (also “if and only if”). For example
\begin{equation*}
\forall A\subseteq[7]\quad A\cap\{1,3,6\}\neq\emptyset\iff
A\nsubseteq\{2,4,5,7\}
\end{equation*}
We will use these notational shortcuts except for the use of \(\wedge\) and \(\vee\text{,}\) as we will use these two symbols in another context: binary operators in lattices.
You have attempted of activities on this page.
