| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: 
Lokacija: Heriot-Watt University, Edinburgh
|
 Postano: 19:45 čet, 6. 2. 2014 Naslov: |
    |
|
|
[quote="stara"]
Još bih zamolila nekoga za rješenje zadnjeg zadatka druge grupe u kolokviju iz 2008:
http://web.math.pmf.unizg.hr/~veky/B/TS.k2z.08-07-02.pdf[/quote]
Neka je [tex]A[/tex] proizvoljan beskonačan skup i neka je [tex]S \stackrel{\mathrm{def}}{=} \{\mathcal{K}\mid \mathcal{K} \subseteq \mathcal{P}(A) \land (\forall X\in\mathcal{K})(A\setminus X\in\mathcal{K}) \land (\forall X\in\mathcal{K})(\forall Y\in\mathcal{K})(X\cup Y\in\mathcal{K})\land (\forall X\in\mathcal{K})(\mathop{\mathrm{card}}X\geqslant \aleph_0)\}[/tex]. Treba dokazati postojanje maksimalnog elementa u parcijalno uređenom skupu [tex](S,\subset)[/tex].
Kao prvo, uočimo da je [tex]S\not=\emptyset[/tex], jer je [tex]\emptyset\in S[/tex].
Neka je sada [tex]\mathcal{C}[/tex] proizvoljan neoprazan lanac u [tex]S[/tex]. Označimo [tex]\mathcal{G}\stackrel{\mathrm{def}}{=}\bigcup\mathcal{C}[/tex].
Očito vrijedi [tex](\forall\mathcal{K}\in\mathcal{C})(\mathcal{K}\subseteq\mathcal{G})[/tex]. Ako dokažemo da je [tex]\mathcal{G}\in S[/tex], dokazali smo da [tex]\mathcal{C}[/tex] ima gornju među u [tex]S[/tex].
Neka su [tex]X, Y\in\mathcal{G}[/tex] proizvoljni. Kako je [tex]X\in\bigcup\mathcal{C}[/tex], vidimo da postoji [tex]\mathcal{K}_x\in\mathcal{C}[/tex] takav da je [tex]X\in\mathcal{K}_x[/tex]. Analogno vidimo da postoji [tex]\mathcal{K}_y\in\mathcal{C}[/tex] takav da je [tex]Y\in\mathcal{K}_y[/tex].
Kako je [tex]\mathcal{C}[/tex] lanac, vidimo da vrijedi [tex]\mathcal{K}_x\subseteq\mathcal{K}_y[/tex] ili [tex]\mathcal{K}_y\subseteq\mathcal{K}_x[/tex]. Definirajmo [tex]\mathcal{K}_0\stackrel{\mathrm{def}}{=}\mathcal{K}_x\cup\mathcal{K}_y[/tex] i uočimo da vrijedi [tex]X,Y\in\mathcal{K}_0[/tex] i [tex]\mathcal{K}_0\in\mathcal{C}[/tex].
Kako bi dokazali da je [tex]\mathcal{G}\in S[/tex] trebamo provjeriti tri stvari.
1. Vrijedi li [tex]A\setminus X\in\mathcal{G}[/tex]?
Kako je [tex]X\in\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], mora biti i [tex]A\setminus X\in\mathcal{K}_0\subseteq\mathcal{G}[/tex].
2. Vrijedi li [tex]X\cup Y\in\mathcal{G}[/tex]?
Kako vrijedi [tex]X,Y\in\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], mora vrijediti i [tex]X\cup Y\in\mathcal{K}_0\subseteq\mathcal{G}[/tex].
3. Da li je [tex]X[/tex] beskonačan?
Znamo da je [tex]\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], pa p definiciji skupa [tex]S[/tex] svi elementi od [tex]\mathcal{K}_0[/tex] moraju biti beskonačni. Kako je [tex]X\in\mathcal{K}_0[/tex], vidimo da je [tex]X[/tex] beskonačan skup.
Ovim smo dokazali da svaki lanac u [tex]S[/tex] ima gornju među u [tex]S[/tex], pa iz Zornove leme slijedi da [tex]S[/tex] ima maksimalni element.
Neka je [tex]A[/tex] proizvoljan beskonačan skup i neka je [tex]S \stackrel{\mathrm{def}}{=} \{\mathcal{K}\mid \mathcal{K} \subseteq \mathcal{P}(A) \land (\forall X\in\mathcal{K})(A\setminus X\in\mathcal{K}) \land (\forall X\in\mathcal{K})(\forall Y\in\mathcal{K})(X\cup Y\in\mathcal{K})\land (\forall X\in\mathcal{K})(\mathop{\mathrm{card}}X\geqslant \aleph_0)\}[/tex]. Treba dokazati postojanje maksimalnog elementa u parcijalno uređenom skupu [tex](S,\subset)[/tex].
Kao prvo, uočimo da je [tex]S\not=\emptyset[/tex], jer je [tex]\emptyset\in S[/tex].
Neka je sada [tex]\mathcal{C}[/tex] proizvoljan neoprazan lanac u [tex]S[/tex]. Označimo [tex]\mathcal{G}\stackrel{\mathrm{def}}{=}\bigcup\mathcal{C}[/tex].
Očito vrijedi [tex](\forall\mathcal{K}\in\mathcal{C})(\mathcal{K}\subseteq\mathcal{G})[/tex]. Ako dokažemo da je [tex]\mathcal{G}\in S[/tex], dokazali smo da [tex]\mathcal{C}[/tex] ima gornju među u [tex]S[/tex].
Neka su [tex]X, Y\in\mathcal{G}[/tex] proizvoljni. Kako je [tex]X\in\bigcup\mathcal{C}[/tex], vidimo da postoji [tex]\mathcal{K}_x\in\mathcal{C}[/tex] takav da je [tex]X\in\mathcal{K}_x[/tex]. Analogno vidimo da postoji [tex]\mathcal{K}_y\in\mathcal{C}[/tex] takav da je [tex]Y\in\mathcal{K}_y[/tex].
Kako je [tex]\mathcal{C}[/tex] lanac, vidimo da vrijedi [tex]\mathcal{K}_x\subseteq\mathcal{K}_y[/tex] ili [tex]\mathcal{K}_y\subseteq\mathcal{K}_x[/tex]. Definirajmo [tex]\mathcal{K}_0\stackrel{\mathrm{def}}{=}\mathcal{K}_x\cup\mathcal{K}_y[/tex] i uočimo da vrijedi [tex]X,Y\in\mathcal{K}_0[/tex] i [tex]\mathcal{K}_0\in\mathcal{C}[/tex].
Kako bi dokazali da je [tex]\mathcal{G}\in S[/tex] trebamo provjeriti tri stvari.
1. Vrijedi li [tex]A\setminus X\in\mathcal{G}[/tex]?
Kako je [tex]X\in\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], mora biti i [tex]A\setminus X\in\mathcal{K}_0\subseteq\mathcal{G}[/tex].
2. Vrijedi li [tex]X\cup Y\in\mathcal{G}[/tex]?
Kako vrijedi [tex]X,Y\in\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], mora vrijediti i [tex]X\cup Y\in\mathcal{K}_0\subseteq\mathcal{G}[/tex].
3. Da li je [tex]X[/tex] beskonačan?
Znamo da je [tex]\mathcal{K}_0\in\mathcal{C}\subseteq S[/tex], pa p definiciji skupa [tex]S[/tex] svi elementi od [tex]\mathcal{K}_0[/tex] moraju biti beskonačni. Kako je [tex]X\in\mathcal{K}_0[/tex], vidimo da je [tex]X[/tex] beskonačan skup.
Ovim smo dokazali da svaki lanac u [tex]S[/tex] ima gornju među u [tex]S[/tex], pa iz Zornove leme slijedi da [tex]S[/tex] ima maksimalni element.
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
aptx
Forumaš(ica)
Pridružen/a: 11. 01. 2013. (00:15:01)
Postovi: (15)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
stara
Forumaš(ica)
Pridružen/a: 06. 02. 2014. (15:27:38)
Postovi: (4)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
angelika
Forumaš(ica)
Pridružen/a: 08. 02. 2011. (17:26:51)
Postovi: (5F)16
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
angelika
Forumaš(ica)
Pridružen/a: 08. 02. 2011. (17:26:51)
Postovi: (5F)16
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 14:17 čet, 20. 2. 2014 Naslov: |
|
|
|
[quote="aj_ca_volin_te"]Plzz netko :lol: pomoc oko zadatka s ovogodisnjeg prvog kolokvija :D
Zadatak
Odredite kardinalnost skupa svih prebrojivih relacija na [tex]\mathcal{P}(\mathbb{R})[/tex].
[/quote]
Ovo [b]ne[/b] vrijedi: [tex]S[/tex]={skup svih prebrojivih relacija na [tex]\mathcal{P}(\mathbb{R})[/tex]}[tex]\subseteq\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})[/tex]
Razlog: relacija na [tex]\mathcal{P}(\mathbb{R})[/tex] je podskup od [tex]\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})[/tex], odnosno element od [tex]\mathcal{P}\left(\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\right)[/tex], prema tome: [tex]S \subseteq \mathcal{P}\left(\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\right)[/tex].
Slijedi rješenje zadatka, no prije toga mali [i]disclaimer[/i]: Budući da je zadatak malo teži, neću raspisivati sve detalje, nego ću za neke manje-više očite stvari reći da se lako vidi, pa promisli zašto se lako vidi. :wink: Osim toga, kada mi zatreba skup neke kardinalnosti, umjesto da kažem npr. "uzmimo prozivoljni skup kardinalnosti [tex]2^\mathfrak{c}[/tex]", jednostavno ću uzeti baš [tex]2^\mathfrak{c}[/tex] jer je to sasvim dobar skup odgovarajuće kardinalnosti, pa time izbjegavam uvođenje dodatnih oznaka u raspis koji će ionako izgledati kao da je prepun hijeroglifa.
Trebamo odrediti kardinalnost skupa [tex]S=\{\rho\mid\rho\subseteq\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\land\mathop{\mathrm{card}}\rho=\aleph_0\}[/tex]. Lako se vidi da nije bitno čega je točno [tex]\rho[/tex] podskup, nego nam je samo bitna kardinalnost tog skupa. Prema tome, za skup [tex]S'=\{X\mid X\subseteq 2^\mathfrak{c} \land \mathop{\mathrm{card}}X=\aleph_0\}[/tex] vrijedi [tex]S\sim S'[/tex].
Prebrojive podskupove možemo promatrati kao injektivne slike prebrojivih skupova. Definirajmo stoga skup [tex]S''=\{f\mid f\colon\aleph_0\to 2^\mathfrak{c} \land f \text{ je injekcija}\}[/tex]. Uočimo da je preslikavanje [tex]f\mapsto\mathop{\mathrm{rng}}f[/tex] surjekcija sa [tex]S''[/tex] na [tex]S'[/tex], što nam daje [tex] \mathop{\mathrm{card}}S'\leqslant \mathop{\mathrm{card}} S''[/tex]. Kako je [tex]S''\subseteq {}^{\aleph_0}{\left(2^\mathfrak{c}\right)}[/tex], vidimo da vrijedi i [tex]\mathop{\mathrm{card}}S''\leqslant \left(2^\mathfrak{c}\right)^{\aleph_0}=2^\mathfrak{c}[/tex]. Ovim smo dobili gornju ogradu na kardinalnost od [tex]S'[/tex]: [tex]\mathop{\mathrm{card}} S' \leqslant 2^\mathfrak{c}[/tex].
Kako bismo dobili i donju ogradu, promotrimo funkciju [tex]\Phi\colon 2^{\mathfrak{c}}\setminus\aleph_0\to S'[/tex] koja proizvoljnom ordinalu [tex]\alpha\in2^{\mathfrak{c}}\setminus\aleph_0[/tex] pridružuje skup [tex]\Phi(\alpha) \mathop{:=} \aleph_0\cup\{\alpha\}[/tex]. Očito vrijedi [tex]\mathop{\mathrm{card}}\left(\Phi(\alpha)\right) = \aleph_0[/tex], pa je prema tome [tex]\Phi(\alpha)[/tex] uistinu element skupa [tex]S'[/tex], odnosno funkcija [tex]\Phi[/tex] je dobro definirana. Injektivnost funkcije [tex]\Phi[/tex] trivijalno slijedi iz definicije, što znači da vrijedi [tex]2^\mathfrak{c} = \mathop{\mathrm{card}}\left( 2^{\mathfrak{c}}\setminus\aleph_0\right) \leqslant \mathop{\mathrm{card}} S'[/tex].
Ovim smo dokazali da je [tex]\mathop{\mathrm{card}} S' = 2^{\mathfrak{c}}[/tex], a zbog ekvipotentnosti skupova [tex]S[/tex] i [tex]S'[/tex] očito je i [tex]\mathop{\mathrm{card}} S = 2^{\mathfrak{c}}[/tex].
| aj_ca_volin_te (napisa): | Plzz netko  pomoc oko zadatka s ovogodisnjeg prvog kolokvija 
Zadatak
Odredite kardinalnost skupa svih prebrojivih relacija na [tex]\mathcal{P}(\mathbb{R})[/tex].
|
Ovo ne vrijedi: [tex]S[/tex]={skup svih prebrojivih relacija na [tex]\mathcal{P}(\mathbb{R})[/tex]}[tex]\subseteq\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})[/tex]
Razlog: relacija na [tex]\mathcal{P}(\mathbb{R})[/tex] je podskup od [tex]\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})[/tex], odnosno element od [tex]\mathcal{P}\left(\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\right)[/tex], prema tome: [tex]S \subseteq \mathcal{P}\left(\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\right)[/tex].
Slijedi rješenje zadatka, no prije toga mali disclaimer: Budući da je zadatak malo teži, neću raspisivati sve detalje, nego ću za neke manje-više očite stvari reći da se lako vidi, pa promisli zašto se lako vidi.  Osim toga, kada mi zatreba skup neke kardinalnosti, umjesto da kažem npr. "uzmimo prozivoljni skup kardinalnosti [tex]2^\mathfrak{c}[/tex]", jednostavno ću uzeti baš [tex]2^\mathfrak{c}[/tex] jer je to sasvim dobar skup odgovarajuće kardinalnosti, pa time izbjegavam uvođenje dodatnih oznaka u raspis koji će ionako izgledati kao da je prepun hijeroglifa.
Trebamo odrediti kardinalnost skupa [tex]S=\{\rho\mid\rho\subseteq\mathcal{P}(\mathbb{R})\times\mathcal{P}(\mathbb{R})\land\mathop{\mathrm{card}}\rho=\aleph_0\}[/tex]. Lako se vidi da nije bitno čega je točno [tex]\rho[/tex] podskup, nego nam je samo bitna kardinalnost tog skupa. Prema tome, za skup [tex]S'=\{X\mid X\subseteq 2^\mathfrak{c} \land \mathop{\mathrm{card}}X=\aleph_0\}[/tex] vrijedi [tex]S\sim S'[/tex].
Prebrojive podskupove možemo promatrati kao injektivne slike prebrojivih skupova. Definirajmo stoga skup [tex]S''=\{f\mid f\colon\aleph_0\to 2^\mathfrak{c} \land f \text{ je injekcija}\}[/tex]. Uočimo da je preslikavanje [tex]f\mapsto\mathop{\mathrm{rng}}f[/tex] surjekcija sa [tex]S''[/tex] na [tex]S'[/tex], što nam daje [tex] \mathop{\mathrm{card}}S'\leqslant \mathop{\mathrm{card}} S''[/tex]. Kako je [tex]S''\subseteq {}^{\aleph_0}{\left(2^\mathfrak{c}\right)}[/tex], vidimo da vrijedi i [tex]\mathop{\mathrm{card}}S''\leqslant \left(2^\mathfrak{c}\right)^{\aleph_0}=2^\mathfrak{c}[/tex]. Ovim smo dobili gornju ogradu na kardinalnost od [tex]S'[/tex]: [tex]\mathop{\mathrm{card}} S' \leqslant 2^\mathfrak{c}[/tex].
Kako bismo dobili i donju ogradu, promotrimo funkciju [tex]\Phi\colon 2^{\mathfrak{c}}\setminus\aleph_0\to S'[/tex] koja proizvoljnom ordinalu [tex]\alpha\in2^{\mathfrak{c}}\setminus\aleph_0[/tex] pridružuje skup [tex]\Phi(\alpha) \mathop{:=} \aleph_0\cup\{\alpha\}[/tex]. Očito vrijedi [tex]\mathop{\mathrm{card}}\left(\Phi(\alpha)\right) = \aleph_0[/tex], pa je prema tome [tex]\Phi(\alpha)[/tex] uistinu element skupa [tex]S'[/tex], odnosno funkcija [tex]\Phi[/tex] je dobro definirana. Injektivnost funkcije [tex]\Phi[/tex] trivijalno slijedi iz definicije, što znači da vrijedi [tex]2^\mathfrak{c} = \mathop{\mathrm{card}}\left( 2^{\mathfrak{c}}\setminus\aleph_0\right) \leqslant \mathop{\mathrm{card}} S'[/tex].
Ovim smo dokazali da je [tex]\mathop{\mathrm{card}} S' = 2^{\mathfrak{c}}[/tex], a zbog ekvipotentnosti skupova [tex]S[/tex] i [tex]S'[/tex] očito je i [tex]\mathop{\mathrm{card}} S = 2^{\mathfrak{c}}[/tex].
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
aj_ca_volin_te
Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
|
|
| [Vrh] |
|
marsupial
Forumaš(ica)
Pridružen/a: 09. 01. 2012. (22:46:33)
Postovi: (63)16
Spol: 
|
|
| [Vrh] |
|
Loo
Forumaš(ica)
Pridružen/a: 11. 06. 2012. (16:02:07)
Postovi: (D0)16
Spol: 
|
|
| [Vrh] |
|
|
taman sam ga i ja skuzio pa da cu ga pretipkati ovdje 
hvala ti 
ali sve je jasno 
od mene