Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI TEORIJA SKUPOVA

Tranzitivnost relacije

[inlmath]C\backslash\left(A\cap B\right)=\left(C\backslash A\right)\cup\left(C\backslash B\right)[/inlmath]

Tranzitivnost relacije

Postod Acim » Utorak, 05. Oktobar 2021, 21:05

Zdravo,
U vezi postupka određivanja da li je relacija tranzitivna, imam par nedoumica. Prvo ću pokazati postupak (koji će se kasnije pokazati kao netačan u 90% slučajeva) koji sam koristio do sad;
Neka nam je skup [inlmath]A=\left\{1,2,3,4\right\}[/inlmath] i uzmimo da je njegova relacija npr [inlmath]\rho=\left\{\left(1,1\right),\left(1,2\right),\left(2,3\right),\left(1,3\right),\left(3,3\right)\right\}[/inlmath]

Prema mom načinu, možemo da odbacimo parove čiji su i jedan i drugi element isti. U ovom slučaju, možemo odbaciti [inlmath](1,1)[/inlmath] i [inlmath](3,3)[/inlmath] i sad, elementi koji nam ostaju za razmatranje su [inlmath]\left(1,2\right),\left(2,3\right),\left(1,3\right)[/inlmath].
Sad, gledamo redom svaki od navedenih parova pojedinačno (gledamo ih tako da se 2. element prvog para poklopi sa 1. elementom drugog para).
Uzmimo prvo par [inlmath]\left(1,2\right)[/inlmath]. Uočavamo da njemu odgovara par [inlmath]\left(2,3\right)[/inlmath]. Prema tome;
[inlmath]\left(1,2\right)\in\rho[/inlmath] i [inlmath]\left(2,3\right)\in\rho[/inlmath] tj. iz toga sledi da [inlmath]\left(1,3\right)\in\rho[/inlmath] ([inlmath](1,3)[/inlmath] sam dobio tako što sam gledao prvi element prvog para i 2. element drugog para) i vidimo da je relacija već sada tranzitivna (koliko sam shvatio, bitno je da je samo jedan ovakav iskaz tačan i da je onda relacija tranzitivna).
Ako uzmemo parove [inlmath]\left(2,3\right)[/inlmath] ili [inlmath]\left(1,3\right)[/inlmath] vidimo da za njih nema parova koji im odgovaraju kao iznad. Sve u svemu, relacija je tranzitivna.

E sad, kao što sam gore naveo, moj postupak se nikako nije ispostavio tačnim (ne kontam zbog čega) kod sledeća 2 primera:
Npr neka je [inlmath]A=\left\{1,2,3\right\}[/inlmath] i neka je njegova relacija [inlmath]\rho=\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right)\right\}[/inlmath]
Kako je ova relacija tranzitivna, ako nemam različite elemente u članovima za razmatranje (po mom načinu, odbacio bih [inlmath]\left(1,1\right),\left(2,2\right),\left(3,3\right)[/inlmath] i ne bi mi ostalo ništa za razmatranje).

Drugi primer mi je bio još nelogičniji zbog čega relacija nije tranzitivna;
Skup [inlmath]A[/inlmath] nam je isti, a njegova relacija nek bude npr [inlmath]\rho=\left\{\left(1,2\right),\left(2,1\right),\left(1,1\right)\right\}[/inlmath]
Istim postupkom, odbacim par [inlmath](1,1)[/inlmath] i posmatram parove [inlmath](1,2)[/inlmath] i [inlmath](2,1)[/inlmath], tj. gledamo da li se [inlmath](1,1)[/inlmath] nalazi u skupu [inlmath]\rho[/inlmath] i vidimo da se zaista nalazi, ali relacija iz nekog razloga nije tranzitivna?? (ovo me još više zbunjuje jer je u sličnom primeru gore relacija bila tranzitivna).

Hvala unapred na objašnjenju.
Acim  OFFLINE
 
Postovi: 370
Zahvalio se: 221 puta
Pohvaljen: 55 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Tranzitivnost relacije

Postod Daniel » Petak, 08. Oktobar 2021, 01:15

