Results 1 to 4 of 4

Math Help - Fol 8

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 8

    Enderton 2.2.17

    Consider a language with equality whose only parameter (aside from \forall) is a two-place predicate symbol P. Show that if A is finite and A \equiv B ( A is elementary equivalent to B), A is isomorphic to B.
    Suggestion: Suppose the universe of A has size n. Make a single sentence \sigma of the form \exists v_1 \cdots \exists v_n \theta that describes A "completely". That is, on the one hand, \sigma must be true in A. And on the other hand, any model of \sigma must be exactly like (i.e., isomorphic to) A.

    ====================
    To get started, how do I make a single sentence \sigma of the form \exists v_1 \cdots \exists v_n \theta that describes A "completely"?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779

    Re: Fol 8

    First, say that all v_i's are distinct. Second, that they are the whole universe, i.e., any other v is equal to one of v_i's. Finally, for each pair (v_i, v_j) say whether P holds on (v_i, v_j).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 8

    Let R \subset |A| \times |A| be the binary relation to which two place predicate symbol P is assigned by A.

    Then,

    \sigma = \exists v_1 \exists v_2 \exists v_3 \ldots \exists v_n( (v_1 \neq v_2 \wedge v_1 \neq v_3 \wedge \ldots \wedge v_1 \neq v_n \wedge v_2 \neq v_3 \wedge \ldots \wedge v_2 \neq v_n \wedge \ldots \wedge  v_{n-1} \neq v_n) \wedge (\bigwedge_{(i,j) \in R} P(v_i, v_j) \wedge \bigwedge_{(i,j) \notin R} \neg P(v_i, v_j)).

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

    Without loss of generality, |A| = \{a_1, a_2, \ldots, a_n\}, and |B|=\{b_1, b_2, \ldots, b_n\}.

    The required isomorphism h: |A| \rightarrow |B| is given by h(a_i) = b_i for 1 \leq i \leq n satisfying

    (a_s, a_t) \in P^A iff (h(a_s), h(a_t) \in P^B.

    Is this correct?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    779

    Re: Fol 8

    Quote Originally Posted by logics View Post
    A \equiv B implies that if \models_A \sigma, then \models_B \sigma. Therefore, the cardinality of B is the same with A, since \sigma ought to be true in its model B by assumption.
    The fact that \models_B\sigma implies that the cardinality of B is at least n, but not necessarily exactly n.

    Quote Originally Posted by logics View Post
    Without loss of generality, |A| = \{a_1, a_2, \ldots, a_n\}, and |B|=\{b_1, b_2, \ldots, b_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 P(m,n) for some relation P on numbers, I could say, "without loss of generality, m\ge n." This means that

    (\forall m',n'.\,m'\ge n'\to P(m',n'))\to P(m,n)

    is easy to prove (for example, because P is symmetric and m\ge n\lor n\ge m holds), and so I only need to show m\ge n\to P(m,n).

    Quote Originally Posted by logics View Post
    The required isomorphism h: |A| \rightarrow |B| is given by h(a_i) = b_i for 1 \leq i \leq n satisfying

    (a_s, a_t) \in P^A iff (h(a_s), h(a_t) \in P^B.
    In the previous step, you have already given names a_i and b_i to the elements of |A| and |B|, and there is no reason to expect that h such that h(a_i)=b_i 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 \sigma=\exists v_1 \exists v_2 \exists v_3 \ldots \exists v_n\tau(v_1,\dots,v_n). We have \models_A\sigma and \models_B\sigma, i.e., \models_A\tau[(v_1,\dots,v_n|a_1,\dots,a_n)] and \models_B\tau[(v_1,\dots,v_n|b_1,\dots,b_n)] for some a_1,\dots,a_n\in|A| and b_1,\dots,b_n\in|B|. Then (a_i,a_j)\in P^A iff (b_i,b_j)\in P^B, so h such that h(a_i)=b_i for 1\le i\le n is an isomorphism.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum