Ultraprodukty

$% \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} $

Przytoczę tutaj konstrukcję, która pozwala w dość namacalny sposób opisać model niestandardowy arytmetyki. Konstrukcja ta nazywa się ultraproduktem, i jest jedną z metod dowodzenia twierdzenia o zwartości, w następującym wariancie (który jest równoważny zwykłej wersji tw. o zwartości – zob. tutaj).

Continue reading Ultraprodukty

Praca domowa – wektory własne

$% \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} $

Zadanie 1. Znajdź wartości własne i podprzestrzenie własne dla następujących macierzy (przypomnienie: jeśli $\lambda$ jest wartością własną, to $$V_\lambda=\set{v: A\cdot v=\lambda\cdot v}=\textrm{Ker}(A-\lambda\cdot Id)$$ jest związaną z nim podprzestrzenią własną).

$A=\left[\begin{array}{cccc}3&-1&0&0\\1&5&-1&0\\0&0&4&0\\0&0&1&4\end{array}\right],$

$B=\left[\begin{array}{cccc}1&-3&4\\4&-7&8\\6&-7&7\end{array}\right]$

Zadanie 2. Niech $A$ będzie macierzę $n\times n$, której wartości na diagonali są równe 2, a poza diagonalą 1 (czyli $A=([i=j]+1)_{1\le i,j\le n}$.

Oblicz wyznacznik macierzy $A$.

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$?

Twierdzenia Gödla

$% \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} $

Będziemy tu omawiać twierdzenia Gödla – o zupełności, o niezupełności, o związkach z twierdzeniem o zwartości, twierdzeniem Turinga, itd.

Continue reading Twierdzenia Gödla

Przed kolokwium z GALu

$% \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} $

W czwartek 8 stycznia odbędzie się kolokwium z GALu. Obowiązuje materiał z wykładów, do wyznaczników (ale bez wyznaczników).

To oznacza, że także obowiązują Państwa tematy takie jak:

macierze Grama, kąt między wektorami, izomorfizmy, epimorfizmy, monomorfizmy, przestrzenie dualne i endomorfizmy,

które nie były omawiane bezpośrednio na ćwiczeniach (choć pojawiały się niejawnie w różnych postaciach). Tym niemniej, od Państwa się wymaga znajomości tych pojęć, gdyż pojawiły się one na wykładzie. Korzystając z wiedzy zdobytej na wykładzie i na ćwiczeniach oraz z własnego rozumu, posługiwanie się tymi pojęciami nie powinno sprawić Państwu problemów. Mimo tego, poniżej omawiam pobieżnie te pojęcia. Jeszcze niżej omawiam typowe zadania i typowe metody ich rozwiązywania.

Macierz Grama układu wektorów $\set{v_1,\ldots,v_n}$ w przestrzeni $V$ z iloczonym skalarnym $\langle\cdot,\cdot\rangle$ jest macierzą która na pozycji $(i,j)$ ma iloczyn skalarny $\langle v_i,v_j\rangle$. Jest to macierz symetryczna. Jeżeli układ jest ortonormalny, to jest to macierz identyczności. Gdy $V=\mathbb R^n$ oraz iloczyn skalarny jest standardowy (tj. $\langle v,w\rangle=v^T\cdot w$), to ta macierz to $A^T\cdot A$, gdzie $A$ to macierz której kolumny to wektory $u_1,\ldots,u_n$. Ta macierz pojawiała się na ćwiczeniach, np. tu i tu.

Kąty. Państwo oczywiście muszą wiedzieć, jaki jest wzór na cosinus kąta między dwoma wektorami, wyrażony przez iloczyny skalarne. Choć kątów nigdy nie liczyliśmy, liczyliśmy iloczyny skalarne, a (cosinus) kąta już sobie Państwo mogą sami w razie potrzeby policzyć.

Endomorfizm przestrzeni $V$ to jest nic innego jak przekształcenie liniowe z przestrzeni $V$ do przestrzeni $V$. Monomorfizm to nic innego jak liniowe przekształcenie różnowartościowe, czyli przekształcenie, którego jądro jest trywialne, czyli zawiera tylko wektor zerowy, a liczenie jąder Państwo mają dobrze opanowane. Epimorfizm to nic innego jak liniowe przekształcenie “na”, a obraz przekształceń liniowych Państwo też mają dobrze opanowane. Wreszcie izomorfizm to jest liniowa bijekcja. Żeby sprawdzić, że przekształcenie liniowe $f:V\to W$ pomiędzy dwiema przestrzeniami (skończenie wymiarowymi) jest izomorfizmem, wystarczy sprawdzić, że ma trywialne jądro (czyli $\textrm{dim}\textrm{Ker}f=0$) i że $\textrm{dim} V=\textrm{dim} W$ – bo ze wzoru $$\textrm{dim} \textrm{Im} f+\textrm{dim}\textrm{Ker} f=\textrm{dim} V$$ wynika wtedy, że $\textrm{dim} \textrm{Im} f=\textrm{dim}W$ więc $f$ jest “na” (bo $\textrm{Im} f$ jest podprzestrzenią $W$ pełnego wymiaru, czyli jest jej równa).

Wreszcie, są przestrzenie dualne. Nie użyliśmy tej nazwy podczas ćwiczeń, ale widzieliśmy ogólniejsze pojęcie: przestrzeń liniowa $\mathcal L(V,W)$ wszystkich przekształceń liniowych z przestrzeni $V$ do przestrzeni $W$. Niech $m=\textrm{dim}V,n=\textrm{dim}W$, oraz ustalmy bazy $\set{v_1,\ldots,v_m},\set{w_1,\ldots,w_n}$ przestrzeni $V$ oraz $W$, odpowiednio.

Ponieważ każde przekształcenie liniowe $f:V\to W$ zapisuje się (w ustalonych bazach) jednoznacznie jako macierz wymiaru $n\times m$, wynika stąd, że przestrzeń $\mathcal L(V,W)$ jest izomorficzna z przestrzenią macierzy $n\times m$, która jest w oczywisty sposób przestrzenią wektorową wymiaru $n\cdot m$. Bazę przestrzeni $\mathcal L(V,W)$ tworzą więc przekształcenia odpowiadające macierzom $n\times m$ które mają jedną jedynkę na jakiejś pozycji $(i,j)$, a poza tym same zera, czyli innymi słowy, przekształcenia postaci $E^i_j$, (dla $1\le i\le m$ oraz $1\le j\le n$) o tej własności, że dle $1\le k\le m$,

$$E^i_j(v_k)=\begin{cases}w_j&\textrm{jeżeli } k=i\\0&\textrm{jeżeli }k\neq i\end{cases}$$

Gdy $W=\mathbb K$ jest ciałem bazowym (zazwyczaj $\mathbb K=\mathbb R$), to tę przestrzeń $\mathcal L(V,\mathbb K)$ oznacza się przez $V^*$, a jej elementy nazywa się funkcjonałami liniowymi, i oznacza tradycyjnie symbolami $v^*,w^*,$ itd. Należy jednak pamiętać, że jest to tylko zwyczajowe oznaczenie, a tak na prawdę są to po prostu przekształcenia liniowe z $V$ do $\mathbb K$.

Ciało bazowe $\mathbb K$ ma swoją ulubioną bazę, mianowicie $\set{1}$. Z powyższych rozumowań wynika, że $V^*$ jest przestrzenią wymiaru $m\cdot 1=m$, a bazę tej przestrzeni tworzą np. funkcjonały $E^1_1,E^2_1,\ldots,E^m_1$, które oznacza się też przez $v_1^*,v_2^*,\ldots,v_m^*$ (bo zależą one od wyboru bazy $v_1,\ldots,v_m$ przestrzeni $V$). Tę bazę nazywa się bazą dualną do bazy $v_1,\ldots,v_m$ przestrzeni $V$. Zauważmy, że $v_i^*$ to przekształcenie liniowe z $V$ do $\mathbb K$, którego macierz (w wybranych bazach) to po prostu macierz o jednym wierszu, która ma same zera z wyjątkiem jedynki na pozycji $i$. Czyli, intuicyjnie, $V^*$ to przestrzeń wektorów zapisanych “poziomo”, podczas gdy w przestrzeni $V$ wektory zapisuje się jako macierze “pionowe” (o jednej kolumnie).

Na ćwiczeniach pojawiały się już pewne funkcjonały. Mianowicie, badaliśmy przekształcenie liniowe $D_t:\mathbb R[x]_3\to \mathbb R$ (gdzie $t\in\mathbb R$ jest ustaloną liczbą), zadane wzorem

$$D_t(f)=f'(t).$$

Ponieważ $D_t$ jest przekształceniem liniowy w ciało bazowe $\mathbb R$, jest to więc “funkcjonał”, tj. $D_t\in (\mathbb R[x]_3)^*$. Badaliśmy nawet macierz tego przekształcenia (gdzie $\mathbb R[x]_3$ ma bazę $\mathcal B=\set{1,x,x^2,x^3}$), jest nią macierz

$$[0,1,2t,3t^2]$$ (proszę pamiętać, że $t$ jest konkretną liczbą, więc powyższe jest macierzą liczb rzeczywistych, różną dla różnych liczb $t$).

Jeżeli przez  $\mathcal B^*=\set{v_1^*,v_2^*, v_3^*,v_4^*}$ oznaczymy bazę dualną do bazy $\mathcal B$, to elementy bazy $\mathcal B^*$ są funkcjonałami, czyli przekształceniami z $\mathbb R[x]_3$ w $\mathbb R$, które w bazie $\mathcal B$ mają macierze

$$\begin{array}{cccccc} [v_1^*]^{\mathcal B}&=&[1&0&0&0],\\ [v_2^*]^{\mathcal B}&=& [0&1&0&0],\\ [v_3^*]^{\mathcal B}&=& [0&0&1&0],\\ [v_4^*]^{\mathcal B}&=&[0&0&0&1]\end{array}$$

A ponieważ funkcjonał $D_t$ ma macierz

$$\begin{array}{cccccc} [D_t]^{\mathcal B}&=&[0&1&2t&3t^2]\end{array},$$ to widać, że

$$D_t=0\cdot v_1^*+1\cdot v_2^*+2t\cdot v_3^*+3t^2\cdot v_4^*,$$

czyli w bazie $\mathcal B^*=\set{v_1^*,v_2^*, v_3^*,v_4^*}$ , funkcjonał $D_t$ ma współczynniki $(0,1,2t,3t^2)$. Innymi słowy, funkcjonał $D_t$ w bazie $\mathcal B^*$ zapisuje się jako wektor $$\left[\begin{array}{c}0\\1\\2t\\3t^2\end{array}\right]$$

