Re: Request for clarification of what is a non first-order definable set.

On 24 Jan 2007 10:01:29 -0800, "Scott" <ToaTerra@xxxxxxxxx> wrote:

Hi:

I recently put together a proof that states for every predicate p(x)
there is a set { x : p(x) }. Thus, a set of predicates P defines a set
of sets S. A reviewer made a comment:

"If we have a set S why must it be definable? That is, why does P
exist? There are sets which are not first-order definable."

Various people have explained why this is - in the set
theory we use it's simply not true that every set is
definable.

In fact it's worse than that. If you have some universal set
in mind that you're not telling us about, for example if
by {x : p(x)} you mean the set of natural numbers x such
that p(x) holds, then fine. But if there's nothing you
haven't told us about then it's simply not true that
every predicate defines a set!

For example, let p(x) be the predicate "x is not an element of
x". Then there can be no such thing as {x : p(x)}. Proof:
Say S = {x : p(x)}. Now either S is an element of S or S is
not an element of S. But if S _is_ an element of S then
the definition of S shows that S is _not_ an element of S.
And if S is _not_ an element of S then the definition of
S shows that S _is_ an element of S. Contradiction.

I am unclear on how there can be sets which are not first-order
definable when the definition of a set requires a predicate. Can
someone provide an explaination or provide an example? Your help would
be appreciated. Thanks.

Scott


************************

David C. Ullrich
.

Relevant Pages

  • Request for clarification of what is a non first-order definable set.
    ... I recently put together a proof that states for every predicate p ... I am unclear on how there can be sets which are not first-order ... someone provide an explaination or provide an example? ...
    (sci.logic)
  • Re: How much intelligence?
    ... operations needed for the processing of logical statements with truth values. ... tautological mechanics and I see a lot of confusion using established ... cause any contradiction that didn't already exist in x. ... predicate or a truth value, the and'ing of them doesn't produce a predicate ...
    (comp.ai.philosophy)
  • Re: atomic
    ... Joe {Jack, Jill} ... As far as the predicate is concerned, this might be seen as contradictory because if Bob has no children, he can't be a father. ... But similar relations seem possible without the second contradiction, depending on the predicate, eg., F has lived with a woman who was mother to the children. ...
    (comp.databases.theory)
  • Re: Question about proof by contradiction
    ... not containing X results in a contradiction, X must contain itself, ... contain X because then X does not satisfy the predicate defining X. ... does follow from your axioms, because the system you construct is ... If it is labeled as such in the specification of your axiomatic system. ...
    (sci.math)
  • Re: Question regard implication and being a theorem of FOL.
    ... Let P be a predicate of 0-arity and let Q be a different predicate of ... by applying completeness to 7a) ... by applying soundness to 7b) ... be proved from a contradiction. ...
    (sci.logic)