Antalet relationer på en mängd (Matematik/Universitet)

Se en relation som att du tilldelar ett svar, ja eller nej, till varje ordnat par du kan skapa från mängden.

Om det inte finns några krav på vad svaren ska vara, som i den du fått uträknad, är det bara välja fritt mellan 2 svar på dina 4 möjliga par, så 2*2*2*2=2^4

Ovanstående talare har gett korrekt svar men jag vidare utvecklar lite.

Givet mängd M så är varje delmängd av MxM en relation. Om M har n element ha MxM n^2 element så det finns lika många relationer på M som delmängder till en mängd med n^2 element det vill säga 2^(n^2).

Ok, tack!

Fastnade på en fråga:

"Hur många transitiva relationer finns på mängden {1,2} ?"

Så totala antalet relationer på den mängden är $2^{2^{2}} = 2^{4} = 16 s t$

Men hur beräknar jag antalet transitiva?

Blir även väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?

Vi fortsätter lite, läste frågan slarvigt.

MxM har alltså n^2 element.

Reflexiva: Av de n^2 elementen är n på formen (x,x) och dessa måste vara med. Övriga n^2-n är med eller inte med, vilket ger 2^(n^2-n) valmöjligheter.

Symmetriska: De n elementen på formen (x,x) är valfria. Övriga n^2-n delar vi upp i par (x,y) och (y,x) och har bara två val för dessa, båda med eller ingen med. Så det ger 2^n * 2^((n^2-n)/2)=2^((n^2+n)/2).

Anti-symmetriska: De n elementen på formen (x,x) är valfria. Övriga n^2-n delar vi upp i par (x,y) och (y,x) och har bara tre val för dessa, (x,y) med men inte (y,x), vice-versa eller ingen med. Så det ger 2^n * 3^((n^2-n)/2).

Transitiva: Om jag visste skulle jag publicera det i någon mycket prestigefylld tidskrift, inte här, det är nämligen inte känt hur många transitiva relationer det finns på en mängd.

Kan jag på något sätt beräkna de som inte är transitiva och sedan subtrahera dem från det totala antalet?

KriAno skrev:
Kan jag på något sätt beräkna de som inte är transitiva och sedan subtrahera dem från det totala antalet?

I så fall skulle du ju kunna beräkna de transitiva och då skulle du bli en världskänd matematiker...

Men jag menar om mängden har två element är det ju inte svårt att beräkna antalet transitiva, det svåra är en generell formel, eller ja, det blir svårt väldigt väldigt snabbt. Redan med tre element är det krångligt att räkna antalet transitiva men med två så kan du ju bruteforca dig igenom alla 16 relationer ganska snabbt.

Smutsmunnen skrev:
KriAno skrev:
Kan jag på något sätt beräkna de som inte är transitiva och sedan subtrahera dem från det totala antalet?
I så fall skulle du ju kunna beräkna de transitiva och då skulle du bli en världskänd matematiker...
Men jag menar om mängden har två element är det ju inte svårt att beräkna antalet transitiva, det svåra är en generell formel, eller ja, det blir svårt väldigt väldigt snabbt. Redan med tre element är det krångligt att räkna antalet transitiva men med två så kan du ju bruteforca dig igenom alla 16 relationer ganska snabbt.

Okej, men jag blir väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?

Hur ser det ut i en riktad graf om det bara är två element?

KriAno skrev:

Blir även väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?

De tre elementen i villkoret behöver inte vara olika.

KriAno skrev:
Smutsmunnen skrev:
KriAno skrev:
Kan jag på något sätt beräkna de som inte är transitiva och sedan subtrahera dem från det totala antalet?
I så fall skulle du ju kunna beräkna de transitiva och då skulle du bli en världskänd matematiker...
Men jag menar om mängden har två element är det ju inte svårt att beräkna antalet transitiva, det svåra är en generell formel, eller ja, det blir svårt väldigt väldigt snabbt. Redan med tre element är det krångligt att räkna antalet transitiva men med två så kan du ju bruteforca dig igenom alla 16 relationer ganska snabbt.
Okej, men jag blir väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?
Hur ser det ut i en riktad graf om det bara är två element?

Ett exempel på en transitiv relation på en mängd med två element är den tomma relationen, eller i form av en graf: två isolerade noder. Eller varje relation med bara ett element, dvs varje graf med bara en kant. Där har du redan betat av 5 stycken.

