Är relationen en ekvivalensrelation? Binära relationer - MT1102: Linjär algebra (introduktion till matematik) - Affärsinformatik

Anteckning: Många nya begrepp beskrivs, såsom ekvivalensrelationen, den partiella ordningsrelationen och isomorfa partiella mängder. Flera satser om detta ämne bevisas med detaljerade förklaringar, grafer och exempel. Ett stort antal exempel på delorder ges. Flera konstruktioner beskrivs som gör att man kan konstruera beställda set från andra. Föreläsningen präglas av många uppgifter för självständig lösning

Ekvivalens och ordningsrelationer

Låt oss komma ihåg det binär relation på en mängd kallas en delmängd; istället för skriver ofta.

En binär relation på en mängd kallas ekvivalensförhållande, om följande egenskaper är uppfyllda:

Följande uppenbara men ofta använda påstående är sant:

Sats 11. (a) Om en mängd är uppdelad i en union av disjunkta delmängder, då är relationen "att ligga i samma delmängd" en ekvivalensrelation.

(b) Vad som helst ekvivalensförhållande erhålls på det beskrivna sättet från någon partition.

Bevis. Det första påståendet är ganska uppenbart; Vi kommer att ge ett bevis för det andra så att det kan ses var alla punkter i definitionen av ekvivalens används. Så låt vara ett ekvivalensförhållande. Tänk på det för varje element ekvivalensklass- uppsättningen av allt som är sant.

Låt oss bevisa att för två olika , sådana uppsättningar antingen inte skär varandra eller sammanfaller. Låt dem skära varandra, det vill säga ha ett gemensamt element. Sedan och , varifrån (symmetri) och (transitivitet), samt (symmetri). Därför, för något av det följer (transitivitet) och vice versa.

Det återstår att notera att, på grund av reflexivitet, tillhör varje element den klass som det definierar, det vill säga att hela uppsättningen är uppdelad i disjunkta klasser.

78. Visa att kraven på symmetri och transitivitet kan ersättas med ett: (med bibehållen krav på reflexivitet).

79. Hur många olika ekvivalensrelationer finns på uppsättningen ?

80. Två ekvivalensrelationer ges på mängden, betecknade med och , som har respektive ekvivalensklasser. Kommer deras skärningspunkt att vara en ekvivalensrelation? Hur många klasser kan han ha? Vad kan man säga om enande av relationer?

81. (Ramseys sats) Mängden av alla - elementära delmängder av en oändlig mängd är indelad i klasser (, - naturliga tal). Bevisa att det finns oändlig uppsättning, där alla elementära delmängder tillhör samma klass.

(Detta är uppenbart: om oändlig uppsättningär uppdelad i ett ändligt antal klasser, då är en av klasserna oändlig. När och påståendet kan formuleras på följande sätt: från en oändlig mängd människor kan man välja antingen oändligt många parvisa bekanta eller oändligt många parvisa främlingar. Den slutliga versionen av detta uttalande - att det bland alla sex personer finns antingen tre parvisa bekanta eller tre parvisa främlingar - är ett välkänt problem för skolbarn.)

Uppsättningen av ekvivalensklasser kallas faktor - många mängder av ekvivalensrelation. (Om relationen överensstämmer med ytterligare strukturer på , blir resultatet faktorgrupper, faktorringar etc.)

Vi kommer att stöta på ekvivalensrelationer mer än en gång, men för närvarande är vårt huvudämne ordningsrelationer.

En binär relation på en mängd kallas partiell orderrelation, om följande egenskaper är uppfyllda:

(I enlighet med traditionen använder vi en symbol (snarare än en bokstav) som tecken på en ordningsrelation.) En mängd med en partiell ordningsrelation angiven på kallas delvis beställd.

De säger att två element delvis beställd set jämförbar, om eller . Observera att definitionen av en partiell ordning inte kräver att två element i uppsättningen är jämförbara. Genom att lägga till detta krav får vi definitionen linjär ordning (linjärt ordnad uppsättning).

