This study reports on how students can be led to make meaningful connections between such structures on a set as a partition, the set of equivalence classes determined by an equivalence relation and the fiber structure of a function on that set (i.e., the set of preimages of all sets {b} for b in the range of the function). In this paper, I first present an initial genetic decomposition, in the sense of APOS theory, for the concepts of equivalence relation and function in the context of the structures that they determine on a set. This genetic decomposition is primarily based on my own mathematical knowledge as well as on my observations of students' learning processes. Based on this analysis, I then suggest instructional procedures that motivate the mental activities described in the genetic decomposition. I finally present empirical data from informal interviews with students at different stages of learning. My goal was to guide students to become aware of the close conceptual correspondence and connections among the aforementioned structures. One theorem that captures such connections is the following: a relation "R" on a set "A" is an equivalence relation if and only if there exists a function "f" defined on "A" such that elements related via "R" (and only those) have the same image under "f".