Förstå vad en relation är - matematik/logik

Säg att X är mängden av naturliga tal.

X x X är då mängden av alla ordnade par av naturliga tal. Tex så innehåller denna mängd (1, 2), (47, 5), (2001, 1984) osv.

Du skulle kunna definiera tex mindre än som en delmängd R till X x X som innehåller alla ordnade par (x, y) där x < y. Så istället för att tillämpa någon regel för att avgöra om x < y så skulle man kunna kolla om paret (x, y) ligger i R.

Jag tror att den viktigaste tillämpning av relationer är att man kan definiera en funktion som ett specialfall av en relation. Men det kanske finns några matematiker som ger mig pisk för att jag säger detta.

Ja okej.

Så ordningsrelationen $\le$ på en mängd $X$ är egentligen en delmängd till $X \times X$ innehållande alla tuplar $(x, y)$ där $x\le y$?

Hur kan man uttrycka det med matematiska symboler? Kommer inte på något bra sätt att göra det utan att skriva någon cirkular definition. Kanske:

$\displaystyle x\le y:=\{ (x,y)\in X\times X| x\le y \}$

Men problemet här är väl att man vill definiera vad relationen $\le$ betyder UTAN att använda $\le$ i definitionen. Det förefaller vara lite cirkulärt att använda $\le$ i definitionen för vad $\le$ betyder.

Kanske skulle man kunna skriva $\le = \left\{\left(x, y\right)\in X\times X: x\le y\right\}$.

Här betecknar $\le$ dock två olika saker. Längst till vänster själva mängden och till höger regeln som bestämmer om x är mindre än eller lika med y.

Det kanske inte är cirkulärt, men jag antar att man bara i enkla fall kan ge mängden utan att ha regeln.

Men vilken av dem är då ordningsrelationen $\le$? Den högra eller den vänstra? Jag antar att det är en vänstra men jag förstår inte hur definitionen för relation som en mängd passar ihop med hur begreppet (och symbolen) normalt sett används. Om vi säger:

$3\le 4$

Använder vi "ordningsrelationen" då eller använder vi en regel? Vad exakt betyder det att vi har "ordningsrelationen $\le$ på en mängd $X$"?

En ordningsrelation behöver inte vara talens vanliga. Du kan säga att Adam < Berta < Caesar.

Okej. Men jag är ganska förvirrad av någon anledning. Kanske ett konkret exempel kan hjälpa? Om vi tar de reella talen som exempel, vad exakt innebär det att det finns en ordningsrelation $\le$ på $\mathbb{R}$?

Just ordningsrelation måste uppfylla att om a < b och b < c så gäller a < c.

Jag kommer inte på någon spännande sådan just nu för R, men vi kan ju ta a <_naytte b omm a > b.

Att utvidga den vanliga < för först heltal och sedan rationella tal, till R, är väl en icketrivial uppgift i sig själv, men det kanske kommer på köpet när man definierar R.

Okej, jag tror det är här kruxet är för mig.

Nu talar du om element a, b, c i någon mängd. Men i definitionen för en relation talar man om en mängd, alltså att själva ordningsrelationen ÄR en mängd. Jag är extremt förvirrad över just den biten.

Om vi tittar på definitionen @PATENTERAMERA föreslog i inlägg #4 talar vi dels om en ordningsrelation $\le$, som i princip är en mängd tuplar, och dels om en "regel" $\le$. Hur kan vi definiera $\le$ med hjälp av symbolen $\le$? Eller jag förstår inte vad som är skillnaden på ordningsrelationen $\le$ och "regeln" $\le$.

Om vi bara kallar vår relation R just nu (vilket inte är R, de reella talen, men det visste du), så är en relation mellan element i en mängd S en delmängd av S x S. Man kan skriva a R b om (a, b) finns i den delmängden, bara för att det blir kortare. Det är egentligen allt om definitionen av relationer.

Jag tycker definitionen i #4 är cirkulär, så jag svarar att ordningsrelationen och "regeln" är samma sak.

