 |
|
| Science Forum Index » Logic Forum » AC and Completeness... |
|
Page 1 of 1 |
|
| Author |
Message |
| Daryl McCullough... |
 Posted: Thu Nov 05, 2009 11:26 am |
|
|
|
Guest
|
Does the completeness theorem require the axiom of choice?
It seems to me that for any theory T, we can beef it up to
a new theory T' by adding choice function *symbols* as follows:
For each formula Phi(x_1,x_2, ..., x_n, y), add a new
function symbol f, and a new axiom
Phi(x_1,x_2, ..., x_n, y) -> Phi(x_1,x_2, ..., x_n, f(x_1,x_2,...x_n))
It seems to me that if we restrict whatever axiom schemas
there are in T so that in T' the schemas only apply to formulas
that do *not* involve the new skolem function symbols (so for
example, in ZF, replacement and separation would not necessarily
hold for formulas involving the new function symbols), then T'
will be a conservative extension of T. T' would not prove any
statements in the original language that were not already provable
in T.
However, if we use Godel's completeness theorem to come up with
a model for T', then we have to come up with a function (as a
set of ordered pairs) for each function symbol in T', which means
that we need the choice functions. So does that mean that without
the axiom of choice, we can't necessarily say that every consistent
theory has a model?
--
Daryl McCullough
Ithaca, NY |
|
|
| Back to top |
|
|
|
| Alan Smaill... |
| Posted: Thu Nov 05, 2009 12:42 pm |
|
|
|
Guest
|
stevendaryl3016 at (no spam) yahoo.com (Daryl McCullough) writes:
[quote]Does the completeness theorem require the axiom of choice?
It seems to me that for any theory T, we can beef it up to
a new theory T' by adding choice function *symbols* as follows:
For each formula Phi(x_1,x_2, ..., x_n, y), add a new
function symbol f, and a new axiom
Phi(x_1,x_2, ..., x_n, y) -> Phi(x_1,x_2, ..., x_n, f(x_1,x_2,...x_n))
It seems to me that if we restrict whatever axiom schemas
there are in T so that in T' the schemas only apply to formulas
that do *not* involve the new skolem function symbols (so for
example, in ZF, replacement and separation would not necessarily
hold for formulas involving the new function symbols), then T'
will be a conservative extension of T. T' would not prove any
statements in the original language that were not already provable
in T.
However, if we use Godel's completeness theorem to come up with
a model for T', then we have to come up with a function (as a
set of ordered pairs) for each function symbol in T', which means
that we need the choice functions. So does that mean that without
the axiom of choice, we can't necessarily say that every consistent
theory has a model?
[/quote]
Not if the language of the theory is countable, completeness
there doesn't need anything fancy.
I suppose that not all models for T are got from models for T'
by ignoring the skolem functions, though.
[quote]--
Daryl McCullough
Ithaca, NY
[/quote]
--
Alan Smaill |
|
|
| Back to top |
|
|
|
| Robert E. Beaudoin... |
| Posted: Thu Nov 05, 2009 5:41 pm |
|
|
|
Guest
|
Alan Smaill wrote:
[quote]stevendaryl3016 at (no spam) yahoo.com (Daryl McCullough) writes:
Does the completeness theorem require the axiom of choice?
It seems to me that for any theory T, we can beef it up to
a new theory T' by adding choice function *symbols* as follows:
For each formula Phi(x_1,x_2, ..., x_n, y), add a new
function symbol f, and a new axiom
Phi(x_1,x_2, ..., x_n, y) -> Phi(x_1,x_2, ..., x_n, f(x_1,x_2,...x_n))
It seems to me that if we restrict whatever axiom schemas
there are in T so that in T' the schemas only apply to formulas
that do *not* involve the new skolem function symbols (so for
example, in ZF, replacement and separation would not necessarily
hold for formulas involving the new function symbols), then T'
will be a conservative extension of T. T' would not prove any
statements in the original language that were not already provable
in T.
However, if we use Godel's completeness theorem to come up with
a model for T', then we have to come up with a function (as a
set of ordered pairs) for each function symbol in T', which means
that we need the choice functions. So does that mean that without
the axiom of choice, we can't necessarily say that every consistent
theory has a model?
Not if the language of the theory is countable, completeness
there doesn't need anything fancy.
I suppose that not all models for T are got from models for T'
by ignoring the skolem functions, though.
--
Daryl McCullough
Ithaca, NY
[/quote]
For uncountable languages the completeness theorem cannot be proved in
(e.g.) ZF. For instance, it's well-known that the completeness theorem
for uncountable languages in propositional logic is enough to show that
every proper filter on a set X extends to an ultrafilter on X. (If F is
a filter on X, consider the propositional language with an atomic
proposition P_a for every subset a of X, and the theory T with axioms
P_a for each a in F, P_a -> P_b for a a subset of b, and
P_a -> (P_b -> P_c) for c equal to the intersection of a and b. T is
consistent because F is a filter, and if T' is a complete extension of T
then the collection of all a for which T' |= P_a will be an ultrafilter
extending F.) Conversely, over ZF the ultrafilter theorem implies the
completeness theorem.
Robert E. Beaudoin |
|
|
| Back to top |
|
|
|
| David C. Ullrich... |
| Posted: Fri Nov 06, 2009 7:37 am |
|
|
|
Guest
|
On 05 Nov 2009 17:42:00 +0000, Alan Smaill <smaill at (no spam) SPAMinf.ed.ac.uk>
wrote:
[quote]stevendaryl3016 at (no spam) yahoo.com (Daryl McCullough) writes:
Does the completeness theorem require the axiom of choice?
It seems to me that for any theory T, we can beef it up to
a new theory T' by adding choice function *symbols* as follows:
For each formula Phi(x_1,x_2, ..., x_n, y), add a new
function symbol f, and a new axiom
Phi(x_1,x_2, ..., x_n, y) -> Phi(x_1,x_2, ..., x_n, f(x_1,x_2,...x_n))
It seems to me that if we restrict whatever axiom schemas
there are in T so that in T' the schemas only apply to formulas
that do *not* involve the new skolem function symbols (so for
example, in ZF, replacement and separation would not necessarily
hold for formulas involving the new function symbols), then T'
will be a conservative extension of T. T' would not prove any
statements in the original language that were not already provable
in T.
However, if we use Godel's completeness theorem to come up with
a model for T', then we have to come up with a function (as a
set of ordered pairs) for each function symbol in T', which means
that we need the choice functions. So does that mean that without
the axiom of choice, we can't necessarily say that every consistent
theory has a model?
Not if the language of the theory is countable, completeness
there doesn't need anything fancy.
[/quote]
In particular (taking a guess at what inspired the question)
not for the language of ZF.
[quote]I suppose that not all models for T are got from models for T'
by ignoring the skolem functions, though.
--
Daryl McCullough
Ithaca, NY
[/quote]
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.) |
|
|
| Back to top |
|
|
|
| LauLuna... |
| Posted: Fri Nov 06, 2009 9:33 am |
|
|
|
Guest
|
On Nov 5, 5:26 pm, stevendaryl3... at (no spam) yahoo.com (Daryl McCullough) wrote:
[quote]Does the completeness theorem require the axiom of choice?
It seems to me that for any theory T, we can beef it up to
a new theory T' by adding choice function *symbols* as follows:
For each formula Phi(x_1,x_2, ..., x_n, y), add a new
function symbol f, and a new axiom
Phi(x_1,x_2, ..., x_n, y) -> Phi(x_1,x_2, ..., x_n, f(x_1,x_2,...x_n))
It seems to me that if we restrict whatever axiom schemas
there are in T so that in T' the schemas only apply to formulas
that do *not* involve the new skolem function symbols (so for
example, in ZF, replacement and separation would not necessarily
hold for formulas involving the new function symbols), then T'
will be a conservative extension of T. T' would not prove any
statements in the original language that were not already provable
in T.
However, if we use Godel's completeness theorem to come up with
a model for T', then we have to come up with a function (as a
set of ordered pairs) for each function symbol in T', which means
that we need the choice functions. So does that mean that without
the axiom of choice, we can't necessarily say that every consistent
theory has a model?
--
Daryl McCullough
Ithaca, NY
[/quote]
I'm not sure I understand your point but it seems interesting.
I'd say that the possibility of adding your axiom implies this:
any model M of a theory T can be extended to a model M' s.t. for every
n+1-tuple <x1...xn+1> that is a member of a relation R in M, there is
a function f in M' s.t. <x1...xn, f(x1...xn)> is in R.
Is that right?
For all I see, this implies at most that the n+1-th term of any n+1-
tuple can be expressed as a function of the n first terms in the
tuple.
Surely, Choice implies the existence of all the required functions;
but I can't see why the existence of all such functions should imply
Choice. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Dec 05, 2009 10:13 pm
|
|