Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding a bug in Dummit and Foote's Abstract Algebra

kallus.org

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#21

Post by troethe »

ndriscoll wrote: post #20
troethe wrote: post #18

While the proposed fix of requiring "either that A be inhabited or that B be uninhabited" works, it seems tacked on just to solve this particular edge-case. I think a more elegant solution would be to soften the definition of a left inverse from a function `g: B -> A` to a function `g: f(A) -> A` where `f(A)` is the subset of elements in `B`, that actually get mapped to by `f` or in the words of the book's function d…

That's basically saying you'll just take all functions to be surjective though, and it's stronger than you really need; the non-surjective case works fine for non-empty A. You could of course interpret some of these basic theorems as saying "well I'd might as well take my function to be surjective since the 'meat' is that case." Much like you could just take all functions to be injective by modding out the kernel sin…

No, f can still map to `B` and does not need to be surjective. We just loosened the definition of `g` a little in a way that doesn't matter.

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#22

Post by ndriscoll »

troethe wrote: post #21
ndriscoll wrote: post #20

Earlier quoted context omitted.

That's basically saying you'll just take all functions to be surjective though, and it's stronger than you really need; the non-surjective case works fine for non-empty A. You could of course interpret some of these basic theorems as saying "well I'd might as well take my function to be surjective since the 'meat' is that case." Much like you could just take all functions to be injective by modding out the kernel sin…

No, f can still map to `B` and does not need to be surjective. We just loosened the definition of `g` a little in a way that doesn't matter.

But f's codomain is B, and g isn't a function on B, so you can't compose them in the first place. And saying "well yeah but you could compose f's restriction" is exactly making f surjective.

The basic result here is every function factors as a surjection (collapsing to the quotient) followed by an isomorphism (with the image) followed by an injection (enlarging the codomain). The surjection and injection are "trivial" and the isomorphism is the part that "does something" (permuting your thing somehow).

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#23

Post by troethe »

ndriscoll wrote: post #22
troethe wrote: post #21

Earlier quoted context omitted.

No, f can still map to `B` and does not need to be surjective. We just loosened the definition of `g` a little in a way that doesn't matter.

But f's codomain is B, and g isn't a function on B, so you can't compose them in the first place. And saying "well yeah but you could compose f's restriction" is exactly making f surjective. The basic result here is every function factors as a surjection (collapsing to the quotient) followed by an isomorphism (with the image) followed by an injection (enlarging the codomain). The surjection and injection are "trivial…

Of course I can compose `f: A -> B` and `g: f(A) -> A`. The composition maps a `x` from `A` to `g(f(x))` which is well defined. Therefore the composition is a function.

`g` and `f` aren't functions in a programming language and `A` and `B` are not types. There is nothing like a type checker forbidding you from composing `f: A -> B` and `g: f(A) -> A`.

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#25

Post by mitxela »

psYchotic wrote: post #15
changoplatanero wrote: post #9

Earlier quoted context omitted.

When there are no pairs, its certainly true that the first element of each pair comes from A. Just like if there are no living dinosaurs its true that all living dinosaurs speak English.

That helps. Thank you! I was trying to come up with something to explain why I couldn't see it myself: every element of an empty set of integers is both even and odd. This feels counterintuitive to me, until I flip it around into a question: what is the set of all integers that are both even and odd?

Neat trick

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#26

Post by mitxela »

shmoil wrote: post #5

I asked AI to formalize an old important paper in analysis. In the paper there is a sequence of epsilon_n > 0, epsilon_n -> 0. It came back, and said: "I formalized it, it is all good, but the assumption that epsilons > 0 is not used anywhere. Shall we remove it, you a get a stronger result this way?" LOL

Was the proof correct?

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#27

Post by ajkjk »

troethe wrote: post #18

While the proposed fix of requiring "either that A be inhabited or that B be uninhabited" works, it seems tacked on just to solve this particular edge-case. I think a more elegant solution would be to soften the definition of a left inverse from a function `g: B -> A` to a function `g: f(A) -> A` where `f(A)` is the subset of elements in `B`, that actually get mapped to by `f` or in the words of the book's function d…

