Let a, b E N, assume they are not both 0, Define L = {n E N+·3x, y E Z,n = az +
ID: 3168230 • Letter: L
Question
Let a, b E N, assume they are not both 0, Define L = {n E N+·3x, y E Z,n = az + by). Prove the claims below, being sure to first state the claim you are proving in predicate logic, and then to write the complete proof. You may use the result of earlier claims in proving later ones, for example you might use claim (f) to help prove claim (e). Claim: has a minimum element m, i.e. m is no larger than any other element of C. You may use, without proof, the fact that any non-empty, finite set of real numbers has a minimum elementExplanation / Answer
Consider the set L of all positive linear combinations of a and b:
L = { n in N | n = ax + by > 0; x,y are integers}
Notice first that L is not empty. For example, if a 0, then the integer | a | = ax + b · 0
lies in L, where we choose x = 1 or x = 1 according as a is positive or negative and y = 0.
hence L is a subset of the set of all natural numbers N
By virtue of the Well-Ordering Principle, L must contain a smallest element d. Thus,
from the very definition of L, there exist integers x and y for which d = as + bt for some s,t in Z.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.