Funkcja charakterystyczna zbioru

Zbiór wzorów, definicji i najczęściej poruszanych problemów ze Zbiór-ki.
Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2710
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 653 razy

Funkcja charakterystyczna zbioru

Post autor: Sylwek » 30 sty 2008, o 02:08

Autor: Sylwek

Funkcja charakterystyczna zbioru to jedno z kluczowych pojęć matematycznych, o szczególnym zastosowaniu w teorii miary i teorii ciągów funkcji mierzalnych. Często spotykaną funkcją charakterystyczną jest funkcja Dirichleta (funkcja charakterystyczna zbioru liczb wymiernych - została ona poniekąd opisana na końcu tego artykułu).


Definicja:
Niech \(\displaystyle{ X}\) będzie ustalonym zbiorem i niech \(\displaystyle{ A \subseteq X}\). Funkcją charakterystyczną zbioru \(\displaystyle{ A}\) nazywamy funkcję \(\displaystyle{ f_A:X\to\{0,1\}}\) zadaną wzorem

\(\displaystyle{ f_{A}(x)=\begin{cases}1, \ x \in A \\ 0, \ x \notin A \end{cases}}\)


Tyle nam wystarczy do udowadniania równości zbiorów . Przyjmuję, że w dalszej części będą obowiązywały następujące oznaczenia: \(\displaystyle{ a=f_{A}(x), \ b=f_{B}(x)}\) itp. oraz będę pisał \(\displaystyle{ f_{A}}\) zamiast \(\displaystyle{ f_{A}(x)}\).


Jeszcze 5 ważniejszych twierdzeń, które nam ułatwią późniejsze obliczenia:


1) \(\displaystyle{ f_{A}^2=f_{A}}\) - najefektywniejsze i najefektowniejsze

Dowód:
\(\displaystyle{ a) \ f_{A}=0 \\ L_{T}=0=f_{A}^2=f_{A}=0=P_{T} \\ b) \ f_{A}=1 \\ L_{T}=1=f_{A}^2=f_{A}=1=P_{T}}\)




2) \(\displaystyle{ f_{A \cap B}=f_{A} \cdot f_{B}}\)

Dowód:
\(\displaystyle{ f_{A} \cdot f_{B}=1 \iff f_{A}=1 \wedge f_{B}=1 \iff x \in A \wedge x \in B \iff \\ x \in A \cap B \iff f_{A \cap B}=1}\)




3) \(\displaystyle{ f_{A \cup B}=f_{A} + f_{B} - f_{A} \cdot f_{B}}\)

Dowód:
\(\displaystyle{ a) \ x \in A \cap B \\ L_{T}=f_{A \cup B}=1=1+1-1=f_{A} + f_{B} - f_{A} \cdot f_{B}=P_{T}}\)
b) x należy do jednego ze zbiorów, bez straty ogólności:
\(\displaystyle{ x \in A \wedge x \notin B \\ L_{T}=f_{A \cup B}=1=1+0-0=f_{A} + f_{B} - f_{A} \cdot f_{B}=P_{T} \\ c) \ x \notin A \cup B \\ L_{T}=f_{A \cup B}=0=0+0-0=f_{A} + f_{B} - f_{A} \cdot f_{B}=P_{T}}\)




4) \(\displaystyle{ f_{A \setminus B}=f_{A} \cdot (1-f_{B})}\)

Dowód:
\(\displaystyle{ f_{A \setminus B}=f_{A \cap B'}=f_{A} \cdot f_{B'}=f_{A} \cdot (1-f_{B})}\)




5) \(\displaystyle{ f_{A \Delta B}=f_{A}+f_{B}-2 \cdot f_{A} \cdot f_{B}}\)
Dowód:
Zacznijmy od tego, że \(\displaystyle{ A \Delta B=(A \setminus B) \cup (B \setminus A)}\) i nazywamy to różnicą symetryczną zbiorów A i B
\(\displaystyle{ f_{A \Delta B}=f_{(A \setminus B) \cup (B \setminus A)}=a(1-b)+b(1-a)-a(1-b)b(1-a)= \\ =a-ab+b-ab-ab(1-a-b+ab)=a+b-2ab-ab+a^2b+ab^2-a^2b^2= \\ =a+b-3ab+2ab-ab=a+b-2ab}\)






Przykład 1.
Udowodnij równość zbiorów:
\(\displaystyle{ A \cup B = (A \setminus B) \cup B}\)

Dowód:
\(\displaystyle{ f_{A \cup B}=a+b-ab \\ f_{(A \setminus B) \cup B}=f_{A \setminus B} + f_{B} - f_{A \setminus B} \cdot f_{B}=a(1-b)+b-a(1-b) \cdot b= \\ =a-ab+b-ab+ab^2=a+b-2ab+ab=a+b-ab=f_{A \cup B}}\)




Dla przećwiczenia:

Zadanie 1.
Udowodnij równość zbiorów:
\(\displaystyle{ A \setminus B=(A \cup B) \setminus B}\)

