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
:)
