Apakah

12

Jika A2 teratur, apakah itu mengikuti bahwa A teratur?

Upaya saya pada bukti:

Ya, untuk kontradiksi anggaplah bahwa A tidak teratur. Kemudian A2=AA .

Karena penggabungan dua bahasa non-reguler adalah tidak biasa, A2 tidak dapat teratur. Ini bertentangan dengan asumsi kami. Jadi A biasa. Jadi jika A2 teratur maka A adalah reguler.

Apakah buktinya benar?

Bisakah kita menggeneralisasi ini menjadi A3 , A4 , dll ...? Dan juga jika A biasa maka A tidak perlu biasa?

Contoh: A={12ii0} tidak teratur tetapi A teratur.

akshay
sumber
2
Bukti pertama membuat lompatan besar. Apa bukti Anda bahwa A tidak berimplikasi A2 tidak teratur? Membuktikan bahwa hal itu mungkin akan mengarahkan Anda pada intuisi untuk membantu menjawab sisa pertanyaan, jika memang benar.
Dave Clarke
@DaveClarke Mengedit buktinya.
akshay
3
Bagaimana Anda bisa mengeja "Apakah saya Benar?" cara itu sangat menarik. Sebagai saran umum: ketika ratusan orang membaca apa yang Anda tulis, kesopanan umum menuntut agar Anda memperhatikan cara Anda menulis ... ;-)
Andrej Bauer
6
@AndrejBauer OP dapat menjadi seseorang yang bukan penutur asli bahasa Inggris, dan yang mungkin belum memiliki kesempatan untuk mendapatkan instruksi tentang bahasa Inggris formal. Ini bukan alasan untuk mengecilkan hati siapa pun, meskipun bisa membantu untuk memperbaikinya.
Yuval Filmus

Jawaban:

28

Pertimbangkan teorema empat persegi Lagrange . Ini menyatakan bahwa jika maka B 4 = { 1 n | n 0 } . Jika B 2 teratur, ambil A = B lain ambil A = B 2 . Either way, ini membuktikan keberadaan A yang tidak teratur sehingga A 2 teratur.B={1n2|n0}B4={1n|n0}B2A=BA=B2AA2

Karolis Juodelė
sumber
Saya tidak mengerti bukti ini; bisakah kamu menguraikan sedikit?
G. Bach
2
Menjelaskan ini (indah) bukti: Kita memiliki , dan bahwa B 4R E G . Perhatikan bahwa B 4 = ( B 2 ) 2 . Sekarang, jika B 2R E G , maka dengan mengambil A = B kita memiliki sampel tandingan, dan jika B 2R E G maka dengan mengambil A = B 2 kita memiliki sampel tandingan. BREGB4REGB4=(B2)2B2REGA=BB2REGA=B2
Shaull
1
Sangat cantik.
vonbrand
3
@YuvalFilmus, memang, tapi saya tidak punya bukti dan saya tidak ingin meninggalkan keraguan. Sekarang saya sepertinya telah menemukan satu. "Angka adalah jumlah dari dua kuadrat jika dan hanya jika semua faktor prima dari bentuk 4 k + 3 bahkan memiliki eksponen dalam faktorisasi prima dari n ." Biarkan n menjadi panjang pemompaan. Pertimbangkan w = ( n ! ) 2 . Biarkan p menjadi prima dari bentuk 4 k + 3 dan biarkan m menjadi panjang yang kita pilih untuk dipompa. Kemudian, w + ( p - 1 )n4k+3nnw=(n!)2p4k+3mmemiliki eksponen aneh padapdan dengan demikian tidak dalamB2. w+(p1)wmm=pwpB2
Karolis Juodelė
1
@ JonasKölker, setuju.
Karolis Juodelė
8

Berikut adalah contoh dari bahasa tidak dapat dihitung sehingga A 2 = Σ . Ambil K yang tidak dapat dihitung (direpresentasikan sebagai sekumpulan angka, mis. Kode mesin Turing yang berhenti), dan tentukan A = { w Σ : | w | 4 k  untuk semua  k K } . Jadi Sebuah berisi semua kata lain daripada yang panjang 4 k untuk beberapa k K . Jika aAA2=ΣK

A={wΣ:|w|4k for all kK}.
A4kkKAdihitung maka Anda dapat menghitung : diberikan k , tentukan apakah 0 4 k (yaitu, 4 k nol) berada di A atau tidak. Karena kami menganggap K tidak dapat dihitung, A juga harus tidak dapat dihitung.Kk04k4kAKA

Klaim: . Biarkan w menjadi kata panjang n . Jika n bukan kekuatan 4 , maka w A dan kata kosongnya di A , jadi w A 2 . Jika n adalah kekuatan 4 maka n / 2 bukan kekuatan 4 . Tulis w = x y , di mana | x | = | y | = n /A2=Σwnn4wAAwA2n4n/24w=xy . Keduanya x , y A jadi w = x y A 2 .|x|=|y|=n/2x,yAw=xyA2

Yuval Filmus
sumber
1
Untuk pemula, sketsa bukti untuk " undecidable" mungkin berurutan. Juga, rintangan kecil mungkin bahwa Anda menggunakan K sebagai bahasa formal dan sebagai seperangkat angka (yang adil, dengan asumsi semantik yang cocok untuk K , tetapi mungkin asing). Kalau tidak, ide yang sangat bagus. AKK
Raphael
2

Bukti Anda masih membuat lompatan besar (dengan alasan bahwa rangkaian bahasa non-reguler adalah non-reguler).

A={1p:p is a prime}A2={12k:k>1}

Ini tidak menyelesaikan pertanyaan sepenuhnya, tetapi memberikan bukti kuat bahwa jawabannya adalah tidak (kalau tidak dugaan Goldbach salah). Namun, jawabannya mungkin sangat sulit untuk dibuktikan, jika ini adalah satu-satunya contoh yang diketahui.

Shaull
sumber
Apa yang bisa kita simpulkan tentang pertanyaan itu?
akshay
A2A
2
Di hadapan bukti "nyata", saya tidak berpikir menggunakan dugaan yang tidak terbukti itu adil. Mungkin koneksi ini menarik untuk sebagian orang?
Raphael
Memang, setelah jawaban berikut, ini berlebihan. Namun, Anda dapat melihat perkembangan matematika yang bagus di sini: jawaban berdasarkan dugaan terkenal, kemudian jawaban terkait (menggunakan teorema Lagrange), yang didasarkan pada ide yang sama (menguraikan angka menjadi penjumlahan).
Shaull
1
Bahkan jika Anda menggunakan bilangan prima dan semiprimes, Anda dapat menggunakan teorema Chen .
sdcvvc
2

Klaim itu salah.

DxDyD|y|>4|x||x|>4|y|

A=ΣDA

A2=Σ    

|y|>2|x||y|>2|x|+2|y|>4|x|

Ran G.
sumber
1A1kA1k1A
2

X1A={1}{12x:xN}{12x+1:1xX}

AA2=1

sdcvvc
sumber
2

UNI={2u+1uU}{0,2,4,}L={aiiI}LL2={a2nnN}{annminI}

David Richerby
sumber
0

{akm is composite}n8n44n13n99n9=2mm2A2={a8,a10}{akk12}{ϵ,a,aa,,a6,a7,a9,a11}

David Richerby
sumber