Löwenheim-Skolem and Induction on complexity: Philosophy Forums

Philosophy Forums » Logic and Philosophy of Math » Logic Homework » Löwenheim-Skolem and Induction on complexity » Löwenheim-Skolem and Induction on complexity

Löwenheim-Skolem and Induction on complexity
I'm not sure what the induction on complexity would amount to in my proof.

Löwenheim-Skolem and Induction on complexity

dense
Initiate

Usergroup: Members
Joined: Oct 12, 2009

Total Topics: 1
Total Posts: 1

Posted 10/12/09 - 12:38 AM:
Subject: Löwenheim-Skolem and Induction on complexity

Hi. My first post.

So I have to prove the Löwenheim-Skolem theorem in class and have some problems understanding what to do. I will write down what I've gotten to this far, and then maybe someone can help.

Let A be a sentence on skolemform in a language L satisfied by an interpretation T with an uncountable domain D. For simplicity let's assume that A has the form ∀x∃yC(x,y).

Let a1 be included in D, then there exist a b1 such that C(a1',b1') is true. Here a1' is the name of a1, and b1' the name of b1. In the same way when an is in D, there will exist a bm such that C(an',bm') is true.

Let D*={a1',...,an',b1',...,bm') for a new interpretation T* and make it such that:

For every n-placed predicate R:

Rⁿ_T*=Rⁿ_T∩D*ⁿ

For every n-placed function f:

fⁿ_T*=fⁿ_T

_{and for every constant} and invidual parameter t:

t_T*∈D*

---

Ok so a few questions. If there are funtionsymbols in A, then for every object d in the domain D I will get a new object f(d) that I will have to include in D*? But I will include it as f(d)' ?

Now I think that the result of all this will be a domain D* which is countable, "closed under f" and such that the restriction of T to T* will make A true. Supposedly I should show this by "induction on complexity". But I'm not really sure what this amounts to. I guess I'm supposed to show the different ways A could be like, and show that T* will make all thouse ways true? But in my simplified case, isn't sorta the complexity left to the case with all-quantification? I'm a bit confused.

Hopefullt someone can give me a hand. Thanks in advance!

Sorry, you don't have permission to post. Log in, or register if you haven't yet.