Podsumowując, raz rozważaliśmy $D_t$ jako przekształcenie liniowe z $\mathbb R[x]_3$ w $\mathbb R$ i obliczyliśmy macierz tego przekształcenia w bazach $\mathcal B$ oraz $\set{1}$; ta macierz to $[0,1,2t,3t^2]$. Innym razem, rozważaliśmy $D_t$ jako wektor w przestrzeni $(\mathbb R[x]_3)^*$, która ma bazę $\mathcal B^*$. W tej bazie, ten wektor zapisuje się jako $[0,1,2t,3t^2]^T$.

 

Zadania przygotowawcze

Polecam wszystkie zadania przygotowawcze z tej strony pana Bechlera. Zadania z kolokwiów z ubiegłych lat są tutaj. Szczególnie polecam pierwsze 3 zadania z kolokwium ubiegłorocznego.

 

Metody rozwiązywania typowych zadań

Jest naprawdę niewiele typów zadań i metod ich rozwiązań, które Państwo muszą opanować.

Typ 0. Dana jest przestrzeń liniowa $V$, znaleźć jej bazę.

Metoda 0: Jeżeli przestrzeń $V$ jest podprzestrzenią przestrzeni $\mathbb R^n$ zadaną poprzez układ równań liniowych, to postępujemy tak, jak opisane poniżej w Metodzie 2. Czasami jednak, przestrzeń $V$ jest zadana w jakiś inny sposób. Wtedy może nie pozostać nic innego (zobacz “Jeszcze jeden przykład” poniżej) jak szukać bazy iteracyjnie: zaczynamy od pustego zbioru wektorów $\mathcal B$, i w każdym kroku, wybieramy dowolny wektor z $V-\textrm{lin}\mathcal B$ (czyli wektor $v\in V$ taki, że układ $\mathcal B\cup\set{v}$ jest liniowo niezależny; zobacz Metodę 1) i dorzucamy go do $\mathcal B$. Powtarzamy tak długo, jak $\textrm{lin}\mathcal B\neq V$.

Typ 1. Sprawdzić, czy układ wektorów w przestrzeni $V$ jest liniowo zależny.

Metoda 1: Znajdujemy współrzędne każdego z wektorów układu w naszej ulubionej bazie przestrzeni $V$ (lub jej nadprzestrzeni $W\supset V$), tworząc macierz, której wiersze to te ciągi współrzędnych. Wykonujemy eliminację Gaussa na wierszach tej macierzy. Jeżeli dostaniemy wiersz zerowy, to znaczy, że układ był liniowo zależny.

Typ 2. Dana jest podprzestrzeń $V$ przestrzeni $\mathbb R^n$, w postaci układu równań. Znaleźć bazę tej podprzestrzeni.

Uwaga: to jest ten sam problem, co znalezienie bazy jądra macierzy.

Metoda 2: Układ równań zapisujemy w postaci macierzowej $A\cdot x=0$ (gdzie $x$ to jest wektor niewiadomych długości $n$, a $0$ to jest wektor długości $m$, gdzie $m$ to liczba równań i też wierszy macierzy $A$). Wtedy oczywiście $V=\textrm{Ker}A$, i szukamy bazy tej przestrzeni. Robimy to wykonując eliminację Gaussa na wierszach macierzy $A$, aż sprowadzimy do macierzy schodkowej $A’$. Wtedy bazę $V=\textrm{Ker}A=\textrm{Ker}A’$ już łatwo znaleźć. [Pro-tip: Można pójść jeszcze dalej, i doprowadzić do postaci schodkowej zredukowanej w której nad wiodącymi jedynkami są same zera. Wreszcie, możemy doprowadzić do postaci zredukowanej diagonalnie usuwając/wstawiając wiersze z samymi zerami tak, by otrzymać macierz kwadratową $A”$ w której wiodące jedynki są tylko na przekątnej. Wtedy przestrzeń $V$ jest rozpięta przez kolumny macierzy $A”-I$, gdzie $I$ to macierz identycznościowa.]

Przykład: Znaleźć bazę podprzestrzeni $V\subset\mathbb R^3$ zadanej równaniami:

\begin{align*}x+y&=0\\ x+y+2z&=0\end{align*}

Oczywiście, $V=\textrm{Ker}A$, gdzie

$$A=\left[\begin{array}{cccc}1&1&0\\1&1&2\end{array}\right]$$

którą przekształcamy (wierszowo) do macierzy

$$A’=\left[\begin{array}{cccc}1&1&0\\0&0&1\end{array}\right]$$

która jest w postaci zredukowanej (nad wiodącymi jedynkami są zera). Dopisujemy jeden wiersz zerowy, tak żeby jedynki wiodące były na przekątnej i żeby otrzymać macierz kwadratową (ogólniej, czasem też trzeba usunąć wiersze zerowe) w postaci schodkowej, zredukowanej diagonalnie:

$$A”=\left[\begin{array}{cccc}1&1&0\\0&0&0\\0&0&1\end{array}\right]$$

Wreszcie, odejmujemy macierz identyczności (czyli odejmujemy jedynki na przekątnej), otrzymując macierz

$$\left[\begin{array}{cccc}0&1&0\\0&-1&0\\0&0&0\end{array}\right]$$

której kolumny rozpinają szukaną przestrzeń. A zatem, $V=\textrm{lin}\set{(1,-1,0)}$.

Typ 2′. Dany jest układ równań afinicznych postaci

\begin{align*}a^1_1\cdot x_1&+\ldots+a^1_n\cdot x_n&=b_1\\\vdots&+\ldots+\vdots&\vdots\\a^m_1\cdot x_1&+\ldots+a^m_n\cdot x_n&=b_m\end{align*}

, gdzie $x_1,x_2,\ldots,x_n$ to zmienne, a $a^i_j,b^i$ to liczby rzeczywiste. Stwierdzić, czy ten układ ma rozwiązanie; jeśli tak, to je znaleźć.

