Relações de Ordem e Indução

Prévia do material em texto

Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Capı́tulo 4
1 Relação de ordem
2 Relação bem fundada
3 Boa ordem
4 Indução
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Capı́tulo 4
1 Relação de ordem
2 Relação bem fundada
3 Boa ordem
4 Indução
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Comparabilidade
≼ denota relação [de ordem] genérica.
Lemos x ≼ y como “x precede, ou é igual a, y”.
Se x ≼ y ou y ≼ x
x e y são comparáveis.
Se não(x ≼ y ou y ≼ x) i.e., x /≼ y e y /≼ x
x e y são incomparáveis.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Comparabilidade
≼ denota relação [de ordem] genérica.
Lemos x ≼ y como “x precede, ou é igual a, y”.
Se x ≼ y ou y ≼ x
x e y são comparáveis.
Se não(x ≼ y ou y ≼ x) i.e., x /≼ y e y /≼ x
x e y são incomparáveis.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Comparabilidade
Em (2Z,⊆) temos
{1, 2} /⊆ {2, 3} e {2, 3} /⊆ {1, 2}
Em (Z,≤) temos
x ≤ y ou y ≤ x.
para quaisquer x e y.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Ordem Parcial
Para um conjunto não vazio A, o par (A,≼) é chamado
ordem parcial se valem as propriedades seguintes para a
relação ≼:
● reflexiva
● antissimétrica
● transitiva
Dizemos que A é conjunto parcialmente ordenado por ≼.
A relação ≼ sobre A com as propriedades acima é
chamada uma relação de ordem em A.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Ordem total
Se A é conjunto parcialmente ordenado por ≼ tal que todo
par é comparável então (A,≼) é dita
ordem total
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Relembrando
1 Uma relação ∼ é reflexiva sse para todo a ∈ A, a ∼ a
Ex. {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 1), (4, 4)}.
2 Uma relação ∼ é antissimétrica sse para todos a ∈ A e
para todo b ∈ A, a ∼ b e b ∼ a⇒ a = b
Ex. {(1, 1), (2, 2), (1, 2), (3, 1), (4, 1), (4, 2), (4, 3)}.
3 Uma relação ∼ é transitiva sse para todo a ∈ A, para
todo b ∈ A, para todo c ∈ A, se a ∼ b e b ∼ c então a ∼ c.
Ex. {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
● ≤ em Z, Q, R
● ⊆ em 2Z e em 2{1,2,3}
● ∣ em N (divisibilidade)
e em Z?
● ≼ em {1, 2, 3, 4, 5, 6} dada por
{(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
● ≤ em Z, Q, R
● ⊆ em 2Z e em 2{1,2,3}
● ∣ em N (divisibilidade) e em Z?
● ≼ em {1, 2, 3, 4, 5, 6} dada por
{(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
● ≤ em Z, Q, R
● ⊆ em 2Z e em 2{1,2,3}
● ∣ em N (divisibilidade) e em Z?
● ≼ em {1, 2, 3, 4, 5, 6} dada por
{(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
Em Z com x ≼ y se, e somente se,
1 ∣x∣Proposição
Se é máximo então é maximal.
Proposição
Se (A,≼) tem máximo então é único.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Mı́nimo e minimal
Em (A,≼) temos que x ∈ A é
minimal se, e só se, para todo y ∈ A,
y ≼ x implica y = x.
mı́nimo se, e só se, para todo y ∈ A,
x ≼ y.
Proposição
Se é mı́nimo então é minimal e é único.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Mı́nimo e minimal
Em (A,≼) temos que x ∈ A é
minimal se, e só se, para todo y ∈ A,
y ≼ x implica y = x.
mı́nimo se, e só se, para todo y ∈ A,
x ≼ y.
Proposição
Se é mı́nimo então é minimal e é único.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Mı́nimo e minimal
Em (A,≼) temos que x ∈ A é
minimal se, e só se, para todo y ∈ A,
y ≼ x implica y = x.
mı́nimo se, e só se, para todo y ∈ A,
x ≼ y.
Proposição
Se é mı́nimo então é minimal e é único.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos maximais, minimais, máximos,
mı́nimos de
1 (N ∖ {0, 1}, ∣).
2 (N ∖ {0}, ∣).
3 (N, ∣).
4 subconjuntos de N com no máximo três elementos e
ordenados por inclusão ⊆.
5 {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1, 1),
(2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
1 2 5
63
4
Figura: diagrama de Hasse da ordem parcial
{(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1, 1),
(2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Limitantes
(A ≼) ordem parcial e B ⊆ A um conjunto não vazio
1 limitante superior para B (quando existe): u ∈ A tal que
b ≼ u, ∀b ∈ B
2 limitante inferior para B (quando existe): l ∈ A tal que
l ≼ b, ∀b ∈ B
3 O menor limitante superior de B (quando existe):
sup(B) = v ≼ u, para todo limitante superior u
4 O maior limitante inferior de B (quando existe):
l ≼m = inf(B), para todo limitante inferior l
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Limitantes
(A ≼) ordem parcial e B ⊆ A um conjunto não vazio
1 limitante superior para B (quando existe): u ∈ A tal que
b ≼ u, ∀b ∈ B
2 limitante inferior para B (quando existe): l ∈ A tal que
l ≼ b, ∀b ∈ B
3 O menor limitante superior de B (quando existe):
sup(B) = v ≼ u, para todo limitante superior u
4 O maior limitante inferior de B (quando existe):
l ≼m = inf(B), para todo limitante inferior l
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Limitantes
(A ≼) ordem parcial e B ⊆ A um conjunto não vazio
1 limitante superior para B (quando existe): u ∈ A tal que
b ≼ u, ∀b ∈ B
2 limitante inferior para B (quando existe): l ∈ A tal que
l ≼ b, ∀b ∈ B
3 O menor limitante superior de B (quando existe):
sup(B) = v ≼ u, para todo limitante superior u
4 O maior limitante inferior de B (quando existe):
l ≼m = inf(B), para todo limitante inferior l
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Limitantes
(A ≼) ordem parcial e B ⊆ A um conjunto não vazio
1 limitante superior para B (quando existe): u ∈ A tal que
b ≼ u, ∀b ∈ B
2 limitante inferior para B (quando existe): l ∈ A tal que
l ≼ b, ∀b ∈ B
3 O menor limitante superior de B (quando existe):
sup(B) = v ≼ u, para todo limitante superior u
4 O maior limitante inferior de B (quando existe):
l ≼m = inf(B), para todo limitante inferior l
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos limitantes
1 (N ∖ {0}, ∣): B = {2, 4, 6}, limitantes?
2 (2A,⊆): para X,Y ⊆ A, o que é sup(X,Y), inf(X,Y)?
Reticulado: A ordem parcial (A ≼) é chamado reticulado se
para qualquer par B = {a,b} ⊆ A, existem sup(B) e inf(B).
Exemplo: Para conjunto não vazio A: (2A,⊆).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos limitantes
1 (N ∖ {0}, ∣): B = {2, 4, 6}, limitantes?
2 (2A,⊆): para X,Y ⊆ A, o que é sup(X,Y), inf(X,Y)?
Reticulado: A ordem parcial (A ≼) é chamado reticulado se
para qualquer par B = {a,b} ⊆ A, existem sup(B) e inf(B).
Exemplo: Para conjunto não vazio A: (2A,⊆).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos limitantes
1 (N ∖ {0}, ∣): B = {2, 4, 6}, limitantes?
2 (2A,⊆): para X,Y ⊆ A, o que é sup(X,Y), inf(X,Y)?
Reticulado: A ordem parcial (A ≼) é chamado reticulado se
para qualquer par B = {a,b} ⊆ A, existem sup(B) e inf(B).
Exemplo: Para conjunto não vazio A: (2A,⊆).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos limitantes
1 (N ∖ {0}, ∣): B = {2, 4, 6}, limitantes?
2 (2A,⊆): para X,Y ⊆ A, o que é sup(X,Y), inf(X,Y)?
Reticulado: A ordem parcial (A ≼) é chamado reticulado se
para qualquer par B = {a,b} ⊆ A, existem sup(B) e inf(B).
Exemplo: Para conjunto não vazio A: (2A,⊆).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Cadeia
(A ≼) ordem parcial
B ⊆ A com elementos comparáveis 2-a-2 é chamada
cadeia.
B ⊆ A com elementos incomparáveis 2-a-2 é chamada
anticadeia.
Exercı́cio: Escreva uma cadeia e uma anticadeia dos
divisores de 60 com respeito a relação de divisibilidade?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Cadeia
(A ≼) ordem parcial
B ⊆ A com elementos comparáveis 2-a-2 é chamada
cadeia.
B ⊆ A com elementos incomparáveis 2-a-2 é chamada
anticadeia.
Exercı́cio: Escreva uma cadeia e uma anticadeia dos
divisores de 60 com respeito a relação de divisibilidade?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Cadeia
(A ≼) ordem parcial
B ⊆ A com elementos comparáveis 2-a-2 é chamada
cadeia.
B ⊆ A com elementos incomparáveis 2-a-2 é chamada
anticadeia.
Exercı́cio: Escreva uma cadeia e uma anticadeia dos
divisores de 60 com respeito a relação de divisibilidade?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
1
2
4
3
6
12
5
10
20
15
30
60
Figura: Uma cadeia em azul e uma anticadeia em vermelho.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Cadeia e anticadeia
Decomposição de ordens parciais: Se (S,≼) é ordem
parcial finita então podemos particioná-la em anticadeias.
1 S = A1 ∪A2 ∪⋯ ∪Ak
2 Ai ∩Aj = ∅, ∀i ≠ j
Teorema de Mirsky
Seja S um conjunto não vazio e finito. O número de
elementos na maior cadeia em (S,≼) é igual ao da menor
partição em anticadeias.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Teorema de Dilworth
Numa ordem parcial finita (S,≼) e não vazia, o menor
número c de cadeias tal que todo elemento de S pertence a
alguma dessas cadeias é igual ao número máximo de
elementos a em uma anticadeia de S.
● Teorema de Mirsky é o dual do Teorema de Dilworth!
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Capı́tulo 4
1 Relação de ordem
2 Relação bem fundada
3 Boa ordem
4 Indução
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Relação bem fundada
Intuitivamente, é uma relação ≺, (não necessariamente de
ordem), para a qual não existe uma cadeia da forma
x0 ≻ x1 ≻ x2 ≻ ⋯
(cadeia descendente infinita)
Como ocorre, por exemplo, com oq0 é par, q0 = 2q1 para algum q1 e
√
2 = p1
q1
Repetindo esse argumento encontramos
p0 > p1 > p2 > ⋯ contradição.
Porque contradição?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Uma prova para
√
2 /∈ Q:
Se
√
2 = p0
q0
(é racional)
então p0 é par, p0 = 2p1 para algum p1 p1 > p2 > ⋯ contradição.
Porque contradição?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Uma prova para
√
2 /∈ Q:
Se
√
2 = p0
q0
(é racional)
então p0 é par, p0 = 2p1 para algum p1 p1 > p2 > ⋯ contradição.
Porque contradição?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Uma prova para
√
2 /∈ Q:
Se
√
2 = p0
q0
(é racional)
então p0 é par, p0 = 2p1 para algum p1 p1 > p2 > ⋯ contradição.
Porque contradição?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Uma prova para
√
2 /∈ Q:
Se
√
2 = p0
q0
(é racional)
então p0 é par, p0 = 2p1 para algum p1 p1 > p2 > ⋯ contradição.
Porque contradição?
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Relação bem fundada
R relação sobre A ≠ ∅ é bem fundada sse
Todo S ⊆ A não vazio tem minimal:
∃m ∈ S, ∀x ∈ S, (x,m) /∈ R
Dizendo de outra maneira,
● m ∈ S é minimal de S se não existe x ∈ S tal que x Rm;
● R é bem fundada sse todo S ⊆ A não vazio tem
minimal (com respeito a relação R).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Relação bem fundada
R relação sobre A ≠ ∅ é bem fundada sse
Todo S ⊆ A não vazio tem minimal:
∃m ∈ S, ∀x ∈ S, (x,m) /∈ R
Dizendo de outra maneira,
● m ∈ S é minimal de S se não existe x ∈ S tal que x Rm;
● R é bem fundada sse todo S ⊆ A não vazio tem
minimal (com respeito a relação R).
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplos
1 {(n,n + 1)∣ n ∈ N}
2 em N
2 em N
2 2 arbitrário, assuma P(x) para todo x 2 arbitrário, assuma P(x) para todo x 2 arbitrário, assuma P(x) para todo x 2 arbitrário, assuma P(x) para todo x 2 arbitrário, assuma P(x) para todo x 2 arbitrário, assuma P(x) para todo xde primos.
Por indução P(n) é verdadeiro para todo n.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução
Para definir uma função indutivamente:
1 Base: Define valor(es) inicial(ais) da função.
2 Recursão: Define uma regra para calcular o valor da
função em x usando um ou mais valores da função em
elementos ≺ x.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
f ∶ N ×N→ N por f(0, 0) = 0 e nos outros casos
f(m,n) =
⎧⎪⎪
⎨
⎪⎪⎩
f(m − 1,n) + 1 se n = 0 e m > 0
f(m,n − 1) +n se n > 0
Usando indução com ≺lex:
1 f está bem definida
2 f(m,n) =m +n(n + 1)/2
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
f ∶ N ×N→ N por f(0, 0) = 0 e nos outros casos
f(m,n) =
⎧⎪⎪
⎨
⎪⎪⎩
f(m − 1,n) + 1 se n = 0 e m > 0
f(m,n − 1) +n se n > 0
Usando indução com ≺lex:
1 f está bem definida
2 f(m,n) =m +n(n + 1)/2
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
f ∶ N ×N→ N por f(0, 0) = 0 e nos outros casos
f(m,n) =
⎧⎪⎪
⎨
⎪⎪⎩
f(m − 1,n) + 1 se n = 0 e m > 0
f(m,n − 1) +n se n > 0
Usando indução com ≺lex:
1 f está bem definida
2 f(m,n) =m +n(n + 1)/2
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Prova por indução – exemplo
Roteiro: P(m,n) ∶ f(m,n) =m +n(n + 1)/2
Para (m,n) = (0, 0) temos P(m,n) verdadeiro.
Tome (x,y) ≠ (0, 0) arbitrário.
Assuma P(a,b) para todo (a,b) ≺lex (x,y).
P((x − 1, y)) e P((x,y − 1)) valem.
se y = 0, f(x,y) = f(x − 1, y) + 1 = x − 1 + y(y + 1)/2 + 1
=x + y(y + 1)/2
se y > 0, f(x,y) = f(x,y − 1) + y = x + y(y − 1)/2 + y
=x + y(y + 1)/2
e em ambos os casos P(x,y), é verdadeiro.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Exemplo
Para calcular mdc de inteiros positivos:
def MDC (m, n):
if m n, temos mdc(m −n,n) =mdc(m,n).
(m −n,n) ≺lex (m,n), portanto, existem x0 e y0 tais que
x0(m −n) + y0n =mdc(m −n,n) =mdc(m,n).
Logo
x0m + (y0 − x0)n =mdc(m,n).
O caso m 0 e y = 0
A(x − 1,A(x,y − 1)) c.c.
A(4, 0) = 13, A(4, 1) = 65533, A(4, 2) = 265536 − 3 e
A(4, y) = 22
2
..
.
2
− 3
as potências formam uma torre com y + 3 ocorrências do numeral
2.
https://gfredericks.com/things/arith/ackermann
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
função de Ackermann
Exercicio
A função de Ackermann está bem definida, ou seja, existe e
é única a imagem de cada par de naturais (x,y) pela
função A. Prove essa afirmação usando a ordem
lexicográfica em N ×N.
https://gfredericks.com/things/arith/ackermann
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução
Para definir um conjunto indutivamente:
1 Base: Define um ou mais elementos do conjunto.
2 Recursão: Fornece uma regra para gerar novos
elementos do conjunto em termos de elementos já
existentes
3 Fecho: Afirma que o conjunto consiste exatamente dos
elementos obtidos a partir da base e da recursão.
O fecho é usualmente assumido, sem o explicitar. Sem ele,
existiriam muitos conjuntos satisfazendo a base e a
recursão.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
Definição indutiva do conjunto dos pares positivos
1 2 ∈ A
2 se n ∈ A então n + 2 ∈ A
3 só os naturais obtidos pelas regras acima estão em A
Até aqui A pode ser N, pode ser
{0, 2, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou muitos outros
A = {2, 4, 6, 8, 10, 12, ...}.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
Definição indutiva do conjunto dos pares positivos
1 2 ∈ A
2 se n ∈ A então n + 2 ∈ A
3 só os naturais obtidos pelas regras acima estão em A
Até aqui A pode ser N, pode ser
{0, 2, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou muitos outros
A = {2, 4, 6, 8, 10, 12, ...}.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
Indução
Definição por indução –
exemplo
Definição indutiva do conjunto dos pares positivos
1 2 ∈ A
2 se n ∈ A então n + 2 ∈ A
3 só os naturais obtidos pelas regras acima estão em A
Até aqui A pode ser N, pode ser
{0, 2, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...}, ou muitos outros
A = {2, 4, 6, 8, 10, 12, ...}.
Mat.Discreta
Relação de
ordem
Relação bem
fundada
Boa ordem
InduçãoEncerramento do capı́tulo 4
1 As seções 4.1 - 4.3 from dados!
2 As seções 4.4 e 4.6 não serão dadas. Se você estiver
interessado, pode estudá-las e, se tiver alguma dúvida,
entre em contato comigo.
3 Pode fazer os exercı́cios das notas de aula e a da lista
5.