Här är några exempel på delbeställningar:

  • Numeriska mängder med den vanliga ordningsrelationen (här blir ordningen linjär).
  • På uppsättningen av alla par av reella tal kan vi introducera delordning, med tanke på att , om och . Denna ordning kommer inte längre att vara linjär: paren är inte jämförbara.
  • På en uppsättning funktioner med riktiga argument och värden kan du ange delordning, med tanke på att om inför alla. Denna ordning kommer inte att vara linjär.
  • På uppsättningen av positiva heltal kan vi bestämma ordningen genom att överväga att , om delar . Denna ordning kommer inte heller att vara linjär.
  • Relationen "alla primtalsdelare av ett tal är också en divisor av ett tal" kommer inte att vara en ordningsrelation på uppsättningen positiva heltal (den är reflexiv och transitiv, men inte antisymmetrisk).
  • Låt vara en godtycklig uppsättning. Sedan, på mängden av alla delmängder av mängden, kommer inkluderingsrelationen att vara en partiell ordning.
  • På bokstäverna i det ryska alfabetet bestämmer traditionen en viss ordning (). Denna ordning är linjär - för två bokstäver kan du se vilken som kommer först (om nödvändigt genom att titta i ordboken).
  • Definierat i ord från det ryska alfabetet lexikografisk ordning (som i en ordbok). Det kan formellt definieras enligt följande: om ett ord är början av ordet , då (till exempel ). Om inget av orden är början på ett annat, titta på den första bokstaven i den ordning som orden skiljer sig åt: då blir ordet där denna bokstav är mindre i alfabetisk ordning mindre. Denna ordning är också linjär (vad skulle ordbokskompilatorer annars göra?).
  • Jämställdhetsrelationen () är också partiell orderrelation, för vilka inte två olika element är jämförbara.
  • Låt oss nu ge ett vardagligt exempel. Låt det bli en massa kartonger. Låt oss införa ordning på den, med tanke på att om lådan passar helt inuti lådan (eller om och är samma låda). Beroende på uppsättningen av lådor kan denna ordning vara linjär eller inte.

I. Indelning i klasser. Ekvivalensförhållande

Definition 2.1. Låt oss kalla utbytbara de och endast de objekten i en given mängd M som har samma uppsättning formella egenskaper som är väsentliga i en given situation.

Låt oss beteckna med M x mängden av alla objekt som är utbytbara med objektet x. Det är uppenbart att x M x och föreningen av alla M x (för alla möjliga x från M) sammanfaller med den kompletta uppsättningen M:

Låt oss låtsas som det. Det betyder att det finns något element z så att det samtidigt tillhör och och. Så x är utbytbart med z och z är utbytbart med y. Därför är x utbytbart med y, och därför med vilket element av. Således. Den omvända omkopplingen visas på samma sätt. De uppsättningar som förekommer i föreningen (2.1) korsar sig alltså inte eller sammanfaller helt.

Definition 2.2. Vi kommer att kalla ett system med icke-tomma delmängder (M 1, M 2,...) av en uppsättning M en partition av denna uppsättning om

Själva uppsättningarna kallas partitionsklasser.

Definition 2.3. En relation c på en mängd M kallas en ekvivalens (eller ekvivalensrelation) om det finns en partition (M 1, M 2,...) av mängden M så att (x, y) gäller om och endast om x och y tillhör någon allmän klass Mi för en given partition.

Låt (M 1 , M 2 ,….) vara en partition av mängden M. Baserat på denna partition bestämmer vi relationen från c till M: (x, y), om x och y tillhör någon allmän klass M i av denna partition. Uppenbarligen är relationen med en likvärdighet. Låt oss anropa med ekvivalensrelationen som motsvarar den givna partitionen.

Definition 2.4. Om vi ​​i varje delmängd M i väljer elementet x i som finns i det, kommer detta element att kallas standarden för varje element y som ingår i samma mängd Mi. Per definition, låt oss anta att relationen c* "att vara en standard" (xi, y) är uppfylld

Det är lätt att se att ekvivalensen c som motsvarar en given partition kan definieras enligt följande: (z, y) om z och y har en gemensam standard (xi, z) och (xi, y).

Exempel 2.1: Betrakta som M mängden heltal icke-negativa tal och ta dess partition i en uppsättning M 0 med jämna tal och en uppsättning M 1 med udda. Motsvarande ekvivalensrelation på mängden heltal betecknas som följer:

och lyder: n är jämförbar med m modulo 2. Det är naturligt att välja 0 för jämna tal och 1 för udda tal som standard. På liknande sätt delar man samma mängd M i k delmängder M 0, M 1,... M k-1, där M j består av alla tal som när de divideras med k ger återstoden j, kommer vi fram till ekvivalensrelationen:

