My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree9Thanks
Reply
 
LinkBack Thread Tools Display Modes
January 17th, 2019, 08:00 AM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 493
Thanks: 36

Question on Dedekind Cuts

The Dedekind cut* for the $\sqrt{2}$ is given by the following partition of $\mathbb{Q}$:
$$A = \{ a \in \mathbb{Q} : a^2 < 2 \text{ or } a < 0 \}$$
$$B = \{ b \in \mathbb{Q} : b^2 \geq 2 \text{ and } b > 0 \}$$

To give the cut for $\sqrt{2}$ as shown above, we are relying on the formula $x^2$. To me, this means that we are relying on the axiom schema of specification to partition $\mathbb{Q}$ into the subsets $A$ and $B$ using the formula $x^2$.

Question(s):

What happens for noncomputable reals where there is no formula with which to apply the axiom schema of specification when partitioning $\mathbb{Q}$? More directly, if there is no formula in the language of set theory to invoke the axiom schema of specification and create the partition, how is it we assert that there is a Dedekind cut consisting of $A$ and $B$?

My (likely flawed) idea is that the axiom of powerset is required to assert the existence of $\mathcal{P}(\mathbb{N})$ within a model of ZF set theory because the axiom schema of specification cannot be applied to the natural numbers to assert the existence of noncomputable subsets of $\mathbb{N}$. If it could so as to ensure that every noncomputable subset of $\mathbb{N}$ existed within the model, then I think the axioms of union and pairing would also allow for the existence of $\mathcal{P}(\mathbb{N})$ within the model even if the power set axiom where omitted from ZF.

* Should anyone be unfamiliar, a Dedekind cut of the rational numbers is given by partitioning $\mathbb{Q}$ into the sets $A$ and $B$ where $A$ is nonempty, $A \neq \mathbb{Q}$, $A$ is closed downwards, and $A$ does not contain a greatest element. Where each real number results in a unique partition of $\mathbb{Q}$ into $A$ and $B$, we generally assert that Dedekind cuts are a method of constructing the real numbers from the rationals.
AplanisTophet is offline  
 
January 17th, 2019, 08:39 AM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,618
Thanks: 2608

Math Focus: Mainly analysis and algebra
Given that the reals are the completion of the rationals under the usual norm, there is always a sequence that exists having the relevant real number as its limit. Indeed, there is always such a monotonic sequence. This can then be used to specify the Dedekind cut.

The obvious complaint is that we can't, in any finite (or countably infinite?) sequence of symbols, write down an appropriate sequence for such non-computable numbers, but that doesn't mean that the sequence doesn't exist.
Thanks from AplanisTophet

Last edited by skipjack; January 19th, 2019 at 09:15 AM.
v8archie is offline  
January 17th, 2019, 09:50 AM   #3
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 493
Thanks: 36

Quote:
Originally Posted by v8archie View Post
Given that the reals are the completion of the rationals under the usual norm, there is always a sequence that exists having the relevant real number as it's limit. Indeed, there is always such a monotonic sequence. This can then be used to specify the Dedekind cut.
This is agreeable to me the same way I can accept the power set axiom. I.e., we accept that there are noncomputable subsets of $\mathbb{N}$ within $\mathcal{P}(\mathbb{N})$ that, if my understanding is correct, we could not otherwise assert exist within a model of ZF without the axiom of powerset.

Quote:
Originally Posted by v8archie View Post
The obvious complaint, is that we can't, in any finite (or countably infinite?) sequence of symbols, write down an appropriate sequence for such non-computable numbers, but that doesn't mean that the sequence doesn't exist.
So what do we mean when we say that we 'construct' the reals from the rationals using Dedekind cuts? That is, if I just assume $x$ is a noncomputable real I can then assert:

$$A = \{ a \in \mathbb{Q} : a < x \}$$
$$B = \{ b \in \mathbb{Q} : b \geq x \}$$

Simply assuming the existence of $x$ makes the whole notion of Dedekind cuts redundant in that the Dedekind cut isn't constructing $x$, but rather, $x$ is constructing the Dedekind cut, yes?

