Philosophy Forums
Forums Links Articles Gallery Chat
Style:


Calendar Quick Links open HelpRegister
Philosophy Forums » Logic and Philosophy of Math » HELP w/ countable downward L-S theorem » HELP w/ countable downward L-S theorem

HELP w/ countable downward L-S theorem

printPrint


HELP w/ countable downward L-S theorem
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/20/08 - 11:25 PM:
Subject: HELP w/ countable downward L-S theorem 		quote post
#1
I need help understanding how to build a countable elementary substructure A of an uncountable structure B. I've been told that all I have to do is build a countable subset of B that is closed under the functions and has witnesses to all of the true existential statements of B. Is that right? If so it seems simple conceptually because the language is countable, so the existential statements must be countable too. All I need to do is add a witness for every one. Can anyone tell me the easiest correct way to do this?
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/21/08 - 02:55 PM:
quote post
#2
In order to add new witnesses, we are going to define a new theory T². First let T be a theory with a language L. The new language L² is obtained by adding a constant c for each sentence of the form "There exists x such that p(x)". So T² is the theory : T U {There exists x such that p(x)->p(c); with there exists x such that p(x) closed and with witnesses c}.

Now we can state that T² is conservative over T. This is where we are going to add the witnesses. Let There exists x such that p(x)->p(c) be a new axiom. Suppose we have a set of sentences A in which the witness c doesn't occur and suppose A, there exists x such that p(x)->p(c) |-v, with v a formula not containing c. We have to prove the conservativity. Show that we have A|-v.
A|-(There exists x such that p(x)->p(c))->v
A|-(There exists x such that p(x)->p(y)->v
A|-For all y((There exists x such that p(x)->p(y))->v)
A|-there exists y(There exists x such that p(x)->p(y))->v
A|-(There exists x such that p(x)->there exists y such that p(y))->v
|-(There exists x such that p(x)->there exists y such that p(y)
Hence A|- v

Now let T²|-v for v belonging to L. We have T U {x1,...,xn}|-v where xi are the axioms of the form (there exists x such that p(x))->p(c). Then T|-v. Show this by induction on n. For n=0, this is direct, there is no {x1,...,xn}. Let T U {x1,....,xn+1}|-v. Let T'= T U {x1,...,xn}, then T',xn+1|-v and we can apply the conservation result from above. Hence T U {x1,...,xn}|-v. By induction hypothesis T|-v.

A more general way to prove this theorem, is to use the skolem function for which the witnesses are just a special case.

Theorem: Let L be countable first order language and A an L-structure. Then A has a countable elementary substructure.

Proof: Let p be a formula in L and a1,...,an be elements of A. p(x1,...,xn) means that all free variables of p are in the xi's. Let p(y,x1,...,xn) be a formula in L. We define a skolem funtion for p: a skolem funtion for p is a function f: A^n->A such that wherenever a1,...,an are in A, then p(f(a1,...,an),a1,...,an) is true in A wherever there is some b such that p(b,a1,...,an) is true in A. Now we can clearly see that the case of the witnesses above is a special case of this one : the case of the witnesses is n=0 and f is a constant function.
For each formula p like this one we choose a skolem function f. if n=0, f is an element of A. Now, if g is a function in L, the interpretation of g in the model A is one of the skolem functions. Let p be the formula y=g(x1,...,xn). Then the interpretation of g in A is f.
Since L is countable, the set of skolem functions will be countable. Let T_0 the empty set and define by recursion T_k+1={f(a1,...,an), f is a skolem function and a1,...,an belong to T_k}.
By induction of k each of the T_k is countable and we have for all k, k a natural number, T_k included in T_k+1. Let T be the union of all the T_k's. Then T is countable, is a subset of the domain of A and is closed under the skolem functions. Then T is the domain of a substructure M of A(because it is closed under the skolem functions).
It remains only to show that M is an elementary substructure of A to finish the proof. This can be done by induction on the complexity of p.(p atomic, p a negation etc...).
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/21/08 - 04:31 PM:
quote post
#3
Thank, Beeboo. I have a few questions.

Let p(y,x1,...,xn) be a formula in L.


y is supposed to be bound, right? By an existential quantifier?

We define a skolem funtion for p: a skolem funtion for p is a function f: A^n->A such that wherenever a1,...,an are in A, then p(f(a1,...,an),a1,...,an) is true in A wherever there is some b such that p(b,a1,...,an) is true in A.


Do you mean that if (Ey)p(y,x1,...,xn)[s], then there is a function such that p(f(a1,...,an),a1,...,an)[s] where a1,...,an = s(x1,...,xn). s is the assignment function.

Now we can clearly see that the case of the witnesses above is a special case of this one : the case of the witnesses is n=0 and f is a constant function.


How would I write the formula to define the function if there are no FVs? For example, let the formula be (Ex)Px where x is the only variable in the formula. That would be P(f()), but I don't know what to put in the embedded parentheses.

Now, if g is a function in L, the interpretation of g in the model A is one of the skolem functions. Let p be the formula y=g(x1,...,xn). Then the interpretation of g in A is f.


Is y bound in p?

Let T_0 the empty set and define by recursion T_k+1={f(a1,...,an), f is a skolem function and a1,...,an belong to T_k}.


Doesn't the skolem function have to be written like you did it earlier in the post? How do I know what the formula is? What I mean is, shouldn't it be P(f(a1,...,an),a1,...,an) for every formula (Ey)Py?



Edited by Patrick R on 04/21/08 - 04:37 PM
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/21/08 - 05:46 PM:
quote post
#4
First, y is a free variable in p as well as x1,...,xn are free variables in p too. So the set of free variables of p is {y,x1,...,xn}.

In the case where n=O the formula "(There exists y such that p(y))->p(c)" is a special case of the skolem axiom :"For all x1,...xn[There exists y such that p(y,x1,...,xn)->p(x1,...,xn,f(x1,...,xn))]"(1). The sentence represented by (1) is called the skolem axiom. Indeed take n=O, you would only write "There exist y such that p(y)->p(c)" with c being the skolem function f. If the skolem function has zero arity then it is a constant (in this case it's c).

Remember, the skolem function is "f", it is not the formula p.

Edited by Beeboo on 04/21/08 - 05:59 PM
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/21/08 - 10:45 PM:
quote post
#5
I have an uncountable structure B and want to build a countable elementary substructure A. First, add the element designated by each constant in B to the empty set. Then add the functions, so that if f(a) in B = b, then f(a) in A = b.

I think all that's left are the skolem functions. If B l= ExPx and y1,...,yn are free in the formula, then B l= P((y1,...,yn),f(y1,...,yn)). If B l= ExPx and the formula is a sentence, then B l= P(a). Can you tell me specifically what I should add to A here? Is it just f(y1,...,yn) or (a) depending on the formula?

Edited by Patrick R on 04/21/08 - 11:35 PM
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/22/08 - 12:01 AM:
quote post
#6
That must be the way it works. If B l= ExPx, then A l= ExPx. If B l= ExPx then B l= P((y1,...,yn),f(y1,...,yn)). All of the skolem functions have been added to A, so f(y1,...,yn) must be there and since A is closed under the functions, f(y1,...,yn) = the same element as in B.

Now I know that the witness must be there, but I also have to show that Px is satisfied in A with f(y1,...,yn) subbed for x. This is the atomic case. The relations of A = the relations of B restricted to A, so since f(y1,...,yn) is in A and B l= P[x/f(y1,...,yn}] or B satisfies Px with f(y1,...,yn) substituted for x, A l= P[x/f(y1,...,yn}].

Is that right?
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/22/08 - 11:01 AM:
quote post
#7
I am not sure I am understanding you when you say "What should I add to A?" Why do you want to add something to A? Maybe I am overlooking something here...

Our problem here is to prove downward Lowenheim-Skolem. We are going to construct a countable structure, call it B out of our model A. This means that A has a countable elementary substructure. How can we built it? The idea is to construct a set (T) that is closed under the Skolem functions (this is the general case). Thankfully, the skolem functions are countable because our language L is countable. So the set T, closed under the Skolem functions, is countable and has a cardinality of at most aleph0. This set contains all the solutions of all the formulas of the type "There exists x such that p(x,a1,...,a1)"(for instance). That means that in T, you add all the solutions to the existential statements we have. Those solutions are exactly the Skolem functions (or the witnesses in the case n=0)




Edited by Beeboo on 04/22/08 - 11:46 AM
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/22/08 - 01:02 PM:
quote post
#8
In other words, one could prove that if we can find a witness in B for every existential formula true in A, then we have B is an elementary substructure of A.


1)(Tarski's Lemma) If B and A are L-structures with B a substructure in A,then B is an elementary substructure of A if for every L-formula p(x,y) and with a€A and b€B (€ means belongs to).
p(a,b) is true in A if and only if for some a' in T (T is the domain of B) we have p(a,a') true in B (1).
In order to show this, suppose the formula (1) holds then show that B is an elementary substructure of A(i.e every formula true in B is true in A). We can do this by using induction on the complexity of formulas

This gives us the tools to built the submodel B satisfying the conditions of the downward Lohenheim-Skolem. We take a subset R of the domain of the model B and close it by taking the witnesses (this is a direct consequence of the axiom of choice) that satisfy the existential statements true in A.

2)Theorem: If A is a L-structure and L a countable first order language. Than there exist a structure B such that B is an elementary substructure of B and B is countable.

Proof: For each L-formula p(x,y), define the skolem function f of p such that f:A^n--->A by : b€dom(A)^n then some b'€dom(A) such that p(b,b') is true in A (if such a b' exists). dom is "the domain of".
The Skolem functions are countable because the language is countable.

Now we're going to construct the model B such that its domain is closed under the skolem functions. Take an existential statement "There exists y such that p(x,y) and take a, a belonging to the domain of B. When we apply the skolem function to a, we get a witness for "There exists x such that p(a,x)". This means "There exists x such that p(a,x)" is true in A => p(a,f(a)) is true in A. By construction f(a) is in the domain of B and B satisfy the property of above in section 1). We have found the substructure B. Now let's take a subset of the domain of A, define recursively those subsets (let's call them N) : Ni={f(a), such that a belongs to Ni-1 and f a skolem function} we have Ni-1 included in Ni and take the domain of the model B to be the union of the Ni's. The domain of B is closed under the skolem function and is clearly countable.

I hope this is clearer and that I didn't do any mistakes.

Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/22/08 - 02:57 PM:
quote post
#9
Beeboo wrote:
I am not sure I am understanding you when you say "What should I add to A?" Why do you want to add something to A? Maybe I am overlooking something here...

Our problem here is to prove downward Lowenheim-Skolem. We are going to construct a countable structure, call it B out of our model A. This means that A has a countable elementary substructure. How can we built it? The idea is to construct a set (T) that is closed under the Skolem functions (this is the general case). Thankfully, the skolem functions are countable because our language L is countable. So the set T, closed under the Skolem functions, is countable and has a cardinality of at most aleph0. This set contains all the solutions of all the formulas of the type "There exists x such that p(x,a1,...,a1)"(for instance). That means that in T, you add all the solutions to the existential statements we have. Those solutions are exactly the Skolem functions (or the witnesses in the case n=0)




Sorry, all I meant was to add the skolem functions to A. That should be all it takes because I've constructed A to include the constants, A has the same interpretation of the relations restricted to A, it is closed under the functions, and A's domain is a subset of B. These are the substructure conditions. Tarski's criterion says that if A is a substructure of B and for every assignment s, B l= Exφ[s] if and only if for some a in A, A l= φ[s(x/a)], then A is an elementary structure of B. The skolem function is the some a in A.
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/22/08 - 03:26 PM:
quote post
#10
Patrick R wrote:


Sorry, all I meant was to add the skolem functions to A. That should be all it takes because I've constructed A to include the constants, A has the same interpretation of the relations restricted to A, it is closed under the functions, and A's domain is a subset of B. These are the substructure conditions. Tarski's criterion says that if A is a substructure of B and for every assignment s, B l= Exφ[s] if and only if for some a in A, A l= φ[s(x/a)], then A is an elementary structure of B. The skolem function is the some a in A.


Ah, I see. Thank you Patrick. Actually the domain of A is a subset of the domain of B in your case. I was confused because in my proof I had written the contrary. I have done my proof using the fact that the domain of B is a subset of the domain of A.

Your formulation of the Tarski criterion is true and it is true that you need to add all the skolem functions(or the witnesses in other words) in the domain of A because to show that A is an elementary substructure of B, we need to add all the skolem functions to the domain of A which are solutions to all the existential statements that are true in B, which is your original idea in your first post.
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/22/08 - 03:41 PM:
quote post
#11
And adding the skolem functions to A' (let's say now that A' is the domain of A, so we won't do any confusion between domain, model etc...) is easy. Take a subset of the domain of B. Call it S. Now define the S's inductively. We take S0:=S and we write Si+1:={f(b); b belonging to Si and f a Skolem function}.

Now let A':= USi (I use U for the Union symbol). Then A' is closed under the skolem function and A' is countable.

Now let's define the interpretation of relations, functions and constants in conformity with the structure B.
For predicate symbols of arity n we say: the interpretation of P in A= the interpretation of P in B intersection A'^n, A' being the domain of A.

For a function of arity r, for x belonging to A'^r, the interpretation of f in A for x =the interpretation of f in B for x

the constants symbols have the same interpretation in A and in B.

We now defined the elementary substructure A.
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/23/08 - 02:18 AM:
quote post
#12
I’m going to go through the proof in my own words. Please read it and tell me if it is good.

B is the uncountable structure and A is the countable elementary substructure. The domains will be B’ and A’. What I need to do is construct A so that 1.) A’ is a subset of B’, 2.) A is closed under the functions of B, 3.) for every relation R in B, R(a1,….,an) in A = R(a1,….,an) in B provided that (a1,….,an) ε A’, 4.) every constant c in B = c in A. This will make A a substructure of B.