Uwaga 1. To zadanie to to samo, co znalezienie rozwiązań równania macierzowego $A\cdot x=b$, gdzie $x=(x_1,\ldots,x_n)$ to wektor zmiennych, a $A=(a^i_j)$ to macierz $m\times n$, oraz $b$ jest wektorem długości $m$.

Uwaga 2. To zadanie to to samo, co znalezienie współczynników wektora $b$ względem układu wektorów $a_1,\ldots,a_n$. Jeżeli równanie $A\cdot x=b$ nie ma rozwiązań, to znaczy, że $b$ jest liniowo niezależny od tego układu. Jeżeli ten układ $a_1,\ldots,a_n$ jest bazą przestrzeni, to rozwiązanie jest jedno, i opisuje ono współrzędne wektora $b$ w tej bazie.

Metoda 2′. Rozważmy równanie macierzowe $A\cdot x=b$, gdzie $x$ jest wektorem niewiadomych długości $n$. Zbiór rozwiązań układu $A\cdot x=b$ jest postaci $x_0+\textrm{Ker}A$, gdzie $x_0$ to dowolne rozwiązanie, a bazę $\textrm{Ker}A$ obliczamy Metodą 2. Można od razu wykonać eliminację Gaussa na wierszach macierzy rozszerzonej $(A|b)$, sprowadzając ją do postaci schodkowej otrzymując macierz $(A’|b’)$. Wtedy już łatwo opisać rozwiązania równania $A’\cdot x=b’$, które są tym samym, co rozwiązania oryginalnego układu.

[Pro-tip: Możemy dalej zredukować tak, by otrzymać układ $(A”|b”)$, w którym macierz $A”$ jest zredukowana diagonalnie. Jeżeli w tej macierzy ostatnia kolumna (czyli $b”$) ma jakąś wiodącą jedynkę, to układ nie ma rozwiązań. W przeciwnym wypadku, jest jakieś rozwiązanie $x_0$ równania $A”\cdot x=b”$, które łatwo odnaleźć. Zbiór wszystkich rozwiązań, natomiast, jest postaci $$x_0+\textrm{przestrzeń rozpięta przez kolumny macierzy}(A”-I).$$]

Przykład: 

Znaleźć zbiór rozwiązań układu równań:

\begin{align*}x+y&=2\\ x+y+2z&=3\end{align*}

Rozwiązanie:

Szukamy zbioru wektorów $x\in\mathbb R^3$ takich, że $Ax=b$, gdzie $b=(2,3)$ oraz

$$A=\left[\begin{array}{ccc}1&1&0\\1&1&2\end{array}\right].$$

Zapisujemy macierz rozszerzoną:

$$(A|b)=\left[\begin{array}{ccc|c}1&1&0&2\\1&1&2&3\end{array}\right].$$

którą przekształcamy (wierszowo) do macierzy

$$(A’|b’)=\left[\begin{array}{ccc|c}1&1&0&2\\0&0&1&1/2\end{array}\right]$$

która jest w postaci zredukowanej. Dopisujemy wiersz zerowy, tak żeby jedynki wiodące były na przekątnej i żeby po lewej otrzymać macierz w postaci schodkowej, zredukowanej diagonalnie:

$$(A”|b”)=\left[\begin{array}{ccc|c}1&1&0&2\\0&0&0&0\\0&0&1&1/2\end{array}\right].$$

Tak się składa, że w prawej kolumnie nie ma wiodących jedynek, więc są rozwiązania równania $A”\cdot x=b”$, np. wektor $(2,0,1/2)$. Odejmując od $A”$ macierz identyczności (patrz Metoda 2), dostajemy że zbiór rozwiązań to zbiór $(2,0,1/2)+\textrm{lin}\set{(1,-1,0)}$.

Typ 2”. Dana jest podprzestrzeń $V=\textrm{lin}\set{v_1,\ldots,v_n}$ przestrzeni $\mathbb R^n$. Znaleźć zbiór równań opisujących tę przestrzeń.

Metoda 2”. Zadania tego typu są odwrotnością zadania typu 2, lecz metoda ich rozwiązywania jest podobna. Najlepiej opisać tę metodę odwołując się do pojęcia prostopadłości, które mamy w przestrzeni $\mathbb R^n$. Wpierw szukamy bazy przestrzeni $V^\bot=\set{x:x\bot V}$. Przestrzeń $V^\bot$ opisana jest układem równań

\begin{align}\langle v_1,x\rangle&=0\\\cdots&=0\\\langle v_n,x\rangle&=0\end{align}

To można zgrabnie zapisać jednym równaniem macierzowym

$$A\cdot x=0,$$

gdzie $A$ jest macierzą której wiersze to wektory $v_1,\ldots,v_n$, a $x$ i $0$ są wektorami długości $n$. Czyli szukamy jądra $\textrm{Ker}A$, i robimy to stosując Metodę 2.

Znaleźliśmy w ten sposób bazę $\set{w_1,\ldots,w_k}$ przestrzeni $V^\bot$. Ale $V=(V^\bot)^\bot$, a $(V^\bot)^\bot$ opisana jest układem równań

\begin{align*}\langle w_1,x\rangle&=0\\\cdots&=0\\\langle w_k,x\rangle&=0.\end{align*}

Zatem ten układ równań opisuje przestrzeń $V$. Można go zgrabnie zapisać równaniem macierzowym $B\cdot x=0$, gdzie $B$ to macierz, której wiersze to wektory $w_1,\ldots,w_k$.