If there is no finite formula for constructing $A$ and $B$ without just assuming the existence of $x$, then wouldn't an axiom be needed to assert the existence of $x$? E.g., just as the power set axiom is needed to assert the existence of $\mathcal{P}(\mathbb{N})$ and, again if I'm not mistaken, all of the noncomputable subsets of $\mathbb{N}$ within a model of ZF, an axiom would be needed to assert the existence of the noncomputable reals.

I may be drawing some confusion in that there is perhaps a difference between a noncomputable subset of $\mathbb{N}$ and a subset of $\mathbb{N}$ such that there is no formula that may be utilized by the axiom schema of specification to assert the subset's existence given $\mathbb{N}$. It could be an issue of confusing definability with computability. In either case, if it takes a finite statement within the language of ZF to define something and a finite statement to compute something, than both the set of what may be defined and the set of what may be computed are countably infinite sets. Where there are uncountably many sets within a model of ZF, then there are sets that can neither be computed or defined.

Quote:
Originally Posted by v8archie View Post
The obvious complaint, is that we can't, in any finite (or countably infinite?) sequence of symbols, write down an appropriate sequence for such non-computable numbers, but that doesn't mean that the sequence doesn't exist.
Allowing countably infinite sequences of symbols would imply that all reals are computable within the system. For example, $0.\overline{01}$ could be 'computed' as:

$$\{ n \in \mathbb{N} : n \neq 1, n \neq 3, n \neq 5, … \}$$
as opposed to the traditional:
$$\{ n \in \mathbb{N} : \frac{n}{2} \in \mathbb{N}\}$$
AplanisTophet is offline  
January 17th, 2019, 10:05 AM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,204
Thanks: 647

Quote:
Originally Posted by AplanisTophet View Post
This is agreeable to me the same way I can accept the power set axiom ...
Are you working from a text? My suggestion would be to Google a pdf of Rudin and work through the section on Dedekind cuts. It sounds like you're trying to reason without fully understanding the actual definition. There's nothing about formulas or computability involved.
Thanks from AplanisTophet
Maschke is offline  
January 17th, 2019, 10:06 AM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,618
Thanks: 2608

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by AplanisTophet View Post
So what do we mean when we say that we 'construct' the reals from the rationals using Dedekind cuts? That is, if I just assume $x$ is a noncomputable real I can then assert:

$$A = \{ a \in \mathbb{Q} : a < x \}$$
$$B = \{ b \in \mathbb{Q} : b \geq x \}$$
I would suggest that, given that there exists a monotonically increasing sequence $(c_n)$ such that $\displaystyle \lim_{n \to \infty} c_n = x$, we can say that \begin{align}A &= \{ a \in \mathbb{Q} : a \lt c_n \, \text{for all sufficiently large $n$} \} \\ B &= \{ b \in \mathbb{Q} : b \ge c_n \, \text{for all $n$} \} \end{align}
We thus use only rationals in our construction. I will agree that it seems dangerously close to circular, but if it is, I'm sure there's a way around it.

Last edited by v8archie; January 17th, 2019 at 10:10 AM.
v8archie is offline  
January 17th, 2019, 10:50 AM   #6
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 493
Thanks: 36

Quote:
Originally Posted by v8archie View Post
I would suggest that, given that there exists a monotonically increasing sequence $(c_n)$ such that $\displaystyle \lim_{n \to \infty} c_n = x$, we can say that \begin{align}A &= \{ a \in \mathbb{Q} : a \lt c_n \, \text{for all sufficiently large $n$} \} \\ B &= \{ b \in \mathbb{Q} : b \ge c_n \, \text{for all $n$} \} \end{align}
We thus use only rationals in our construction. I will agree that it seems dangerously close to circular, but if it is, I'm sure there's a way around it.
In this case, $c_n$ would have to equal $x$ (where $n$ is sufficiently large as you state). If it didn't, the sets $A$ and $B$ would not form a Dedekind cut for $x$. Rather, they would form a Dedekind cut for $c_n$.

PS - Your $A$ and $B$ above are not a partition and therefore cannot constitute a Dedekind cut. I assume a typo?

Last edited by AplanisTophet; January 17th, 2019 at 10:54 AM.
AplanisTophet is offline  
January 17th, 2019, 11:04 AM   #7
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 493
Thanks: 36

