1
$\begingroup$

For me, facts like the independence of the continuum hypotheses from ZFC cast a doubt on the "law of the excluded middle". (In this context, the doubt is that there might be no "final set theory" such that every proposition about sets is either true or false.) Now I'm looking for simpler (mathematical) examples that are easier to understand, but still cast a similar doubt on the "law of the excluded middle" (or on another law of the three classical laws of thought). Right now, I think that recursion theory (also known as computability theory) might teach me the sort of examples I'm looking for (at least I can appreciate the difference between primitive recursive functions and $\mu$-recursive functions).

Here is an example closely related to "computability theory" that I "nearly" understand:

For a sequence $(a_n)_{n\in \mathbb N}$ of natural numbers, the set of all natural numbers occurring in the sequence $U_a:=\cup_{n\in \mathbb N}\{a_n\}$ is a subset of the natural numbers. Each subset $U$ of the natural numbers gives rise to a unique sequence $(a_n^U)_{n\in \mathbb N}$ with $a_n^U < a_{n+1}^U$ and $U=\cup_{n\in \mathbb N}\{a_n^U\}$. Two subsets $U$ and $V$ of the natural numbers are identical if and only if the sequences $(a_n^U)_{n\in \mathbb N}$ and $(a_n^V)_{n\in \mathbb N}$ are identical. Comparing two sequences for equality is easy, at least when the sequences are given explicitly in a computable form. However, it may happen that a computable sequence $(a_n)_{n\in \mathbb N}$ gives rise to a set $U_a$ for which the sequence $(a_n^{U_a})_{n\in \mathbb N}$ is not computable. Even worse, there are computable sequences $(a_n)_{n\in \mathbb N}$ and $(b_n)_{n\in \mathbb N}$ for which there exists no computable way to determine whether $U_a$ and $U_b$ are identical.

It seems to me that all references to "computable" in this example can be made exact by interpreting them as "computable by a $\mu$-recursive function", except the statement "there exists no computable way".

  • Is there a way to also give the statement "there exists no computable way" a well defined meaning in the context of recursion theory?
  • Can the example be further simplified? Is the statement "there exists no computable way" necessary at all for understanding the "undecidability properties" that allow the "law of the excluded middle" to not apply (in certain mathematical contexts)?
  • Are there simpler examples using less infinite objects and assumptions, for examples just working with sequences of 0 and 1 without making the rest of the construction significantly more complicated?
  • Are there any questionable assumptions or axioms used by the example above, except the assumption that the union $\cup_{n\in \mathbb N}\{a_n\}$ always exists?

