Sets

• Definition of a set
• The objects in a set are elements
• A set is said to contain its elements
  • $a \in A$

Describing a Set

• $S = \{a, b, c, d\}$
• Ordering of elements is unimportant
• Repeating an element doesn’t change the set
• Elipses (…) can describe a set without listing all elements if the pattern is clear

Important Sets

• $\mathbb{N}$: natural numbers = $\{0, 1, 2, 3, \dots\}$
• $\mathbb{Z}$: integers = $\{\dots,-3,-2,-1,0,1,2,3,\dots\}$
• $\mathbb{Z}^{+}$: positive integers = $\{1, 2, 3, \dots\}$
• $\mathbb{R}$: real numbers
• $\mathbb{R}^{+}$: positive real numbers
• $\mathbb{C}$: complex numbers
• $\mathbb{Q}$: rational numbers

Set-Builder Notation

• Specify the property that all members of a set satisfy
  • $S = \{x \ | \ P(x)\}$
• Intervals:
  • $[a, b] = \{x | a \le x \le b\}$
  • $[a, b) = \{x | a \le x \lt b\}$
  • $(a, b] = \{x | a \lt x \le b\}$
  • $(a, b) = \{x | a \lt x \lt b\}$

Set Equality

• Two sets are equal iff they have the same elements
  • $\forall x(x \in A \iff x \in B)$
• Definition of universal set and empty set
  • Note that $\emptyset \ne \{\emptyset\}$

Set Cardinality

• Definition of finite and cardinality
• Cannot take the cardinality of an infinite set or interval

Subsets

• Definition of subset
• $A = B$ iff $A \subseteq B$ and $B \subseteq A$
• For any set S: $\emptyset \subseteq S$ and $S \subseteq S$
• Definition of proper subset

Power Set

• Definition of power set
• $B \in \mathscr{P}(A) \iff B \subseteq A$
• $|\mathscr{P}(A)| = 2^{|A|}$
• If $|A| > 0$, $\mathscr{P}(A) \ge 2$

Tuples and Cartesian Product

• Definition of tuple
• Definition of cartesian product
• $|A_1 \times A_2 \times \dots A_n| = |A_1| \cdot |A_2| \cdot \dots \cdot |A_n|$

Truth Set

• Outputs a set of elements that meet the constraints of the domain
• Denoted $TS(P, D)$

Quantifiers with Sets

• $\forall x \in A \ P(x) \equiv\forall x(x \in A \implies P(x))$
• $\exists x \in A \ P(x) \equiv \exists x(x \in A \land P(x))$

References

• Course slides §7.2: Sets
• Course slides §8.1: Power Set, Cartesian Product