To start building A, pick out a countable subset of B, add all the constants, close under the functions and relations. Call this substructure A1 and its domain A1’. I should now be able to prove that for any assignment s : vars -> A1’, B l= 0 <-> A1 l= 0 assuming that 0 has no quantifiers. I will do the atomic case for R(x1,….,xn)[s] where s is an assignment function to A1’, or the domain of A1. I will write R/B for R in the structure B, etc.

A1 l= R(x1,….,xn)[s] <-> (x1,….,xn)[s] ε R/A1
…………………......……<-> (x1,….,xn)[s] ε R/B
………………………......<-> B l= R(x1,….,xn)[s]

The second step is immediate because of the interpretations of relations. The relations for A1 are the same as the relations for B, except they’re restricted to A1. s is an assignment function to A1’, so (x1,….,xn)[s] ε A1’. Therefore the relation is the same for those elements as in B. I won’t do the other cases.

I still need to add witnesses for the existential statements true in B.

B l= Exφ <-> B l= φ(y1,…,yn,f(y1,...,yn))

Add all of the skolem functions f to A1. This makes it an elementary substructure of B. I will call it A from now on.

Once again make s an assignment function to A’. I will prove B l= Exφ[s] <-> for some a ε A’, A l= φ[s(x/a)]

B l= Exφ[s] <-> B l= φ(y1,…,yn,f(y1,...,yn))[s]
………...... …<-> B l= φ[s(x/f(y1,...,yn)]
f(y1,...,yn) ε A’
…………........…<-> A l= φ[s(x/f(y1,...,yn)]

The first line is just the skolem axiom. Since the function is a choice function that picks out a witness that makes φ true in B, the formula must be true with that function substituted for x. A is closed under the functions and relations of B, so φ[s(x/f(y1,...,yn)] must be true in A too. For example, if φ is an n+1 place relation R, we can say that f(y1,...,yn) ε A’, so it must be in the relation R in A as in B.

Please look it over carefully and tell me if it is all right.

Edited by Patrick R on 04/23/08 - 03:06 AM
Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81
Posted 04/23/08 - 01:51 PM:
quote post
#13
Patrick R wrote:
I’m going to go through the proof in my own words. Please read it and tell me if it is good.

B is the uncountable structure and A is the countable elementary substructure. The domains will be B’ and A’. What I need to do is construct A so that 1.) A’ is a subset of B’, 2.) A is closed under the functions of B, 3.) for every relation R in B, R(a1,….,an) in A = R(a1,….,an) in B provided that (a1,….,an) ε A’, 4.) every constant c in B = c in A. This will make A a substructure of B.

To start building A, pick out a countable subset of B, add all the constants, close under the functions and relations. Call this substructure A1 and its domain A1’. I should now be able to prove that for any assignment s : vars -> A1’, B l= 0 <-> A1 l= 0 assuming that 0 has no quantifiers. I will do the atomic case for R(x1,….,xn)[s] where s is an assignment function to A1’, or the domain of A1. I will write R/B for R in the structure B, etc.

A1 l= R(x1,….,xn)[s] <-> (x1,….,xn)[s] ε R/A1
…………………......……<-> (x1,….,xn)[s] ε R/B
………………………......<-> B l= R(x1,….,xn)[s]

The second step is immediate because of the interpretations of relations. The relations for A1 are the same as the relations for B, except they’re restricted to A1. s is an assignment function to A1’, so (x1,….,xn)[s] ε A1’. Therefore the relation is the same for those elements as in B. I won’t do the other cases.


Nothing guarantees here that the domain of A is countable and nothing guarantees that it will be closed under the skolem functions. We need to construct it. This step you outlined here will come after we constructed the domain of A by adding the skolem functions in it and closing it.



Patrick R wrote:
I still need to add witnesses for the existential statements true in B.

B l= Exφ <-> B l= φ(y1,…,yn,f(y1,...,yn))

Add all of the skolem functions f to A1. This makes it an elementary substructure of B. I will call it A from now on.


