Conjunto de funções que aumentam rapidamente é incontável?

8
Manoj Kumar 2019-10-20 07:15.

Deixei $$ S=\{f \colon \mathbb{N} \mapsto \mathbb{R} \mid f(n+1) \ge 2^{f(n)} \}.$$ Como provar $S$ é incontável?

Tentei provar por contradição, mas não consegui construir uma nova função diferente da coleção contável.

Qualquer ajuda seria apreciada.

5 answers

11
Shiranai 2019-10-20 07:19.

Você pode definir recursivamente $f(n+1) = 2^{f(n)}+c$, Onde $c$ é real maior do que $0$, e desde $\mathbb{R}^+$ é incontável que você terminou.

Em seguida, vou construir um conjunto de funções $F=\bigcup\limits_{i>0} \{f_i \}$:

  1. Para cada $i$: $f_i(0)=1$

  2. $f_i(n+1) = 2^{f_i(n)}+i$

Primeiro, observe como esse conjunto de funções satisfaz sua restrição crescente; segundo, há um$f_i$ para cada $i\in\mathbb{R}^+$ então a cardinalidade de $F$deve ser incontável. Para um exemplo concreto:$f_1(0)=1$, e $f_1(1)=2^1+1=3$, $f(2)=2^3+1=9$ e assim por diante.


Uma prova não construtiva via diagonalização seria a seguinte:

Presumir $S$ é contável e a ordem $f, g \in S$ de $f \ll g \iff \forall x f(x)<g(x)$. Observe como, sob esta definição, nem sempre é verdade que$f \ll g$ ou $f=g$ ou $f\gg g$. Portanto, esta é uma ordem parcial. Agora escolha uma cadeia máxima$f_i$ e definir $\hat f(1)=f_1(1)$ e $\hat f(i)=f_i(i) + \left[f_{i+1}(i)-f_{i}(i)\right]/2$. Você pode verificar se este $\hat f$ satisfaz a restrição crescente e é diferente de cada $f_i$ em $i$. Uma contradição!

5
TheDayBeforeDawn 2019-10-20 07:28.

Você pode realmente mostrar que o conjunto $S=\{f:\mathbb{N} \to \mathbb{N} : f(n+1) \geq 2^{f(n)}\}$é incontável. Para cada dado$n$, deixei $A_n \subset S$ denotam essas funções de modo que $f(n+1) > 1 + 2^{2^{f(n)}}$. Temos uma surjection$g:S \to \mathcal{P}(\mathbb{N})$ por mapeamento $f \in S$ para $\{n \in \mathbb{N} : f \in A_n\}$.

5
Noname 2019-10-20 08:56.

Acho que uma prova mais simples é notar que, se restringirmos o predicado a $f(n+1)=2^{f(n)}$, cada função $f:\mathbb N\to blah$ é determinado pelo seu valor $f(0)$. Configuração$blah=\mathbb R$, $f(0)$ pode então levar $\mathbb R$-muitos valores, então o conjunto de todas essas funções é incontável. Então, a injeção óbvia do conjunto anterior de funções ao seu prova que o último é incontável.


A resposta de Shiranai é semelhante, exceto que eles corrigem o primeiro (ou $n$-muitos) valores, então $f(n+1)$ deve ser maior ou igual a $2^{f(n)}$.

4
Mirko 2019-10-20 18:46.

Sim, você pode apresentar uma prova por contradição. Também funciona se você substituir$\Bbb R$ com $\Bbb N$ na definição de $S$. (A versão com$\Bbb R$ é tão fácil quanto $f(0)$pode assumir vários valores contínuos, como nas respostas de palmpo e de Shiranai. A resposta de MathematicsStudent1122 já mostra que podemos substituir$\Bbb R$ com $\Bbb N$, mas usarei uma prova por contradição e diagonalização.)

