Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence Class

  1. Nov 20, 2007 #1

    Let L be the language with = and one binary relation symbol E. Let epsilon be the class of all L-structures A such that E interpreted by A is an equivalence relation on |A|.

    K = { A in epsilon | E interpreted by A has infinitley many equivalence classes }.


    EC - There exists a sentance alpha such that the class K = mod(alpha)
    EC_delta - There exists a set of sentances sigma such that the class K = mod(sigma)


    a) Show epsilon is EC

    This is pretty easy, just list the 3 things it E needs to satisfy for it to be an equivalence relation.

    b) Show K is EC_delta

    Also pretty straightforward, take the sentance for epsilon and add on countably infinite sentances saying that there are n things such that <x_i,x_j> is not in E.

    c) Show K is not EC.

    We had a homework problem prior that proves this though I forgot how I proved it, and this is a midterm review so I would like to know how to prove it directly. Any suggestions would be greatly appreciated.

    We went over a theorem in class that said the follow where equivalent:

    1) A class K is EC
    2) A class K and its compliment K_2 are both EC_delta.

    Maybe it would be better to prove that the compliment of K ie: All structures that are finite and all infinite structures that do not have infinitely many equivalence classes is not EC_delta.

    We know that all finite structures is not EC_delta but I'm not sure how to show this for all finite structures AND all infinite structures without infinite equivalence classes.
    Last edited: Nov 20, 2007
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted