Sets, Relations, Functions, and Cardinality Flashcards
What are “sets?”
Sets is a mathematical notion
Considered by some to be the foundation of all mathematics: “All mathematics is (just) set theory”
Things with elements have certain properties:
x is an element of the set A
x ∈ A
- Uordered collection of objects
- Not “boxes” - some have infinite sets, and sets that contain themselves
What is an extensional presentation of a set?
List the elements
eg. {1, 2, 3}
What is an intensional presentation of a set?
Given a set A, and a property P,
{x ∈ A | P(x)} is “the set of all elements of A that satisfies P
Ex:
- {x ∈ ℕ | x < 10}
- {x ∈ ℕ | x is prime}
- {x ∈ ℕ | Ǝy ∈ IN : x = 2y}
Russell’s Paradox: S = {x | x ∉ x}. Is S ∈ S?
Sets for “x is an element of the set A”
x ∈ A
How do you write that “A is a subset of B:”
A⊆B <=>df ∀x : (x ∈ A) → (x ∈ B)
A set A is a subset of another set B if all elements of the set A are elements of the set B. In other words, the set A is contained inside the set B. The subset relationship is denoted as A⊆B.
For example, if A is the set {♢,♡,♣,♠} and B is the set {♢,△,♡,♣,♠}, then A⊆B but B⊄A.
Since B contains elements not in A, we can say that A is a proper subset of B. Or if I1 is the interval [0,2] and I2 is the interval [0,1], then I2⊂I1.
How do you write that “All elements in A are also in B:”
A = B <=>df (A ⊆ B) ∧ (B ⊆ A)
How do you write “A is a proper subset of B:”
A ⊂ B <=>df (A ⊂ B) ∧ (A ≠ B)
A proper subset of a set A is a subset of A that is not equal to A. In other words, if B is a proper subset of A, then all elements of B are in A but A contains at least one element that is not in B.
For example, if A={1,3,5} then B={1,5} is a proper subset of AA. The set C={1,3,5} is a subset of AA, but it is not a proper subset of AA since C=A. The set D={1,4} is not even a subset of A, since 4 is not an element of A.
How to indicate that something is an empty set:
∅, {}
P(a, b) = {∅, {∅}, {a}, {b}, {a, ∅}, {b,∅}, {a, b}, {a, b, ∅}}
What is an intersection?
A⋂B
Contains all and only the elements of both A and B
What is a union?
A⋃B
Contains all and only the elements of A, or B, or both
What is a complement of set A?
Denoted A¯:
Contains all those elements of the universe of discourse that are not in A
What is a powerset (of A)?
P(A), “powerset of A,” the set of all the subsets of A
- Defined in terms of sets
What is an ordered pair / n-tuple?
A collection with n elements where the order matters
< a, b >, < a, a, b >
- Rather than introducing ordered pairs as another primitive notion, we can define them as sets:
< a, b > <=>df {{a}, {a, b}}
*a first to illustrate the order
What is the cross product?
A x B, “cross product or Cartesian product of A and B,” the set of all ordered pairs < a,b > consisting of the elements a ∈ A and b ∈ B
A x B <=>df { < x, y > | x ∈ A and y ∈ B}
Show that < a, b > = < c, d > iff a = c and b = d
Formula to determine the number of formations in the powerset of A with n elements?
2n
What are the elements of a relation?
What is a relation?
What are the elements of a relation? Ordered pairs!
What is a relation? A relation is a set of ordered pairs
How many relations are there between two sets *A* with *n* elements, and *B* with m elements (where *n,m* ∈ *IN* )?
2(n x m)
What are the writing convention, domain, and range for < a, b> ∈ R?
R(a, b) or aRb
- Domain: R: { a | there is some b, such that < a, b> ∈ R }
- Range R: { b | there is some a, such that < a, b> ∈ R }
What is the layman’s definition of a function?
Rules that connect inputs to outputs
What is the definition of a function in the set-theoretic view?
A function f : A -> B from A (domain) to B (range) [⊆ codomain] is a binary relation Rf on A and B, such that:
(1) The relation is single-valued
- Every element in the domain is paired with just one element in the range
(2) The domain of Rf is A (except partial functions)
- Write f(a) = b rather than Rf(a, b)
What is an injective (one-one) function?
If for each y in the range of f there is only one x,
such that f(x) = y or (< x, y> ∈ f)
If a, a’ ∈ A and a ≠ a’ then f(a) ≠ f(a’)
- Assume f(a) = f(a’)
- Show: a = a’
What is a surjective (onto) function?
If the range of f is equal to the codomain
range = codomain
What is the difference between the range and codomain?
The codomain is the set of all possible values which can come out as a result but the range is the set of values which actually comes out.
What is a bijective (one-to-one correspondence) function?
Injective and surjective
Composition: For f : A -> B and g : B -> C, f * g : A -> C**, such that g* f(a) = g(f(a))
Inverse function: f * f-1 = id
What is a powerset of the set {87, Ø, tree}
P{87, Ø, tree} = {Ø, {Ø}, {87}, {tree}, {Ø, 87}, {Ø, tree}, {Ø, 87, tree}, {87, tree}}
