Faits: A. Le 21 mars 2013, le Ministère public genevois a rendu une ordonnance de non-entrée en matière au sujet d'une plainte déposée le 26 novembre 2012 par X._. Cette plainte était dirigée contre Y._ pour faux dans les titres et fausse déclaration d'une partie en justice. Elle était motivée par une contradiction entre les déclarations faites par ce dernier le 29 novembre 2011 devant le tribunal de première instance et le témoignage de Z._ lors de l'audience d'enquête du 13 novembre 2012 devant le même tribunal. Alors que le premier avait affirmé avoir été présent lors de la signature d'un pacte successoral instrumenté le 24 avril 2006, le second avait déclaré que Y._ était absent lors de cette signature. B. Par arrêt du 12 juin 2013, la Chambre pénale de recours de la Cour de justice genevoise a rejeté le recours formé par X._ contre cette ordonnance. Elle a estimé que compte tenu des éléments de preuve à disposition c'est à juste titre que le Ministère public avait retenu que Y._ était présent lors de la signature du pacte successoral et que dans l'hypothèse où celui-ci serait renvoyé en jugement un acquittement apparaissait, de loin, plus vraisemblable qu'une condamnation. C. X._ forme un recours en matière pénale contre cet arrêt. Invoquant une violation du principe « in dubio pro duriore », il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt attaqué et au renvoi de la cause au Ministère public principalement pour qu'il engage l'accusation contre l'intimé du chef des art. 251 al. 1 et 306 CP et subsidiairement afin qu'il instruise la cause en organisant une confrontation entre toutes les personnes concernées. D. Invité à présenter des observations, l'intimé s'en remet à justice s'agissant de la recevabilité du recours, en notant toutefois que selon lui le dommage invoqué repose exclusivement sur des prétentions de droit successoral. Au fond, il conclut, avec suite de frais et dépens, au rejet du recours. Le Ministère public s'en remet également à justice en ce qui concerne la recevabilité et conclut au rejet du recours. Répondant à ces observations, le recourant conclut à l'admission du recours, à l'annulation de l'ordonnance attaquée et au renvoi de la cause au Ministère public. 