Student 555 – vnoreni1 [REL] – Diskrétní matematika

Martin Koutecký — modified 2021-10-21 15:40 (441 days ago) — reply

*Lexikografické uspořádání* $\N \times \N$ je uspořádání po souřadnicích, tzn. platí $(a,b) \leq (c,d)$ pokud $a < c$ nebo $a = c$ a $b \leq d$.

*Vnoření* jedné uspořádané množiny $(X, \leq)$ do jiné uspořádané množiny $(Y, \preccurlyeq)$ je prosté zobrazení $f: X \to Y$ takové, že $\forall x, x' \in X: x \leq x' \Leftrightarrow f(x) \preccurlyeq f(x')$

1. Popište nějaké vnoření množiny $\{1,2\}\times \N$ s~lexikografickým
uspořádáním do uspořádané množiny $(\mathbb{Q},\leq)$, kde $\leq$ je obvyklé uspořádání
podle velikosti.
2. Popište vnoření $\N\times \N$ s lexikografickým uspořádáním do
  $(\mathbb{Q},\leq)$.

Martin Koutecký — 2021-10-22 13:55 (440 days ago) — reply

Ahoj, někteří z vás bojujete s definicí vnoření. Tady je příklad:

Řekněme, že $X = \{1,2,3\}$ a uspořádání $\leq$ je $1 \leq 2 \leq 3$. A $Y= \{a,b,c,d\}$ a uspořádání $\preccurlyeq$ je definováno jako $a \preccurlyeq b \preccurlyeq c$ a zároveň $a \preccurlyeq d \preccurlyeq c$. Pak funkce $f: X \to Y$ definovaná jako $f(1) = a, f(2) = b, f(3) = c$ je vnoření toho prvního uspořádání do toho druhého.

Student 555 — 2021-10-26 22:21 (435 days ago) — reply

1. Lexikografické uspořádání $\{1,2\} × N$ může vypdat $\{1,1\} \le \{1,2\} \le \{2,2\}$, nebo takto $\{1,1\} \le \{2,1\} \le \{2,2\}$.Tedy vnoření prvního uspořádání do Q ${1 \over 3} \le {1 \over 2} \le {1 \over 1}$ by mohlo vypdat takto $f(\{1,1\})={1 \over 3}$,$f(\{1,2\})={1 \over 2}$,$f(\{2,2\})={1 \over 1}$
2. Lexikografické uspořádání $N×N$ by obecně naznačit takto $\{x,x\} \le \{x,y\} nebo \{y,x\}  \le \{y,y\}$. Upořádání Q je trošku obtížnější popsat. Ale zjednodušeně Q jsou zlomky ve tvaru ${a \over b}$ kde $a,b \in \Z,b \ne 0$ obecně čím větší b tím menší prvek. Ve finále bych mohl jako příklad použít uspořádání jako v 1.

Santa Claus — 2021-10-27 18:38 (434 days ago) — edit — reply

Ahoj, asi sis špatně vyložil příklad na vnoření. V pomocném příkladu máš tříprvkovou množinu $X$, takže zobrazení bude taky tříprvkové.

V prvním příkladu máš ale nekonečnou množinu, a sice:

$\{1,2\}\times \N = \{(1, 1), (1, 2), (1, 3), ... , (2, 1), (2, 2), ... \}$

Ta už je taky uspořádaná:

$(1, 1) < (1, 2) < (1, 3) < ...  < (2, 1) < (2, 2) < ...$

Úkolem je najít takové zobrazení, které **každému** prvku přiřadí číslo z $\mathbb{Q}$, a pro které bude platit druhá podmínka vnoření (myslím tím: $\forall x, x' \in X: x \leq x' \Leftrightarrow f(x) \preccurlyeq f(x')$)

V druhém příkladu je to skoro stejné, jenom ta původní množina je kartézský součin $\N \times \N$

$\N \times \N = \{(1, 1), (1, 2), (1, 3), ... , (2, 1), (2, 2), ..., (3, 1), ... \}$

Points: 0.00

Martin Koutecký — 2021-10-28 07:26 (434 days ago) — reply

Souhlas s korektorem, jen ještě poznámka k notaci, uspořádané dvojice se píší s kulatými závorkami $(a,b)$, když píšeš $\{1,1\}$, tak to je ve skutečnosti množina obsahující jediný prvek, $1$. Samozřejmě to vůbec není podstata toho, co je potřeba napravit, ale pomůže to srozumitelnosti.

Student 555 — 2021-11-21 20:45 (409 days ago) (after deadline) — reply

Takže lexikografická uspořádání budou vypdat takto:

1.$(1,1)<(1,2)<...<(2,1)<(2,2)<...$

2.$(1,1)<(1,2)<...<(2,1)<(2,2)<...<(3,1)<(3,2)<...$

A tato uspořádání bych mohl vnořit stejným postupem. Jelikož to jsou prvky uspořádané dvojice (a,b) tak je mohu využít na konstrukci zlomků. Obecně bych to zapsal takto. $f(a,b) = \frac{a}{b}$. Což by nás potom dovedlo k tomuto.

1.f(1,1)=$\frac{1}{1}\le$f(1,2)$\frac{1}{2}\le...\le$f(2,1)=$\frac{2}{1}\le$f(2,2)=$\frac{2}{2}\le...$

2.f(1,1)=$\frac{1}{1}\le$f(1,2)$\frac{1}{2}\le...\le$f(2,1)=$\frac{2}{1}\le$f(2,2)=$\frac{2}{2}\le...$f(3,1)=$\frac{3}{1}\le$f(3,2)=$\frac{3}{2}\le...$

Santa Claus — 2021-11-21 21:49 (409 days ago) — edit — reply

Ahoj, takovéto zobrazení by nebylo vnořením, podívej se třeba na dvojice $(1, 2)$ a $(2 , 5)$: Platí $1 < 2$, ale $\frac12 >  \frac25$.

Už u toho prvního příkladu píšeš $\frac11 \leq \frac12 \leq \frac21 \leq \frac22$, z čehož vlastně skoro žádná nerovnost neplatí. Po úpravě to totiž vypadá takto:
$1 \leq 0.5 \leq 2 \leq 1$.

Zkus to ještě přepracovat.

Student 555 — 2021-11-26 10:36 (405 days ago) (after deadline) — reply

Ahoj, tohle bude poslední jinak mě už nic nenapadá.
Opět bych si vzal v uspořádanou dvojici ve formátu (a,b) a vnořil jí tímto způsobem $f(a,b)$=${b}\over{b+1}$ $+a$

Což by mělo dosáhnout tohoto výsledku:

1. $f(1,1)$=${3}\over{2}$ $\le$ $f(1,2)$=${5}\over{3}$ $\le$ $...$ $\le$ $f(2,1)$=${5}\over{2}$ $\le$ $f(2,2)$=${8}\over{3}$ $\le$ $...$

2. $f(1,1)$=${3}\over{2}$ $\le$ $f(1,2)$=${5}\over{3}$ $\le$ $...$ $\le$ $f(2,1)$=${5}\over{2}$ $\le$ $f(2,2)$=${8}\over{3}$ $\le$ $...$ $\le$
$f(3,1)$=${7}\over{2}$ $\le$ $f(3,2)$=${11}\over{3}$ $\le$ $...$

Martin Koutecký — 2021-11-30 12:02 (401 days ago) — reply

To už mi přijde funkční, dobrá práce :)

Points: 5.00

The Postal Owl

Diskrétní matematika

vnoreni1 [REL] (Student 555)

New post (You can use Markdown with KaTeX math here)