vilket gäller om n och m har samma rest när de divideras med k.

Det är naturligt att välja motsvarande rest j som standard i varje M j.

II. Faktoruppsättning

Låt vara ett ekvivalensförhållande. Sedan finns det enligt satsen en partition (M 1, M 2,....) av mängden M i klasser av element som är likvärdiga med varandra - de så kallade ekvivalensklasserna.

Definition 2.5. Uppsättningen av ekvivalensklasser med avseende på en relation betecknas med M/ och läses som kvotmängden för mängden M med avseende på en relation.

Låt μ: M > S vara en surjektiv kartläggning av mängden M på någon mängd S.

För varje μ: M > S - surjektiv mappning finns det en ekvivalensrelation på mängden M så att M/ och S kan sättas i en-till-en-överensstämmelse.

III. Ekvivalensegenskaper

Definition 2.6. En relation c på en mängd M kallas en ekvivalensrelation om den är reflexiv, symmetrisk och transitiv.

Sats 2.1: Om en relation c på en mängd M är reflexiv, symmetrisk och transitiv, finns det en partition (M 1 , M 2 ,….) av mängden M så att (x, y) gäller om och endast om x och y tillhör någon allmän klass Mi för en given partition.

Omvänt: Om en partition är given (M 1, M 2,...) och den binära relationen c ges som "tillhör den allmänna klassen av partition", så är c ​​reflexiv, symmetrisk och transitiv.

Bevis:

Betrakta en reflexiv, symmetrisk och transitiv relation c till M. Låt för vilken som helst bestå av alla z för vilka (x, z) c

Lemma 2.1: För alla x och y, antingen eller

Av lemma och reflexiviteten i relationen c följer att mängder av formen bildar en partition av mängden M. (Denna partition kan naturligtvis kallas partitionen som motsvarar den ursprungliga relationen). Låt nu (x, y) c. Det betyder att y. Men också x i kraft av (x, x) c. Därför ingår båda delarna i. Så, om (x, y) c, så ingår x och y i allmän klass partitioner. Omvänt, låt u och v. Låt oss visa att (u, v) c Ja, vi har (x, u) c och (x, v) c. Därför, genom symmetri (u, x) c. Genom transitivitet, från (u, x) c och (x, v) följer c (u, v) c. Den första delen av satsen har bevisats.

Låt en partition (M 1, M 2,...) av uppsättningen M ges. föreningen av alla klasser av partitionen sammanfaller med M, då ingår vilket x som helst i någon klass. Av detta följer att (x, x) c, dvs. s - reflexmässigt. Om x och y är i någon klass, så är y och x i samma klass. Det betyder att (x, y) c innebär (y, x) c, dvs. förhållandet är symmetriskt. Låt nu (x, y) c och (y, z) c hålla. Det betyder att x och y är i någon klass, och y och z är i någon klass. Klasserna har ett gemensamt element y, och sammanfaller därför. Det betyder att x och z ingår i klassen, dvs. (x, z) gäller och relationen är transitiv. Teoremet har bevisats.

IV. Operationer om ekvivalenser.

Här definierar vi några mängdteoretiska operationer på ekvivalenser och presenterar deras viktiga egenskaper utan bevis.

Kom ihåg att en relation är ett par (), där M är uppsättningen av element som ingår i relationen, och är den uppsättning par för vilka relationen är uppfylld.

Definition 2.7. Skärningspunkten mellan relationer (c 1, M) och (c 2, M) är den relation som definieras av skärningspunkten mellan motsvarande delmängder. (x, y) från 1 från 2 om och endast om (x, y) från 1 och (x, y) från 2 samtidigt.

Sats 2.2: Skärningen av ekvivalenser med 1 med 2 med 1 med 2 är i sig en ekvivalensrelation.

Definition 2.8. Unionen av relationer (med 1, M) och (med 2, M) är en relation definierad av unionen av motsvarande delmängder. (x, y) med 1 med 2 om och endast om (x, y) med 1 eller (x, y) med 2.

Sats 2.3: För att föreningen av ekvivalenser med 1 med 2 ska vara en ekvivalensrelation i sig är det nödvändigt och tillräckligt att

från 1 från 2 = från 1 från 2

Definition 2.9. Den direkta summan av relationerna (c 1, M 1) och (c 2, M 2) kallas förhållandet). Den direkta summan betecknas (c 1, M 1) (c 2, M 2).

