My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Question on Dedekind Cuts (http://mymathforum.com/number-theory/345633-question-dedekind-cuts.html)

 AplanisTophet January 17th, 2019 08:00 AM

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.

 v8archie January 17th, 2019 08:39 AM

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.

 AplanisTophet January 17th, 2019 09:50 AM

Quote:
 Originally Posted by v8archie (Post 604538) 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 (Post 604538) 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 (Post 604538) 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}\}$$

 Maschke January 17th, 2019 10:05 AM

Quote:
 Originally Posted by AplanisTophet (Post 604539) 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.

 v8archie January 17th, 2019 10:06 AM

Quote:
 Originally Posted by AplanisTophet (Post 604539) 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.

 AplanisTophet January 17th, 2019 10:50 AM

Quote:
 Originally Posted by v8archie (Post 604541) 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?

 AplanisTophet January 17th, 2019 11:04 AM

Quote:
 Originally Posted by Maschke (Post 604540) 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?

 Maschke January 17th, 2019 11:50 AM

Quote:
 Originally Posted by AplanisTophet (Post 604545) 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?

 AplanisTophet January 17th, 2019 12:07 PM

Quote:
 Originally Posted by Maschke (Post 604546) 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.

 Maschke January 17th, 2019 12:24 PM

Quote:
 Originally Posted by AplanisTophet (Post 604547) 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.

All times are GMT -8. The time now is 08:16 AM.