Discrete Structures Week 9 Flashcards
cardinality
the number of elements in a set
aleph zero
the cardinality of n
countable
set is either finite or its cardinality is equal to the cardinality of N
there exists a bijection from S to N
but not every map from S to N is a bijection
is Q and R countable
Q is
R is not
power set
all the subsets
|A| = n then |P(A)| = 2^n
them of |A| and |P(A)|
for finite or infinite
|A| < |P(A)|
if A is finite, then |P(A)| = 2^n
|P(N)| is uncountable
|N| is the smallest infinite cardinality
|N| < |R| so there is no set S such that |N| < |S| < |R|
pigeonhole principle
not injective, not room for each pigeon to have own hole
If A and B are finite sets, if |A| > |B| then there is no injection from A to B
generalized pigeonhole principle
suppose that N objects are distributed into k boxes
1. there is a box containing at least N/k objects
2.there is a box with at most N/k objects
addition
if A n B = empty
|A U B| = |A|+|B|
subtraction
if A is a subset of B
|B\A|=|B|-|A|
multiplicity
|AxB| = |A|x|B|
power rule
|A|=n, |B|=l
how many maps from A->B
|B|^|A| = l^n
inclusion-exclusion principle
A, B finite sets
if A n B != empty
|A U B|= |A|+|B| - |A n B|
string length with 2 zeros at end and start problem
:)
algin 5 people in rows problem
:)
how many injections
There are n(n-1)(n-2)….(n-m+1) injections from A to B if |A| = m and |B| =n
distributing tasks among people problem
:)
what is |A|=|B| with an injection, proof and theorem
proof in notes :)
if A, B are finite sets such that |A| =|B| and f:A->B then the following are equivalent
1. f is injective
2.f is surjective
3.f is bijective
