Osnovno preštevanje

Število elementov neke množice lahko v osnovi ugotovimo tako, da jih preštejemo - pregledamo vse možnosti. Ker je navadno preštevanje lahko zelo dolgotrajno opravilo, si mnogokrat pomagamo z določenimi "simetrijami" znotraj množice - z zakonitostmi, ki nam lahko zelo skrajšajo čas, potreben za preštevanje elementov.

Osnovna pravila

1. Pravilo enakosti: Če lahko iz elementov množic A in B sestavimo pare (a, b) - , - tako, da vsak element pripada natanko enemu takemu paru, potem je |A| = |B|. Povedano drugače: množici sta enako močni, če in samo če obstaja med njima Bijektivna funkcija. (Zgled: Prüferjeva zveza)
2. Pravilo vsote: |A∪B| = |A| + |B| - |A∩B| oz. moč disjunktivne unije množic je enaka moči vsote moči obeh množic odštete z močjo preseka.
3. Pravilo produkta: |AxB| = |A||B| oz. moč kartezičnega produkta množic je enaka produktu moči obeh množic.

"Računovodsko" pravilo

Definicija:

je relacija za katero velja:

in

potem je:

razbitje po prvih komponentah

razbitje po drugih komponentah

Od tod sledi:

Vsota elementov pravokotne matrike je enaka vsoti vsot po stolpcih in vsoti vsot po vrsticah.

a1,1	a1,2	...	a1,m
a2,1	a2,2	...	a2,m
...	...	...	...	...
an,1	an,2	...	an,m
		...

Predalčno (Dirichletovo) načelo

• uporabljamo za dokazovanje obstoja
• če n+1 predmetov porazdelimo po n predalih, potem sta vsaj v enem predalu vsaj 2 predmeta

Pravilo matematične indukcije

Naj bo P lastnost naravnih števil. Radi bi dokazali, da P velja za vsa naravna števila.

1. Baza indukcije: P(1).
2. Indukcijski korak: .

Če dokažemo oba dela (1.) in (2.), trditev P velja za vsa naravna števila.