Laguna skrev:
KriAno skrev:

Blir även väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?
De tre elementen i villkoret behöver inte vara olika.

I facit står det att dessa inte är transitiva:

Men i fallet längst till höger är ju 1R2 och 2R1 samt 1R1 ? Då borde väl den vara transitiv?

Ja, men från 2R1 och 1R2 skulle det följa 2R2 om den var transitiv.

KriAno skrev:
Laguna skrev:
KriAno skrev:

Blir även väldigt förvirrad av hur det ens kan finnas en transitiv relation på en mängd av bara två element - hur går det till?
De tre elementen i villkoret behöver inte vara olika.
I facit står det att dessa inte är transitiva:
Men i fallet längst till höger är ju 1R2 och 2R1 samt 1R1 ? Då borde väl den vara transitiv?

Nej du har 2R1 och 1R2 men inte 2R2.

Smutsmunnen skrev:
Ett exempel på en transitiv relation på en mängd med två element är den tomma relationen, eller i form av en graf: två isolerade noder. Eller varje relation med bara ett element, dvs varje graf med bara en kant. Där har du redan betat av 5 stycken.

Ursäkta men jag fattar verkligen inte, hur kan en relation mellan två isolerade noder vara transitiv? (det finns väl inte ens någon relation där till att börja med?)

KriAno skrev:

Smutsmunnen skrev:
Ett exempel på en transitiv relation på en mängd med två element är den tomma relationen, eller i form av en graf: två isolerade noder. Eller varje relation med bara ett element, dvs varje graf med bara en kant. Där har du redan betat av 5 stycken.
Ursäkta men jag fattar verkligen inte, hur kan en relation mellan två isolerade noder vara transitiv? (det finns väl inte ens någon relation där till att börja med?)

En relation på M är en delmängd till MxM, den tomma mängden är en delmängd till MxM så den tomma mängden är en relation på M. Den kan illustreras grafiskt som två isolerade noder, det vill säga inga element är relaterade.

En relation på M är transitiv om:

För alla x,y,z i M ((xRy och yRz) -----> xRz)

Det viktiga är att förstå implikationen i parantesen. En implikation är sann om slutsatsen är sann eller om premissen är falsk. Det är alltså inte nödvändigt att slutsatsen är sann, det funkar även om premissen är falsk.

Den tomma relationen är transitiv eftersom premissen i implikationen (xRy och yRz) -----> xRz alltid är falsk, så implikationen är alltid sann.

Du kanske börjar ana att det är lättare att avgöra om en relation inte är transitiv. Så när är en relation inte transitiv?

Motsatsen till:

För alla x,y,z i M ((xRy och yRz) -----> xRz)

är :

Det existerar x,y,z i M sådana att (xRy och yRz) men (inte xRz).

Oj vad förvirrad jag känner mig...

Så den här relationen är transitiv?:

1R1 och 2R2

KriAno skrev:
Oj vad förvirrad jag känner mig...
Så den här relationen är transitiv?:
1R1 och 2R2

Ja.

Den är för övrigt även symmetrisk och anti-symmetrisk.

Så relationen är alltid transitiv när $x R y o c h y R z \to x R z$

det som jag rödmarkerat är falskt??

Nej den är inte automatiskt transitiv om det gäller för några x,y,z, det måste gälla för alla kombinationer av x,y och z. Det kan gälla för några ändå.

Och angående tolkning av graferna, tolka pil från x till y som ett ja-svar på xRy, så är det kanske enklare att koppla till de 16 paren.

Jag kom på ett hyfsat enkelt sätt att kolla om en relation är transitiv:

Låt A vara relationen i matrisform. Relationen är transitiv om och endast om

A^2_ij >0 -----> A_ij>0 för alla i,j.

Det vill säga, överallt där A^2 är positiv är A positiv.

Smutsmunnen skrev:
Jag kom på ett hyfsat enkelt sätt att kolla om en relation är transitiv:
Låt A vara relationen i matrisform. Relationen är transitiv om och endast om
A^2_ij >0 -----> A_ij>0 för alla i,j.
Det vill säga, överallt där A^2 är positiv är A positiv.

Oj nu hänger jag inte med... Kan du visa med något exempel så kanske jag förstår bättre?