This is not what will make A be an elementary substructure of B. Adding the skolem function to the domain of A and closing the domain of A under the skolem functions makes this domain countable because the skolem functions are countable and this is due to the fact that the language is countable.

What will make A be an elementary substructure of B is the fact that for a1,...,an in domain of A, p(a1,...,an) is true in A if and only if p(a1,...,an) is true in B. And this is proved by induction on the complexity of p

Patrick R wrote:
Once again make s an assignment function to A’. I will prove B l= Exφ[s] <-> for some a ε A’, A l= φ[s(x/a)]


On the other hand, this fact will make A be an elementary substructure of B

Patrick R wrote:

B l= Exφ[s] <-> B l= φ(y1,…,yn,f(y1,...,yn))[s]
………...... …<-> B l= φ[s(x/f(y1,...,yn)]
f(y1,...,yn) ε A’
…………........…<-> A l= φ[s(x/f(y1,...,yn)]

The first line is just the skolem axiom. Since the function is a choice function that picks out a witness that makes φ true in B, the formula must be true with that function substituted for x. A is closed under the functions and relations of B, so φ[s(x/f(y1,...,yn)] must be true in A too. For example, if φ is an n+1 place relation R, we can say that f(y1,...,yn) ε A’, so it must be in the relation R in A as in B.

Please look it over carefully and tell me if it is all right.



I suggest you do the two steps in this order:
1)The domain of A has to be closed under the skolem functions. You first define the skolem functions, their domain of definition and their range. Now we construct A. Given an existential statement and "a" belonging to the domain of A, the skolem function gives us a witness (for a formula p, "there exists x such that p(a,x)" is true in B entails that p(a,f(a)) is true in B) and we have f(a) belonging to A(by construction, the skolem functions take their arguments from some set T^n and range over T). A will meet the requirement of the Tarski's criterion you've stated. A will be an elementary substructure then.

2)Take some subset S of the domain of A. Construct it in such a way that it is closed under the skolem function. we do this recursively (like above) and take the union of all Si's (defined recursively) to be the domain of A

It remains only to give interpretations of relations,functions and constants that matches the structure B.


Edited by Beeboo on 04/23/08 - 02:04 PM
Patrick R
Initiate

Usergroup: Members
Joined: Apr 20, 2008
Total Topics: 1
Total Posts: 7
Posted 04/23/08 - 06:24 PM:
quote post
#14
Nothing guarantees here that the domain of A is countable and nothing guarantees that it will be closed under the skolem functions. We need to construct it.


I don't understand what you mean that it's not guaranteed that the domain is countable. The uncountable set B' has a countable subset. I added the constants and closed under the functions and relations. None of that could make it uncountable.

This step you outlined here will come after we constructed the domain of A by adding the skolem functions in it and closing it.


Why do I have to do it that way? A1 is a substructure of B, so for any assignment s to A1' and quantifier free φ, B l= φ[s] <-> A1 l= φ[s]. I can do this because it's a substructure. I only need it to be elementary for the quantified formulas.


This is not what will make A be an elementary substructure of B. Adding the skolem function to the domain of A and closing the domain of A under the skolem functions makes this domain countable because the skolem functions are countable and this is due to the fact that the language is countable.


Yes, I neglected to say that its closed under the skolem functions. Add that and A1 becomes the countable elementary substructure, A.

1)The domain of A has to be closed under the skolem functions. You first define the skolem functions, their domain of definition and their range. Now we construct A. Given an existential statement and "a" belonging to the domain of A, the skolem function gives us a witness (for a formula p, "there exists x such that p(a,x)" is true in B entails that p(a,f(a)) is true in B) and we have f(a) belonging to A(by construction, the skolem functions take their arguments from some set T^n and range over T). A will meet the requirement of the Tarski's criterion you've stated. A will be an elementary substructure then.