Etablerade relationer som < brukar man inte tänka på som mängder, men de kan uppfattas så.

Jag pladdrar kanske förbi kärnan i din fråga.

Okej, det är fortfarande lite förvirrande men jag tror det börjar klarna. 

Men hur skulle du, om du vore tvungen, definiera relationen ? Med matematiska tecken, dvs. utan ord.

I N, Z, Q eller R?

$\mathbb{R}$.

Då skulle jag behöva läsa på om definitionen av R, t.ex. Dedekind-snitt. Det är något för din andra tråd, som jag bara har slöföljt litet grann.

Okej, om vi tar någon lite enklare mängd då, som $\mathbb{N}$?

a < b om och endast om det finns ett c skilt från 0 i N sådant att b = a + c.

Det kanske är fusk. Det verkar som om Z är svårare. Men det kanske också går bra så här och det borde gå att överföra på Z: vi använder successor-funktionen p(X), som används för att definiera N (p för Peano, tror jag). Axiomen säger ju att varje tal X i N har en efterföljare p(N).

Så a < b om och endast om b = p(a) eller p(a) < b.

Hoppas nån som kan det här tar över...

Binära relationer av typen "" eller "$\prec$"  samt "$\leq$" och "$\preceq$" är sätt att uttrycka hur en mängd är ordnad (till exempel i vilken följd talen kommer)

Definition: En binär relation $\preceq$ i en mängd $A$ som är reflexiv, antisymmetrisk och transitiv är en partiell ordning av mängden.  Man säger att paret $(A, \preceq)$ är en partiellt ordnad mängd.

Definition: En binär relation $\prec$ i en mängd $A$  som är asymmetrisk och transitiv är en sträng ordning av mängden. Man säger att paret $(A, \prec)$ är en strängt ordnad mängd.

Tillämpade matematiker säger ibland att den binära relationen är "på" eller "av" en mängd, alltså $\prec$ på $A$. Men i mer teoretiska sammanhang bör man undvika halvsemantiska betydelseglidningar.

Att definiera ordning genom en operation är förvisso möjligt men riskerar att bli cirkulärt eftersom man inte får använda någon mer fundamental byggsten på vägen. En tänkbar hjälpsats för addition kan konstrueras och sedan får man metodiskt bevisa den utan att använda någon referens till ordning.

Hjälpsats: Det finns en unik funktion $+\,:\, \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ så att :

(a) $+(m,0)=m$ för alla $m\in\mathbb{N}$

(b) $+(m,n+1)=+(m,n)+1$ för alla $m,n\in \mathbb{N}$.

När det rigorösa beviset är klart kan vi skriva $m+n$ istället för $+(m,n)$. Det innebär att vi på klassiskt vis kan påstå att $m+0=m$ samt $m+(n+1)=(m+n)+1$

En lättare väg är dock att använda hur de naturliga talen i sig är definierade:

Definition: Relationen $<$ på $\mathbb{N}$ är $m< n$ om och endast om $m\in n$

Edit: fixade $\leq \to <$

Definition: En binär relation $\preceq$ i en mängd $A$ som är reflexiv, antisymmetrisk och transitiv är en partiell ordning av mängden.  Man säger att paret $(A,\preceq )$ är en partiellt ordnad mängd.

Men när vi bekräftar dessa kriterier, använder vi oss inte av relationen då redan? Eller hur kan vi använda oss av relationen i vår definiton för relationen? För att vi ska veta om $\preceq$ är reflexiv måste vi ju kolla på om:

$a\preceq a$ 

Men här låtsas vi att vi redan vet vad $\preceq$ är för något. Är inte hela poängen med en definition att vi inte vet vad det är från början?

Jag använde $\prec$ och $\preceq$ för att det skulle vara lätt att se vilket vanligt förekommande relationstecken som passar ihop med vilken definition. VI kan lika gärna använda $R$

Från början vet vi inget om relationen $R$.

