MTH 110 Discrete Mathematics I - Basic Set Theory (Vocabulary Flashcards)

Vocabulary flashcards covering key set theory concepts from the notes.

Set

A collection of definite, distinct objects where membership is the only property; order and repetition do not matter.

Element (member) ∈

An object that belongs to a set; written as x ∈ S.

Cardinality | |

The number of elements in a set, denoted |S|.

Equality of Sets

Two sets S and T are equal if they contain exactly the same elements: ∀x, x ∈ S ⇔ x ∈ T.

Subset ⊆

A ⊆ B if every element of A is also an element of B.

Proper Subset

B ⊊ A if B ⊆ A and B ≠ A (B is a subset of A that is not equal to A).

Empty Set

The set with no elements; denoted ∅; ∅ ⊆ A for any A; ∅ is unique.

Universe

A universal set U containing all objects under consideration; operations like complement depend on U.

Union

A ∪ B is the set of elements that are in A or in B (or both).

Intersection

A ∩ B is the set of elements that are in both A and B.

Complement

A^c (relative to U) is the set of elements of U that are not in A.

Difference

A \ B is the set of elements in A but not in B; equivalently A ∩ B^c.

Real Numbers (R)

The set of all real numbers (numbers on the real number line).

Positive Real Numbers

R+ = {x ∈ R | x > 0}.

Natural Numbers

N = {0, 1, 2, 3, …}.

Positive Naturals

N+ = {1, 2, 3, …}.

Integers

Z = {…, -2, -1, 0, 1, 2, …}.

Rational Numbers

Q = {p/q | p,q ∈ Z, q ≠ 0}.

Complex Numbers

C = {x + iy | x,y ∈ R}.

Closed Interval

[a,b] = {x ∈ R | a ≤ x ≤ b} (all numbers between a and b including endpoints).

Open Interval

(a,b] = {x ∈ R | a < x ≤ b} or (a,b) = {x ∈ R | a < x < b} (endpoints excluded accordingly).

Half-Open Interval

[a,b) or (a,b] (one endpoint included, the other excluded).

Singleton

A set with one element: {x}.

Doubleton

A set with two distinct elements: {x, y} with x ≠ y.

Predicate

A statement about a variable x that can be true or false, used in set-builder notation P(x).

Set-Builder Notation

T = {x ∈ S | P(x)} denotes the subset of S consisting of elements that satisfy P.

Symmetric Difference △

Given 2 sets A & B the symmetric Difference of A & B denoted, A & B is everything in A which is not in B

Disjoint Sets

Two sets are called disjoint if and only if they have no elements in common. Formally: Given two sets A and B they are disjoint if and only if A ∩B = ∅.

Mutually/Pairwise Disjoint Sets

A collection of sets A1, A2, . . . , An are mutually disjoint or pairwise disjoint if and only if every pair of sets is disjoint. Formally: for all i, j = 1, . . . , n, Ai ∩Aj = ∅ whenever i ≠ j.

Set Partition

A collection of non-empty sets {A1, A2, . . . , An} is a partition of a set A if A = A1 ∪A2 ∪. . . ∪An; and A1, A2, . . . , An are mutually disjoint.

Power Set

Given a set A, the power set of a set A, denoted P(A), is the set of all subsets of A. Formally: for any sets A and X, X ∈P(A) if and only if X ⊆A.

Cardinality of the power set

Let S be a finite set with |S| = n. Then |P(S)| = 2n.

Characteristic string

For each T ∈P(S), define the characteristic string a1a2...an of length n, where ai = 1 if si ∈T; ai = 0 otherwise.

Subset

A subset is a set T such that T ⊆ S.

Set Identities

Complex Compound Sets can be created using Complement, Union, and Intersection.

Counterexample

To show a set relation is False, find explicit sets that do not satisfy the supposed identity.

Distributive Law

(A ∪B) ∩C = (A ∩C) ∪(B ∩C) is a true set identity.

Commutative laws

A ∩B = B ∩A and A ∪B = B ∪A.

Associative laws

A ∩(B ∩C) = (A ∩B) ∩C and A ∪(B ∪C) = (A ∪B) ∪C.

Identity laws

A ∩U = A and A ∪φ = A.

Complement laws

A ∪Ac = U and A ∩Ac = φ.

Double Complement law

(Ac)c = A.

Idempotent laws

A ∩A = A and A ∪A = A.

DeMorgan's laws

(A ∩B)c = Ac ∪Bc and (A ∪B)c = Ac ∩Bc.

Universal bound laws

A ∪U = U and A ∩φ = φ.

Absorption laws

A ∪(A ∩B) = A and A ∩(A ∪B) = A.

Negation of U and φ

U c = φ and φc = U.

Inclusion of Intersection

A ∩B ⊆A and A ∩B ⊆B.

Inclusion of Union

A ⊆A ∪B and B ⊆A ∪B.

Transitivity of inclusion

If A ⊆B and B ⊆C then A ⊆C.

Alternate Representation of Set Minus

A −B = A ∩Bc.

Set Difference

A −(A ∩B) = A ∩(Ac ∪Bc).

Universal Bound

The universal bound states that ∅ ∩ ∅ = ∅.