First, say that all 's are distinct. Second, that they are the whole universe, i.e., any other is equal to one of 's. Finally, for each pair say whether holds on .

Results 1 to 4 of 4

- Nov 11th 2011, 06:28 AM #1

- Joined
- Nov 2011
- Posts
- 59

## Fol 8

Enderton 2.2.17

Consider a language with equality whose only parameter (aside from ) is a two-place predicate symbol . Show that if is finite and ( is elementary equivalent to ), is isomorphic to .

Suggestion: Suppose the universe of has size . Make a single sentence of the form that describes "completely". That is, on the one hand, must be true in . And on the other hand, any model of must be exactly like (i.e., isomorphic to) .

====================

To get started, how do I make a single sentence of the form that describes "completely"?

Thanks.

- Nov 11th 2011, 07:38 AM #2

- Joined
- Oct 2009
- Posts
- 5,573
- Thanks
- 789

- Nov 12th 2011, 07:18 AM #3

- Joined
- Nov 2011
- Posts
- 59

## Re: Fol 8

Let be the binary relation to which two place predicate symbol is assigned by .

Then,

.

implies that if , then . Therefore, the cardinality of B is the same with A, since ought to be true in its model B by assumption.

Without loss of generality, , and .

The required isomorphism is given by for satisfying

iff .

Is this correct?

Thank you.

- Nov 12th 2011, 08:41 AM #4

- Joined
- Oct 2009
- Posts
- 5,573
- Thanks
- 789

## Re: Fol 8

The fact that implies that the cardinality of B is at least n, but not necessarily exactly n.

Strictly speaking, the phrase "without loss of generality" is used to claim a proposition, not to make a definition or introduce a notation. For example, when I am proving for some relation on numbers, I could say, "without loss of generality, ." This means that

is easy to prove (for example, because is symmetric and holds), and so I only need to show .

In the previous step, you have already given names and to the elements of |A| and |B|, and there is no reason to expect that h such that is an isomorphism. Also, when you say, "consider x satisfying P(x)" for some property P, you need to explain why such x exists. The idea is clear, of course, but I would say as follows.

Let's denote . We have and , i.e., and for some and . Then iff , so h such that for is an isomorphism.