Przykład: Znaleźć układ równań który opisuje podprzestrzeń $V\subset\mathbb R^4$ rozpiętą przez wektory $$\set{(5,3,1,5),(2,0,1,2),(1,1,0,1)}.$$

Rozwiązanie: Szukamy bazy przestrzeni $V^\bot=\textrm{Ker}A$, gdzie $A$ to macierz której wiersze to powyższe wektory:

$$A=\left[\begin{array}{cccc}5&3&1&5\\2&0&1&2\\1&1&0&1\end{array}\right].$$

Przekształcamy $A$ do macierzy schodkowej, zredukowanej diagonalnie:

$$A’=\left[\begin{array}{cccc}1&0&1/2&1\\0&1&-1/2&0\\0&0&0&0\\0&0&0&0\end{array}\right]$$

Przestrzeń $V^\bot=\textrm{Ker} A’$ jest rozpięta przez wektory

$$(1/2,-1/2,-1,0),(1,0,0,-1).$$

A zatem układ równań opisujący $V=(V^\bot)^\bot$ to układ $B\cdot x=0$, gdzie macierz $B$ ma wiersze będącymi powyższymi wektorami, lub, inaczej:

\begin{align*} x -y-2z&=0\\x-t&=0.\end{align*}

 

Typ 3. Dane jest przekształcenie liniowe $f:\mathbb R^m\to \mathbb R^n$, za pomocą macierzy $m\times n$. Znaleźć jądro oraz obraz przekształcenia $f$.

Metoda 3: Obraz jest po prostu przestrzenią liniową rozpiętą przez kolumny macierzy. Możemy znaleźć bazę tej przestrzeni, wykonując eliminację Gaussa na kolumnach (albo – dla mnie łatwiej – eliminację Gaussa na wierszach macierzy transponowanej); bazą obrazu są niezerowe wiersze wynikowej macierzy. W szczególności, wymiar tego obrazu (czyli rząd wyjściowej macierzy)  jest równy liczbie niezerowych wektorów. Jądro za to obliczamy za pomocą Metody 2 (eliminacja Gaussa na wierszach macierzy, a potem jeszcze jeden myk żeby znaleźć bazę przestrzeni $\textrm{Ker}A$).

Typ 4. Dane jest przekształcenie liniowe $f:V\to W$ w jakiś sposób. Obliczyć macierz tego przekształcenia w ustalonych bazach $\set{v_1,\ldots,v_m},\set{w_1,\ldots,w_n}$ przestrzeni $V,W$.

Metoda 4: Ta macierz to macierz $n\times m$ której $i$-ta kolumna to wektor współrzędnych wektora $f(v_i)$ w bazie $\set{w_1,\ldots,w_n}$. Żeby znaleźć współrzędne wektora w bazie, możemy zastosować np. Metodę 2′.

Typ 5. Zadania analogiczne do zadań typów 2,2′ i 4, ale w przestrzeniach wektorowych innych niż postaci $\mathbb R^n$.

Metoda 5: Sprowadzamy do przestrzeni postaci $\mathbb R^n$, znajdując bazy (Metodą 0) oraz macierze przekształceń w tych bazach (Metodą 4).

Przykład: Dane jest przekształcenie liniowe $f:V\to W$ w jakiś sposób. Obliczyć jądro oraz obraz tego przekształcenia.

Obliczamy macierz $A$ przekształcenia $f$ w jakichś bazach $\mathcal V,\mathcal W$, stosując metodę 4. Wtedy, stosując metodę 3, obliczamy bazę jądra $\mathcal K$ oraz bazę obrazu $\mathcal I$ macierzy $A$. Wtedy $\mathcal K$ opisuje nam też bazę jądra przekształcenia $f$, tylko że wyrażoną względem bazy $\mathcal V$. Podobnie, $\mathcal I$ opisuje nam bazę obrazu przekształcenia $f$, tylko wyrażoną względem bazy $\mathcal W$.

Przykład bardziej konkretny: 

Niech $D:\mathbb R[x]_3\to \mathbb R[x]_3$, będzie przekształceniem rozważanym na ćwiczeniach, zadane wzorem $D(f)=f’$.

Baza $\mathbb R[x]_3$ to np. $\set{1,x,x^2,x^3}$. W tej bazie przekształcenie $D$ ma macierz

$$\left[\begin{array}{cccc}0&1&0&0\\0&0&2&0\\0&0&0&3\\0&0&0&0\end{array}\right].$$

Jądro tej macierzy jest rozpięte przez wektor $(1,0,0,0)$, a obraz jest rozpięty przez wektory $(1,0,0,0),(0,1,0,0),(0,0,1,0)$.

A to znaczy, że jądro przekształcenia $D$ jest rozpięte przez funkcję $1$, a obraz jest rozpięty przez funkcje $1,x,x^2$.

Jeszcze jeden przykład.

Dla $\alpha\in\mathbb R$, niech $f_\alpha:\mathbb R^3\to \mathbb R^3$ będzie przekształceniem obrotu o kąt $\alpha$ wokół osi $z$. Znajdź bazę podprzestrzeni $V=\textrm{lin}\set{f_\alpha:\alpha\in\mathbb R}$ przestrzeni $\mathcal L(\mathbb R^3,\mathbb R^3)$.

Rozwiązanie. Obliczamy macierz przekształcenia $f_\alpha$ (w bazach standardowych przestrzeni $\mathbb R^3$), obserwując że $f_\alpha(0,0,1)=(0,0,1)$ oraz $f_\alpha(1,0,0)=(\cos\alpha,-\sin\alpha,0)$, $f_\alpha(0,1,0)=(\sin\alpha,\cos\alpha,0)$:

