0

Prove that for each $x,y$ an element of the natural numbers ($\mathbb{N}$), $x<y$ or $x=y$ or $x>y$. So at least one is true. I have the definition of order to work with and the basic algebra of the natural numbers to work with (i.e. commutativity of add./mult., associativity of add./mult., etc.). I figured it best to begin by doing this by cases. So, for case 1: assume $x\nless y$ and $x\neq y$, show $x>y$. I'm not sure, however, what $x\nless y$ and $x\neq y$ allows me to conclude. Thanx for the help and my apologies for the formatting.

Steve D.
  • 1
  • 1
    What is the definition of order that you have? – vadim123 Nov 03 '14 at 20:27
  • For x, y ∈ N, we say that x < y if and only if ∃k ∈ N such that y = x+k. For x, y ∈ N, x ≤ y if and only if x < y or x = y. For x, y ∈ N, x > y if and only if y < x. For x, y ∈ N , x ≥ y if and only if y ≤ x – Steve D. Nov 03 '14 at 20:29
  • The key here is that every natural number can be constructed as a successor of $1$. If this weren't true then trichotomy would not hold. – vadim123 Nov 03 '14 at 20:31
  • Ah, yes, however, I am not proving trichotomy I just want to show that at least one of xy is true, not that at most one is. Sorry if I'm misinterpreting what you are trying to convey. – Steve D. Nov 03 '14 at 20:33
  • There is no difference, as it is very simple to prove that at most one of these is true. The hard part is the part you are doing. – vadim123 Nov 03 '14 at 20:34

1 Answers1

1

Proof by induction on $x$.

Base case: $x=1$. Then either $y=1$ (and $x=y$) or $y\neq 1$, and then $x<y$ because each natural number is a successor of $1=x$.

Inductive case: $x\neq 1$. This breaks into two parts:
1. $y=1$. Then $x>y$, since each natural number except $1$ is a successor of $1=y$.
2. $y\neq 1$. Then both $x,y$ are successors, so we apply the inductive hypothesis to $x-1, y-1$. Either $x-1<y-1$, $x-1=y-1$, or $x-1>y-1$. In the first case, $x-1+k=y-1$, so $x+k=y$ and hence $x<y$. The last two cases are similar.

vadim123
  • 82,796
  • Ah, thank you very much. I was leaning towards induction but was not sure how to approach it. – Steve D. Nov 03 '14 at 20:45
  • Glad to help, you're welcome. – vadim123 Nov 03 '14 at 20:45
  • Ok, so I concluded both other cases, however, I am unsure of the x-1=y-1 case. How can I conclude that x-1=y-1 implies x=y via the given definition of order? Would it be via the cancellation property of addition? That wouldn't work because 1 isn't an element of N. So could I apply the induction hypothesis to x+1 and y+1? Making the cancellation for addition a valid justification? – Steve D. Nov 03 '14 at 21:58
  • If two numbers are equal, then their successors are equal -- this should be one of the properties of equality you have. – vadim123 Nov 03 '14 at 22:00
  • Correct, however, are you saying that I am allowed to state the successor of x and y as x-1 and y-1 respectively? What I have is a conditional statement for all x,y an element of N, x'=y' implies x=y. Are you saying the converse is true as well? – Steve D. Nov 03 '14 at 22:02
  • When I write "$x-1$" this is shorthand for "$x'$, whose successor is $x$". There is no subtraction defined. – vadim123 Nov 03 '14 at 22:04
  • Ah, my mistake, I haven't seen it represented that way before. So you are saying that x-1 is defined as x successor whose successor is x? – Steve D. Nov 03 '14 at 22:19