Således, om (c 1, M 1) (c 2, M 2) = (), då M =.

Sats 2.4: Om, och relationerna är ekvivalenser, så är den direkta summan av relationerna (c 1, M 1) (c 2, M 2) = (), också en ekvivalens.

V. Typer av relationer

Låt oss presentera flera viktiga typer av relationer. Exempel kommer att ges i det tredje kapitlet.

Definition 2.10. En relation c på en mängd M kallas tolerans om den är reflexiv och symmetrisk.

Definition 2.11. En relation c på en mängd M kallas en relation av strikt ordning om den är antireflexiv och transitiv.

Definition 2.12. En strikt ordningsrelation c kallas en perfekt strikt ordning om för något par av element x och y från M antingen (x, y) eller (y, x) är sant.

Definition 2.13. En relation c på en mängd M kallas en relation av icke-strikt ordning om den kan representeras i formen:

där det finns en strikt ordning på M, och E är en diagonal relation.

RELATION

Relationer är korrespondenser mellan element i samma mängd, det vill säga korrespondenser vars grundmängder sammanfaller:

x A, y A attityd Г = ((x,y)| P(x,y)), P(x,y) något uttalande (predikat).

Om (x,y) Г, då säger de det Xär i ett förhållande G Till på.

Till exempel att ha samma återstod (för siffror), vara på samma avstånd från en linje (för poäng), familjerelationer eller grannförhållanden (för många människor).

Mer strikt definition:

En binär relation är två uppsättningar:

1) stödsats A,

2) en uppsättning par Г=((x,y)| x A, y A), som är en delmängd av kvadraten på den stödjande mängden.

En n-är relation, eller en n-är (ternär, kvartär, ...) relation är en stödjande mängd A och uppsättningar av tupeldimension n, som är en delmängd av uppsättningen En.

Ett exempel på en ternär relation: att vara en del av de "tre spelarna".

Om en relation helt enkelt förstås som en uppsättning av tupler (utan en stödjande uppsättning), så kan alla lagar för mängdteorin användas. Den universella uppsättningen kommer att vara kvadraten på den stödjande uppsättningen, det vill säga uppsättningen av alla möjliga tupler (när varje element är i förhållande till alla andra element).

En relation kan också definieras som ett tvåställspredikat av objektvariabler x, y, som tar värdet "true" if (x, y) G och falskt om inte hör hemma.

Beteckningar: (x, y) Г, у = Г(x), у = Гx eller bara xGu t.ex. jämställdhetsrelationen (x = y), beställningsförhållande (X< у) .

Om (x, y) G, Den där xGu tar värdet "true", annars - "false".

Om relationerna är specificerade på en diskret mängd kan de skrivas i form av en matris

Ai, j =

Attityd - specialfall korrespondens, för det kan du introducera omvända relationer, sammansättning av relationer:

Г -1 =((y,x)| (x,y) Г), Г ◦ Δ = ((x,z) | y ((x,y) Г &(y,z Δ))).

De introducerar begreppet "enhetselement" Δ 0 = ((x,x)) - "att vara i relation till sig själv." I matrisrepresentation kommer detta att vara huvuddiagonalen).

Egenskaper binära relationer

1 Reflexivitet – "att vara i relation till sig själv"

xGx - sant(till exempel relationer x=x, x≤x, x≥x).

2 Antireflexivitet - "att inte vara i relation till sig själv"

xGx - lögn(till exempel relationer x≠x, x X).

Om en uppsättning inte är "reflexiv", betyder det inte att den är "anti-reflexiv".

3 Symmetri "oberoende av vilket element som är först och vilket som är andra"

хГу – sanning → уГх – sanning(till exempel relationer x=y, x≠y).

4 Antisymmetri "inte överskrida"

(xGy – sant) & (yGx – sant) → (x=y) (till exempel relationer x≤y, x≥y).

5 Asymmetri (icke-symmetri) "överstiga"

xGy – sant → yGx – falskt (till exempel relationer X<у, х>på).

6. Transitivitet "överföring"

(xГу – sant) & (yГz – sant) → (хГz – sant)(till exempel relationer x=y, x<у, х>y, x≤y, x≥y, attityd x≠y har inte transitivitet).

SÄRSKILDA BINÄRA RELATIONER

