CODEWITHSUNDEEP
javamathset-theory
21kondav
21kondav

Reputation: 19

Mathematical Predicate Equality in Java

I am writing a class PredicateSet in Java to model the mathematical definition of a countable set using predicates to accept or reject membership. But I am having trouble coming up with an equals method. I want two PredicateSets to be equal if the membership test returns the same value for any Object (not necessarily an object already in both sets). For example if we have two sets of objects defined by 1=1 and 2 = 2 respectively, both sets would equivalent to the universal set since any Object could be added to either set.

Obviously infinity doesn't work in practice, but I want to get as close as possible to the real definition of equality.

Does anyone have any suggestions?

Upvotes: 0

Views: 63

Answers (1)

Louis Wasserman
Louis Wasserman

Reputation: 198391

This is not remotely doable in general; it runs straight into the Halting Problem to determine if two programs (the arbitrary predicates) are equivalent. You might be able to detect equality for some very simple predicates, like "the set of elements that equal 0," but that's as far as it goes.

For anything more involved, you're really going to need an entirely different framework and probably language to reason about predicate equality. This would be a pretty normal thing to do in Agda, for example, but no language can solve the halting problem: It restricts the ways in which you can express your predicates (if you want it to reason about predicate equality).

Given that you have a countable set, if you add the caveat that a predicate must give the same answer to a given value every time, you could simply check the end result for all possible values. If that isn't going to end up being a performance issue, then by all means. There is no way in java to enforce the 'must give consistent answers' requirement.

Upvotes: 2

Related Questions