Deixei $S=\{f \colon \mathbb{N} \mapsto \mathbb{N} \mid f(n+1) \ge 2^{f(n)} \}$ Onde $\Bbb N$ é o conjunto $\{0,1,2,...\}$de todos os inteiros não negativos. Suponha$S$ foram contáveis, digamos $S=\{f_n : n\in\Bbb N\}$. Defina uma nova função$f$ de $f(0)=f_0(0)+1$ e, recursivamente, $f(n+1)=\max\{f_{n+1}(n+1)+1,2^{f(n)}\}$. Então$f(n+1)\ge 2^{f(n)}$, conseqüentemente $f\in S$, mas por outro lado, para cada $n$ temos $f(n)\ge f_n(n)+1>f_n(n)$, conseqüentemente $f\notin S$. Esta contradição mostra que$S$ é incontável.

1
Samuel 2019-10-21 07:44.

O conjunto de poderes de qualquer conjunto tem maior cardinalidade do que o conjunto original.

Cada pôr do sol não trivial de $\mathbb{N}$ pode ser mapeado por alguma função de $\mathbb{N}$ para $\mathbb{R}$.

Então agora você só precisa mostrar cada subconjunto não trivial de $\mathbb{N}$ pode corresponder a uma função particular de crescimento rápido.

Comece com uma função de crescimento rápido F. Para cada subconjunto de $\mathbb{N}$ com n elementos e o maior elemento m, construa um polinômio de grau m com n termos com expoentes correspondentes aos membros de $\mathbb{N}$. Multiplique este polinômio por F e você terá uma nova função de crescimento rápido.

Related questions

MORE COOL STUFF

Cate Blanchett dormiu com o marido depois de 3 dias juntos e ainda está casada com ele 25 anos depois

Cate Blanchett dormiu com o marido depois de 3 dias juntos e ainda está casada com ele 25 anos depois

Cate Blanchett desafiou os conselhos típicos de namoro quando conheceu o marido.

Por que Michael Sheen é um ator sem fins lucrativos

Por que Michael Sheen é um ator sem fins lucrativos

Michael Sheen é um ator sem fins lucrativos, mas o que exatamente isso significa?

Hallmark Star Colin Egglesfield Pratos Emocionantes Encontros de Fãs no RomaDrama Live! [Exclusivo]

Hallmark Star Colin Egglesfield Pratos Emocionantes Encontros de Fãs no RomaDrama Live! [Exclusivo]

A estrela da Hallmark Colin Egglesfield falou sobre emocionantes encontros com fãs no RomaDrama Live! além de seu programa INSPIRE na convenção.

Por que você não pode transmitir 'Exposição do Norte' online

Por que você não pode transmitir 'Exposição do Norte' online

Você terá que tirar o pó de um Blu-ray ou DVD player para ver por que Northern Exposure se tornou um dos programas mais populares dos anos 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

Como a matéria branca ajuda a função da matéria cinzenta do cérebro

Como a matéria branca ajuda a função da matéria cinzenta do cérebro

Todos nós já ouvimos falar da massa cinzenta do cérebro, mas e a massa branca? O que isso faz?

Doe seu cabelo para ajudar a manter nossa água limpa

Doe seu cabelo para ajudar a manter nossa água limpa

Aparas de cabelo de salões e doações pessoais podem ser reaproveitadas como tapetes que absorvem derramamentos de óleo e ajudam a proteger o meio ambiente.

Um olhar sobre os casamentos mais memoráveis ​​da Casa Branca

Um olhar sobre os casamentos mais memoráveis ​​da Casa Branca

Apenas algumas pessoas se casaram na Casa Branca nos últimos 200 anos. Quem eram eles e o que é necessário para marcar um casamento lá?

Esta semana no mercado de trabalho: a verdade na publicidade

Esta semana no mercado de trabalho: a verdade na publicidade

CITAÇÃO | “Recebemos mais de dois milhões de visitantes únicos neste stream para assistir, não sei o quê, nada.” - Todd Howard da Bethesda Game Studios descreve a transmissão ao vivo de 24 horas da empresa de uma estátua do Vault Boy e uma TV com um gráfico “Please Stand By” levando à revelação do teaser Fallout 76.

Wall Street Journal se preocupa com o fato de que profissionais do sexo "ilícitas" prejudicam sites de namoro de milhões de dólares

Wall Street Journal se preocupa com o fato de que profissionais do sexo "ilícitas" prejudicam sites de namoro de milhões de dólares