I think a slightly better fix is to change definitions to allow g = { (1, {}) } to be regarded as a left-inverse to g, that is, to allow left-inverses to be partial functions, rather than full functions. The definition still requires they be defined on the image of f, but no choices have to be made on the complement of the image. Probably this breaks some other definitions but it seems intuitively correct to me. It keeps the structure that function B->A could be a left inverse and then only some of them are, rather than limiting them to the functions which are defined only on image(f).

This is kinda nice also because it means that for e.g. the function (a,b) -> (1, 2) given by f(a) = 1, f(b) = 1, you don't need its left inverse to specify that g(2) = a or b, but instead you can have g(2) = {} which doesn't require making any non-canonical choices.

(I'm too sleepy atm to think through this in detail. I might regret this proposal after a nap)

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#28

Post by troethe »

ajkjk wrote: post #27
troethe wrote: post #18

While the proposed fix of requiring "either that A be inhabited or that B be uninhabited" works, it seems tacked on just to solve this particular edge-case. I think a more elegant solution would be to soften the definition of a left inverse from a function `g: B -> A` to a function `g: f(A) -> A` where `f(A)` is the subset of elements in `B`, that actually get mapped to by `f` or in the words of the book's function d…

I think a slightly better fix is to change definitions to allow g = { (1, {}) } to be regarded as a left-inverse to g, that is, to allow left-inverses to be partial functions, rather than full functions. The definition still requires they be defined on the image of f, but no choices have to be made on the complement of the image. Probably this breaks some other definitions but it seems intuitively correct to me. It k…

> your fix kinda breaks a lot of the structure of algebra in other ways

What are you referring to here in particular?

I think the property of `g` to be a well defined function is a lot more important than for its domain to be `B`, when `f(A)` is enough to make the composition well defined.

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#29

Post by ndriscoll »

troethe wrote: post #28
ajkjk wrote: post #27

Earlier quoted context omitted.

I think a slightly better fix is to change definitions to allow g = { (1, {}) } to be regarded as a left-inverse to g, that is, to allow left-inverses to be partial functions, rather than full functions. The definition still requires they be defined on the image of f, but no choices have to be made on the complement of the image. Probably this breaks some other definitions but it seems intuitively correct to me. It k…

> your fix kinda breaks a lot of the structure of algebra in other ways What are you referring to here in particular? I think the property of `g` to be a well defined function is a lot more important than for its domain to be `B`, when `f(A)` is enough to make the composition well defined.

Typically one defines relations before functions anyway (unless you're doing type theory/programming, in which case types matter), and relations also offer a fix (the empty relation from the empty set is left inverted by the empty relation from the target to the empty set).

Most algebra books I've read are either explicitly or at least implicitly setting up structural analogies to introduce categories, where your A and B are indeed fixed/"typed".

Re: Finding a bug in Dummit and Foote's Abstract Algebra

#30

Post by ndriscoll »

troethe wrote: post #23
ndriscoll wrote: post #22

Earlier quoted context omitted.

But f's codomain is B, and g isn't a function on B, so you can't compose them in the first place. And saying "well yeah but you could compose f's restriction" is exactly making f surjective. The basic result here is every function factors as a surjection (collapsing to the quotient) followed by an isomorphism (with the image) followed by an injection (enlarging the codomain). The surjection and injection are "trivial…

Of course I can compose `f: A -> B` and `g: f(A) -> A`. The composition maps a `x` from `A` to `g(f(x))` which is well defined. Therefore the composition is a function. `g` and `f` aren't functions in a programming language and `A` and `B` are not types. There is nothing like a type checker forbidding you from composing `f: A -> B` and `g: f(A) -> A`.

I suppose, but then your definition of composition requires checking compatibility of codomain/domain instead of it being automatic (and your definition of composition does not fit the shape to form a category), which seems way worse than stipulating f non-empty for some theorem that isn't even true for other categories either.

And for e.g. for vector spaces or modules over semisimple rings they're actually the same so there's a real statement being made to say they're not always.

Post reply on HN