$$[f_\alpha]=\left[\begin{array}{cccc}\cos \alpha&\sin \alpha&0\\-\sin\alpha&\cos\alpha&0\\0&0&1\end{array}\right].$$

Przestrzeń liniowa $\mathcal L(\mathbb R^3,\mathbb R^3)$ ma swoją standardową bazę 9-elementową, składającą się z macierzy $e^i_j$ o jedynce na pozycji $(i,j)$ oraz zerach poza tym. Przekształcenie $f_\alpha$ jest wektorem w tej przestrzeni, i w tej bazie ma takie współrzędne, jak współczynniki macierzy $[f_\alpha]$, czyli

$$(\cos \alpha,\sin \alpha,0,-\sin\alpha,\cos\alpha,\\0,0,0,1)$$

(kolejność tych współczynników zależy oczywiście od tego, jaką wybierzemy kolejność wektorów bazowych).

Zadanie sprowadziło się więc do obliczenia bazy podprzestrzeni $V’\subset \mathbb R^9$ rozpiętej przez wektory powyższej postaci.

Łatwo widzieć że to sprowadza się do obliczenia bazy podprzestrzeni $V”\subset\mathbb R^5$ rozpiętej przez wektory postaci:

$$v_\alpha=(\cos \alpha,\sin \alpha,-\sin\alpha,\cos\alpha,1).$$

 

Żeby policzyć tę bazę, stosujemy Metodę 0. Weźmy np. $\alpha=0,\pi$ (bo dla tych się łatwo liczy) i sprawdźmy, czy są liniowo zależne. Mamy:

\begin{align*}v_0&=(1,0,0,1,1)\\ v_\pi&=(-1,0,0,-1,1)\end{align*}

Te wektory są liniowo niezależne, więc możemy je wziąć do naszej bazy, i szukać pozostałych wektorów bazowych. Zauważmy, że $e_5=\frac 1 2(v_0+v_\pi)$.

Rozważmy $\alpha={\pi/2}$:

\begin{align*}v_{\pi/2}&=(0,1,-1,0,1)\end{align*}

Ten wektor jest liniowo niezależny od $v_0$ oraz $v_\pi$, dorzucamy go do bazy. Wreszcie, twierdzimy, że dowolny wektor $v_\alpha$ jest kombinacją liniową wektorów $v_0,v_{\pi}, v_{\pi/2}$. Istotnie:

$$v_\alpha=\cos\alpha\cdot v_0+\sin\alpha\cdot v_{\pi/2}-(\cos\alpha+\sin\alpha-1)\cdot e_5,$$

a $e_5$ jest kombinacją liniową $v_0$ oraz $v_\pi$. Tak więc, wektory $v_0,v_{\pi/2},v_{\pi}$ tworzą bazę przestrzeni $V”$. Zatem jest to przestrzeń trójwymiarowa. To się tłumaczy na bazę oryginalnej przestrzeni $V$: jest nią zbiór przekształceń $\set{f_0,f_{\pi/2},f_{\pi}}$.

 

Typ 6. Dana jest podprzestrzeń $V$ przestrzeni $\mathbb R^n$. Znaleźć bazę ortonormalną tej podprzestrzeni.

Metoda 6: Znajdujemy jaką bądź bazę przestrzeni $V$, i wykonujemy na niej ortogonalizacja Grama-Schmidta. To jest opisane tutaj.

Typ 7. Dana jest podprzestrzeń $V$ przestrzeni $\mathbb R^n$, oraz wektor $v\in \mathbb R^n$. Znaleźć rzut ortogonalny $v’$ wektora $v$ na przestrzeń $V$.

Metoda 7: Jeżeli mamy już bazę ortonormalną $\set{u_1,\ldots,u_k}$ przestrzeni $V$ (np. obliczoną za pomocoą Metody 6) to wektor $v’$ wyraża się wzorem $$v’=\sum_{i=1}^k\langle v,u_i\rangle u_i.$$

Jeżeli nie mamy tej bazy, to stosujemy jedną z metod przedstawionych tutaj. Na przykład, wektor $v’$ zdefiniowany jest warunkami:

\begin{align*}(v-v’)&\in V^\bot\\v’&\in V\end{align*}

Przypuśćmy, że $V=\textrm{lin}\set{u_1,\ldots,u_n}$. Znajdujemy bazę $\textrm{lin}\set{w_1,\ldots,w_k}$ przestrzeni $V^\bot$ (patrz Metoda 2”). Warunek $(v-v’)\in V^\bot$ tłumaczy się na układ równań $$\langle v-v’,u_i\rangle =0\textrm{ dla }i=1,\ldots,n,$$ a warunek $v’\in V$ tłumaczy się na układ równań  $$\langle v’,w_j\rangle =0\textrm { dla }j=1,\ldots,k$$. Rozwiązując te dwa układy równań razem, znajdziemy wektor $v’$.

Typ 8. Znaleźć przecięcie podprzestrzeni $V$ i $W$ przestrzeni $\mathbb R^n$. (To się przydaje by np. stwierdzić, czy suma $V+W$ jest prosta).

Metoda 8. Znajdujemy układy równań opisujące przestrzenie $V$ i $W$ (patrz Metoda 2”). Bierzemy sumę tych dwóch układów. To jest układ równań opisujących przestrzeń $V\cap W$. Możemy znaleźć bazę tej przestrzeni, np. stosując Metodę 2. W ten sposób możemy stwierdzić jaki jest wymiar $V\cap W$, i czy to przecięcie jest trywialne (równe $\set{0}$), czy nie.

