Fol 14

**logics** · November 17th 2011, 04:45 AM

Enderton 2.2.25

Consider a fixed structure $A$ . Expand the language by adding a new constant symbol $c_a$ for each $a \in |A|$ . Let $A^+$ be the structure for this expanded language that agrees with $A$ on the original parameters and that assigns to $c_a$ the point $a$ . A relation $R$ on $|A|$ is said to be definable from points in $A$ iff $R$ is definable in $A^+$ . (This differs from ordinary definability only in that we now have parameters in the language for members of $|A|$ .) Let $K=(\mathbb{Re}; <, +, \cdot)$ .

(a) Show that if $X$ is a subset of $\mathbb{Re}$ consisting of the union of finitely many intervals, then $X$ is definable points in $K$ .

(b) Assume that $A \equiv K$ . Show that any subset of $|A|$ that is non-empty, bounded (in the ordering $<^A$ ), and definable from points in $A$ has a least upper bound in $|A|$ .

(*) $A \equiv K$ iff for any sentence $\sigma$ , $\models_A \sigma \Leftrightarrow \models_K\sigma$ .

============================
To get started,

Why $c_a$ and $A^+$ are introduced in this problem?
How an open set and a closed set are defined by formulas in $A^+$ ?

Thanks.

**emakarov** · November 17th 2011, 09:40 AM

Originally Posted by logics

Why $c_a$ and $A^+$ are introduced in this problem?

Usually they don't ask such questions in mathematics. Every mathematical contribution starts with "Consider such and such objects." If the first question is, "Why are we supposed to consider them?", we would not get far.

Originally Posted by logics

How an open set and a closed set are defined by formulas in $A^+$ ?

Why do you need this? The problem does not mention open and closed sets (in the sense of topology). Do you mean open and closed intervals?

**logics** · November 17th 2011, 03:41 PM

The set of open intervals is a basis for the standard topology on $\mathbb{Re}$ , so I assumed the standard topology on $\mathbb{Re}$ . What I meant was that an open set in (the standard topology) $\mathbb{Re}$ is the union of open intervals in $\mathbb{Re}$ .

However, you are correct in the sense that an open set is not defined in this problem.

**emakarov** · November 17th 2011, 03:50 PM

I think (a) is simple. For (b), I am not sure what $A\equiv B$ means and why B is not mentioned in the rest of the question. Also, the text before the questions defines a specific structure K and it is not clear how A and B are related to K.

**logics** · November 17th 2011, 03:58 PM

Originally Posted by emakarov

Usually they don't ask such questions in mathematics. Every mathematical contribution starts with "Consider such and such objects." If the first question is, "Why are we supposed to consider them?", we would not get far.

Why do you need this? The problem does not mention open and closed sets (in the sense of topology). Do you mean open and closed intervals?

We are only considering "finitely many intervals" instead of "arbitrary many intervals". It seems like I have to define an open and closed interval in $A^+$ first.
The question is how do we define an open and closed interval in $A^+$ ?

**logics** · November 17th 2011, 04:05 PM

Originally Posted by emakarov

I think (a) is simple. For (b), I am not sure what $A\equiv B$ means and why B is not mentioned in the rest of the question. Also, the text before the questions defines a specific structure K and it is not clear how A and B are related to K.

Sorry, I will edit the typo in the problem, and give the definition.

**emakarov** · November 17th 2011, 04:12 PM

Originally Posted by logics

The question is how do we define an open and closed interval in $A^+$ ?

The same as anywhere. An for two real numbers $a$ , $b$ , the interval $(a, b]$ is definable from points in $K$ using the formula $a<x\land (x<b\lor x=b)$ . We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $K$ . A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.

**logics** · November 17th 2011, 04:22 PM

Originally Posted by emakarov

The same as anywhere. An for two real numbers $a$ , $b$ , the interval $(a, b]$ is definable from points in $K$ using the formula $a<x\land (x<b\lor x=b)$ . We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $K$ . A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.

Why do we consider this definition,

"A relation $R$ on $|A|$ is said to be definable from points in $A$ iff $R$ is definable in $A^+$ ".

Why don't we just define in $A$ rather than $A^+$ .

It seems like I am missing some fundamental concepts.

**emakarov** · November 17th 2011, 04:41 PM

Using elements of the structure domain in formulas can allow building more expressive formulas. A structure has a limited vocabulary and sometimes it does not have the means to refer to a particular domain element. This Wikipedia page refers to relations definable from points in A as relations definable in A with parameters. For example, in $(\mathbb{N},<)$ without parameters every singleton can be defined by a formula, while in $(\mathbb{Z},<)$ the only definable sets without parameters are $\emptyset$ and $\mathbb{Z}$ .

**logics** · November 18th 2011, 12:14 AM

Originally Posted by emakarov

The same as anywhere. An for two real numbers $a$ , $b$ , the interval $(a, b]$ is definable from points in $K$ using the formula $a<x\land (x<b\lor x=b)$ . We can basically use all real numbers (or names for them) in formulas, so every interval is definable from points in $K$ . A finite union of intervals can be expressed as a disjunction. To represent an infinite union may be a problem.

Thank you for your help. Now I am getting to understand why parameters are needed in this problem. My another question is

Since constant symbols are not defined in $K$ , doesn't $(a, b]$ have to be defined in $K^+$ using

$c_a<x\land (x<c_b\lor x=c_b)$ ?

**emakarov** · November 18th 2011, 03:29 AM

Originally Posted by logics

Since constant symbols are not defined in $K$ , doesn't $(a, b]$ have to be defined in $K^+$ using

$c_a<x\land (x<c_b\lor x=c_b)$ ?

Yes, $(a, b]$ is definable in $K^+$ , which, by definition, is the same thing as definable from points in K. You are right that instead of actual real numbers $a$ , $b$ one has to use their constant symbols $c_a$ , $c_b$ in formulas. After a while, though, it is convenient to leave out the bijection $a\mapsto c_a$ and to pretend to write numbers themselves.

Thread: Fol 14

LinkBack

Thread Tools

Display

Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Re: Fol 14

Search Tags