O Wall Street Journal de hoje tem um artigo sobre o impacto potencialmente negativo da nova lei “anti-tráfico” do nosso país - não sobre as trabalhadoras do sexo, veja bem, mas sobre o grande negócio do namoro online. Sim, a Lei de Permitir que Estados e Vítimas Combatam o Tráfico de Sexo Online (FOSTA) está colocando em risco a subsistência e a vida de profissionais do sexo - mas, ah, alguém não pensará nas empresas multimilionárias? Como o artigo adverte seus leitores conservadores e preocupados com o dinheiro, “O negócio florescente de namoro online enfrenta novos riscos de uma lei projetada para prevenir o tráfico sexual e a prostituição.

O cantor Scott Hutchison do Frightened Rabbit desapareceu

O cantor Scott Hutchison do Frightened Rabbit desapareceu

Scott Hutchison, vocalista da banda indie escocesa Frightened Rabbit, foi relatado como desaparecido por sua família. A BBC relata que ele está atualmente em Edimburgo e a polícia está chegando ao público para obter qualquer informação sobre sua localização.

Me chame de 'Mestre': Ex diz que o ex-procurador-geral de Nova York estava interessado em interpretar papéis racistas durante o sexo

Me chame de 'Mestre': Ex diz que o ex-procurador-geral de Nova York estava interessado em interpretar papéis racistas durante o sexo

O agora ex-procurador-geral de Nova York Eric Schneiderman em 2017 Na segunda-feira, o New Yorker publicou uma exposição de mais de 6.000 palavras sobre o agora ex-procurador-geral de Nova York Eric Schneiderman, na qual pelo menos quatro mulheres em relacionamentos anteriores com ele acusaram a operadora democrata de abuso físico, sexual, verbal e emocional. Horas depois, Schneiderman negou as acusações, mas renunciou ao cargo.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Carne de porco Mapo de Dawn Burrell e homus de Edamame

Carne de porco Mapo de Dawn Burrell e homus de Edamame

"Esta é uma indústria dominada por homens, e estou feliz por ser uma das pessoas que quebrou o molde para ajudar as mulheres de cor", diz Top Chef: finalista de Portland e chef-parceiro do final de agosto em Houston. "Muitas vezes somos ignorados e às vezes não ensinados, mas isso vai mudar."

Kate Middleton passa um dia à beira da água em Londres, além de Jennifer Lopez, Julianne Hough e mais

Kate Middleton passa um dia à beira da água em Londres, além de Jennifer Lopez, Julianne Hough e mais

Kate Middleton passa um dia na água em Londres, além de Jennifer Lopez, Julianne Hough e muito mais. De Hollywood a Nova York e em todos os lugares, veja o que suas estrelas favoritas estão fazendo!

Jovem de 17 anos esfaqueado até a morte enquanto outros 4 ficaram feridos em um ataque de faca no rio Wisconsin

Jovem de 17 anos esfaqueado até a morte enquanto outros 4 ficaram feridos em um ataque de faca no rio Wisconsin

Investigadores estão investigando se o grupo e o suspeito se conheciam antes do ataque

Aterrissagens na pista

Aterrissagens na pista

O final do verão e o outono são estações nostálgicas. Os postes de luz lançam sua luz sobre as ruas escorregadias pela chuva, e as folhas sob os pés – vermelho-alaranjado nas sombras do crepúsculo – são um lembrete de dias passados.

Imagine criar uma estratégia de conteúdo que realmente CONVERTE. É possível.

Imagine criar uma estratégia de conteúdo que realmente CONVERTE. É possível.

Em 2021, encorajo você a repensar tudo o que sabe sobre os clientes que atende e as histórias que conta a eles. Dê um passo para trás.

Uma perda gigantesca abriu meu coração para o amor

Uma perda gigantesca abriu meu coração para o amor

No dia do aniversário de 9 anos de Felix The Cat, lembro-me de uma das maiores perdas da minha vida adulta – minha Sophie em 2013. Escrevi este ensaio e o compartilhei brevemente nesta plataforma em 2013.

Quando você não pode ser a pessoa que a internet quer que você seja

Quando você não pode ser a pessoa que a internet quer que você seja

Odeio a palavra “naufrágio”. As pessoas se confortam em sua própria bússola moral e, ao fazê-lo, encontram-se julgando.

Language