Typ 8′. Znaleźć sumę podprzestrzeni $V$ i $W$ przestrzeni $\mathbb R^n$.

Metoda 8′. Znajdujemy bazy przestrzeni $V$ i $W$ (patrz Metoda 0). Wtedy przestrzeń $V+W$ jest rozpięta przez sumę tych baz.

Praca domowa: ortogonalizacja Grama-Schmidta

$% \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} $

Niech $v\in \mathbb R^n$ będzie dowolnym wektorem oraz niech $U\subseteq \mathbb R^n$ będzie podprzestrzenią liniową. Przypuśćmy, że $U$ ma bazę ortonormalną $\set{u_1,\ldots,u_k}$, tj. $U=\textrm{span}\set{u_1,\ldots,u_k}$ oraz układ $u_1,u_2,\ldots,u_k$ jest ortonormalny, tzn. taki, że $$\langle u_i,u_j\rangle=\begin{cases}0&\text{jeśli }i\neq j\\1&\text{jeśli }i=j\end{cases}$$

Fakt. Rzut $v_0$ wektora $v$ na podprzestrzeń $U$ wyraża się wzorem:

$$v_0=\langle v,u_1\rangle\cdot u_1+\ldots \langle v,u_k\rangle\cdot u_k=\sum_{i=1}^k \langle v,u_i\rangle\cdot u_i.$$

Zadanie. Pokazać powyższy fakt na dwa sposoby:

1) Uzasadnić, że $v_0\in U$ oraz $(v-v_0)\bot U$.

2) Zauważyć, że jeżeli $A$ jest macierzą której kolumny to wektory $u_1,\ldots,u_k$, to macierz $A^T\cdot A$ jest macierzą identycznościową $k\times k$, i skorzystać z trzeciego podpunktu zadania 1 z poprzedniej serii zadań, że wektor $x$ współrzędnych rzutu wektora $v$ na przestrzeń  $\textrm{span}\set{u_1,\ldots,u_k}$ spełnia równanie $A^T\cdot A\cdot x=A^T\cdot v$.

Zadanie 2. Metodą ortogonalizacji Grama-Schmidta (korzystając z powyższego faktu), znaleźć bazę ortonormalną podprzestrzeni $V$ przestrzeni $\mathbb R^4$, gdzie $$V=\textrm{span}\set{(5,-5,3,-4),(5,0,3,-4),(10,10,12,-16)}$$

Zadanie 3. Obliczyć odwrotność macierzy

$$M=\left[\begin{array}{ccc}1&-2&1\\-1&2&1\\0&1&1\end{array}\right]$$

 

Praca domowa

$% \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} $

Dzień dobry. Poniżej są zadania domowe, które proszę o rozwiązanie na kartkach na piątek 12.12.14. Rozwiązań nie będę zbierał i sprawdzał – sprawdzą je sobie Państwo sami, porównując wyniki zadania otrzymane na różne sposoby opisane poniżej.

Zadanie 1. Niech $V$ będzie podprzestrzenią w $\mathbb R^3$ określoną następująco:

$$V=\textrm{span}\set{(1,2,0),(-2,1,1)},$$

oraz niech $w=(5,3,6)$. Znaleźć rzut prostopadły $w_0$ wektora $w$ na przestrzeń $V$ na cztery sposoby ($r$ oznacza wektor $w-w_0$):

  1. Znaleźć przestrzeń $W=V^{\bot}$, i znaleźć wektor $r\in W$ taki, że $w_0\in V$. Warto tu skorzystać z tego, że $V=W^{\bot}$, więc $w_0\in V$ wtedy i tylko wtedy, gdy $w_0\bot W$, czyli $(w-r)\bot W$.
  2. Z definicji: znaleźć parę liczb $x_1,x_2\in\mathbb R$ taką, że dla $w_0=x_1\cdot (1,2,0)+x_2\cdot (-2,1,1)$, zachodzi $(w-w_0)\bot V$, czyli $(w-w_0)\bot (1,2,0)$ oraz $(w-w_0)\bot (-2,1,1)$. To daje układ dwóch równań o dwóch niewiadomych $x_1,x_2$: $$\begin{align*}\langle w-w_0,(1,2,0)\rangle&=0\\\langle w-w_0,(-2,1,1)\rangle&=0\end{align*}$$
  3. Niech $A$ oznacza macierz $3\times 2$, której kolumny to wektory rozpinające przestrzeń $V$. Znaleźć wektor $x\in\mathbb R^2$ taki, że $A^T\cdot A\cdot x=A^T\cdot w$ (to też daje układ równań o dwóch niewiadomych, który ma postać macierzową $(A^T\cdot A\ |\ b)$ gdzie $b=A^T\cdot w$, który rozwiązujemy eliminacją Gaussa). Wtedy $w_0=A\cdot x$.
  4. Zgadnij wektor $w_0\in \mathbb R^3$ (zapewne na podstawie powyższych obliczeń) i sprawdź, czy spełnia warunki: $w_0\in V$ oraz $(w-w_0)\bot V$.