Låt oss betrakta "ekvivalensrelationen", den "icke-strikta ordningsrelationen", den "strikta ordningsrelationen" och "dominansrelationen".

Ekvivalensförhållande

En ekvivalensrelation är en reflexiv(x~x), symmetrisk ((x~y)=(y~x)), transitiv ((x~y)&(y~z)→(x~z)) attityd.

Exempel: likhet, identitet, ekvivalens av mängder, ekvivalens av logiska påståenden, likhet geometriska former, linjers parallellitet, men linjers vinkelräthet är inte ett ekvivalensförhållande.

En delmängd av element som är ekvivalenta med ett element kallas ekvivalensklass eller relaterad klass.

Alla element från en klass kallas en klassrepresentant.

Egenskaper.

Alla element i klassen är likvärdiga med varandra.

Element från olika klasser är inte likvärdiga.

Ett element kan bara tillhöra sin egen klass.

Hela uppsättningen kan representeras som en förening av klasser.

Således bildar en uppsättning ekvivalensklasser eller ett komplett system av klasser en uppdelning av den stödjande uppsättningen. Påminnelse: partitionering av en uppsättning representerar den som osammanhängande delmängder.

Partitionsindex– antal ekvivalensklasser.

Faktoruppsättning med avseende på ekvivalensrelationen är detta uppsättningen av alla klasser eller representanter för en klass.

Kardinaliteten för en faktoruppsättning är lika med partitionsindexet.

Ordningsrelationer

Orderrelation hänvisar till två typer av binära relationer.

Attityd lös ordning kallas reflexiv (x≥x), antisymmetrisk ((x≤y)&(y≤x)→ (x=y)), transitiv ((x≥y)&(y≥z)→(x≥z)) attityd.

