نوع مقاله : پژوهشی

نویسنده

• امیر خمسهء

دانشکده علوم ریاضی و کامپیوتر دانشگاه خوارزمی

چکیده

قضیه هیندمن بیان می‌کند که برای هر افراز از مجموعه اعداد طبیعیN به تعداد متناهی بخش، یک زیر مجموعه نامتناهی از اعداد طبیعی وجود دارد که همه مجموع‌های متناهی از اعضای متمایز این زیر مجموعه، عضو یک بخش مشخصی از افراز باشند. همچنین قضیه شور بیان می‌کند که برای هر افراز از مجموعه اعداد طبیعیN به تعداد متناهی بخش، حداقل یکی از بخش‌های افراز وجود دارد که شامل سه عدد x,y,z است که x+y=z. قضیه برائر شبیه قضیه شور است با این تفاوت که به جای جواب برای معادله x+y=z، حداقل یکی از بخش‌های افراز شامل تصاعد حسابی به صورت \{a,a+b,a+2b,…,a+(l-1)b\} باشد. در این مقاله، اثبات پذیری قضیه هیندمن شور و هیندمن برائر را در حساب مرتبه اول پئانو مطالعه می‌کنیم و نشان می‌دهیم که نسخه متناهی این قضایا در حساب مرتبه اول پئانو اثبات پذیر است. در ادامه خواهیم دید که با اضافه شدن شرط مجزا بودن هم نتایج در حساب مرتبه اول پئانو اثبات پذیر باقی می‌ماند.

کلیدواژه‌ها

• اثبات پذیری
• حساب پئانو
• قضیه هیندمن
• قضیه برائر
• قضیه شور
• قضیه رمزی

موضوعات

• منطق ریاضی استاندارد

عنوان مقاله [English]

Provability of Hindman-Schur and Hindman-Brauer in Peano Arithmetic

نویسنده [English]

• amir khamseh

Department of Mathematics, Kharazmi University

چکیده [English]

Hindman’s Theorem states that for every coloring of natural numbers N with finitely many colors, there is an infinite set H such that the set of numbers which can be written as a sum of distinct elements of H is monochromatic. On the other hand, Brauer’s Theorem states that for all r,l,s≥1, there exists t=t(r,l,s) such that if the interval [1,t] is r-colored then there exists a,b>0 such that the set \{a,b,a+b,a+2b,…,a+(l-1)b\}⊆[1,t] is monochromatic. If A and B are sets, FS^A (B) is the set of all sums of j-many distinct elements of B, for all j∈A. Hindman-Brauer Theorem is the following statement: for every r-coloring of the set of natural numbers N, there is an infinite set H⊆N and a,b>0 such that FS^(\{a,b,a+b,a+2b,…,a+(l-1)b\}) is monochromatic. In this paper, we study the finite version of Hindman-Brauer Theorem and also Hindman-Schur Theorem and show that these results are provable in first order Peano Arithmetic. Also, we will see that these results are provable if we consider the apartness condition.

کلیدواژه‌ها [English]

• Provability
• Peano Arithmetic
• Hindman Theorem, Brauer Theorem, Schur Theorem,
• Ramsey Theorem