Praca domowa z Podstaw Matematyki

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Poniżej znajdują się pisemne zadania domowe (każde za 10 punktów), terminy podane niżej.

Zadanie 1 (termin: 26 stycznia). Niech $f:X\to Y$ będzie funkcją.
Pokazać, że następujące warunki są równoważne:
1) Funkcja $f$ jest różnowartościowa
2) Dla dowolnego zbioru $Z$ oraz dowolnych
dwóch funkcji $g,h:Z\to X$, zachodzi implikacja $f\circ g=f\circ h\implies g=h$.

Zadanie 2 (termin: 19 stycznia). Niech $f:\mathbb R^3\to \mathbb R$ będzie funkcją. Pokazać, że istnieje $x\in\mathbb R$ taki, że zbiór $f^{-1}(\set x)$ nie zawiera żadnej kuli.

Zadanie 3 (termin: 26 stycznia). Niech $\sim$ będzie relacją równoważności na $\mathbb R^ {\mathbb R}$ taką, że dla $f,g:\mathbb R\to\mathbb R$, zachodzi $f\sim g$ wtw. gdy funkcja $h=f-g$ jest taka, że $h(n)=0$ dla $n\in\mathbb Z$.

  • Znaleźć funkcję $G$ taką, że $\sim\ =\ \textrm{ker}G$ (czyli $f\sim g$ wtw. $G(f)=G(g)$).
  • Jaka jest moc zbioru $\mathbb R^{\mathbb R}/\sim$ klas abstrakcji relacji $\sim$?
  • Niech $C$ będzie klasą abstrakcji relacji $\sim$. Jaka jest moc $C$?

Zasada dobrego uporządkowania

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Udowodnimy następujące twierdzenie, zwane zasadą dobrego uporządkowania.
Tw.Każdy niepusty podzbiór zbioru liczb naturalnych posiada element najmniejszy.

Continue reading Zasada dobrego uporządkowania

Zadania dodatkowe z pmat.

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Można zdobyć dodatkowe 40 punktów, pisemnie oddając mi rozwiązania następujących zadań.
Termin oddania: przyszła środa.

  1. Udowodnić, że istnieje liczba rzeczywista $r>0$ o następującej własności.
    W przestrzeni trójwymiarowej $\mathbb R^3$ sfera o promieniu $r$ i środku w $(0,0,0)$ nie zawiera żadnego punktu o współrzędnych wymiernych.

    Inaczej mówiąc, nie istnieje punkt o trzech współrzędnych wymiernych, którego odległość od punktu $(0,0,0)$ wynosi dokładnie $r$. Jeszcze inaczej, w przestrzeni $\mathbb Q^3$, sfera o środku $(0,0,0)$ i promieniu $r$ jest pusta.

  2. Niech $U\subseteq\mathbb N$.
    Powiemy, że funkcja $x:\{0,1\}^{U}\rightarrow\{0,1\}$
    jest xor-em na zbiorze $U$, jeżeli spełniona jest następująca własność (*):

    $x(a)=1-x(a’)$ jeżeli a i a’ są funkcjami które różnią się dokładnie na jednej pozycji $a\in U$, tzn. istnieje takie $n\in U$, że $a(n)\neq a'(n)$ oraz $a(m)=a'(m)$ dla wszystkich $m\in U-\{n\}$.

    Na przykład, dla $U=\set{0,\ldots,10}$, funkcja $x:\{0,1\}^U\rightarrow\{0,1\}$ zdefiniowana tak, że
    $x(a)=(\sum_{i=0}^{10} a(i))\ (\textit{mod}\ 2)$
    jest xor-em na zbiorze $U$.

    Pokazać, że istnieje funkcja która jest xor-em na zbiorze $\mathbb N$.

    Wskazówka: Rozważyć porządek przez inkluzję na zbiorze wszystkich xor-ów, na wszystkich podzbiorach $U\subseteq\mathbb N$:
    $$(\{x: x\text{ jest xor-em na pewnym podzbiorze }U\subseteq\mathbb N\},\subseteq).$$
    Porządek przez inkluzję na funkcjach jest zadany tak:
    $$f\subseteq g\Leftrightarrow (\text{Dom}(f)\subseteq\text{Dom}(g))\wedge (\forall x\in \text{Dom}(x)f(x)=g(x)).$$

    Korekta:
    xor-em częściowym nazwiemy funkcję częściową $f: 2^{\mathbb N}\to \{0,1\}$,
    która spełnia własność (*) dla funkcji $a,a’\in \textrm{Dom}(f)$.
    (Czyli taki xor bierze pod uwagę wszystkie pozycje ciągu $a$, ale
    jest określony tylko dla niektórych ciągów $a\in 2^{\mathbb N}$).
    Np. dobrym xor-em częściowym jest funkcja która jest określona tylko dla funkcji stałej $0_{\mathbb N}$ tak, że $f(0_\mathbb N)=0$.

    Na xor-ach częściowych jest zadany porządek przez inkluzję, taki jak opisany wyżej.
    Należy rozważyć ten porządek.