Men om vi kan visa att $R$ uppfyller definitionen för sträng ordning av mängden $A$ så kan vi prata om den strängt ordnade mängden $(A, R)=(A,<)$.

För att visa det måste vi såklart veta något om hur relationen $R$ ser ut.

Den enklaste definitionen för naturliga tal $m,n\in \mathbb{N}$ är som sagt att $R$ är

$mRn$ om och endast om $m\in n$ $\quad$ dvs ($m<>$ om och endast om $m \in n$)

Man kan ganska enkelt visa att den binära relationen $R$ i $\mathbb{N}$ uppfyller villkoren (R ska vara asymmetrisk och transitiv) för en strängt ordnad mängd.

Den ordnade mängden $(N,<)$ kan vi sedan använda som byggsten när vi konstruerar de hela talen och småningom de rationella talen. För att komma vidare behöver du också kunna definiera isomorfi mellan mängder.

Vad betyder det att "$m\in n$"? Vad betyder det att ett tal är ett element i ett annat tal?

Ja. Varje naturligt tal är (definierat som) mängden av alla "tidigare" naturliga tal.

$3=\{0,1,2\}$

Alltså är $2\in 3$ liksom $1\in 3$

Det betyder att $2R3$ och att $1R3$, dvs såväl $2<3$ som $1<3$

Däremot är $3\notin 3$

Ja, just det! Det minns jag att jag läst någon gång i förbifarten!

Visst utgår man från den tomma mängden? Alltså:

$\displaystyle 0=\emptyset, \;1=\{ \emptyset \}, \;2=\{ \emptyset, \{ \emptyset \} \}...$

Ja, det stämmer. Tekniskt sett kan man utgå från en annan "basmängd", men den tomma mängden har stora räknetekniska fördelar när man ska skapa aritmetiska operationer och vid vissa bevis.

Om jag får komma med ett råd tänker jag att du först ska försöka definiera (och konstruera) de hela talen och de rationella talen innan du ger dig på hur man konstruerar de reella talen. Då tror jag det blir mindre obekvämt att se "tal" som mängder av Dedekindsnitt apropå dina frågor i en av dina  andra trådar.

Jag antar att man kan använda de naturliga talen (som vi nu har en definition för) för att skapa heltalen och sedan de rationella talen då?

naytte skrev:

Jag antar att man kan använda de naturliga talen för att skapa heltalen och sedan de rationella talen då?

Ja, en ungefärlig mellan tummen-och-pekfingret-variant är

1. Mängdlära (axiom, egenskaper, elementära operationer osv)

2. Relationer (funktioner), partitioner och ordningar

3. Naturliga tal, hela tal, aritmetik, operationer och strukturer.

4. Kardinalitet, skillnaden mellan ändliga och oändliga mängder, linjär total ordning osv.

5. Rationella tal

6. Reella tal.

Man kan som du hoppa rakt in i smeten, men det innebär vissa förenklingar och att man måste hoppa över saker samt använda lite vaga (oprecisa) formuleringar. Å andra sidan är det kanske roligare och mer spännande :)

Anledningen till att jag hoppade rakt in i smeten på det viset var att jag inte visste var jag skulle börja (det är ju inte som om man lär sig sådant här på gymnasiet).

Har du någon bra rekommendation på en bok / böcker som tar upp dessa saker? Språk spelar ingen roll.

De första 70 sidorna "Topology" av James A Munkres tror jag kan ligga på en lämplig nivå. Fördelen med den boken är också att resten av boken är en introduktion till topologi, vilket verkar intressera dig :)  Det är dessutom en riktigt bra och motiverande bok! Tror jag lärde mig mer matematik av den än någon annan under mina grundkurser.

(Munkres täcker in Mängdlära, relationer, struktur, ordning, kardinalitet, vill du ha en djupdykning om de reella talen har jag svårt att komma någon bok som inte kräver matematisk mognad motsvarande några års universitetsstudier)

Perfekt, den gick att hitta som PDF!

Tack så mycket för förslaget! Ska börja läsa i den och återkomma!

