I'm planning on writing a short story and I'm just wondering if it'd be possible to add an element of discovery into it. I think it'd be interesting if the reader would be able to learn things about the world in the book without having it handed to them, they would need to pay attention to certain parts of the story to learn things about some characters or places. Is this possible or would it ruin the story?
It is in fact positive to not overwhelm and bore the readers at the start with a lot of details about characters they feel no connection with.
Connection to a character comes through seeing how he acts, in the best case the reader may even impersonate himself with the character, feel so bound to it to almost feel the story on his skin.
I would start with a fast-paced action lasting a chapter or two. Seeing what the protagonist will do when in trouble will be both more relevant to the story and interesting than a random list of qualities and characteristics.
After this introduction, you may stop and (briefly) explain explicitly what could not be deduced by reading the above introduction.
The level of inferring readers can get to with a book is infinite. There are actually many books that only in the end you get a new clue that makes the story much different (example). Sometimes you don't even get a clue, you have to understand it yourself (example - although simple one).
Other examples you can see are the games "Her Story", "Gone Home" and "Scratches" which have long blog posts about their hidden meanings and story-lines. As a reader, love trying to figure out the hidden meanings of the story. As a writer, it's a fun challenge to do.
So to your question: It is very possible, and as a comment say, it's much better than the infamous info-dump. If you are aiming towards readers with at least basic level of connecting the dots, it would be a pleasant thing to read.
If I pull off what I hope I can, I'll be very pleased. I'm hoping to put elements in the story that make the reader curious, but not completely sure as to what's going on behind the scenes. I hope readers figure pieces out on their own, and once they finish the book, they immediately want to re-read the book and can better fully understand the significance of the back story.
And if it goes really well, I hope people on forums start arguments with each other about the specifics, because while you might get a strong gist, you can still argue about the specific details.
I absolutely love the element of discovery!