Prev: Can Rosser 1936 be Extended? Alan Turing vs. Martin Davis et. al.
Next: What are Sets?
From: Rupert on 31 May 2010 18:30
On Jun 1, 12:25 am, Charlie-Boo <shymath...(a)gmail.com> wrote:
> On May 31, 4:11 am, Rupert <rupertmccal...(a)yahoo.com> wrote:
>
> > On May 30, 10:59 pm, Charlie-Boo <shymath...(a)gmail.com> wrote:
>
> > > The class of sets represented by PA wffs is the r.e. sets.  We can
> > > represent no more.
>
> > > If we add the (true unprovable) Godel sentence G (the wff that
> > > expresses “It is not provable on itself.” applied to itself) to the
> > > axioms of PA, which sets can we then represent?  Should that class
> > > change after adding G to the axioms?  It can’t contain a superclass of
> > > this class.
>
> > > C-B
>
> > Would you be able to clarify exactly what you mean by a set being
> > "representable" in a theory?
>
> http://groups.google.com/group/sci.logic/msg/e8946bb14f10372f?hl=en

If a wff with one free variable represents the set of numbers which,
when substituted into it, yield a true sentence, then the
representable sets are the arithmetically definable sets, not the
recursively enumerable ones. This is why I asked for clarification.

I will assume you want to say "provable in PA" rather than "true".
Then the representable sets are indeed the recursively enumerable
sets, but this situation does not change when we pass to any
consistent extension of PA.
From: George Greene on 31 May 2010 23:28
On May 31, 1:42 pm, Charlie-Boo <shymath...(a)gmail.com> wrote:
> On May 31, 12:19 pm, George Greene <gree...(a)email.unc.edu> wrote:
>
> > On May 30, 8:59 am, Charlie-Boo <shymath...(a)gmail.com> wrote:
>
> > > The class of sets represented by PA wffs is the r.e. sets.
>
> > This is not true.
>
> So is there an r.e. set that PA cannot represent, or is there a non-
> r.e. set that PA can represent?

PA *DOESN'T* "represent" sets.
As Rupert is already pointing out, "represent" IS NOT the verb you
WANT, here.
It is possible, however, in PA, to *Define* or *Describe* subsets of N
using 1-place
predicates. A reasonable restriction would be that the string stating
the predicate
would have to be finite. But PA has an axiom[schema, at first-
order]of induction,
so it is possible for the definition to have lots of clauses. Godel's
definition of the
"Proof" predicate is complicated like that. But you can eventually
use it to DESCRIBE
a set that is not r.e. (the set of all numbers that are godel-numbers
of sentences that
ARE NOT theorems of PA).
From: Aatu Koskensilta on 1 Jun 2010 15:45
Charlie-Boo <shymathguy(a)gmail.com> writes:

> If we add the (true unprovable) Godel sentence G (the wff that
> expresses “It is not provable on itself.” applied to itself) to the
> axioms of PA, which sets can we then represent? Should that class
> change after adding G to the axioms?

Why should the class change? You're being silly.

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Daryl McCullough on 1 Jun 2010 21:02
Aatu Koskensilta says...
>
>Charlie-Boo <shymathguy(a)gmail.com> writes:
>
>> If we add the (true unprovable) Godel sentence G (the wff that
>> expresses “It is not provable on itself.” applied to itself) to the
>> axioms of PA, which sets can we then represent? Should that class
>> change after adding G to the axioms?
>
>Why should the class change? You're being silly.

I don't remember the exact terminology, but there are several
different ways that a set can be associated with a formula:

1. A formula Phi(x) can define a set S of naturals in the
sense that S = { x in N | Phi(x) }

2. A formula Phi(x) can strongly represent a set S of naturals in the
sense that for each n,

(n in S) <-> (Phi(n) is provable)
(n not in S) <-> (~Phi(n) is provable)

3. A formula Phi(x) can weakly represent a set S of naturals in the
sense that for each n,

(n in S) <-> (Phi(n) is provable)

Since definitions 2 and 3 involve provability, it's conceivable
that adding more axioms might change what is representable.
In fact, adding more axioms to PA doesn't change what is representable,
but I wouldn't say that fact is completely trivial.

--
Daryl McCullough
Ithaca, NY

From: George Greene on 1 Jun 2010 22:51
On Jun 1, 9:02 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
> I don't remember the exact terminology, but there are several
> different ways that a set can be associated with a formula:

Exactly, and kudos to you for saying it THAT way, as OPPOSED to saying
"ways that a set can represent a formula".

For precisely the reasons you are about to assert "represent" is just
too
complicated/ambiguous a verb to be involved in a discussion with
anybody
as low-level as Herc.
>
> 1. A formula Phi(x) can define a set S of naturals in the
> sense that S = { x in N | Phi(x) }

This is THE ONLY way that matters for anybody at Herc's level,
and precisely as you chose, the CORRECT way to say this is that
the formula DEFINES the set, NOT that it represents it.

> In fact, adding more axioms to PA doesn't change what is representable,

That matters if and only if you care about what is representable,
which,
I repeat, GIVEN THAT IT'S A LOW-LEVEL DISCUSSION WITH someone who
needs instructinon IN THE BASICS, BEFORE ANY FINE POINTS become
relevant,
you should NOT care about.

Adding G as an axiom does not increase what is definable, but adding
~G does
augment the signature of the language if you actually introduce a term
for
the Godel number of the (formerly) false theorem.
There will come into existence whole new
terms&expressions denoting non-standard numbers; there were no such
terms
in the original language of PA.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Can Rosser 1936 be Extended? Alan Turing vs. Martin Davis et. al.
Next: What are Sets?