Hej, igen!

Jag läste ett exempel där man definierade heltalen utifrån de naturliga talen, och som jag förstår det är ett heltal en särskild ekvivalensklass för en ekvivalensrelation $\displaystyle \simeq$ definierad enligt:

$\displaystyle (a,b)\simeq (c,d)$ om och endast om $\displaystyle a+d=b+c, (a+b), (c+d)\in\mathbb{N}\times\mathbb{N}$

Som jag förstår det skulle vi t.ex. kunna definiera -3 som:

$\displaystyle -3=[(0,3)]=\{ (0,3),(1,4)...,(n,n+3) \}$

Men nu har jag lite frågor kring notation. Främst undrar jag över följande notation:

$\displaystyle \mathbb{Z}=\mathbb{N}\times\mathbb{N}\;\backslash\simeq$

Hur ska man läsa detta? Och vad exakt betyder det? Är det "mängden av alla ekvivalensklasser för $\simeq$ på $\displaystyle \mathbb{N}\times\mathbb{N}$"?

Ja, det stämmer utmärkt.

Man säger att $\approx$ är en ekvivalensrelation (en speciell typ av binär relation) på mängden $\mathbb{Z}^\prime=\mathbb{N}\times \mathbb{N}$ (mängden $\mathbb{Z}^\prime$ är en kartesisk produkt).

Då kan mängden av alla heltal $\mathbb{Z}$ skrivas som mängden av alla ekvivalensklasser $\mathbb{Z}^\prime$ modulo $\approx$
Mer kompakt skriver man

$\mathbb{Z}=\mathbb{Z}^\prime/\approx$

Ekvivalensklasser har du säkert stött på när du läste om "modulär aritmetik". Då studerar man restklasser (alla tal som lämnar samma rest är "samma sak"). Inom tillämpad matematik använder man ekvivalensklasser när man pratar om till exempel kvotrum.

Okej, tack!

Och när man skriver en ekvivalensklass för en särskild ekvivalensrelation (kanske har man flera olika), skriver man det med ett nedsänkt tecken då? Alltså typ:

$\displaystyle -3=[(0, 3)]_{\simeq}$

Ja, om det inte framgår av sammanhanget eller om man vill vara tydlig ska man ange vilken relation man avser.

Hakparenteserna betyder ungefär "[representant för just den här klassen]"

Man kan också ange modulo separat, t.ex. $12\equiv 1 \ (\mathrm{mod}\ 11)$

Men jag tror folk skulle förstå  om du skrev $[12]_{11}$

För de hela talen är de flesta överens om vilken ekvivalensrelation som ska gälla. Det du får se upp med är när någon påstår att de naturliga talen $\mathbb{N}$ inte innehåller talet 0. Då måste man antingen ha överseende eller be personen förklara hur hen definierar de hela talen, eftersom vissa problem kan uppstå vid ett antal fundamentala referenser och bevis.

Okej, tack så mycket! Härnäst ska jag läsa om hur man definierar aritmetik för heltalen.

Jag måste medge att det fortfarande känns ganska främmande att betrakta tal som inte bara mängder, utan nu även som mängder av tuplar. Men det börjar bli tydligare och tydligare i min hjärna att det fungerar. Om man tänker på -3, -2 osv. som representater för något, alltså bara som symboler utan inherent betydelse, är det enklare att acceptera.

En sak jag undrar också är hur vi kan veta att olika representationer för samma tal faktiskt är ekvivalenta. Vi har ju sedan tidigare att t.ex:

$\displaystyle 1=\{ \emptyset \}$

Men vi vet med denna nyvunna kunskap dessutom att en annan representation för 1 är:

$\displaystyle 1=[(1,0)]=\{ (\{ \emptyset \},\emptyset ),(\{ \emptyset ,\{ \emptyset \} \},\{ \emptyset \})... \}$

Hur kan vi veta att dessa skrivsätt är ekvivalenta?