Quote:
Originally Posted by Maschke View Post
Are you working from a text? My suggestion would be to Google a pdf of Rudin and work through the section on Dedekind cuts. It sounds like you're trying to reason without fully understanding the actual definition. There's nothing about formulas or computability involved.
I have no issue with asserting that each real number will result in a unique $A$ and $B$ that partition $\mathbb{Q}$ so as to form a Dedekind cut.

I am asking, how is it that we derive $A$ and $B$ in cases where $x$ is noncomputable and/or not definable using a finite string of symbols? I am stating that we must first prove the existence of $A$ and $B$ before we can assert the existence of $x$ if not simply assuming the existence of $x$.

Alternatively, if we are in fact just assuming the existence of $x$ (which I can be fine with), then what is the point of a Dedekind cut?
AplanisTophet is offline  
January 17th, 2019, 11:50 AM   #8
Senior Member
 
Joined: Aug 2012

Posts: 2,204
Thanks: 647

Quote:
Originally Posted by AplanisTophet View Post
I have no issue with asserting that each real number will result in a unique $A$ and $B$ that partition $\mathbb{Q}$ so as to form a Dedekind cut.

I am asking, how is it that we derive $A$ and $B$ in cases where $x$ is noncomputable and/or not definable using a finite string of symbols? I am stating that we must first prove the existence of $A$ and $B$ before we can assert the existence of $x$ if not simply assuming the existence of $x$.

Alternatively, if we are in fact just assuming the existence of $x$ (which I can be fine with), then what is the point of a Dedekind cut?
What is the exact definition of Dedekind cut that you're working from? Going back to the precise definition is the key to your question.

In case you're wondering, yes I could spoon feed you the answer here but I'm trying to see if I can assist you in working through it for yourself.

ps -- A sharper clue: "I am stating that we must first prove the existence of $A$ and $B$" -- Ok. What are $A$ and $B$? Exactly?

Last edited by Maschke; January 17th, 2019 at 12:03 PM.
Maschke is offline  
January 17th, 2019, 12:07 PM   #9
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 493
Thanks: 36

Quote:
Originally Posted by Maschke View Post
What is the exact definition of Dedekind cut that you're working from? Going back to the precise definition is the key to your question.

In case you're wondering, yes I could spoon feed you the answer here but I'm trying to see if I can assist you in working through it for yourself.

ps -- A sharper clue: "I am stating that we must first prove the existence of $A$ and $B$" -- Ok. What are $A$ and $B$? Exactly?
I gave the definition of a Dedekind cut in the OP.
AplanisTophet is offline  
January 17th, 2019, 12:24 PM   #10
Senior Member
 
Joined: Aug 2012

Posts: 2,204
Thanks: 647

Quote:
Originally Posted by AplanisTophet View Post
I gave the definition of a Dedekind cut in the OP.
Given your def, isn't it clear how A and B exist? I guess I no longer understand your question.

> It could be an issue of confusing definability with computability.

You are way overthinking this.

ps ok here's what I think is the answer to your question.

> a Dedekind cut of the rational numbers is given by partitioning ℚ into the sets A and B where A is nonempty, A≠ℚ, A is closed downwards, and A does not contain a greatest element.

That is the specification! Isn't it? What you wrote can be coded as a predicate against the powerset of the rationals, right? We don't have to specifically name all the elements of the powerset. They all exist, and then we cut the powerset down by specifying that we're only interested in certain types of subsets, namely the ones that are nonempty, closed downward, etc.
Thanks from AplanisTophet

Last edited by Maschke; January 17th, 2019 at 01:05 PM.
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
cuts, dedekind, question



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dedekind Cuts :( Antoniomathgini Calculus 2 December 4th, 2017 11:48 AM
Question about Dedekind's paper "Continuity and Irrational Numbers" Yosef Number Theory 4 July 12th, 2017 10:46 AM
Addition with Dedekind cuts, proof Awesomo Real Analysis 1 June 28th, 2014 08:18 PM
Showing R is an ordered set with cuts Awesomo Real Analysis 5 June 18th, 2014 06:41 PM
101 Short Cuts in Math Anyone Can Do Dundero Math Books 2 February 14th, 2011 07:49 PM





Copyright © 2019 My Math Forum. All rights reserved.