Edit The comments below show that it is quite difficult (for me) to explain what I actually would like to know. Especially, there was the suggestion to change the title of the question. The problem is that the title is actually quite appropriate for my question, but that mentioning of the "laws of thought" seems to divert the attention of the readers completely from what I actually want to know. There is also a limit to how much I want to change an existing question by editing. Trying to clarify the question is fine, but if it should be necessary to turn it into a completely different question I prefer to ask another question instead.

  • 4
    I don't see that this casts any doubt on the law of identity. Difficulty in recognizing that two descriptions actually describe the same object is hardly the same as actual 'fuzziness' of identity.2012-05-06
  • 1
    There is a concept of "equivalence", which is coarser than that of identity. When we talk about "representations of objects", we are dealing with equivalence, so there is no problem with the fact that two different things may represent the same object. In any case, this would be in the "opposite direction" as the law of identity, which saysthat identical things are "equal", not that two "equal/equivalent" things must be identical. I don't see the connection with computability, though.2012-05-06
  • 0
    "Even worse, there are computable sequences (an)n∈ℕ and (bn)n∈ℕ for which there exists no computable way to determine whether Ua and Ub are identical." In some sense this is not quite true. Because they are computable sequence they have index $i$ and $j$. The answer to whether the sequence given by $i$ and $j$ are equal is a finite piece of information - yes or no. However, if you want a uniform procedure such that given any index $i$ and $j$ to determine if the sequence is the same, then no such computable function exists.2012-05-06
  • 0
    Continuing: philosophically do you think the law of identity requires that you know the answer to a whole class of question in a computable way? For any two fixed sequence, computably the answer is yes or no. Should the law of identity require you to have a single uniform way to answer this entire class of similar questions? I don't really think about these philosophical things, but you might want to consider this aspect.2012-05-06
  • 0
    @ArturoMagidin You're right, I see now that it's the "opposite direction". So $(a_n)_{n\in \mathbb N}$ and $(b_n)_{n\in \mathbb N}$ ($U_a$ and $U_b$) are certainly not identical if they have different representations, but they might still be equal. I guess it's always possible to define equality in such a way that at least identical objects are recognizable as equal.2012-05-06
  • 0
    @William You say "In some sense this is not quite true", but only argue that we can determine whether the sequences are equal or not. However, the point is that sometimes it's impossible to determine whether the sets $U_a$ and $U_b$ defined by the sequences are equal or not. The sets can be equal even if the sequences themselves are not.2012-05-06
  • 0
    @BrianM.Scott I was assuming that a subset of the natural numbers has an identity. However, that might be wrong from a programmers perspective, because a subset of the natural numbers should probably be treated as a "value object", i.e. only equality is important and identity is irrelevant. Note that "difficulty in recognizing ..." is not strictly identical to "impossibility of determining ...", because there is a difference whether we are just unable to do something out of ignorance, or whether we can prove that the thing can't be done at all.2012-05-07
  • 0
    Does the fact that the existence of $\sqrt 2$ is independent of the axioms of field theory cast disbelief in anyone's heart? I doubt. Why would the same fact about the subsets of $\mathbb N$ would?2012-05-08
  • 0
    @AsafKaragila I could try to explain it, but given the comments so far, I have little hope to be successful. So I tried to change to focus of the question instead, while still making it clear that my "personal doubts" remain, even if this question is not primarily concerned with my "personal doubts". Also, please note that some of the comments have a "deficits of understanding" even regarding the less debatable parts of the question. I don't see how answering to comments brings me closer to an answer to my question. I will have to accept that nobody here considers this a valid question.2012-05-08
  • 0
    Thomas, I had several doubts on how CH could be independent, or how large cardinals (which prove the consistency of ZFC, alas ZFC itself cannot prove itself consistent, might be consistent with ZFC) and I can tell you that most of my problems stemmed from inadequate understanding of the axioms. Once things are clearing up in your head it gets easier to handle. I do agree that it is hard to see how "the amount of sets" can be different, but it is much like the amount of unit roots in a given field. It can be more, less, etc. but no one cares because it makes sense somehow, but with sets? no...2012-05-08
  • 0
    @AsafKaragila The "law of the excluded middle" can be interpreted to say that a proposition is either true or false. Of course CH might fail to be a proposition, but assuming it is a proposition in ZFC, then its independence can be interpreted to say that it is neither true nor false in ZFC. But my doubts are more subtle, and are more related to the changes in microstructure of the meaning of a statement being true in different contexts.2012-05-08
  • 3
    But the statement "*There are exactly $n$ distinct numbers $\zeta$ such that $\zeta^k=1$*" is a statement which is true or false in different models of field theory where $n$ can vary anywhere between $2$ to $2^{\aleph_0}$. *How* is this any different than the statement "*There are only $\aleph_\alpha$ many sets of natural numbers.*" other than a psychological pan? Think about this, please do, not for ten minutes. For a few days. I gave this thought about two years in which I studied set theory, I don't expect anyone who's not studying set theory in full to get an answer in ten minutes.2012-05-08
  • 0
    Every statement in mathematics can be written as a statement about whether two computable sequences are equal I believe, so there cant be any simpler examples.2012-05-08
  • 3
    If your question is "Are there (simpler) examples which (more clearly) cast doubt on one of the three classical laws of thought," then why is your title "Equivalence of sequences and subsets of natural numbers"? Wouldn't a more congruent title be something like, "Examples casting doubt on the laws of thought"?2012-05-09
  • 0
    @ThomasKlimpel: Yes, but you seem to be misinterpreting what "or" means. In classical logic, $p \lor q$ means "it is not the case that neither $p$ nor $q$". A proof of $p \lor q$ is not necessarily either a proof of $p$ or a proof of $q$; in other words, classical logic does not have the [disjunction property](http://en.wikipedia.org/wiki/Disjunction_property).2012-05-09
  • 0
    @GerryMyerson The problem is that my question not so much about the "laws of thought", but about how it actually happens that they are "not necessary enforced" in certain mathematical contexts. The described example is basically the simplest example I managed to come up with, but it still uses results from a theory that I don't fully understand yet.2012-05-09

1 Answers 1