I won't ever have to worry about the element a failing to belong to the domain of A. The Skolem function f[y1,....,yn)[s] has to pick out something in the domain of A' because s is a variable assignment to A'.

2)Take some subset S of the domain of A. Construct it in such a way that it is closed under the skolem function. we do this recursively (like above) and take the union of all Si's (defined recursively) to be the domain of A


Do you mean Si + 1 = Si ∪ {f(y1,...,yn)} where f is some skolem function?


7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 154
Posted 04/25/08 - 04:08 AM:
quote post
#15
B l= Exφ[s] <-> B l= φ(y1,…,yn,f(y1,...,yn))[s]
………...... …<-> B l= φ[s(x/f(y1,...,yn)]
f(y1,...,yn) ε A’
…………........…<-> A l= φ[s(x/f(y1,...,yn)]


That is basically right. Remember that a formulation of Tarski's criterion is: if A is a substructure of B, and for all Exφ and A-assignments s, B l= Exφ[s] <-> for some a in A', B l= φ[s(x/a)], then A is an elementary substructure of B. Well, f/B(a1...an) = f/A(a1...an), provided that a1...an are in A'. So as you said, s(y1...yn) is in A' because s is an assignment to A'. Since the substructure is closed under the skolem functions f/A(y1...yn)[s] = f/B(y1...n)[s]. Hence, f/A(y1...yn) can be subbed into the first formula(the skolem axiom) for f/B(y1...yn). There is your some a in A', as specified by the Criterion.
Download thread as


You don't have permission to post.

Please login or register.

Contact the Administration

Powered by WSN Forum

4 total queries
This page was created in 0.16 seconds
Memory used: 2556904 bytes
Server Status: time since last reboot is 111 days, 10:13, load average: 1.35, 1.58, 1.44