0

and does this mean there cant be sets of things I have not defined equivalency for?

This is maybe a weird question and maybe not even a meaningful one, my understanding of sets and such is not complete, but it seems like "two sets are the same if they contain the same elements" implies that for all elements in both sets I can decide if they are equivalent or not. Specifically I thought of this question because I think in computer science I came across sets of Turing machines for which equivalency in general can not be determined because it would solve the halting problem (if equivalency is defined as same input leads to same output considering halting and not halting). Is such a set then ill-defined and not actually a set?

Andrés E. Caicedo
  • 79,201
user156192
  • 1
  • 1
  • It seems that the weak link in your grasp is how logic works. In particular "have the same elements" doesn't mean we go over them one by one. It means that if we can prove $a\neq b$, then we can prove there is an element of one which is not an element of the other. Then we can instantiate this existential quantifier to have an actual element. – Asaf Karagila Jun 09 '14 at 22:17
  • To "clarify" -- there are "computational" notions of equivalence like you (user156192) have described. But "mathematics" typically deals with the first order logic, which is strictly stronger than an "intuitionistic" or "constructive" logic. The other logics are studied as well, but if you're "doing math" (with no further qualifiers), you're using the first order logic. – nomen Jun 09 '14 at 22:19
  • 1
    It also seems that you are conflating "equivalence" with "equality". – mweiss Jun 10 '14 at 02:02

1 Answers1

0

Equivalence relations are mainly used to partition a given set, not normally a relation between sets.

kdaftari
  • 11
  • 1