Zadanie 2.
Udowodnij równość zbiorów:
\(\displaystyle{ A \setminus (B \cap C)=(A \setminus B) \cup (A \setminus C)}\)

Zadanie 3*.
Udowodnij zawieranie się zbiorów:
\(\displaystyle{ A \cup (B \Delta C) \supset (A \cup B) \Delta (A \cup C)}\)
(Podpowiedź: \(\displaystyle{ A \supset B \iff f_{a} \geq f_{b}}\))


Zadania dla przećwiczenia zaczerpnięte z książki Impresje liczbowe. Od cyfry do szeregu, autor: Lev Kourliandtchik.



---------------

Autor: PFloyd

Poniżej zaprezentuję dowód, że: \(\displaystyle{ |P(\mathbb{N})|=\mathfrak{c}}\), korzystajacy właśnie z funkcji charakterystycznych zbiorów (funkcję charakterystyczna zbioru \(\displaystyle{ A}\) będę oznaczał \(\displaystyle{ \chi_A}\)):

Pierwsza część dowodu to znalezienie injekcji między \(\displaystyle{ \mathbb{R}}\) i zbiorem \(\displaystyle{ P(\mathbb{Q})}\), bo oczywiście \(\displaystyle{ |P(\mathbb{Q})|=|P(\mathbb{N})|}\).
Taką injekcje możemy skonstruować w prosty sposób:
\(\displaystyle{ \mathbb{R}\ni x \rightarrow (- \infty, x) \cap \mathbb{Q} \in P(\mathbb{Q})}\)

Injekcja z \(\displaystyle{ P(\mathbb{N})}\) w \(\displaystyle{ \mathbb{R}}\) wygląda tak:
\(\displaystyle{ P(\mathbb{N})\ni A \rightarrow \sum_{n=0}^{\infty}\frac{\chi_A (n)}{10^n}\in \mathbb{R}}\)
przy czym \(\displaystyle{ \chi_A(n)=\left\{\begin{array}{l} 0, \, n\in\mathbb{N} -A\\ 1, \, n\in A\end{array}}\)

i teraz pozostaje udowodnić indukcjynie, że istotnie jest to injekcja, czyli że:
\(\displaystyle{ \forall _n \sum_{n=0}^{\infty}\frac{\chi_A (n)}{10^n}=\sum_{n=0}^{\infty}\frac{\chi_B (n)}{10^n} \Rightarrow \chi_A(n)=\chi_B(n)}\) bo oczywiście \(\displaystyle{ A=\chi_A ^{-1}(\{1\})\wedge B=\chi_B ^{-1}(\{1\})}\)

Dowód:
\(\displaystyle{ k=0 \\
\chi_A(0)+\sum_{n=1}^{\infty}\frac{\chi_A (n)}{10^n}=\chi_B(0)+\sum_{n=1}^{\infty}\frac{\chi_A (n)}{10^n}}\)

Stąd \(\displaystyle{ \chi_A(0)=\chi_B(0)}\) bo oczywiście \(\displaystyle{ \sum_{n=1}^{\infty}\frac{\chi_A (n)}{10^n} \leq \sum_{n=1}^{\infty}\frac{1}{10^n}=\frac{1}{9}}\)

\(\displaystyle{ 0,...,k \rightarrow k+1}\)
ponieważ \(\displaystyle{ \chi_A(0)=\chi_B(0) \wedge \chi_A(k)=\chi_B(k)}\) to
\(\displaystyle{ \sum_{n=k+1}^{\infty}\frac{\chi_A (n)}{10^n}=\sum_{n=k+1}^{\infty}\frac{\chi_B (n)}{10^n} \, \, / \cdot 10^{k+1}\\
\chi_A(k+1)+\sum_{n=k+2}^{\infty}\frac{\chi_A (n)}{10^{n-k-1}}=\chi_B(k+1)+\sum_{n=k+2}^{\infty}\frac{\chi_B (n)}{10^{n-k-1}}}\)

i z tego samego powodu co w pierwszym kroku indukcyjnym, \(\displaystyle{ \chi_A(k+1)=\chi_B(k+1)}\)



-----



Autor: mol_ksiazkowy

Kilka słów o funkcji Dirichleta:
\(\displaystyle{ D(x)=\begin{cases}1, &x \in \QQ \\ 0, &x \notin \QQ \end{cases}}\)
Ma ona takie właściwości:
- Nie ma punktu, w którym była by ona ciągła
- Nie ma nigdzie granicy
- Funkcja \(\displaystyle{ x \mapsto xD(x)}\) jest ciągła w zerze i tylko w zerze
- funkcja \(\displaystyle{ x \mapsto x^{2}D(x)}\) jest różniczkowalna tylko w zerze
- Każda liczba wymierna jest okresem funkcji \(\displaystyle{ D(x)}\), żadna liczba niewymierna nie jest okresem \(\displaystyle{ D(x)}\).
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