Acim je napisao:[inlmath]\left(1,2\right)\in\rho[/inlmath] i [inlmath]\left(2,3\right)\in\rho[/inlmath] tj. iz toga sledi da [inlmath]\left(1,3\right)\in\rho[/inlmath] ([inlmath](1,3)[/inlmath] sam dobio tako što sam gledao prvi element prvog para i 2. element drugog para) i vidimo da je relacija već sada tranzitivna (koliko sam shvatio, bitno je da je samo jedan ovakav iskaz tačan i da je onda relacija tranzitivna).

Ovo u zagradi je netačno. :nene: Da bi relacija bila tranzitivna, mora za bilo koja tri uređena para važiti [inlmath]x\rho y\land y\rho z\;\Longrightarrow\;x\rho z[/inlmath] (definicija tranzitivnosti glasi [inlmath]({\color{red}\forall}x,y,z\in S)(x\rho y\;\land\;y\rho z\;\Longrightarrow\;x\rho z)[/inlmath], obrati pažnju na univerzalni kvantifikator [inlmath]\forall[/inlmath]).
Znači, da bi dokazao da je relacija tranzitivna, nije dovoljno da nađeš neka tri uređena para za koja to važi, već je neophodno da pokažeš da to važi za bilo koja tri uređena para. To jest, da ih sve ispitaš.
Sa druge strane, ako naiđeš na neka tri uređena para za koja ova osobina ne važi, time si pokazao da relacija nije tranzitivna (tj. našao si kontraprimer), i u tom slučaju dalje ispitivanje tranzitivnosti nije potrebno.

Acim je napisao:Npr neka je [inlmath]A=\left\{1,2,3\right\}[/inlmath] i neka je njegova relacija [inlmath]\rho=\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right)\right\}[/inlmath]
Kako je ova relacija tranzitivna, ako nemam različite elemente u članovima za razmatranje (po mom načinu, odbacio bih [inlmath]\left(1,1\right),\left(2,2\right),\left(3,3\right)[/inlmath] i ne bi mi ostalo ništa za razmatranje).

Tačno, ne bi ti ostalo ništa za razmatranje, prema tome, ne postoji kontraprimer za tranzitivnost, što znači da relacija jeste tranzitivna.
Inače, postoje i ovde uređeni parovi koji zadovoljavaju uslov tranzitivnosti (štaviše, svi uređeni parovi ispunjavaju taj uslov, što i jeste uslov da bi relacija bila tranzitivna):
[dispmath]1\rho1\land1\rho1\;\Longrightarrow\;1\rho1\\
2\rho2\land2\rho2\;\Longrightarrow\;2\rho2\\
3\rho3\land3\rho3\;\Longrightarrow\;3\rho3[/dispmath]
Acim je napisao:Skup [inlmath]A[/inlmath] nam je isti, a njegova relacija nek bude npr [inlmath]\rho=\left\{\left(1,2\right),\left(2,1\right),\left(1,1\right)\right\}[/inlmath]
Istim postupkom, odbacim par [inlmath](1,1)[/inlmath] i posmatram parove [inlmath](1,2)[/inlmath] i [inlmath](2,1)[/inlmath], tj. gledamo da li se [inlmath](1,1)[/inlmath] nalazi u skupu [inlmath]\rho[/inlmath] i vidimo da se zaista nalazi, ali relacija iz nekog razloga nije tranzitivna?? (ovo me još više zbunjuje jer je u sličnom primeru gore relacija bila tranzitivna).

Ova relacija nije tranzitivna jer ne važi [inlmath]2\rho1\land1\rho2\;\Longrightarrow\;2\rho2[/inlmath], pošto relacija ne sadrži uređeni par [inlmath](2,2)[/inlmath]. Kada bi sadržala i taj par, bila bi tranzitivna. Uporedi ovu tvoju relaciju s ovom relacijom.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Tranzitivnost relacije

Postod Acim » Petak, 08. Oktobar 2021, 07:34

Sada shvatam, hvala puno.
Acim  OFFLINE
 
Postovi: 370
Zahvalio se: 221 puta
Pohvaljen: 55 puta


Povratak na TEORIJA SKUPOVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 24 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Petak, 29. Mart 2024, 06:07 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs