Sets and Logic Cheat Sheet – IMT DeCal

# Sets and Logic Cheat Sheet

by Sagnik Bhattacharya, Suraj Rampure
Last modified: March 21, 2019

This chart summarizes all of the notation we’ve seen so far regarding sets, functions, and propositional logic.

Symbol Name Description Example
$\{ \}$ set used to define a set $S = \{ 1, 2, 3, 4, … \}$
$\in$ in, element of used to denote that an element is part of a set $1 \in {1, 2, 3}$
$\not \in$ not in, not an element of used to denote than an element is not part of a set $4 \not \in {1, 2, 3}$
$\mid S \mid$ cardinality used to describe the size of a set (refers to the number of unique elements if the set is finite) $S = \{1, 2, 2, 2, 3, 4, 5, 5 \}$
$\mid S \mid = 5$
$:$, $\mid$ such that used to denote a condition, usually in set-builder notation or in a mathematical definition $\{x^2 : x + 3 \text{ is prime}\}$
$\subseteq$ subset set $A$ is a subset of set $B$ when each element in $A$ is also an element in $B$ $A = \{ 1, 2 \}$
$B = \{ 2, 1, 4, 3, 5 \}$
$A \subseteq B$
$\subset$ proper subset set $A$ is a proper subset of set $B$ when each element in $A$ is also an element in $B$ and $A \neq B$ $A = \{ 1, 2, 3, 4, 5 \}$
$B = \{ 2, 1, 4, 3, 5 \}$
$A \subseteq B$ is true but $A \subset B$ is not true
$\supseteq$ superset set $A$ is a superset of set $B$ when $B$ is a subset of $A$ $A = \{ 2, 4, 6, 7, 8 \}$
$B = \{ 2, 4, 8 \}$
$A \supseteq B$
$\cup$ union a set with the elements in set $A$ or in set $B$ $A = \{1, 2\}$
$B = \{2, 3, 5\}$
$A \cup B = \{1, 2, 3, 5\}$
$\cap$ intersection a set with the elements in set $A$ and in set $B$ $A = \{1, 2\}$
$B = \{2, 3, 5\}$
$A \cap B = \{2\}$
$\emptyset$ the empty set the set with no elements $\{1, 2, 3\} \cap \{4, 5, 6\} = \emptyset$
$-$, $\backslash$ set difference elements in set $A$ that are not in $B$ $A = \{1, 2, 3, 4\}$
$B = \{2, 3, 5, 8\}$
$A - B = \{1, 4\}$
$B - A = \{5, 8\}$
$\times$ Cartesian product a set containing all possible combinations of one element from $A$ and one element from $B$ $A = \{1, 2\}$
$B = \{3, 4\}$
$A \times B = \{(1, 3), (2, 3), (1, 4), (2, 4)\}$
$B \times A = \{(3, 1), (3, 2), (4, 1), (4, 2)\}$
$A^c$ complement a set containing the elements of the universe $U$ that are not in set $A$ $U = \{1, 2, 3, 4, 5\}, A = \{2, 4\} \implies A^c=\{1, 3, 5\}$
$f : A \rightarrow B$ function the function $f$ maps elements of the set $A$ to elements of the set $B$; $A$ is the domain and $B$ is the codomain $f(x) = x^2+5$ is an example of a function $f : \mathbb{R} \rightarrow \mathbb{R}$
$f : x \mapsto x^3$ mapping/function the function maps any $x$ to $x^3$; this notation refers to elements of sets rather than sets themselves $f(x) = x^2+5$ can be written as $f: x \mapsto x^2+5$
$\mathbb{N}$ the set of natural numbers the set of naturals numbers starting at $1$ $\mathbb{N} = \{1, 2, 3, …\}$
$\mathbb{N}_0$ the set of whole numbers the set of whole numbers starting at $0$ $\mathbb{N}_0 = \{0, 1, 2, 3, …\}$
$\mathbb{Z}$ the set of integers the union of the whole numbers with their negatives $\mathbb{Z} = \{…, -3, -2, -1, 0, 1, 2, 3, …\}$
$\mathbb{Q}$ the set of rational numbers the set of all possible combinations of one integer divided by another, with the latter integer being non-zero, i.e., $\mathbb{Q} = \{ \frac{p}{q} : p, q \in \mathbb{Z}, q \neq 0\}$ $\{\frac{1}{2}, \frac{5}{14}, \frac{-17}{3}\} \subset \mathbb{Q}$
$\wedge$ conjunction/and $P \wedge Q$ is true if both $P$ and $Q$ are true if $P = (2 \text{ is prime}), Q = (8 \text{ is a perfect cube})$ then $P \wedge Q$ is true
$\vee$ disjunction/or $P \vee Q$ is true if either $P$ or $Q$ is true if $P = (2 \text{ is prime}), Q = (4 \text{ is a perfect square})$ then $P \vee Q$ is true
$\neg$ negation $\neg P$ is true if $P$ is false and vice versa if $P = (\text{35 is prime})$ then $\neg P$ is true
$\implies$ implication $P \implies Q$ means that $Q$ is true whenever $P$ is true (but it does not say anything about what happens when $P$ is false) if $P = (x \text{ is divisible by 4})$, $Q = (x \text{ is even})$ then $P \implies Q$ (but note that $P \nrightarrow Q$)
$\iff$ if and only if (iff) $P \implies Q$ and $Q \implies P$ if $P = (\text{it is new year})$ and $Q = (\text{it is January 1})$ then $P \iff Q$
$\forall$ for all refers to all the elements in a set if $A = \{2, 4, 10\}$ then $x \in \mathbb{N} \text{ } \forall x \in A$
$\exists$ there exists refers to the existence of at least one of something $\exists x \in \mathbb{N}_0 : x = -x$
$\oplus$ XOR either $P$ is true or $Q$ is true but not both if $P = (\text{Donald Trump is a Democrat})$ and $Q = (\text{Hillary Clinton is a Democrat})$ then $P \oplus Q$ is true, but if $P = (\text{Donald Trump is a Republican})$ then $P \oplus Q$ is false