Prev: Theorem 4.6. The class of box perfect graphs is in co-NP.
Next: [Port%d] \\.\HCD%d
From: cplxphil on 20 Oct 2009 22:36
On Oct 20, 9:58 pm, Tim Little <t...(a)little-possums.net> wrote:
> On 2009-10-21, cplxphil <cplxp...(a)gmail.com> wrote:
>
> > A language defined by a sentence corresponds to the set containing
> > every natural number x (expressed as a binary string) that satisfies
> > the sentence.
>
> What exactly do you mean by "satisfies", in the case that the sentence
> is undecidable?  For example in ZFC, suppose the sentence with free
> natural-number variable x is "aleph_(x+1) = 2^(aleph_x)" (related to
> the Continuum Hypothesis).
>
> - Tim

By "satisfies," I suppose I mean that the formula cannot be proven
false when the value of x is substituted in. In other words, the
axiom system remains consistent.

I think that Tim Chow is right that this is related to Richard's
paradox...I was not previously familiar with it, though I'd heard of
it offhand. It sounds very similar.

Here is a quote from Wikipedia:

"If it were possible to determine which English expressions actually
do define a real number, and which do not, then the paradox would go
through. Thus the resolution of Richard's paradox is that there is no
way to unambiguously determine exactly which English sentences are
definitions of real numbers (see Good 1966)"

I take this to mean that in my example, the problem is that
describability is not describable. There must be situations in which
it is not possible to determine whether or not a particular well-
formed sentence describes a language. I can't think of any sentences
that can't be described, but I'm sure there are some.

Thanks to all who offered input and insight.

-Phil
From: Tim Little on 21 Oct 2009 04:28
On 2009-10-21, cplxphil <cplxphil(a)gmail.com> wrote:
> By "satisfies," I suppose I mean that the formula cannot be proven
> false when the value of x is substituted in. In other words, the
> axiom system remains consistent.

Then some definable language ends up containing members for which the
formula is actually false. For example, consider the language of
encodings of inconsistent formal systems. If you use any
(sufficiently expressive) theory T to determine provability, then the
membership of T's encoding will be incorrect by Goedel's 2nd
incompleteness theorem.


> I take this to mean that in my example, the problem is that
> describability is not describable.

Semantic describability is not formally describable, correct.


Let's work through a slight adaptation of Richard's paradox for your
definition:

There is a sequence of sets of natural numbers L_i such that p_i is
the i'th smallest encoding of a 1-place predicate P_i, and P_i
describes L_i. Let K be the set of natural numbers such that i in K
iff i not in L_i. Then K != L_i for all i. That is, K is not
described by any predicate. Yet this definition of the membership of
K is a predicate P.

The flaw is that just because P(i) is true iff i in K, it does not
mean that P *describes* K: the definition involves provability (or
rather lack of disprovability), not truth.


> There must be situations in which it is not possible to determine
> whether or not a particular well- formed sentence describes a
> language.

For your definition, it is always possible to determine whether a
sentence describes a language. The problem is that the members of the
language do not satisfy the sentence in the usual sense.


- Tim
From: cplxphil on 21 Oct 2009 19:56
> The flaw is that just because P(i) is true iff i in K, it does not
> mean that P *describes* K: the definition involves provability (or
> rather lack of disprovability), not truth.
>

Ah, OK, I think I get it then. The issue is that if I try to phrase
the definition in terms of truth, the sentences don't describe
languages; and if I try to phrase the definition in terms of proof,
the members of the language don't actually satisfy the sentence. Is
that right?

Thanks again for helping me clear up my misconception.

-Phil
From: Tim Little on 22 Oct 2009 01:43
On 2009-10-21, cplxphil <cplxphil(a)gmail.com> wrote:
> Ah, OK, I think I get it then. The issue is that if I try to phrase
> the definition in terms of truth, the sentences don't describe
> languages

Almost: If you phrase the definition in terms of truth, sentences of
the formal system do describe languages. The problem is that there is
no predicate for "x satisfies P", so you can't recurse into
descriptions that are based on describability.


- Tim
First  |  Prev  | 
Pages: 1 2
Prev: Theorem 4.6. The class of box perfect graphs is in co-NP.
Next: [Port%d] \\.\HCD%d