För varje heltal (ekvivalensgrupp) $[(a,b)]$ är antingen $a\ge b$ eller $a<>$. Om vi börjar med fallet $a\ge b$ inser vi att

$(a,b)\approx (a-b,0)$

Här förutsätts subtraktion av två naturliga tal $n=a-b$. Varje heltal för vilket $a\ge b$ kan därmed identifieras fullständigt av det unika talparet

$(n,0),\, n\in \mathbb{N}$

Vi kan nu skapa en funktion $h: \,\mathbb{N}\to\mathbb{Z}$ definierad av $h(n)=[(n,0)]$ som är 1-1 och ordningsbevarande${}^*$. Varje positivt heltal $[(n,0)]$ kan sägas motsvara exakt ett naturligt tal $n$. För $(a<>$ kan vi genomföra ett liknande resonemang och identifiera $[(0,n)]$ med $-n$.

Med ordningsbevarande menar vi att $n_1<>$ medför $h(n_1)<>$.

En rimlig ordningsrelation $<$ är

$[(a,b)]<[(c,d)] \iff a+d<>$

${}^*$Med lite möda kan man visa att ordningsrelationen $[(a,b)]<[(c,d)]$ är såväl väldefinierad som linjärt ordnad.

Ja, okej. Jag tror jag är med på vad vi gör här.

Definitionerna som von Neumann ordinaler och heltal i sig sammanfaller inte, men man kan alltid mappa exakt en "von Neumann ordinal" till exakt en ekvivalensklass för heltalen (om vi endast betraktar dem på formen [n, 0])?

Och den här "mappningen" kan man då också använda för att visa att aritmetik (multiplikation och addition) fungerar i $\mathbb{Z}$ precis som i $\mathbb{N}$?

Och en sak till:

Jag har läst på lite om homomorfi och isomorfi nu. Skulle bara vilja bekräfta att jag förstår begreppen rätt:

Homomorfi: en funktion $\displaystyle f:(G,\oplus )\to (H,\oslash )$ är en homomorfi för två grupper slutna under någon binär relation omm  $\displaystyle f(x\oplus y)=f(x)\oslash f(y)$, där $\oplus$ och $\oslash$ är de binära operatioerna.

Isomorfi: ett specialfall av homomorfi där det dessutom existerar en inversfunktion $f^{-1}$ sådan att $\displaystyle f^{-1}(x\oslash y)=f^{-1}(x)\oplus f^{-1}(y)$

Ett exempel på en homomorfi är $\displaystyle f(x)=e^x:(\mathbb{R},+)\to (\mathbb{R},\cdot)$. 

Motivering:

$\displaystyle e^{x+y}=e^{x}\cdot e^{y}$

Ett exempel på en isomorfi är $\displaystyle \ln :(\mathbb{R^+},\cdot)\to(\mathbb{R},+)$

Motivering:

$\displaystyle \ln xy=\ln x+\ln y$

Alltså är kravet för en homomorfi uppfyllt. Nu testar vi för isomorfi:

$\displaystyle \ln^{-1} {x}=e^x$

$\displaystyle e^{x+y}=e^x \cdot e^y$

Alltså är kravet för isomorfi uppfyllt.

Det var många frågor på en gång med ämnen som skulle kunna fylla åtminstone 10 olika trådar :)

Vi kan vi börja med att fundera de olika talmängderna $\mathbb{N}$, $\mathbb{Z}$ och $\mathbb{Q}$. Varje mängd är uppräkneligt oändlig och de har alla samma kardinalitet.

Men hur lika är egentligen mängderna? vi inser snabbt att det måste finnas vissa skillnader, särskilt om vi försöker ordna mängderna efter storlek på sedvanligt vis. Till exempel har $\mathbb{N}$ ett minsta element, en tydlig "början". Denna egenskap är uppenbarligen något såväl $\mathbb{Z}$ som $\mathbb{Q}$ saknar. Och mellan två godtyckliga rationella tal $q_1,q_2\in \mathbb{Q}$ finns det ett oändligt antal rationella tal, medan det mellan två godtyckliga heltal $z_1,z_2\in \mathbb{Z}$ bara finns ett ändligt antal tal.

