Comments (24)
Oops! You are right that this implementation is buggy.
I think that in this case, every element is its own inverse, since xor(x, x) = false
for any x
. In that case, negate(x) = x
.
from algebra.
I'll try to prepare a patch with laws, law-checking, and a correction. If I can't prove (and test) that this change is correct, we'll have to remove the method.
from algebra.
That seems to work.
from algebra.
Actually, I'm not sure. I realized that I just checked that for a Boolean algebra, not Heyting algebra.
from algebra.
From Heyting
:
def xor(a: A, b: A): A = or(and(a, complement(b)), and(complement(a), b))
xor(a, a)
// expand definition
or(and(a, complement(a)), and(complement(a), a))
// we know that and(a, complement(a)) is false even in just heyting algebras
or(false, false)
// we know this is false
false
So I'm pretty sure we know xor(a, a) = false
.
EDIT: See pseudo-complement here: https://en.wikipedia.org/wiki/Heyting_algebra#Formal_definition
from algebra.
The tricky part IMO will be to prove the ring's distributive law.
On Oct 8, 2015 5:44 PM, "Erik Osheim" [email protected] wrote:
From Heyting:
def xor(a: A, b: A): A = or(and(a, complement(b)), and(complement(a), b))
xor(a, a)// expand definition
or(and(a, complement(a)), and(complement(a), a))// we know that and(a, complement(a)) is false even in just heyting algebras
or(false, false)// we know this is falsefalseSo I'm pretty sure we know xor(a, a) = false.
—
Reply to this email directly or view it on GitHub
#89 (comment).
from algebra.
Here's why it cannot be true. Suppose the object defined by Heyting#asCommutativeRing is a ring. Then it is a ring with a property a•a = a. A ring with this property is called a Boolean ring and is equivalent to a Boolean algebra (with xor
defined as ring addition, and or
defined in terms of xor
). Since we know that Heyting algebra is weaker than Boolean algebra, our assumption must have been wrong.
from algebra.
Ah yes, you are right of course. Let's just remove this method for now. Later on if someone discovers a useful structure (e.g. Semiring
) we can add a conversion.
from algebra.
Thanks again for your help @TomasMikula!
from algebra.
I think the method should be moved from Heyting
to Bool
, where it is true. Or even make Bool
extend CommutativeRing
directly?
from algebra.
Yeah let's move the method to Bool
, I think that makes the most sense. I'd rather not having it extend it directly because it would often conflict with other (possibly more natural) rings.
from algebra.
Do you have an example of a Boolean algebra that is also a ring different than the one given by a•b = a∧b
and a+b = a⊕b
(where ⊕ means xor)?
from algebra.
You can create a Bool[Int]
using &
and |
which is different from the Ring[Int]
one might normally expect.
from algebra.
If you don't want Bool
to extend CommutativeRing
directly, should there be a new trait BoolRing
and have asCommutativeRing
return that? BoolRing
can then have a method asBool
to get the Boolean algebra back.
from algebra.
Hm. My sense was that people were likely to want to use a [A: Bool]
constraint on their generic methods, and that they would be using asCommutativeRing
only when they were calling into code that was already parameterized on [A: Ring]
. I don't see an obvious situation where someone would need to recover the boolean algebra again where they couldn't just ask for it in the first place. Can you think of a situation where someone would need to talk about BoolRing
instead of just Bool
(or Ring
)?
from algebra.
I have a situation where I need to talk about a Boolean algebra (potentially) without a unit. I don't have a good name for it, but there is a good name for a Boolean ring without a unit - Boolean rng (see also my question on math.stackexchange). So I will have methods parameterized by [A: BoolRng]
. If someone has a Bool
, that should be good enough, except Bool#asCommutativeRing
only returns a CommutativeRing
, which is not enough. Anyway, this does not concern the current state of algebra
directly (since it has no BoolRng
), but this is the use case that I had in mind.
An example of a Boolean algebra without the top element is the set of finite subsets of an infinite set. For example, the type Set[String]
.
from algebra.
Also, in a Boolean algebra without unit, there will be no complement, but I'm still interested in the relative complement a\b
(set-theoretic difference). In Bool
, it could be implemented as a∧¬b
, but it can still be implemented even without ¬
. For Set
, it is a -- b
.
I think it would be nice to have this notion of a Boolean algebra without unit, but with relative complement, in algebra
(whether it would be called BoolRng
or something else).
from algebra.
Right, interesting.
I actually came up with a set data type that had a valid unit (i.e. the set containing everything) specifically to be able to use it in a boolean context. So I definitely see the value in something like that.
Interestingly, the link you gave defines Boolean Ring as the name for a boolean algebra with no "top" element, which sounds like what you actually want here.
from algebra.
Yeah, there doesn't seem to be consensus on whether ring assumes unit or not. But since Ring
in algebra
has a unit, it would be strange if BooleanRing
didn't.
from algebra.
What was your construction of a set type with unit? I constructed a type isomorphic to (Boolean, Set[A])
, where the Boolean
bit indicates whether the elements of Set
are meant to be included or excluded. However, if A
has a finite number of elements, this construction yields two representations for each subset of A
. If A
is infinite, then it represents only finite and co-finite subsets (which is better than just finite subsets represented by only Set
itself, but not much better).
from algebra.
I did something similar. I also used a type Universe[A]
to track the cardinality of A
(finite or infinite, etc) when I needed to be able to compare the two kinds of sets.
from algebra.
I can go ahead and move the method to Bool
if you want. Do you think it makes sense to rename it to just asRing
, where the fact that it is a commutative ring is captured by the return type? This way, we don't have to change the name again if in the future we decide that we want it to return a BoolRing
.
from algebra.
Fixed by #94
from algebra.
See my comment.
from algebra.
Related Issues (20)
- add Kleene Algebra HOT 1
- fromInt and Ring-like structures.
- ConicMonoid: when values are always increasing. HOT 10
- Publish a version for cats 0.8.0 HOT 1
- cast class exception using algebra with algebird HOT 1
- Annihilator -- Structure with element that "annihilates" any other element of the set HOT 3
- Add tests for the functions in companion objects of the types. HOT 1
- Publish 0.7.0 to address binary incompatibility HOT 1
- Algebra Syntax (was #78 Symbolic Infix Operators)
- link to docs is broken HOT 5
- Why don't we move Spire's Module/VectorSpace/MetricSpace/etc. here? HOT 3
- Possible compatibility breaking change in cats-kernel HOT 1
- Upgrade to Cats RC1 HOT 2
- Law testing guidelines HOT 1
- Broken links in README.md HOT 2
- Integrating cats.kernel.Semigroup and friends HOT 30
- publish for Scala 2.13.0-M5 HOT 26
- publish for Scala 2.13 HOT 1
- Integrate intermediate steps between `CommutativeRing` and `Field` HOT 1
- Archive this repo? HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from algebra.