My Math Forum Question on Dedekind Cuts

 Number Theory Number Theory Math Forum

 January 17th, 2019, 08:00 AM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 528 Thanks: 43 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.
 January 17th, 2019, 08:39 AM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,674 Thanks: 2654 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.
January 17th, 2019, 09:50 AM   #3
Senior Member

Joined: Jun 2014
From: USA

Posts: 528
Thanks: 43

Quote:
 Originally Posted by v8archie 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 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 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, … \}$$
$$\{ n \in \mathbb{N} : \frac{n}{2} \in \mathbb{N}\}$$

January 17th, 2019, 10:05 AM   #4
Senior Member

Joined: Aug 2012

Posts: 2,355
Thanks: 737

Quote:
 Originally Posted by AplanisTophet 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.

January 17th, 2019, 10:06 AM   #5
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,674
Thanks: 2654

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by AplanisTophet 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.

January 17th, 2019, 10:50 AM   #6
Senior Member

Joined: Jun 2014
From: USA

Posts: 528
Thanks: 43

Quote:
 Originally Posted by v8archie 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.

January 17th, 2019, 11:04 AM   #7
Senior Member

Joined: Jun 2014
From: USA

Posts: 528
Thanks: 43

Quote:
 Originally Posted by Maschke 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?

January 17th, 2019, 11:50 AM   #8
Senior Member

Joined: Aug 2012

Posts: 2,355
Thanks: 737

Quote:
 Originally Posted by AplanisTophet 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.

January 17th, 2019, 12:07 PM   #9
Senior Member

Joined: Jun 2014
From: USA

Posts: 528
Thanks: 43

Quote:
 Originally Posted by Maschke 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.

January 17th, 2019, 12:24 PM   #10
Senior Member

Joined: Aug 2012

Posts: 2,355
Thanks: 737

Quote:
 Originally Posted by AplanisTophet 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.

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

 Tags cuts, dedekind, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Antoniomathgini Calculus 2 December 4th, 2017 11:48 AM Yosef Number Theory 4 July 12th, 2017 10:46 AM Awesomo Real Analysis 1 June 28th, 2014 08:18 PM Awesomo Real Analysis 5 June 18th, 2014 06:41 PM Dundero Math Books 2 February 14th, 2011 07:49 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top