Chapter 1. Set Theory and Logic Flashcards
First distributive law for sets
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Second distributive law for sets
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
DeMorgan’s laws
A - (B ∪ C) = (A - B) ∩ (A - C)
A - (B ∩ C) = (A - B) ∪ (A - C)
Definition: Rule of Assignment
also:
- domain
- range
A subset ‘r’ of a Cartesian product C x D of two sets, having the property that each element of C appears as the first coordinate of at most one ordered pair belonging to ‘r.’
domain: all c in C such that c is the first coordinate of some element in ‘r’
range: The subset of D containing all second coordinates of elements in ‘r.’
Definition: Function ‘f’
A rule of assignment ‘r’ together with a set B that contains the image of ‘r.’ The set B (which could be larger than the image set of ‘r’) is called the range.
f: A -> B implies that A is the domain and B is the range.
Definition:
- Injective (one-to-one), as a property of a function f: A -> B
- Surjective (onto)
injective: if ‘a’,’b’ in A, ‘a’ not equal to ‘b’ implies f(a) not equal to f(b)
surjective: Every element ‘b’ in the image B has at least one corresponding ‘a’ in A such that b = f(a)
Lemma 2.1: Condition for bijectivity
Let f: A -> B. If there are functions g : B -> A and h : B -> A such that g(f(a)) = a for every a in A, and g(h(b)) = b for every b in B, then f is bijective, and its inverse is g=h=f^-1
Definition: image and preimage
let f: A -> B. f(A0) where A0 is a subset of A
we denote f(A0) to be the image of A0 under f.
the preimage f^-1(B0), for B0 as a subset of B, is the set of all a in A such that f(a) in B0.
Definition: relation
A relation on a set A is a subset C of the Cartesian product A x A
notation: if C is a relation on A, then xCy is the same as (x,y) in C. Rea: “x is in the relation c to y”
Definition: an equivalence relation C on a set A
an equivalence relation is a relation with the properties:
(1) reflexivity: xCx for every x in A
(2) symmetry: if xCy then yCx
(3) transitivity: if xCy and yCz then xCz.
equivalence relations are often denoted by ~, as a replacement for C. The properties are then:
(1) x~x
(2) x~y implies y~x
(3) if x~y and y~z then x~z
Definition: An equivalence class E of A, given an equivalence relation ~ on a set A and an element x.
E = {y | y ~ x}
Lemma 3.1: When equivalence classes have overlap
Two equivalence classes are either disjoint or equal
Definition: A partition
a partition of a set A is a collection of disjoint nonempty subsets of A whose union is all of A.
Note: given any partition of A, these is exactly one equivalence relation on A, from which it can be derived, using the fact that :
the set of all equivalence classes, given an equivalence relation, is a partition
Definition: An order C relation on a set A
a relation such that we have:
(1) comparability: for every x and y in A for which x is not equal to y, either xCy or yCx.
(2) nonreflexivity: for no x in A does xCx hold
(3) transitivity: if xCy and yCz then xCz
the standard symbol for an order relation is
Definition: order type
Two sets A and B with order relations have the same order type if there is a bijection f: A ->B such that a1 < a2 implies f(a1) < f(a2)