De säger att ett set har en lös ordning. Begreppen ≤ , ≥ har en vidare betydelse: inte sämre - inte bättre, inte tidigare - inte senare, och så vidare. I mängdteorin är ett exempel på icke-strikt ordning icke-strikt inkludering (som är en delmängd av en annan uppsättning0.

Attityd strikt ordning kallas antireflexiv ((X , antisymmetrisk ((x , transitiv

((x>y)&(y attityd.

De säger att en uppsättning har en strikt ordning. I koncept< , >de har en vidare betydelse: sämre är bättre, tidigare är senare och så vidare. I mängdteorin är ett exempel på strikt ordning strikt inkludering (att vara en delmängd av en annan mängd utan att vara lika med den).

Beställda set

Uppsättningen heter linjärt ordnade, om något element kan jämföras (det vill säga: större än, mindre än eller lika med).

Uppsättningen av reella tal eller heltal: klassiska exempel på en ordnad uppsättning.

Om det är möjligt att upprätta en ordningsrelation på en mängd, men inte för alla par av element, så kallas en sådan mängd delvis beställd.

Detta är en uppsättning vektorer, en uppsättning komplexa tal, mängder i mängdlära. I vissa fall kan vi säga "mer är mindre" eller "vara en supermängd och en delmängd", men inte i alla fall.

Klasser av ekvivalenta element och deras egenskaper

Låt %%R%% — ekvivalensförhållande på uppsättningen %%M%% och %%a%% - något element från %%M%%. Betrakta mängden av alla element från %%M%% som står i relation %%R%% till element %%a%%.

Ekvivalensklass%%M_a%%

är mängden av alla element %%M%% som står i relation %%R%% till elementet %%a%%, det vill säga mängden

$$ M_a = \(x \i M: x~R~a\). $$

Exempel

Låt %%M%% vara uppsättningen av alla invånare i Ryssland och %%R%% vara ekvivalensrelationen "att bo i samma stad." Hitta klasser av ekvivalenta element %%M_a%% för %%a \in M%%.

Klassen av element som motsvarar elementet %%a%% har formen: $$ M_a = \(x \i M: x \text( bor i samma stad som personen ) a\) $$

Beroende på elementet %%a%% får vi flera ekvivalensklasser. Till exempel ekvivalensklassen för invånare i Moskva eller St Petersburg.

Egenskaper för ekvivalensklasser

Låt %%R%% vara en ekvivalensrelation på mängden %%M%% och %%M_a, M_b, \dotsc, M_z, \dotsc%% vara alla ekvivalensklasser för relationen %%R%%. Då har dessa klasser följande egenskaper.

Fastighet 1

För alla element %%a \in M%% är villkoret $$ a \in M_a $$ uppfyllt

I själva verket, per definition, klassen %%M_a = \(x \in M: x~R~a\)%%. Då måste för elementet %%a%% villkoret %%a \in M_a \leftrightarrow a~R~a%% vara uppfyllt, vilket är uppfyllt på grund av att relationen %%R%% är reflexiv enligt definitionen av ett ekvivalensförhållande. Därför %%a \in M_a%%.

Följaktligen Den här egenskapen låter oss säga att varje klass %%M_a%% är en icke-tom uppsättning.

Fastighet 2

Låt %%M_a%% och %%M_b%% vara ekvivalensklasser för relationen %%R%%. Klasserna %%M_a%% och %%M_b%% är lika om och endast om elementet %%a%% är i relationen %%R%% till elementet %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$

Fastighet 3

Låt %%M_a%% och %%M_b%% vara ekvivalensklasser för relationen %%R%%. Då har klasserna %%M_a%% och %%M_b%% inga gemensamma element. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

Fastighet 4

Föreningen av alla ekvivalensklasser av uppsättningen %%M%% är lika med uppsättningen %%M%%. $$ \bigcup_(a\in M)(M_a) = M. $$

Dela upp ett set

Samlingen av delmängder %%M_i%%, där %%i \i I%% (till uppsättningen index), av uppsättningen %%M%% kallas splittring ställ in %%M%% om följande villkor är uppfyllda:

  1. Var och en av delmängderna %%M_i%% är inte tomma.
  2. Unionen av alla delmängder %%M_i%% är lika med uppsättningen %%M%%.
  3. Två olika delmängder %%M_i%% och %%M_j%%, där %%i \neq j%%, inte har gemensamma element.

Sats. Låt %%R%% vara ett ekvivalensförhållande på uppsättningen %%M%%. Sedan bildar uppsättningen av ekvivalensklasser för uppsättningen %%M%% dess partition.

Faktum är att om vi tar ekvivalensklasserna %%M_a%% som delmängder av %%M_i%%, så är alla tre villkoren uppfyllda:

  1. Varje ekvivalensklass är en icke-tom uppsättning, enligt fastighet 1.
  2. Unionen av alla ekvivalensklasser är uppsättningen %%M%%, enligt egendom 4.
  3. Två olika ekvivalensklasser har inga gemensamma element, enl egendom 3.

Alla villkor för att definiera en partition är uppfyllda. Därför är ekvivalensklasser en partition av uppsättningen %%M%%.

Exempel

Låt uppsättningen %%M = \(1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \)%% ges, då kan följande samlingar av uppsättningar vara en partition av denna uppsättning:

  1. %%A_1 = \(1, 2, 3\), A_2 = \(4, 5, 6, 7\), A_3 = \(8, 9, 0\)%%.
  2. %%B_1 = \(0, 7, 2\), B_2 = \(1, 3, 5\), B_3 = \(4, 6, 8, 9\)%%.

Men följande aggregat är inte partitioner:

  1. %%C_1 = \(1, 2, 3\), C_2 = \(4, 5, 6, 7\), C_3 = \(8, 9, 0, 3\)%%.
  2. %%D_1 = \(0, 7, 2\), D_2 = \(1, 3, 5\), D_3 = \(4, 6, 8, 9\), D_4 = \varnothing%%.
  3. %%E_1 = \(0, 1, 2\), E_2 = \(3, 4, 5\), E_3 = \(6, 7, 8\)%%.

Uppsättningen %%C_i%% är inte en partition, eftersom den uppfyller inte villkor 3 för partitioneringsuppsättningar: uppsättningarna %%C_1%% och %%C_3%% har ett gemensamt element %%3%%.

Uppsättningen %%D_i%% är inte en partition, eftersom den uppfyller inte villkor 1 för partitioneringsuppsättningar: uppsättningen %%D_4%% är tom.

Uppsättningen %%E_i%% är inte en partition, eftersom den uppfyller inte villkor 2 för partitioneringsuppsättningar: föreningen av uppsättningarna %%E_1, E_2%% och %%E_3%% bildar inte uppsättningen %%M%%.

Ekvivalensförhållande är en relation som har egenskaperna reflexivitet, symmetri och transitivitet. Indikeras av skylten ~, spela in A ~ V betyder att A likvärdig V .

Enligt definitionen har ekvivalensrelationen följande egenskaper:

Exempel på ekvivalensrelationer – jämlikhet, likhet av trianglar.

Genom att använda ekvivalensrelationen är det möjligt att dela upp en uppsättning i ekvivalensklasser.

Ekvivalensklass , genererad av elementet – uppsättningen av alla element från , med början från i förhållande till likvärdighet. Ekvivalensklassen definieras enligt följande:

, För
element är valda
, som är i överensstämmelse med elementet X .

Ekvivalensrelationen har stor praktisk tillämpning, vilket gör att uppsättningar kan delas in i ekvivalensklasser. Ekvivalensklassen kan erhållas om för det valda elementet X från många X du kan välja element
, belägen med X i en ekvivalensklass

Faktoruppsättningar set genom ekvivalensförhållandeφ – uppsättningen av alla olika ekvivalensklasser, betecknadA/φ .

Partitionsindex , genererad av relationenφ är kraften hos faktoruppsättningen A/φ .

Exempel2 .11.

A) Jämställdhetsförhållande
på vilken mängd som helst är en ekvivalensrelation.

Jämlikhet är en minimal ekvivalensrelation i den meningen att när man tar bort något par från
(det vill säga vilken enhet som helst på matrisens diagonal
) den upphör att vara reflexiv och är därför inte längre en likvärdighet.

b) Uttalanden av formuläret
eller
, som består av formler förbundna med ett likhetstecken, definierar en binär relation på en uppsättning formler som beskriver superpositioner av elementära funktioner. Denna relation brukar kallas ekvivalensrelationen och definieras enligt följande: formler är ekvivalenta om de definierar samma funktion. Ekvivalens, även om den betecknas med tecknet =, skiljer sig från förhållandet jämlikhet
, eftersom det kan utföras för olika formler. Attityd
för formler är detta sammanträffandet av formlerna i stavning. Det heter grafisk jämlikhet .

V) Låt oss betrakta en uppsättning trianglar på ett plan, och anta att en triangel är given om koordinaterna för dess hörn är givna. Två trianglar kallaskongruent (likvärdig ) , om de sammanfaller när de överlagras, det vill säga de kan omvandlas till varandra genom någon rörelse. Kongruens är en ekvivalensrelation på en uppsättning trianglar.

G) Attityd" har samma återstod när de divideras med 9" motsvarar
. Denna relation gäller för par (12, 21), (17, 36) och gäller inte för par (11, 13), (19, 29).

Släpp på uppsättningen givet ekvivalensförhållande . Låt oss utföra följande konstruktion. Låt oss välja ett element
och bildar en klass (delmängd ), bestående av ; välj sedan elementet
och bilda en klass , bestående av och alla element likvärdiga , etc. Resultatet är ett klasssystem
(möjligen oändlig) så att något element från ingår i minst en klass, dvs
. Detta klasssystem har följande egenskaper:

    det bildas dela, det vill säga klasser i par skär inte varandra;

    två valfria element från samma klass likvärdig;

    två valfria element från olika klasser är inte likvärdiga.

Alla dessa egenskaper följer av reflexivitet, symmetri och transitivitet . Ja, om klasser, till exempel Och , korsade, då skulle de ha ett gemensamt element , likvärdig Och , men då på grund av transitivitet skulle
, vilket strider mot konstruktionen . De andra två egenskaperna bevisas på liknande sätt.

Den konstruerade partitionen, det vill säga klasssystemet, kallas ett system ekvivalensklasser i relation med . Kardinaliteten i detta system kallas partitionsindex. Å andra sidan, vilken partition som helst klasser definierar en viss ekvivalensrelation, nämligen relationen " tillhör samma klass av en given partition».

Exempel. 2.12.

A) Alla ekvivalensklasser med avseende på jämställdhetsrelationen
består av ett element.

b) Formler som beskriver samma elementära funktion är i samma ekvivalensklass med avseende på ekvivalensrelationen. I det här exemplet är själva uppsättningen av formler, uppsättningen av ekvivalensklasser (det vill säga partitionsindex) och varje ekvivalensklass räknebara.

c) Partition
i relation med " har en total återstod när de divideras med 7" har ett slutindex på 7 och består av 7 räkneklasser: 0, 7, 14, ...; 2, 9, 16, …; ...; 6, 13, 20, …



Liknande artiklar