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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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

Similar Threads - Equivalence Class Date
Equivalence classes of proper classes Jul 15, 2014
Quotient set of equivalence class in de Rham cohomology Jun 5, 2012
Equivalence classes Jun 1, 2012
Equivalence Classes Explaination Mar 30, 2012
Equivalence class help Mar 21, 2012