Discrete Mathematics Fundamentals Lecture

Flashcards covering key concepts from sets, relations, functions, graphs, and formal languages.

What is a set in mathematics?

A well-defined collection of distinct objects considered as a single object, usually written inside curly braces { }.

Name the three key characteristics of a set.

(1) Distinct elements (no duplicates), (2) Unordered elements (order doesn’t matter), and (3) Clear membership (each element either is or is not in the set).

How is the empty set commonly denoted?

Either ∅, {} or sometimes 0 depending on the context.

Define the term subset.

A set A is a subset of B (written A ⊆ B) if every element of A is also an element of B.

When are two sets equal in terms of subsets?

If A ⊆ B and B ⊆ A, then A = B.

Is the empty set a subset of every set? Why?

Yes. ∅ ⊆ B for any set B because it contains no elements that could violate the subset condition.

Why is any set a subset of itself?

Because every element of A is trivially in A, so A ⊆ A.

Define the set of natural numbers ℕ.

The positive counting numbers 1,2,3,… (sometimes including 0 by convention).

Define the set of integers ℤ.

All natural numbers, their negatives, and 0; …,−3,−2,−1,0,1,2,3,…

Define the set of rational numbers ℚ.

Numbers expressible as p⁄q where p and q are integers and q ≠ 0 (fractions, including terminating or repeating decimals).

Define the set of real numbers ℝ.

All points on the number line, including both rational and irrational numbers.

What is the power set P(B)?

The set of all subsets of B, including ∅ and B itself.

List the elements of the power set of {1,2}.

{∅, {1}, {2}, {1,2}}.

Define the union of two sets A and B.

A ∪ B = {x | x ∈ A or x ∈ B} – all elements that are in A, B, or both.

Define the intersection of two sets A and B.

A ∩ B = {x | x ∈ A and x ∈ B} – elements common to both sets.

Define the difference A \ B.

A \ B = {x | x ∈ A and x ∉ B} – elements in A that are not in B.

Define the Cartesian product A × B.

A × B = {(x,y) | x ∈ A and y ∈ B} – the set of all ordered pairs with first entry from A and second from B.

Define the complement of a set A (relative to universal set U).

Ā = {x | x ∈ U and x ∉ A} – everything in U that is not in A.

How do you read A ∪ B in English?

"The union of set A and set B."

How do you read A ∩ B in English?

"The intersection of set A and set B."

How do you read A \ B in English?

"The difference between set A and set B (elements in A but not in B)."

What is a binary relation R from A to B?

Any subset of the Cartesian product A × B; R ⊆ A × B.

Define a function using relation terminology.

A relation f ⊆ A × B where each a ∈ A appears in exactly one ordered pair (a,b).

What is the domain of a function f: A → B?

The set of all inputs: Domain(f) = A.

What is the range (image) of a function f: A → B?

Range(f) = {b ∈ B | ∃ a ∈ A such that f(a) = b} – all actual outputs.

When is a relation not a function?

If some element of the domain is paired with more than one output in the codomain.

Define an injective (one-to-one) function.

A function in which different inputs map to different outputs; formally, if a ≠ a′ then f(a) ≠ f(a′).

Define a surjective (onto) function.

A function whose range equals its entire codomain; every element of B is hit by some a ∈ A.

Define a bijection.

A function that is both injective and surjective; establishes a perfect one-to-one correspondence between A and B.

State the reflexive property of a relation.

(a,a) ∈ R for every a in the set.

State the symmetric property of a relation.

If (a,b) ∈ R then (b,a) ∈ R.

State the transitive property of a relation.

If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R.

What is an equivalence relation?

A relation that is reflexive, symmetric, and transitive.

Define a graph G = (V,E).

A collection of vertices V and edges E where each edge connects two vertices.

What is the degree of a vertex v?

deg(v) is the number of edges incident to v.

Define a path in a graph.

A sequence of vertices where each consecutive pair is connected by an edge.

Define a cycle in a graph.

A path that starts and ends at the same vertex without repeating any other vertex.

Define a simple path.

A path in which no vertex is repeated.

When is a graph connected?

If there is a path between every pair of vertices.

What is an alphabet Σ in formal language theory?

A finite set of symbols used to build strings.

Define a string over an alphabet.

A finite sequence of symbols from that alphabet.

What is the empty string and its length?

The string ε (or "") containing zero symbols; its length is 0.

How is the length of a string w denoted?

|w| – the number of symbols in w.

Define a language in formal language theory.

A set of strings constructed from a particular alphabet that satisfy given rules or criteria.