För att beskriva skillnaderna kan man använda konceptet ordinaltyp, vi säger att de två ordnade mängderna $(A, <)$ och $(B,\prec)$ är av samma ordinaltyp om de är isomorfa.

Den beskrivning av isomorfism du använder är lämplig för gruppteori eller algebra, men den är inte tillräckligt allmängiltig för att användas i en mer rigorös kontext. En formulering som passar mer rigorösa (mängdteoretiska) sammanhang och samtidigt liknar den man använder i gruppteori kan formuleras mellan generaliserade strukturer men en sådan definition är förmodligen lite krånglig att förstå innan man lärt sig operationer och strukturer.

En enklare definition som du redan nu kan använda är

Definition: En isomorfism mellan två ordnade mängder $(P,<)$ och $(Q,\prec)$ är en 1-1 funktion $h$ med definitionsmängd $P$ och värdemängd $Q$ så att för alla $p_1,p_2\in P$ gäller

$p_1$

Du kan också redan nu definiera de grundläggande operationerna addition och multiplikation för $\mathbb{Z}$ enligt:

$[(a,b)]+[(c,d)]=[(a+c,b+d)]$

$[(a,b)]\cdot [(c,d)]=[(ac+bd, ad+bc)]$

Ja okej, så vår mängd $\mathbb{N}$ och den nya mängden $\mathbb{Z}$ är isomorfa då med andra ord, eftersom det uppenbarligen finns en ordningsbevarande 1-1 funktion $\displaystyle h:(\mathbb{N},<)\to(\mathbb{Z}^+\cup \{0\},\prec )$? (om vi tänker att $\prec$ är den "vanliga" ordningsrelationen på $\mathbb{Z}$)

Tillägg: 20 feb 2024 08:33

Och ett exempel på två mängder då som inte skulle vara isomorfa är $\mathbb{N}$ och $\mathbb{Q}$, för $\mathbb{Q}$ har "oändligt många fler" element än $\mathbb{N}$. Så trots att båda är oändliga har den ena större kardinalitet och då kan man inte skapa en sådan funktion.

Stämmer det?

naytte skrev:

Ja okej, så vår mängd $\mathbb{N}$ och den nya mängden $\mathbb{Z}$ är isomorfa då med andra ord, eftersom det uppenbarligen finns en ordningsbevarande 1-1 funktion $\displaystyle h:(\mathbb{N},<)\to(\mathbb{Z}^+\cup \{0\},\prec )$? (om vi tänker att $\prec$ är den "vanliga" ordningsrelationen på $\mathbb{Z}$)

Nu har du korrekt visat att det finns en isomorfism mellan en delmängd av heltalen och de naturliga talen genom naturlig inklusion $h(n)=n$ (närmare bestämt positiva heltal). Du kommer dock upptäcka att hela $\mathbb{Z}$ under till exempel addition inte kommer kunna uppfylla kraven (om vi använder dina kunskaper inom gruppteori kan man säga att $\mathbb{Z}$ under addition är en grupp, $\mathbb{N}$ är det inte). Den viktigaste ordningsskillnaden är att $\mathbb{Z}$ saknar ett minsta element, till skillnad från $\mathbb{N}$

Det stämmer att $\mathbb{Q}$ i någon mening har oändligt många fler element än $\mathbb{N}$. Men lustigt nog anser man att alla oändliga mängder som är uppräkneliga har samma kardinalitet $\aleph_0$. För att skilja uppräkneliga mängder åt, som $\mathbb{Z}$ och $\mathbb{Q}$, använder man istället ordinalta/välordning och ordningstyper.

Jag tror att det är dags för några nya trådar för att till exempel reda ut kardinalitet och ordinalitet, välordning och så vidare. Det ger också andra hjälpare en chans att hjälpa dig :)

Tack så hemskt mycket för din hjälp hittills!