1.1 Sets & Subsets

set

a well-defined collection of objects

elements or members

the objects in a set

x ∈ A

x is an element of the set A

x ∉ A

x is not an element of the set A

finite set

set with a limited number of elements: the order of element does not matter, and repeated elements do not change the set.

• ex: {1, 2, 3} = {3, 2, 1} = {1, 3, 2, 3}

{x | P(x)}

set-builder notation: specifies a property (P) shared by all the elements of a set.

• “collect all x’s such that x has property p”

ℤ⁺

the positive integers: {x | x is a positive integer} = {1, 2, 3,…}

ℕ

the natural numbers: {x | x is a natural number} = {0, 1, 2, 3, …}

ℤ

the integers: {x | x is an integer} = {…, -2, -1, 0, 1, 2,…}

ℚ

the rational numbers: {a/b | a, b ∈ ℤ, b ≠ 0}

• {x | x is a fraction a/b where a and b are integers, and b does not equal zero}

ℝ

the real numbers: {x | x is a real number}

• real numbers are those that can be placed on a number line, including rational and irrational numbers such p

∅ or { }

empty set notation: no elements in the set.

equality of sets

two sets A and B are equal, written A = B, if and only if they contain exactly the same elements.

A ⊆ B

A and B are sets. A is a subset of B if every element of A is also an element of B.

A ⊈ B

A and B are sets. A is not a subset of B if any element of A is not an element of B.

ℤ ⊆ ℚ

every integer is rational.

A ⊆ A

every set is a sub set of itself.

A ⊇ B

A is a superset of B if every element of B is also an element of A: therefore B is a subset of A.

∅ ⊆ A

for every set A, the empty set is a subset.

A = B ← → A ⊆ B and B ⊆ A

equality: two sets A and B are equal if and only if each is a subset of the other.

finite set: n ∈ N

a set with a countable number of elements, n ∈ N

cardinality |A|

is the number (n) of distinct elements in set A.

𝒫(A)

is the power set of A, which contains all possible subsets of A, including the empty set, and each combination of the elements (order does not matter).

|𝒫(A)| powerset cardinality

the number of elements in the powerset of A given by 2 to the power of the cardinality |A| of the set A.

• ex: if cardinality of A is |A| = 3, then 2³=8 is powerset cardinality.