matematikk.net

Litt generelt spørsmål:

Gitt en mengde A med m elementer, kan man si med en gang hvor mange relasjoner det finnes på mengden? Og hva med ekvivalensrelasjoner?

Når det gjelder antall relasjoner så ser jeg for meg at for hvert element x i A, så kan det mappes til m andre elementer. Men det virker litt rart at det blir [tex]m^m[/tex] relasjoner?

Og hvis vi innfører en ny mengde B med n elementer, kan vi si hvor mange relasjoner det finnes fra B til A, eller A til B?

Her tenker jeg at for hvert element x i A, så kan det mappes til n elementer i B. Dette gir [tex]n^m[/tex] for A til B og [tex]m^n[/tex] for B til A. Tenker jeg feil her?

På forhånd takk!

Antall binære relasjoner på en mengde [tex]A=\{a_i\}_{i=1}^m[/tex] blir vel [tex]2^{m^2}[/tex] ? Se for deg en [tex]m\times m[/tex] matrise der hver entry er enten 0 eller 1 avhengig av om det fins en relasjon mellom [tex]a_i[/tex] og [tex]a_j[/tex]. F.eks. dersom [tex]a_1Ra_2[/tex] så er elementet i rad 1 kolonne 2 lik 1.

En generell relasjon behøver ikke være hverken symmetrisk, refleksiv eller transitiv, så hvert element i matrisa er uavhengig og kan enten være 0 eller 1. Siden det er [tex]m^2[/tex] elementer i matrisa kan det være [tex]2^{m^2}[/tex] ulike relasjoner på mengden [tex]A[/tex].

For ekvivalensrelasjoner blir naturligvis enkelte elementer avhengige av hverandre, og antallet mulige relasjoner færre.

EDIT:

Hmm. Jeg så på det som at hvert element i A kan mappes til så mange elementer som det er i A, altså med tilbakelegging.

Når du får [tex]2m^2[/tex], har du ikke da telt refleksive relasjoner [tex](a_i , \ a_i)[/tex] to ganger?

Aleks855 wrote:Hmm. Jeg så på det som at hvert element i A kan mappes til så mange elementer som det er i A, altså med tilbakelegging.

Når du får [tex]2m^2[/tex], har du ikke da telt refleksive relasjoner [tex](a_i , \ a_i)[/tex] to ganger?

Det skal være 2 opphøyd i m^2, ikke 2*m^2..

Ah, da ble det mer fattelig. Ser jeg har formulert meg litt feil her, men det ble riktig til slutt.

Takker!