Zadanie 2. Niech $A: \mathbb R^3\to \mathbb R^2$ będzie przekształceniem liniowym takim, że \begin{align*}A(0,1,1)&=(2,0),\\A(1,0,1)&=(0,0)\\A(1,1,0)&=(0,1)\end{align*}

 

  1. Znaleźć macierz $[A]^{st}_{st}$ tego przekształcenia w bazach standardowych: $st=\set{(1,0,0),(0,1,0),(0,0,1)}$ w dziedzinie oraz $st=\set{(0,1),(1,0)}$ w przeciwdziedzinie.
  2. Znaleźć macierz $[A]^{\mathcal B}_{\mathcal C}$ tego przekształcenia w bazach $\mathcal B=\set{(1,1,0),(1,2,1),(0,0,1)}$ oraz $\mathcal C=\set{(1,1),(-1,1)}$ przestrzeni $\mathbb R^3$ oraz $\mathbb R^2$, odpowiednio.
  3. Znaleźć macierz $[id]^{st}_{\mathcal C}$ przekształcenia identycznościowego $id:\mathbb R^3\to \mathbb R^3$ w bazach standardowej (w dziedzinie) oraz $\mathcal C$ (w przeciwdziedzinie).
  4. Znaleźć macierz $[id]^{st}_{\mathcal B}$ przekształcenia identycznościowego $id:\mathbb R^2\to \mathbb R^2$ w bazach standardowej (w dziedzinie) oraz $\mathcal B$ (w przeciwdziedzinie).
  5. Znaleźć macierz $[id]^{\mathcal B}_{st}$ przekształcenia identycznościowego $id:\mathbb R^2\to \mathbb R^2$ w bazach $\mathcal B$ (w dziedzinie) oraz standardowej w przeciwdziedzinie. Zauważ, że wynikowa macierz jest odwrotnością macierzy z poprzedniego podpunktu, tj. $$[id]^{\mathcal B}_{st}=([id]^{st}_{\mathcal B})^{-1}.$$
  6. Zauważ, że $$[A]^{\mathcal B}_{\mathcal C}=[id]^{st}_{\mathcal C} \cdot [A]^{st}_{st}\cdot [id]^{\mathcal B}_{st}$$

 

Modele Kripkego

$% \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} $

Pokażemy, za pomocą modeli Kripkego, że następujące zdanie nie jest tautologią w logice intuicjonistycznej.

$$\phi=((p\rightarrow q)\rightarrow p)\rightarrow p).$$

Continue reading Modele Kripkego

Praca domowa nr 3

$% \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} $

Zadanie 1. Niech $v=(1,2)$ będzie wektorem w przestrzeni $\RR^2$. Pokazać, że dla dowolnego wektora $w\in\RR^2$ przestrzeń $W=\textrm{span}\set{v,w}$ jest równa $\textrm{span}\set{v}$, albo jest równa $\RR^2$.

Zadanie 2. Rozstrzygnąć, czy poniższe układy wektorów są liniowo zależne; jeśli tak, to znaleźć zbiór ich kombinacji liniowych, które dają wyniku wektor $0$.

  1. $\set{(3,2,5),(1,2,4),(1,0,2)}$ w przestrzeni $\RR^3$.
  2. $\set{(3,2,1),(1,2,1),(1,0,0)}$ w przestrzeni $\RR^3$.
  3. $\set{w_1,w_2,w_3}$ w przestrzeni $\RR^\RR$ funkcji z $\RR$ w $\RR$, gdzie $$\begin{align*}w_1(x)&=x^2+x\\ w_2(x)&=2x^2 \\ w_3(x)&=3x\end{align*}$$
  4. $$\begin{align*}\{(0,1,0,0,0,1),\\(0,0,1,1,1,1),\\(1,0,0,1,0,0),\\(1,1,0,0,1,0),\\(0,0,0,1,1,1)\}\end{align*}$$ w sześciowymiarowej przestrzeni $\mathbb{Z}_2^6$ nad ciałem $\mathbb{Z}_2$.

Zadanie 3Sprzątaczka ma za zadanie po zakończonych zajęciach wyłączyć wszystkie światła w sali 5440. Tych świateł jest sześć, ale włączniki są tylko cztery:

  • pierwszy włącznik zmienia stan lamp 2 oraz 6
  • drugi włącznik zmienia stan lamp 3,4,5,6
  • trzeci włącznik zmienia stan lamp 1,4
  • czwarty włącznik zmienia stan lamp 1,2,5.

Włączone są lampy 4,5,6. Które włączniki powinna przełączyć sprzątaczka, by wyłączyć wszystkie lampy?

 

 

 

Praca domowa nr 2 z GALu

$% \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} $

1. Obliczyć iloczyn macierzy

$$\left[\begin{array}{cccc}1&1&0&0\\1&2&0&0\\0&0&3&1\\0&0&1&1\end{array}\right]\cdot \left[\begin{array}{cccc}1&1&0&0\\1&4&0&0\\0&0&1&2\\0&0&-3&1\end{array}\right]$$

2. Znajdź macierz $X$ taką, że zachodzi równość

$$\left[\begin{array}{ccc}1&2&-3\\3&2&-4\\2&-1&0\end{array}\right]\cdot X=\left[\begin{array}{ccc}1&-3&0\\10&2&7\\10&7&8\end{array}\right]$$

 

3. Czy mnożenie macierzy $2\times 2$ jest przemienne, tj. czy $A\cdot B=B\cdot A$ dla dowolnych macierzy $A,B$ nad liczbami rzeczywistymi? Czy każda macierz niezerowa $A$ jest odwracalna, tj. czy istnieje $B$ t.że $A\cdot B=B\cdot A$? Jaka jest odpowiedź na powyższe pytania, jeżeli rozważyć tylko macierze diagonalne, tzn. takie, że $a_{i,j}=0$ dla $i\neq j$?