Antonio Majocchi
email: antonio.majocchi@unipv.it

Ulrike Mayrhofer

Joaquin Camps

The choice between joint ventures and non equity-alliances: evidence from Italian firms

Keywords:

This paper investigates the factors affecting the choice between joint ventures and non-equity alliances, when firms enter foreign markets. Using a database of Italian firms compiled by the authors with 879 observations, we test the possible effects of firm specific characteristics, host country institutional characteristics and cultural distance on alliance mode choice. Using both transaction cost analysis and the resource based view, our findings demonstrate the crucial role played by firm size and by institutional and political features of host countries.

The results concerning the role of functional activities involved and the industrial sector are mixed. Overall, our analysis shows that it is necessary to develop a more integrated approach to understand this complex choice made by firms when expanding abroad.

Introduction

In a context of globalisation of markets and competition, companies need to increase their international market presence. The choice of market entry mode is one of the most critical elements of a firm's foreign investment strategy [START_REF] Root | Entry Strategies for International Markets[END_REF][START_REF] Kumar | A contingency framework for the mode of entry decision[END_REF][START_REF] Nakos | Entry mode choice of SMEs in Central and Eastern Europe[END_REF]. When conquering foreign markets, firm frequently choose to establish alliances with local companies [START_REF] Dunning | Reappraising the eclectic paradigm in an age of alliance capitalism[END_REF][START_REF] Guidice | Governing joint venture: tension among principals' dominant logic on human motivation and behaviour[END_REF]. Firms increasingly use this entry mode choice to access market and resources worldwide. Alliances can be defined as medium and long term agreements between companies, which involve the mutual transfer of intangible resources such as technology or human skills with or without the development of a dedicated administrative structure [START_REF] Pisano | Using equity participation to support exchange: Evidence from the biotechnology industry[END_REF][START_REF] Oxley | Appropriability hazards and governance in strategic alliances: a transaction cost approach[END_REF]. Once firms have decided to expand internationally with a partner, they can use either the equity form (joint ventures) or a non-equity form (non-equity alliances).

The objective of the present paper is to identify the factors that are likely to affect the choice between equity and non-equity agreements. The study empirically explores the determinants of the choice between joint ventures and non-equity agreements contributing to a field that is very important in terms of number of deals but that still requires further investigation [START_REF] Globerman | Equity versus non-equity international strategic alliances involving Danish firms: An empirical investigation of the relative importance of partner and host country determinants[END_REF]. Using a database compiled by the authors for this specific purpose, covering both large and small-and medium-sized firms, we test some of the determinants affecting the alliance mode choice. The paper is organised in the following way.

Firstly, the theoretical framework and the research hypotheses will be developed. Then, the research methodology will be explained, and the findings of the empirical study will be discussed. Finally, we will outline major limitations and perspectives for future research.

Theoretical framework

Factors affecting the choice between joint ventures and contractual agreements can be classified into three main categories: (1) country specific, (2) industry specific and (3) firm specific factors. Concerning country specific factors, previous research shows that factors such as cultural distance between the firm's home country and the host country [START_REF] Leung | Entry of foreign banks in the people's republic of China: a survival analysis[END_REF][START_REF] Chen | An analysis of determinants of entry mode and its impact on performance[END_REF][START_REF] Gillespie | Transplanted company law: an ideological and cultural analysis of market entry in Vietnam[END_REF], institutional aspects such as the progresses in market institution building (Meyer, 2001) or the foreign exchange rate and the host country currency characteristics [START_REF] Baek | Foreign exchange rates and the corporate choice of foreign entry mode[END_REF] or the level of environmental uncertainty [START_REF] Lòpez-Duarte | The effect of firm and host country characteristics on the choice of entry mode: empirical evidence from Spanish firms[END_REF] can play an important role. Industry specific factors such as market size, market structure, or the level of industry barriers have also proved influential (e.g. [START_REF] Chen | Japanese investors' choice of joint ventures versus wholly owned subsidiaries in the US: the role of market barriers and firm capabilities[END_REF][START_REF] Siripaisalpipat | Firm specific advantages, entry modes and performance of Japanese FDI in Thailand[END_REF]. Many authors have emphasised the impact of firm specific factors such firm resources and firm size [START_REF] Leung | Entry of foreign banks in the people's republic of China: a survival analysis[END_REF] or the level of international experience of firms [START_REF] Reuber | Targeting exports support to SMEs: owners' international experience as a segmentation basis[END_REF][START_REF] King | Incumbent entry into new market Niches: the role of experience and managerial choice in the creation of dynamic capabilities[END_REF] or the characteristics of CEOs [START_REF] Herrmann | CEO successor characteristics and the choice of foreign market entry mode: an empirical study[END_REF].

As far as the theoretical framework is concerned, most available studies have used Transaction Cost (TC) economics as their main theoretical framework to analyse the determinants of this strategic choice [START_REF] Brouthers | Why service and Manufacturing Entry Mode Choices Differ: The Influence of Transaction Cost Factors, Risk and Trust[END_REF]. In the TC view, it is the level of uncertainty surrounding market transactions that determines the cost of this specific entry mode. TC theorists (Williamson, 1985;[START_REF] Gatignon | The multinational corporations' degree of control over foreign subsidiaries: an empirical test of a transaction cost explanation[END_REF]Nakos and Brothers 2002) identify two kind of uncertainty: behavioural uncertainty and environmental uncertainty with the first referring to the risk of any opportunistic behaviours by partners and the second referring to all the risks that are generated by the entry in an unknown country.

When the perceived risk associated with the new environment is considered as high, firms tend to avoid committing resources and to select non-equity entry modes.

Recently, several authors have criticised the transaction cost approach pointing to the fact that TC analysis only takes into account internal but not external resources that firms have and that can lower the transaction costs related to the entry mode choice [START_REF] Thuy | Relation capital and performance of international joint ventures in Vietnam[END_REF]. This criticism suggests the adoption of complementary approaches to the entry mode dilemma such as the institutional perspective [START_REF] Yiu | The choice between joint ventures and wholly owned subsidiary: An institutional perspective[END_REF] or the resource-based view (RBV). [START_REF] Tse | How Mncs choose entry modes and form alliances: the China experience[END_REF] with regards to the case of investment in China have analysed the effects of country-specific, industry-specific, and operation-related factors on market entry strategy through either export or licensing or joint ventures or wholly owned-subsidiaries.

More specifically, their analysis shows how host and home country characteristics are important in determining entry mode decisions. With regards to the resources developed by firms [START_REF] Davidson | Global Strategic Management[END_REF], and [START_REF] Anderson | Modes of foreign entry: A transaction cost analysis and propositions[END_REF] suggest that international experience is a resource affecting the governance of foreign transaction since firms with more international experience tend to adopt a high equity entry mode. The study conducted by [START_REF] Cantwell | Technological and output complementarities, and interfirm cooperation in information technology ventures[END_REF] shows that technological competencies and technological similarity between partners are variables that affect the choice between equity and non-equity agreements with close technological specialisation leading to greater likelihood of non equity arrangements. However, their analysis is limited to the information technology sector and lacks observations concerning joint ventures, thus limiting its generalisation.

Several authors have emphasised the necessity to adopt a more integrated approach when analysing the choice between equity and non-equity alliances. For example, [START_REF] Hill | An eclectic theory of the choice of international entry mode[END_REF], and [START_REF] Yiu | The choice between joint ventures and wholly owned subsidiary: An institutional perspective[END_REF] estimate that TC economics offers a useful but only partial explanation of the complex phenomenon. More specifically, the TC approach seems well suited to interpret the cost effects on firms of the alternative modes of governance but needs additional theoretical approaches to fully capture the complexity of the process. In this research, we have thus decided to adopt an integrated framework in order to study the alliance mode choice. Combining two approaches that are frequently used in the field, that is transaction cost theory and resource based-view, we focus on a few features that are likely to affect alliance mode choice, namely industry features, activities of the value-chain involved in the agreement and characteristics of the host countries. This last point is of special interest. In recent years, a lot of effort has been made to examine the impact of specific factors on entry mode decisions and among these factors institutions attracted the most attention. Some contributions extended the Transaction Cost theory by adding institutional factors to the given framework [START_REF] Brouthers | Institutional culture and transaction cost influences on entry mode choice and performance[END_REF][START_REF] Lu | Intra-and inter-organizational imitative behaviour: institutional influences on Japanese Firms' Entry Mode Choice[END_REF]. Others argued that institutions modify the uncertainty surrounding transactions [START_REF] Said | Institutional reform and entry mode by foreign firms: the case of Jordan[END_REF][START_REF] Meyer | Direct investment in economies in transition[END_REF]. We develop this analysis adding some specific variables to the effect of cultural distance. The specific variables introduced in our model test the effects of aspects that may affect alliance mode choice, but that have not been widely investigated. These effects refer to variables developed in order to measure the level of legal rights protection and the level of political risk surrounding foreign investments in a country. We first consider several variables proposed by the TC approach and then we also take into account variables suggested by the RBV.

In the transaction cost approach, the role of intangible assets is considered as crucial in driving firms towards a more hierarchical mode of governance. For example, [START_REF] Gatignon | The multinational corporations' degree of control over foreign subsidiaries: an empirical test of a transaction cost explanation[END_REF] and [START_REF] Hennart | The Impact of Culture on the Strategy of Multinational Enterprises: Does National Origin Affect Ownership Decisions[END_REF] find a positive relationship between R&D intensity and the probability of creating a wholly owned subsidiary rather than a JV. [START_REF] Brouthers | Institutional culture and transaction cost influences on entry mode choice and performance[END_REF] underlines how the firms operating in high-technology sectors tend to have a higher assets specificity of their investments that leads to higher risk of opportunistic behaviours by partners. Therefore, he suggests that TC theory supports the view that more integrated modes provide more efficient organisational structures when there is a threat from opportunism. We can thus consider that, when firms exchange knowledge, a highly specific asset with a high degree of uncertainty, more integrated forms are preferred. This tendency should be stronger in industries where research input is an essential part of the production chain and an essential factor in developing a competitive advantage, as it is the case in science-based sectors. Therefore we can propose the two following hypotheses: H1: Firms that form agreements involving R&D functions tend to chose joint ventures rather than non-equity alliances.

H2:

In science based industries, firms are more likely to choose joint ventures rather than non-equity alliances.

Recent IB literature relying on the works by [START_REF] North | Institutions, Institutional Change and Economic Performance[END_REF] underlines the role that institutional features have on corporate strategies. [START_REF] Brouthers | Perceived environmental Uncertainty, Entry Mode Choice and satisfaction with EC-MNC Performance[END_REF] and [START_REF] Meyer | Direct investment in economies in transition[END_REF] demonstrate how institutional characteristics of the host country can impact investment strategies affecting the uncertainty involving foreign transactions. More specifically, [START_REF] Brouthers | Institutional culture and transaction cost influences on entry mode choice and performance[END_REF] shows that the legal framework can play an important role. Countries where the legal structure is less developed and where legal protection for foreign entities is low are perceived as more risky by foreign firms. Joint ventures, when associating local partners, allow foreign investors to hedge against the political risk of government intervention [START_REF] Chen | A hostage theory of joint ventures: why do Japanese investors choose partial over full acquisitions to enter the United States?[END_REF][START_REF] Lòpez-Duarte | Foreign direct investment through partial acquisitions: hostage effect or conflicts enhancement[END_REF]. When entering foreign markets, the legal restrictions and the political hazard are considered as sources of risk and this risk can be better hedged with the presence of a local partner. Consequently, a high level of risk in the host country favours a less hierarchical entry mode. However, this conclusion does not hold in the same way when firms evaluate the possibility to enter the market either with an alliance or with a JV. In this case, the choice to have a partner in the host country has already been made and the firms must evaluate whether to enter the market with an equity stake (JV) or with a non equity agreement. Here, the low level of legal protection and the high level of political hazard are sources of risk that increase the transaction costs of the agreements (both equity and non equity). In this case, according to TC theory, a more hierarchical form of agreement will be preferred thus favouring JV agreements rather than non equity entry modes. Moreover, the JV alternative is seen as a stake in a local concern and the presence of a joint investment with a local partner is seen as an insurance against possible retaliation by the foreign government.

We thus suggest two hypotheses on the effects of the legal and political environment on alliance mode choice:

H3a

The lower the legal protection in a country, as measured by the efficiency of contract enforcement, the more likely it will be that firms choose joint ventures rather than non-equityalliances.

H3b

The higher the political hazard in a country, the more likely the probability that firms choose a joint venture rather than a non-equity alliance.

Despite the increasing globalisation of markets, distance still influences internationalisation strategies. More specifically, cultural distance plays an important role when firms decide to enter new markets [START_REF] Erramilli | Service Firms' International Entry-Mode Choice: A Modified Transaction-Cost Analysis Approach[END_REF][START_REF] Hennart | The Impact of Culture on the Strategy of Multinational Enterprises: Does National Origin Affect Ownership Decisions[END_REF]. [START_REF] Kogut | The effect of national culture on the choice of entry mode[END_REF] argue that differences in culture between home and host countries increase the level of risk in integration processes, and thus lead firms to choose less risky agreements. More generally speaking, the more distant the culture between home and host countries, the more difficult and expensive is the process of adaptation to the new environment for the firm. The lack of knowledge increases the cost and the risk of the market entry so most of the scholars assume that the larger the cultural distance the lower the preference for internal modes of entry. Therefore, we assume that firms prefer to enter distant markets with a non-equity alliance in order to gain knowledge and we posit that: H4: The higher the cultural distance between the home and the host country, the more likely firms will choose non-equity alliances rather than joint ventures.

Recently, several scholars used the resources-based view to interpret entry mode choice [START_REF] Ekeledo | International market entry mode strategies of manufacturing firms and service firms -A resource-based perspective[END_REF]. The two views are not necessarily conflicting as TC focuses mainly on the cost of governing foreign transaction while RBV underlines how foreign entry is a means to increase firm resource endowments (Meyer et al. 2009b). More generally, the RBV underlines how firms choose their entry mode in foreign markets on the basis of both the existing resources they control and on the basis of the ones they would like to have access to. As argued by [START_REF] Grant | The resource-based theory of competitive advantage: implications for strategy formulation[END_REF], firm size defines the scope of its own resources and what a particular firm can and cannot do. It thus reflects available resources. In fact, larger firms, which have more resources in terms of managerial and organizational knowledge, will tend to look more for complementary resources and less for new knowledge. This will lead large firms to prefer equity forms. Conversely, small firms, being limited in the resources that they control, will prefer non equity arrangements. Consequently we posit our last hypothesis: H5 When small firms are involved, it is more likely that they will choose a non-equity alliance rather than a JV.

The sample

The empirical investigation is based on a sample of 879 interfirm agreements concluded by Italian firms with partners from all over the world. The observation period extends from 2000 to 2006. The database, compiled by the authors, covers announced agreements reported in "Il Sole 24 Ore", the main Italian economic newspaper. The collected information has been verified through web sources and press releases regarding the firms involved in the agreements. Data extracted from the press has frequently been used to identify cooperative alliances [START_REF] Mayrhofer | The influence of national origin and uncertainty on the choice between cooperation and merger-acquisition: an analysis of French and German firms[END_REF]). In our database the percentage of joint ventures is 54%. The geographic origin of partner companies is mainly Europe (42%), followed by the United States and Canada (20.9%), and China (12%). The industry distribution of the sample is fairly

The variables

The variables that have been extracted and used in the model are reported in table 1. The dependent variable is the contractual form of the agreement which has been coded 1 if the agreement takes the form of a joint venture and 0 if the agreement is a non-equity alliance.

The variables used in the model concern the following categories: the geographical scope of the agreement, the country characteristics of the host country, the size and the industrial sector of the Italian firms and two other firm characteristics namely: the international strategy of the firm and the main functional activity concerned by the agreement. Enforcing contracts From -∞ to = 0, with 0 = highest level of legal protection H3a (-)

Enfcon

Political constraints From 0 to 100 with 100 = low political hazard -H3b (-)

Costri

Cultural distance

Kogut & Singh index. The index has been adapted to Italy and is represented algebraically as:

CD j     4 / / 4 1 2    I i iu ij V I I 
where CDj is the cultural difference of the jth country from Italy, Iij represents the index of the ith cultural dimension and the jth country, u stands for Italy and Vi is the variance of the index of the ith dimension.

H4 (-)

Cult_dist

Size of enterprise Dummy variable

<49 employees

Small 49-499 employees H5 (-) Medium

>500 employees Large

Control Variables

Credit rating 1-100 (100= high rating grade), OECD data Rating

Investor protection index 0-10 (10=high investor protection) (World Bank, doing business with database)

Invpro

Global competitiveness index 1-10 with 10 = high global competitiveness (World Economic forum) The functional content of an alliance represents the activities of the value chain that are primarily concerned by the agreement. The activities that have been coded using a dummy variable are: Logistics (Logistic), Operations (Prod.), Sales and marketing (Mkting) with regards to the primary activities. The support activities are: Procurement (Proc) Human Resource management (HR) Research and Development (R&D) and Infrastructure (Infras) i.e. the functions of departments such as accounting, legal, finance, planning, public affairs, government relations, quality assurance and general management. The variable sector (Sector) defines the main industry sector of the firm promoting the agreement. In order to code the industry, we use the NACE nomenclature of economic activities provided by the European Commission. Using the well-known [START_REF] Pavitt | Technology transfer among the industrially advanced countries: in overview[END_REF] taxonomy the NACE codes have been recoded. We end up with a total of 8 industrial sector dummy variables: the primary sector, the four Pavitt sectors (traditional, scale-intensive, specialised suppliers and science-based sectors), the utilities sector (energy gas and water), the trade sectors and a residual sector.

Compet

Firm strategies

Dummy variable

Risk reduction

With regards to the institutional characteristics of the host country we have taken different variables into account. The first variable measures the degree of protection of contracts in a country (Enfcon). We use an index produced by the World Bank, the Enforcing contracts index, that measures the efficiency of the legal system in resolving commercial disputes in a country averaging three main indicators: the number of procedures from the moment the plaintiff files a lawsuit in court until the moment of payment, the time in days to resolve the dispute, and cost in court fees and attorney fees. The index measures the efficiency of contract enforcement. In the model, the index has been inserted with a negative sign so that lower values of the index correspond to lower values of legal protection and efficiency in contract enforcement. The level of political risk in the country has been measured using the political constraints index (Costri) developed by [START_REF] Henisz | The Institutional Environment for Economic Growth[END_REF]. The index underlines the differences between policy systems of different countries measuring the extent to which a given political actor is constrained in his or her choice of future policies. We have scaled the index on a 100 basis so the possible scores for the final measure of political constraints range from zero for the most hazardous countries to 100 for the safest. It must be noted that, since the measure of political risk we have used assigns a lower value to the most risky countries, we predict a negative relationship between the political risk variable and the entry mode choice: riskier countries with a lower value of political constraint index will attract, ceteris paribus, more JV than non-equity agreements. The index has been calculated as the average of the values of the index over the last five years. The cultural distance measure relies on the usual Hofstede (1980) index. However, because most of the studies [START_REF] Barkema | Foreign entry, cultural barriers, and learning[END_REF]) use a composite index we also follow this approach. More specifically, our variables measuring cultural distance (Cult_dist) have been constructed on the basis of the [START_REF] Kogut | The effect of national culture on the choice of entry mode[END_REF] index, a composite index of cultural distance that is based on the deviation along the first four dimensions of Hofstede's framework and that has been extensively used in the study of foreign market entry [START_REF] Morosini | National Cultural Distance and Cross-Border Acquisition Performance[END_REF]. Following similar empirical studies [START_REF] Majocchi | Firm size, business experience and export intensity in SMEs: a longitudinal approach to complex relationship[END_REF], we proxy the firm resources with the firm size at the time of the agreement. Using the numbers of employees, three classes can be defined: small, medium and large firms. The smaller group is made up of firms with less than 50 employees, the medium firms have a number of employees between 50 and 499 and large firms are those with more than 500 employees.

As usual in empirical work, a series of control variables have been introduced. A first dummy variable identifies the country of destination in order to catch all the potential host country effects not defined in our previous variables. We defined 10 regions as reported in table 1.

Then we insert an index measuring the level of Investor protection (Invpro). This index is computed by the World Bank and measures the strength of minority shareholder protections.

The index ranges from 0 to 10, with higher values indicating more investor protection.

Moreover, in order to identify potential effects caused by different strategies we identify the motives behind alliance decisions. This variable has been defined according to the firm goals as stated in the press reports or in the press releases regarding the agreements. In order to classify the internationalisation strategy we use the taxonomy proposed by [START_REF] Contractor | Why should firms cooperate? The strategy and economic basis for cooperative ventures[END_REF]. In their landmark work on alliances, they underline the strategic reasons behind the choice to develop alliances. According to this taxonomy, each agreement can be classified in one of the following cases using dummy variables:  Vertical quasi-integration (QV integration); i.e access to technology, labour capital or to distribution channels, etc. Finally, two other indexes have been inserted as control variables in order to measure the overall risk of the host countries: one that measures the economic development of the country and one that measures the level of solvency of public finances. The first index the Global Competitiveness index (Compet) produced by the World Economic Forum considers a collection of factors, policies and institutions which determine the level of productivity of a country and that, therefore, determine the level of prosperity that can be achieved by an economy. The index ranges from 0 to 100 with the higher values corresponding to higher levels of competitiveness. The second index is an index of financial stability (Rating) and it has been taken by OECD. The index is a financial indicator to potential investors of debt securities issued by the State. In the context of our analysis it is another measurement for the overall financial and economic risk affecting the target country. The variable ranges from 0 to 100; the higher the rate the better the state of public finances and the lower the overall risk in investing in the country.



The Model

We test our hypothesis using logistic regression techniques, the standard logit procedures of the Intercooled Stata 9 package. Logistic regression is used in order to estimate the incidence of the independent variables on the probability that firms will choose either a non-equity alliance or a joint venture. Since the variable "agreement" takes the value 0, if partners decide to collaborate on a non-equity basis, and 1, if the operation takes the form of joint venture. A positive sign of the coefficients indicates that an increase in the value of the independent variable will increase the probability that the firm will choose a joint venture rather than a non-equity agreement. As usual for group variables, a variable has been dropped in order to avoid the dummy variable trap (perfect multicollinearity). The sign of the coefficients for these variables should be interpreted with regards to the variable that has been dropped and that acts as a reference variable [START_REF] Greene | Econometric analysis[END_REF]. The descriptive statistics and the correlation coefficients of the variables (dummy variables excluded) are reported in table 2. Data show that, given the low value of the correlation coefficients, multicollinearity is not a concern for this analysis. well with significant value of the Chi-square and of the area under the ROC curve and with a satisfactory percentage of correctly predicted observations. The low value of the pseudo Rsquare is not fully satisfactory but it must be noted that the pseudo-R 2 is not analogous to the R 2 in linear regression though there is an empirical relationship between the two, and a pseudo-R 2 of 0.2 represents an R 2 of approximately 0.4 [START_REF] Hensher | Applied choice analysis: a primer[END_REF]. The main results are reported in the following table.

Results and Discussion

Since the results are robust for both models, we refer our analysis only to the more restricted model. The results of the logistic regression analysis provide support for some of our hypotheses but not for all of them. Hypothesis 1 is not supported by the results of the statistical analysis. The coefficient for the dummy variable R&D is significant, but has a negative sign and not, as expected, a positive sign. When the R&D function is concerned, firms prefer to use non-equity alliances rather than joint ventures. We developed hypothesis 1 on the basis of Transaction cost theory considerations. The result of our analysis seems to challenge this view. Our results show that uncertainty and the risk of opportunistic behavior can be dealt with by a firm, even with less integrated forms that, at the same time, guarantee speed of execution and low costs of bargaining. Unfortunately, due to lack of data, we could not consider the kind of knowledge that is transferred through the JV or the agreement. Both Meyer et al. (2009a) and Lòpez-Duarte and Garcìa-Canal (2002) underline how it is the kind of knowledge sought by a firm that affects the market entry choice.

Hypothesis 2 predicting that, in science sectors, firms tend to prefer joint ventures appears to be confirmed. Our analysis supports the transaction cost view that asset specificity has a positive impact on the choice between hierarchical (equity) and non hierarchical modes of governance. From this point of view, our results confirm previous findings [START_REF] Hennart | The Impact of Culture on the Strategy of Multinational Enterprises: Does National Origin Affect Ownership Decisions[END_REF][START_REF] Brouthers | Institutional culture and transaction cost influences on entry mode choice and performance[END_REF] in the new context that we have analysed.

The same applies to the hypothesis that concerns the level of legal protection and political hazard in the target country. Hypothesis 3a and 3b jointly state that, when the legal protection in a country is low and political hazard is high, firms prefer to set up a joint venture with a local partner in order to have some kind of hedging against political risk. This result is statistically significant (even if only in the restricted model) and confirms previous results [START_REF] Delios | Political hazard, experience and sequential entry strategies: the international expansion of Japanese firms, 1980-1998[END_REF] regarding the role that the legal and political environment plays in affecting firm entry mode choice. Our results suggest that high political risk pushes firms to enter foreign markets with an equity form (JV) rather then with a non-equity agreement.

Considering the control variables, it must be noted that, with the notable exception of the rating grade, and even if at a different level, all the indexes that define the host country characteristics are significant. This result reinforces the view that economic and political features of the host country are important.

Similarly, the hypothesis regarding the effects of cultural distance on alliance mode choice is confirmed (Hypothesis 4), even if only at the 10% level of significance.

Finally, hypothesis 5 regarding the role of size has the expected sign for both small and medium sized firms but it is significant only for the medium sized firm variable. Resources seem to be an important determinant of the choice of alliance mode. Prior research tends to concentrate only on large firms which have been the main players in the international arena.

The exploration of small and medium sized firms however seems a promising line of research and we think that our results offer some useful insights in this field. Moreover, our findings provide further support for the resource-based view that is at the basis of our hypothesis and that has increasingly been used in IB research. A more integrated approach that merges TC economic with a RBV approach could be a useful staring point for research on cooperative alliances.

Conclusions, managerial relevance and limitations

This study is an attempt to empirically test the role of five factors on the choice between joint ventures and non-equity alliances: firm size, activities of the value-chain concerned by the agreement, industrial sector, host country institutional characteristics and cultural distance.

Our findings confirm that the factors we have explored do have, at different degrees, an effect on this alternative. We refer more specifically to the effect of country risk and legal protection on alliance mode choice. In our case the usual conclusion drawn by scholars [START_REF] Contractor | Modal Choice in a World of Alliances: Analyzing Organizational Forms in the International Hotel Sector[END_REF], using TC economics, have been reversed. Our findings show that more hierarchical modes of entry are preferred when the level of political risk is high. This conclusion needs further empirical validation but it suggests that not all the choices in the entry mode range follow the same rationale. This result is significant both by the managerial and the theoretical point of view. For business practitioners, it means that once a firm decided to enter in a new market with a partner this choice is not only affected by efficiency considerations, as it is typically assumed in the TC approach, but also by the kind of resources available to the firm. Both TC theory and a RBV approach seem to highlight different determinants. Consequently, from the theoretical point of view, our results call for a more integrated approach that combines the strengths of both theoretical perspectives. Finally, our analysis shows that host country characteristics influence the alliance mode choice, but that institutional features are also relevant. Further development of this idea seems a very promising stream of research.

Notwithstanding these encouraging results, we are well aware that certain limitations of the study should be born in mind. The first limitation is given by the single institutional setting that we use. All the firms in our sample are Italian so we could not differentiate firms according to the country of origin. We are aware that empirical findings in management are usually context specific and that any generalisation out of the specific context is difficult. Secondly, we could not control for other factors that are important in the alliance mode selection process such as the level of international experience or the degree of internationalisation, the intangible intensity and the kind of knowledge transferred through the agreements. Therefore, further analysis of the joint venture -non-equity alliance alternative that will include these factors would contribute to a better understanding of this choice.

Figure 1

 1 Figure 1 presents the conceptual framework of our research. The model illustrates the possible

Figure 1

 1 Figure 1 Factors affecting alliance mode choice

  representative of the Italian industrial and service structure. Firms operating in the traditional sectors cover 11% of the sample, scale-intensive firms are 34 %, the energy and utility sectors cover 9%, the trade sector 7% and the residual sector (mainly financial and telecommunication industries) represents 28% of the total sample.



  Risk reduction (Risk) i.e. product portfolio diversification; dispersion of fixed cost, etc. Economies of scale and or rationalization (Scale) i.e. lower cost by using the comparative advantage of each partner, etc.  Overcoming government-mandated investment or trade barriers (barriers); i.e. to operate as a "local" entity because of local partner, etc.  Co-opting or blocking competition (Comp); i.e. defensive joint ventures to reduce competition or offensive joint ventures to increase costs and/or lower market share for a third company, etc.  International expansion (Int exp); i.e. benefiting from local partner's know-how, etc.  Complementary technologies and patent (Compl-tech); i.e technological synergy or exchange of patents and territories, etc.

Table 1 :

 1 variable definition

			Hypothesis
	Construct	Variable definition and scale	(expected	Variable Name
			sign)
	Contractual form	JV =1 -Alliance = 0
		1. Primary activity		S_primary 1
	Nace Sector Code	2. Traditional sector		S_trad 2
		3. Scale-intensive sector		S_scale 3
	(Pavitt classification)	4. Specialized suppliers	H1	S_spec 4
		5. Science-based sectors	(-)	S_science 5
	Dummy variable	6. Energy sector , gas and water		S-enregy 6
		7. Wholesale trade and retail trade		S-trade 7
		8. Financial activity communication & other services		S_othersr 8
		Dummy variable:		Infras
	Value chain activities	1. Infrastructure	H2	R&D
		2. R&D	(-)	Proc
	involved in the agreement/JV	3. Procurement		Logistic
		4. Logistic		HR
	Dummy variable	5. Human resource Management		Prod
		6. Production		Mkting
		7. Marketing and Sales

Table 2 .

 2 Descriptive statistics and correlation table (dummy variables excluded)The results reported in table 3 are those of the general model (model 1) where the coefficients of the country variable have not been reported for reasons of simplicity (they are not statistically significant). The second model (model 2) is the restricted model where, due to the low significance of the coefficients, country ratings and the dummies on the geographical areas have been dropped. A likelihood ratio test comparing these two models confirms that the reduced model is as relevant as the full model. Overall, the model performs reasonably

		Mean	Std. D.	(1)	(2)	(3)	(4)	(5)	(6)
	cult_dist (1)	1.28	.989	1
	Costri (2)	39.37	14.61	-0.651 *	1
	Compet (3)	50.77	6.67	-0.624 *	0.544 *	1
	Rating (4)	94.30	11.81	-0.339 *	0.314 *	0.644 *	1
	Invpro (5)	6.018	1.61	-0.242 *	0.047	0.396 *	0.238 *	1
	Enfcon (6)	368.66	220.80	0.001	0.128 *	-0.310 *	-0.487 *	-0.181 *	1
	* = significant at the 0.01

Table 3 :

 3 Logistic regression results:

			Variable name	Model 1	Model 2
			Infras	.1472 (.1776)	.1648 (.1756)
	Function mainly	agreem. the in involved	R&D Proc Logistic Prod Mkting	-.4986** (.2175) -.0690 (.2962) -.2271 (.2598) .9215*** (.2047) -.3879** (.1748)	-.5039** (.2163) -.1021 (.2913) -.2386 (.2559) .9487*** (.2022) -.3554** (.1722)
			S_primary	1.263** (.6268)	1.307** (.6184)
			S_trad 2	.2725 (.2967)	.2547 (.2942)
			S_Scale 3	0.324 (.2365)	.0550 (.2307)
			S_Spec 4	.2817 (.3272)	.3040 (.3201)
	sector Industry		S_Science 5 S_energy 6 S_trade 7	1.234** (.5559) .3828 (.3010) -.2009 (.3057)	1.265** (.5519) .3702 (.2953) -.1822 (.3025)
			Invpro	-.1110 (.0821)	-.0949* (.0513)
			Enfcon	-.0004 (.0007)	-.0008** (.0004)
			Costri	-.0130 (.0132)	-.0139* (.0077)
			Cult-dist	-.1901 (.1330)	-.2038* (.1132)
			Small	-.6418 (.4704)	-.6100 (.4642)
	Size		Medium	-.5298*** (.2012)	-.5156*** (.1990)
			Compet	-.0529** (.0253)	-.0545*** (.0186)
			Rating	.0084 (.0143)	-
			Risk	-.1305 (.2027)	-.1491 (.2006)
			Scale	-.1588 (.2103)	-.1813 (.2065)
	strategy Internation		Compl-tech Comp Barriers Int exp	-.1532 (.1900) -.1310 (.1750) -3119 (.2989) .3770** (.1691)	-.1539 (.1877) -.1206 (.1723) -.2107 (.2747) .3915** (.1658)
			Log-likelihood;	-540.04403	-543.50815
			Chi-square (36, 26)	132.72	125.80
			Pseudo-R 2	0.1094	0.1037
			Correctly classified	65.64%	64.62%
			Area under ROC curve =	0.7124	0.7061
	Notes: (1) The sample consists of 879 observations; (2) For model 1 estimation results
	for the geographical area dummies are not reported in the table for the sake of
	simplicity. None of the variables not reported are statistically significant (3) Standard
	errors are in brackets. The symbol * denotes that the coefficient is significant at the
	10% level, ** 5% level and *** at a 1% level


Federico Aschieri

Margherita Zorzi

Eliminating Skolem Functions in Peano Arithmetic with Interactive Realizability

Keywords:

We present a new syntactical proof that first-order Peano Arithmetic with Skolem axioms is conservative over Peano Arithmetic alone for arithmetical formulas. This result -which shows that the Excluded Middle principle can be used to eliminate Skolem functions -has been previously proved by other techniques, among them the epsilon substitution method and forcing. In this paper, we employ Interactive Realizability, a computational semantics for Peano Arithmetic which extends Kreisel's modified realizability to the classical case.

Introduction

For a long time it has been known that intuitionistic realizability can be used as a flexible tool for obtaining a wealth of unprovability, conservativity and proof-theoretic results [START_REF] Troelstra | Notions of Realizability for Intuitionistic Arithmetic and Intuitionistic Arithmetic in all Finite Types[END_REF][START_REF] Troelstra | Realizability[END_REF]. As title of example, with Kreisel's modified realizability [16], one can show the unprovability of Markov Principle in Heyting Arithmetic in all finite types (HA ω ) and the conservativity of HA ω with the Axiom of Choice (AC) over HA ω for negative formulas. In both cases, one starts by showing that any formula provable in one of those systems can be shown to be realizable in HA ω . In the first case, one proves that the realizability of Markov Principle implies the solvability of the Halting Problem, and concludes that Markov Principle is unprovable in HA ω . In the second, one exploits the fact that the assertion "t realizes A" is exactly the formula A when A is negative and concludes that HA ω proves A.

The situation in classical logic has been very different: for a long time it did not exist any realizability notion suitable to interpret directly classical proofs, let alone proving independence or conservation results. However, recently several classical realizability interpretations have been put forward. Among them: Krivine's classical realizability [START_REF] Krivine | Typed lambda-calculus in classical Zermelo-Fraenkel set theory[END_REF], which has been shown in [START_REF] Krivine | Realizability Algebras 2: new models of ZF + DC, Logical Methods in Computer Science[END_REF] to yield striking unprovability results in Zermelo-Fraenkel set theory, and Interactive realizability [1, 4, 6, 7], which has been shown in [3,6] to provide conservation results for Π 0 2 -formulas. Being a tool for extracting programs from proofs, it is however quite natural that Interactive realizability is capable of producing Π 0 2 -conservativity results. The aim of this paper is to prove that Interactive realizability can as well be used to prove other conservativity results. In particular, let us consider first-order classical Peano Arithmetic PA, which is HA + EM, where EM is the excluded middle over arithmetical formulas. Then we give a new syntactic proof that PA with the Skolem axiom scheme SK is conservative over PA for arithmetical formulas -a result first syntactically proven by Hilbert and Bernays [15] by means of the epsilon substitution method. The result is particularly interesting since it implies that classical choice principles can be eliminated by using the excluded middle alone. The structure of our proof resembles the pattern of the intuitionistic-realizability conservation proofs we have sketched above and allows to obtain a stronger result. Namely, we shall show that if an arithmetical formula A is provable in HA ω + EM+ SK, then the assertion "t realizes A" is provable in HA ω alone. Afterwards, we shall show the provability in HA ω + EM of the assertion "(t realizes A) implies A" and thus conclude that HA ω + EM proves A. Since this latter system is conservative over PA for arithmetical formulas, we obtain the result.

In our opinion, there are at least two reasons our proof technique is interesting. First, it does not lead to an exponential increase in the size of the proof, when passing from a proof in HA ω + EM + SK to a corresponding proof in HA + EM: our transformation is polynomial. To the best of our knowledge, there is only another method that does equally well, which is Avigad's [9]. The technique of Avigad is related to ours since it uses the method of forcing, in which the conditions are finite approximations of the Skolem functions used in the proof. With forcing one avoids speaking about infinite non-computable objects (i.e. the Skolem functions) and can approximate the original proof. Avigad's method is very simple and elegant when there is only one Skolem function to eliminate, but it becomes more complicated and difficult to handle when dealing with several Skolem functions. In fact, a nesting of the notion of forcing together with a technical result about elimination of definitions become necessary and the method looses some intuitive appeal. Instead, the use of Interactive realizability allows to deal with all the Skolem functions at the same time, and we conjecture that the resulting proofs are much shorter than the ones obtained by forcing. Moreover, the method of forcing seems a bit "magical" and it is much more natural to talk about states and approximations when dealing with programs.

Secondly, the theory of Interactive realizability offers a uniform explanation of a number of different phenomena. Rather than proving each particular meta-theoretic result about classical Arithmetic with an ad-hoc technique, one employs a single methodology. For example, one may prove conservativity of PA over HA for Π 0 2 -formulas by a negative translation followed by Friedman's translation [12]; one may extract from proofs terms of Gödel's System T by realizability or functional interpretations [13]; one may prove the result about the elimination of Skolem functions with forcing; one may extract from proofs strategies in backtracking Tarski games by analyzing sequent calculus proofs [11]; one may obtain a simple ordinal analysis of PA + SK by using update procedures [8]. Instead, with the theory of Interactive realizability one obtains all the results above as a consequence of a single concept (see [3,5,7]).

Plan of the paper

In Section §2 we review the term calculus T Class in which Interactive realizers are written, namely an extension of Gödel's system T plus Skolem function symbols for a countable collection of Skolem functions. In Section §3 we recall Interactive realizability, as described in [7], a computational semantics for HA ω + EM + SK, an arithmetical system with functional variables which includes first-order classical Peano Arithmetic and Skolem axioms. In Section §4 we use Interactive realizability to prove the conservativity of HA ω +EM+SK over HA ω + EM for arithmetical formulas. In Section §5 we explain in more detail how to formalize the proofs of Section 4 in HA ω + EM and HA + EM.

The Term Calculus T Class

In this section we follow [7] and recall the typed lambda calculi T and T Class in which interactive realizers are written. T is an extension of Gödel's system T (see Girard [14]) with some syntactic sugar. The basic objects of T are numerals, booleans, and its basic computational constructs are primitive recursion at all types, if-then-else, pairs, as in Gödel's T. T also includes as basic objects finite partial functions over N and simple primitive recursive operations over them. T Class is obtained from T by adding on top of it a collection of Skolem function symbols Φ 0 , Φ 1 , Φ 2 , . . . , of type N → N, one for each arithmetical formula. The symbols are inert from the computational point of view and realizers are always computed with respect to some approximation of the Skolem maps represented by Φ 0 , Φ 1 , Φ 2 , . . ..

Updates

In order to define T , we start by introducing the concept of "update", which is nothing but a finite partial function over N. Realizers of atomic formulas will return these finite partial functions, or "updates", as new pieces of information that they have learned about the Skolem function Φ 0 , Φ 1 , . . .. Skolem functions, in turn, are used as "oracles" during computations in the system T Class . Updates are new associations input-output that are intended to correct, and in this sense, to update, wrong oracle values used in a computation.

Definition 1 (Updates and Consistent Union). We define:

1. An update set U , shortly an update, is a finite set of triples of natural numbers representing a finite partial function from N 2 to N.

2.

Two triples (a, n, m) and (a

′ , n ′ , m ′ ) of numbers are consistent if a = a ′ and n = n ′ implies m = m ′ . Two updates U 1 , U 2 are consistent if U 1 ∪ U 2 is an update.
3. U is the set of all updates.

The consistent union

U 1 U U 2 of U 1 , U 2 ∈ U is U 1 ∪ U 2
minus all triples of U 2 which are inconsistent with some triple of U 1 .

The consistent union U 1 U U 2 is an non-commutative operation: whenever a triple of U 1 and a triple of U 2 are inconsistent, we arbitrarily keep the triple of U 1 and we reject the triple of U 2 , therefore for some U 1 , U 2 we have

U 1 U U 2 = U 2 U U 1 . U represents a way of selecting a consistent subset of U 1 ∪ U 2 , such that U 1 UU 2 = ∅ =⇒ U 1 = U 2 = ∅.

The System T

T is formally described in figure 1. Terms of the form if A t 1 t 2 t 3 will be sometimes written in the more legible form if t 1 then t 2 else t 3 . A numeral is a term of the form S(. . . S(0) . . .). For every update U ∈ U, there is in T a constant U : U, where U is a new base type representing U. We write ∅ for ∅. In T , there are four operations involving updates (see figure 1):

1. The first operation is denoted by the constant min : U → N. min takes as argument an update constant U ; it returns the minimum numeral a such that (a, n, m) ∈ U for some n, m ∈ N, if any exists; it returns 0 otherwise.

2.

The second operation is denoted by the constant get : U → N 3 → N. get takes as arguments an update constant U and three numerals a, n, l; it returns m if (a, n, m) ∈ U for some m ∈ N (i.e. if (a, n) belongs to the domain of the partial function U ); it returns l otherwise.

3.

The third operation is denoted by the constant mkupd : N 3 → U. mkupd takes as arguments three numerals a, n, m and transforms them into (the constant coding in T ) the update {(a, n, m)}.

4.

The forth operation is denoted by the constant ⋒ : U 2 → U. ⋒ takes as arguments two update constants and returns the update constant denoting their consistent union.

We observe that the constants min, get, mkupd are just syntactic sugar and may be avoided by coding finite partial functions into natural numbers. System T may thus be coded in Gödel's T.

Types σ, τ

::= N | Bool | U | σ → τ | σ × τ Constants c ::= Rτ | ifτ | 0 | S | True | False | min | get | mkupd | ⋒ | U (∀U ∈ U) Terms t, u ::= c | x τ | tu | λx τ u | t, u | π0u | π1u
Typing Rules for Variables and Constants

x τ : τ | 0 : N | S : N → N | True : Bool | False : Bool | U : U (for every U ∈ U) | ⋒ : U → U → U | min : U → N | get : U → N → N → N → N | mkupd : N → N → N → U | ifτ : Bool → τ → τ → τ | Rτ : τ → (N → (τ → τ )) → N → τ
Rτ uv0 → u Rτ uvS(t) → vt(Rτ uvt) ifτ True u v → u ifτ False u v → v πi u0, u1 → ui, i = 0, 1
plus the following ones, assuming a, n, m, l be numerals:

min U → a if ∃m, n. (a, n, m) ∈ U ∧ ∀(b, i, j) ∈ U. a ≤ b 0 otherwise U 1 ⋒ U 2 → U1 U U2 get U a n l → m if ∃m. (a, n, m) ∈ U l otherwise mkupd a n m → {(a, n, m)} Figure 1 the extension T of Gödel's system T As proved in [1, 4],
T is strongly normalizing, has the uniqueness-of-normal-form property and the following normal form theorem also holds.

Lemma 2 (Normal Form Property for T + C + R). Assume that R is a functional set of reduction rules for C. Assume A is either an atomic type or a product type. Then any closed normal term t ∈ T of type A is: a numeral n : N, or a boolean True, False : Bool, or an update constant U : U, or a constant of type A, or a pair u, v : B × C.

The System T Class

We now define a classical extension of T , that we call T Class , with a Skolem function symbol for each arithmetical formula. The elements of T Class will represent (non-computable) realizers.

Definition 3 (The System T Class ). Define T Class = T + SC, where SC is a countable set of Skolem function constants, each one of type N → N. We assume to have an enumeration Φ 0 , Φ 1 , Φ 2 , . . . of all the constants in SC (while generic elements of SC will be denoted with letters Φ, Ψ, . . .).

Every Φ ∈ SC represents a Skolem function for some arithmetical formula ∃y N A(x, y), taking as argument a number x and returning some y such that A(x, y) is true if any exists, and an arbitrary value otherwise. In general, there is no set of computable reduction rules for the constants in SC, and therefore no set of computable reduction rules for T Class . Each (in general, non-computable) term t ∈ T Class is associated to a set {t[s] |s ∈ T , s : N 2 → N} ⊆ T of computable terms we call its "approximations", one for each term s : N 2 → N of T , which is thought as a sequence s 0 , s 1 , s 2 , . . . of computable approximations of the oracles Φ 0 , Φ 1 , Φ 2 , . . . (with s i we denote s(i)).

Definition 4 (Approximation at State

). 1. A state is a closed term of type N 2 → N of T . If i is a numeral, with s i we denote s(i).

Assume t ∈ T Class and s is a state. The "approximation of t at a state s" is the term t[s]

of T obtained from t by replacing each constant Φ i with s i .

3 Interactive Realizability for HA ω + EM + SK

In this section we introduce a notion of realizability based on interactive learning for HA ω + EM + SK, Heyting Arithmetic in all finite types (see e.g. Troelstra [START_REF] Troelstra | Constructivism in Mathematics[END_REF]) plus Excluded Middle and Skolem axiom schemes for all arithmetical formulas. Then we prove our main Theorem, the Adequacy Theorem: "if a closed formula is provable in HA ω + EM + SK, then it is realizable". We first define the formal system HA ω + EM + SK. We represent atomic predicates of HA ω +EM+SK with closed terms of T Class of type Bool. Terms of HA ω +EM+SK are elements of T Class and thus may include the function symbols in SC. We assume having in Gödel's T some terms ⇒ Bool : Bool → Bool → Bool, ¬ Bool : Bool → Bool, ∨ Bool : Bool → Bool → Bool . . ., implementing boolean connectives. As usual, we shall use infix notation: for example, we write t 1 ⇒ Bool t 2 in place of ⇒ Bool t 1 t 2 and similarly for the other connectives.

Language of HA ω + EM + SK

We now define the language of the arithmetical theory HA ω + EM + SK.

Definition 5 (Language of HA ω + EM + SK). The language L Class of HA ω + EM + SK is defined as follows. 1. The terms of L Class are all t ∈ T Class .

The atomic formulas of L

Class are all Q ∈ T Class such that Q : Bool.
3. The formulas of L Class are built from atomic formulas of L Class by the connectives ∨, ∧, → , , ∀, ∃ as usual, with quantifiers possibly ranging over variables x τ , y τ , z τ , . . . of arbitrary finite type τ of T Class .

4.

A formula of L Class is said arithmetical if it does not contain constants in SC and all its quantifiers range over the type N, i.e. it has one of the following forms: ∀x N A, ∃x N A, A ∨ B, A ∧ B, A → B, A B, P , with A, B arithmetical and P atomic formula of T .

We denote with ⊥ the atomic formula False and with ¬A the formula A → ⊥. A B is the dual of implication as in bi-intuitionistic logic and means "A and the opposite of B". If F is a formula of L Class in the free variables x τ1 1 , . . . , x τn n and t 1 : τ 1 , . . . , t n : τ n are terms of L Class , with F (t 1 , . . . , t n ) we shall denote the formula

F [t 1 /x 1 , . . . , t n /x n ]. Sequences of variable x N 1 , . . . ,
x N k will be written as x. We denote with x a term of T in the free numeric variables x representing a injection of N k into N. Moreover, for every sequence of numerals n = n 1 , . . . , n k , we define n := x [ n/ x] and assume that the function n → n is a bijection.

The Excluded Middle axiom scheme EM is defined as the set of all formulas of the form:

∀ x N . A( x) ∨ ¬A( x)
where A is an arithmetical formula.

The Skolem axiom scheme SK contains for each arithmetical formula A( x, y) an axiom:

∀ x N . ∃y N A( x, y) → A( x, Φ x )
with Φ ∈ SC. We assume that for every Φ ∈ SC there is in SK one and only one formula in which Φ occurs. Such unique formula A is said to be the formula associated to Φ and Φ will be sometimes written as Φ A . If s is a state and Φ i = Φ A , with s A we denote s i and with mkupd A u t we denote mkupd i u t.

For each formula F of L Class , its involutive negation F ⊥ is defined by induction on F . First, we say that an atomic formula P is positive if it is of the form ¬ Bool . . . ¬ Bool Q, Q is not of the form ¬ Bool R, and the number of ¬ Bool in front of Q is even. Then we define:

(¬ Bool P ) ⊥ = P (if P positive) P ⊥ = ¬ Bool P (if P positive) (A ∧ B) ⊥ = A ⊥ ∨ B ⊥ (A ∨ B) ⊥ = A ⊥ ∧ B ⊥ (A → B) ⊥ = A B (A B) ⊥ = A → B (∀x τ A) ⊥ = ∃x τ A ⊥ (∃x τ A) ⊥ = ∀x τ A ⊥ As usual, one has (F ⊥ ) ⊥ = F .
Definition 6 (Set Γ ). We fix an arbitrary finite set Γ of arithmetical formulas A( x, y) of L Class .

In the following, the set Γ will serve as a parameter in order to relativize the definitions of the realizability relation and of the ordering of states given in [7]. The idea is that we shall have to interpret proofs in the system HA ω + EM + SK and each one of them will use only a finite number of instances of EM and SK. Thus, realizers will contain only a finite number of Skolem functions, each one of them corresponding to some formula in Γ . The restriction of all the concepts to the set Γ is necessary in order to avoid to speak about the truth of an infinite number of formulas in the definitions we are going to give. In such a way, with a proper choice of Γ we shall be able to interpret any given proof of HA ω + EM + SK.

Truth Value of a Formula in a State

The axioms of the system HA ω + EM + SK give a great computational power to the system T Class : one can "compute" by a term χ F of T Class the truth value of any arithmetical formula F . When one effectively evaluates χ F in a particular state s, we say that one computes the truth value of a formula F in a state s.

Definition 7 (Truth Value of a Formula F in a State s). For every arithmetical formula F ( x) of L Class we define, by induction on F , a term χ F : Bool of system T Class , with the same free variables of F :

χ P = P, P atomic χ A∨B = χ A ∨ Bool χ B χ ∀y N A = χ A [Φ A ⊥ x /y] χ A B = χ A ∧ Bool χ B ⊥ χ A∧B = χ A ∧ Bool χ B χ ∃y N A = χ A [Φ A x /y] χ A→B = χ A ⇒ Bool χ B
We define F s := χ F [s] and call it the truth value of F in the state s.

Intuitively, if F ( n) is a closed formula, our intended interpretation is:

1. χ F ( n) is a term of T Class denoting, in any standard model of HA ω + EM + SK, the truth value of F ( n). 2. F s ( n) is a term of T computing
what would be the truth value of F ( n) in some standard model of HA ω +EM under the (possible false) assumption that the interpretation mapping Φ i to s i satisfies the axioms of SK.

We remark that thus F s ( n) is only a conditional truth value: if F s ( n) is not the correct truth value of F ( n) -it may well happen -then the interpretation mapping Φ i in s i does not satisfy the axioms of SK. This subtle point is what makes possible learning in Interactive realizability: whenever a contradiction follows, realizers are able to effectively find counterexamples to the assertion that the interpretation mapping Φ i in s i satisfies the axioms of SK. We also observe that this way of computing the truth of a formula comes from the epsilon substitution method (see Avigad [8], Mints et al. [START_REF] Mints | Epsilon Substitution Method for Elementary Analysis[END_REF]).

Every state s is considered as an approximation of the Skolem functions denoted by the constants of SC: for each formula A, s A may be a correct approximation of Φ A on some arguments, but wrong on other ones. More precisely, we are going to consider the set def(s) of the pairs (i, n ) such that Φ i = Φ A and A ∈ Γ ⇒ ∃y N A( n, y) → A( n, s i n ) is true as the real "domain" of s, representing the set of arguments at which s i is surely a correct approximation of Φ i , in the sense that s i returns an appropriate witness if any exists. We point out that if

Φ i = Φ A and A / ∈ Γ , then trivially (i, n ) ∈ def(s).
The choice is made just for technical convenience, since one is not interested in the behaviour of s outside Γ . We also define an ordering between states: we say that s ′ ≥ s if, intuitively, s ′ is at least as good an approximation as s. Thus, we ask that if s is a correct approximation at argument (i, n ) also s ′ is and in particular s ′ i n = s i n .

Definition 8 (Domains, Ordering between States). 1. We define

def(s) = {(i, n ) | Φ i = Φ A and (A ∈ Γ ⇒ ∃y N A( n, y) → A( n, s i n )}
where i and n range over numerals and sequences of numerals.

2.

Let s and s ′ be two states. We define s ′ ≥ s if and only if for all (i, n ), (i, n ) ∈ def(s)

implies s i n = s ′ i n .
We remark that by definition, s ′ ≥ s implies def(s ′ ) ⊇ def(s) and that thanks to the restriction to Γ the relation s ′ ≥ s is arithmetical, because the condition (i, n ) ∈ def(s) is non-trivial only for finitely many i. From now onwards, for every pair of terms t 1 , t 2 of system T , we shall write t 1 = t 2 if they are the same term modulo the equality rules corresponding to the reduction rules of system T (equivalently, if they have the same normal form).

Interactive Realizability

For every formula A of L Class , we now define what type |A| a realizer of A must have.

Definition 9 (Types for realizers). For each formula A of L Class we define a type |A| of T Class by induction on A: The ideas behind the definition of s in the case of HA ω + EM + SK are those we already explained in [7]. A realizer is a term t of T Class , possibly containing some non-computable Skolem function of SC; if such a function was computable, t would be an intuitionistic realizer. Since in general t is not computable, we calculate its approximation t[s] at state s. t is an intelligent, self-correcting program, representing a proof/construction depending on the state s. The realizer interacts with the environment, which may provide a counter-proof, a counterexample invalidating the current construction of the realizer. But the realizer is always able to turn such a negative outcome into a positive information, which consists in some new piece of knowledge learned about some Skolem function Φ i .

|P | = U, if P is atomic |A ∧ B| = |A| × |B| |∃x τ A| = τ × |A| |A B| = |A| × |B ⊥ | |A ∨ B| = Bool × (|A| × |B|) |∀x τ A| = τ → |A| |A → B| = |A| → |B| Let now p 0 := π 0 : σ 0 × (σ 1 × σ 2 ) → σ 0 , p 1 := π 0 π 1 : σ 0 × (σ 1 × σ 2 ) → σ 1 and p 2 := π 1 π 1 : σ 0 × (σ 1 × σ 2 ) → σ 2 be the three canonical projections from σ 0 × (σ 1 × σ 2 ).
The next proposition tells that realizability at state s respects the notion of equality of T Class terms, when the latter is relativized to state s. That is, if two terms are equal at the state s, then they realize the same formulas in the state s.

Proposition 11 (Saturation). If t 1 [s] = t 2 [s] and u 1 [s] = u 2 [s], then t 1 s B[u 1 /x] if and only if t 2 s B[u 2 /x].
Proof. By straightforward induction on A. ◭ In the following, we use a standard natural deduction system for HA ω +EM+SK, together with a term assignment in the spirit of Curry-Howard correspondence for classical logic. We denote with HA ω + EM + SK ⊢ t : A the derivability relation in that system, where t is a term of T Class and A is a formula of L Class . All details can be found in [4], [7].

The main theorem about Interactive realizability is the Adequacy Theorem: if a closed formula is provable in HA ω + EM + SK, then it is realizable (see [7] for a proof).

Theorem 12 (Adequacy Theorem). If A is a closed formula such that HA ω +EM+SK ⊢ t : A and all the subformulas of the instances of EM and SK used in the derivation belong to Γ , then t A.

4 Conservativity of HA ω + EM + SK over HA ω + EM (HA + EM)

The aim of this section is to use Interactive realizability in order to prove that for every arithmetical formula A, if HA ω + EM + SK ⊢ A then HA ω + EM ⊢ A (HA + EM ⊢ A). Since we know by the Adequacy Theorem 12 that HA ω +EM+SK ⊢ A implies HA ω +EM+SK ⊢ t : A and HA ω proves t A, our goal is to show in HA ω + EM that t A implies A.

The intuitive reason this latter result is true is the following: one can always find an approximation s of the Skolem functions of t which is good enough to contain all the information needed by t to compute the true witnesses for A against any particular purported counterexample. The idea is that one has only to collect finitely many values of each Skolem function called during the execution of the program represented by t. To this end, it suffices to invoke the excluded middle a number of times which, intuitively, can be expressed in a proof formalizable in HA ω + EM. This is possible because HA ω + EM is strong enough to prove the normalization of each term t of T Class with respect to any interpretation of its Skolem functions. Finally, if there existed a counterexample to A, it would be possible to falsify the construction of the realizer t in the state s. Since t is a self-correcting program, it would be able to correct one of the values of s it has used in the computation of some witness for A. But s is constructed as to be correct on all the values used by t, which entails a contradiction.

For example, let A = ∃x N ∀y N ∃z N P (x, y, z). Then one can find a state s which contains all the values of the Skolem functions needed to compute n = π 0 t[s]. Suppose a counterexample m to the formula ∀y N ∃z N P (n, y, z) existed. Then one can find a state s ′ ≥ s which contains all the values of the Skolem functions needed to compute l = π 0 ((π 1 t)m) [s ′ ]. Now, we would have that P (n, m, l) is false; thus, π 1 ((π 1 t)m) [s ′ ] would be equal to some update U containing some corrections to s ′ . We shall show that this will not be the case, and the intuitive reason is that s ′ can be chosen as to be correct everywhere it is needed.

We now elaborate our argument. We start with a definition axiomatizing the informal concept that a state s contains all the information needed to compute the normal form of a term t of ground type. Namely, if for every s ′ extending s the evaluation of t in the state s ′ gives the same result obtained evaluating t in s, then we may assume all the relevant information is already in s.

Definition 13 (Definition of a term in a state s). For every state s and term t of T Class of atomic type, we define t ↓ s (and we say "t is defined in s") as the statement: for all states

s ′ ≥ s, t[s ′ ] = t[s].
◮ Remark. There is another, perhaps more intuitive way to express the concept of "being defined in the state s". For every state s we may define a binary reduction relation s → ⊆ T Class × T Class as follows: t s → u if either t → u in T Class or u is obtained from t by replacing one of its subterms Φ i (n) with a numeral m = s i (n) such that (i, n) ∈ def(s). Then one could say that t is defined in s if t s → a where a is either a numeral, a boolean or an update. Though this approach works well, it is unsuitable to be directly formalized in HA ω , because in that system one cannot express this syntactical reasoning on terms.

We now define for every type τ a set of "computable" terms of type τ by means of the usual Tait-style computability predicates [START_REF] Tait | Intensional Interpretations of Functional of Finite Type[END_REF]. In our case, following the approach of the previous discussion, we consider a term t of ground type to be computable if for every state s, one can find a state s ′ ≥ s such that t is defined in s ′ . The notion is lifted to higher types as usual.

Definition 14 (Computable terms).

For every type τ of T Class , we define a set of closed terms of T Class of type τ as follows:

N ={t : N | for all states s there is a state s ′ ≥ s such that t ↓ s ′ } Bool ={t : Bool | for all states s there is a state s ′ ≥ s such that t ↓ s ′ } U ={t : U | for all states s there is a state

s ′ ≥ s such that t ↓ s ′ } τ → σ ={t | ∀u ∈ τ . tu ∈ σ } τ × σ ={t | π 0 t ∈ τ and π 1 t ∈ σ }
In order to show that every term t in T Class is computable, as usual we need to prove that the set of computable terms is saturated with respect to some suitable relation. In our case, to terms are related if they are equal in all states greater than some state.

Lemma 15. For every term t : ρ of T Class , if for every state s there exists a state s ′ ≥ s and u ∈ T such that for all state

s ′′ ≥ s ′ , t[s ′′ ] = u[s ′′ ], then t ∈ T .
Proof. By induction on the type ρ. ρ = N. Let s be a state. We have to show that there exists a state r ≥ s such that t ↓ r . By assumption on t there exists a state s ′ ≥ s and u ∈ N such that for all

s ′′ ≥ s ′ , t[s ′′ ] = u[s ′′ ]. Since u ∈ N , there exists s ′′ ≥ s ′ such that u ↓ s ′′ . Let r = s ′′ ; we prove t ↓ r . Let r ′ ≥ r. We have that u[r ′ ] = u[r], by u ↓ r , and t[r ′ ] = u[r ′ ], since r ′ ≥ s ′ . Hence, t[r ′ ] = u[r] = t[r]
. We conclude t ↓ r and finally t ∈ N . ρ = Bool, U: as for the case ρ = N. ρ = τ → σ. Let v ∈ τ . We have to show that tv ∈ σ . Let s be any state. By assumption on t there exist a state s ′ ≥ s and u ∈ τ → σ such that for all s ′′ ≥ s ′ , t[s ′′ ] = u[s ′′ ]. Therefore for all s ′′ ≥ s ′ , tv[s ′′ ] = uv[s ′′ ] and uv ∈ σ . Hence, by induction hypothesis, tv ∈ σ . ρ = τ 0 × τ 1 . Let i ∈ {0, 1}, we have to show that π i t ∈ τ i . Let s be any state. By assumption on t there exist s ′ ≥ s and u ∈ τ 0 × τ 1 such that for all

s ′′ ≥ s ′ , t[s ′′ ] = u[s ′′ ]. Therefore for all s ′′ ≥ s ′ , π i t[s ′′ ] = π i u[s ′′ ] and π i u ∈ τ i . Hence, by induction hypothesis π i t ∈ τ i .

◭

We are now ready to prove, by using the excluded middle alone, that every term t of T Class is computable.

Theorem 16 (Computability Theorem).

Let v : τ be a term of T Class and suppose that all the free variables of v are among x σ1 1 , . . . ,

x σn n . If t 1 ∈ σ 1 , . . . , t n ∈ σ n , then v[t 1 /x σ1 1 , . . . , t n /x σn n ] ∈ τ .
Proof. We proceed by induction on v. We first remark that if u = t and t ∈ τ , then u ∈ τ by trivial application of Lemma 15.

◮ Notation 1. For any term w in T Class , we denote w[t 1 /x σ1 1 , . . . , t n /x σn ] with w.

1. v is a variable x σi i : σ i and τ = σ i . Then, v = t 1 ∈ σ i = τ .
2. v is 0, True, False, U : trivial.

3. v is uw, then by means of typing rules, u : σ → τ , w : σ. Since by induction hypothesis u ∈ σ → τ and w ∈ σ , we obtain v = uw ∈ τ .

4. v is λx τ1 .u : τ 1 → τ 2 .
Then, by means of typing rules, u : τ 2 . Suppose now, for a term t : τ 1 in T Class , that t ∈ τ 1 . We have to prove that vt ∈ τ 2 . We have:

vt = (λx τ1 .u)[t 1 /x σ1 1 • • • t n /x σn n ]t = (λx τ1 u)t[t 1 /x σ1 1 • • • t n /x σn n ] = u[t/x τ1 ][t 1 /x σ1 1 • • • t n /x σn n ] = u[t/x τ1 t 1 /x σ1 1 • • • t n /x σn n ]
By induction hypothesis, this latter term belongs to τ 2 . We conclude vt ∈ τ 2 .

5. v is u, w : τ 0 × τ 1 . By means of typing rules, u : τ 0 , w : τ 1 and by induction hypothesis

π 0 v = u ∈ τ 0 and π 1 v = w ∈ τ 1 . The thesis v ∈ τ 0 × τ 1 follows by definition. 6. v is π i (u) : τ i , i = 0, 1, where u : τ 0 × τ 1 . π i u ∈ τ i because u ∈ τ 0 × τ 1 by induction hypothesis. 7. v is if τ : Bool → τ → τ → τ . Suppose that u ∈ Bool , u 1 ∈ τ , u 2 ∈ τ .
Then, for all states s there exists s ′ ≥ s such that u ↓ s ′ . We have to prove that if τ uu 1 u 2 ∈ τ . Let s be a state and let s ′ ≥ s be such that u

↓ s ′ . If u[s ′ ] = True, then for all s ′′ ≥ s ′ , if τ uu 1 u 2 [s ′′ ] = u 1 [s ′′ ] and u 1 ∈ τ . If u[s ′ ] = False, then for all s ′′ ≥ s ′ , if τ uu 1 u 2 [s ′′ ] = u 2 [s ′′ ] and u 2 ∈ τ . By Lemma 15, we conclude if τ uu 1 u 2 ∈ τ . 8. v is R τ : τ → (N → (τ → τ )) → N → τ . Suppose that u ∈ τ , w ∈ N → (τ → τ ) , z ∈ N .
We have to prove that R τ uwz ∈ τ . By a plain induction, it is possible to prove, for each numeral n, R τ uwn ∈ τ . Let s be a state and let s ′ ≥ s be such that z

↓ s ′ . Let z[s ′ ] = n with n numeral. Then for all s ′′ ≥ s ′ , R τ uvz[s ′′ ] = R τ uvn[s ′′ ] ∈ τ
By Lemma 15, we conclude R τ uwz ∈ τ . 9. v is min : U → N. Suppose, for a term u in T Class , that u ∈ U . Let s be a state. Since u ∈ U , there exists s ′ ≥ s such that u ↓ s ′ . We have to prove that min u ∈ N .

There exists an update U such that for all s ′′ ≥ s ′ , u[s ′′ ] = U . Then for all s ′′ ≥ s ′ , min u[s ′′ ] = min U = n for some numeral n. By definition of N , min u ∈ N .

10. v is ⋒ : U → U → U.
Suppose that u 1 ∈ U and u 2 ∈ U . We have to prove that ⋒ u 1 u 2 ∈ U . Let s be a state. Since u 1 ∈ U there exists s ′ ≥ s such that u 1 ↓ s ′ . Since u 2 ∈ U , there exists s ′′ ≥ s ′ such that u 2 ↓ s ′′ . Therefore, there exist two constants U 1 and U 2 such that for all

s ′′′ ≥ s ′′ , u 1 [s ′′′ ] = U 1 and u 2 [s ′′′ ] = U 2 . Finally, for all s ′′′ ≥ s ′′ , ⋒ u 1 u 2 [s ′′′ ] = ⋒ U 1 U 2 = U 3
and by definition of U , ⋒ u 1 u 2 ∈ U .

11. v is S, mkupd or get. Analogous to the previous case.

12. v is a constant Φ i : N → N in SC. Suppose now, for a term u : N, that u ∈ N . We have to prove that Φ i u ∈ N . Let s be a state. We must show that there exists a s ′ ≥ s such that

Φ i u ↓ s ′ . Since u ∈ N , there exists a state s ′ ≥ s such that u ↓ s ′ . Let n = u[s ′ ],
with n numeral, and

m = s ′ i (n). Let Φ i = Φ A(x,y) . If A / ∈ Γ , then trivially (i, n) ∈ def(s ′ ) by definition 8. Therefore for all s ′′ ≥ s ′ , Φ i u[s ′′ ] = s ′′ i (n)
= m and we are done. Hence, we may assume A ∈ Γ . There are two cases, and this is the only point of this proof in which we use EM.

a. A(n, m) is true. Therefore, for all s ′′ ≥ s ′ , s ′′ i (n) = m because (i, n) ∈ def(s ′ ). Thus, for all s ′′ ≥ s ′ , Φ i u[s ′′ ] = s ′′ i (n) = m, which is the thesis. b. A(n, m) is false. If there exists l such that A(n, l) is true, then let s ′′ := λx N λy N . if x = i ∧ Bool y = n then m else s ′ x (y) Then, for all s ′′′ ≥ s ′′ , s ′′′ i (n) = l because (i, l) ∈ def(s ′′ ). Thus, for all s ′′′ ≥ s ′′ , Φ i u[s ′′′ ] = s ′′′ i (n) = l, which is the thesis. If there is no l such that A(n, l) is true, then trivially (i, n) ∈ def(s ′ ). Thus for all s ′′ ≥ s ′ , Φ i u[s ′′ ] = s ′′ i (n)
= m and we are done.

◭

According to the Definition 7 of the truth value A s of a formula A in a state s, when we compute A s we need only a finite number of Skolem function values, one for each quantifier of A. Thus, we can show with the excluded middle that for every state s there exists a state s ′ ≥ s such that when we evaluate A in the state s ′ we obtain the real truth value of A. Proposition 17. Let A( x) be any arithmetical formula and n be numerals. For every state s, there exists a state s ′ ≥ s such that A s ′ ( n) = True if and only if A( n) is true.

Proof. We prove the thesis by induction on A. Let s be any state. The cases in which A is atomic or A = B ∨ C, B ∧ C, B → C are trivial. Let us consider those in which A starts with a quantifier.

A( n) = ∃y N B( n, y). By the excluded middle, we extend s to a state

s ′ ≥ s such that m = s ′ B n implies that ∃y N B( n, y) → B( n, m)
By induction hypothesis, there exists a state s ′′ ≥ s ′ such that B( n, m) is true if and only if

B s ′′ ( n, m) = χ B ( n, m)[s ′′ ] = True Assuming Φ i = Φ B , since (i, n ) ∈ def(s ′ ), we have s ′′ B n = s ′ B n . Since A s ′′ ( n) = χ B ( n, Φ B n )[s ′′ ] = χ B ( n, m)[s ′′ ]
and A( n) is equivalent to B( n, m), we obtain the thesis.

A( n) = ∀y N B( n, y). By the excluded middle, we extend s to a state

s ′ ≥ s such that m = s ′ B ⊥ n implies that ∃y N B ⊥ ( n, y) → B ⊥ ( n, m)
By induction hypothesis, there exists a state s ′′ ≥ s ′ such that B ⊥ ( n, m) is true if and only if

(B ⊥ ) s ′′ ( n, m) = χ B ⊥ [s ′′ ]( n, m) = True Assuming Φ i = Φ B ⊥ , since (i, n ) ∈ def(s ′ ), we have s ′′ B ⊥ n = s ′ B ⊥ n . Since A s ′′ ( n) = χ B ⊥ ( n, Φ B ⊥ n )[s ′′ ] = χ B ⊥ ( n, m)[s ′′ ]
we obtain the thesis.

◭

Now we prove a special case of the statement that the realizability of a formula implies the formula itself. Namely, we show that t realizes ⊥ implies ⊥. The idea, as we have explained before, is to find a state s which contains all the information needed to evaluate t.

Theorem 18 (Consistency of Interactive Realizability). For every closed term t of T Class , t ⊥. In particular, for every state s, there exists a state s ′ ≥ s such that t s ′ ⊥.

Proof. Suppose, for the sake of contradiction, that there exists a term t such that t ⊥. Let s be any state. Since t : U, by theorem 16 we have t ∈ U and therefore there exists a state r ≥ s such that t ↓ r . Let t[r] = U for some update U . Since t r ⊥, U is non-empty: let (i, n, m) ∈ U . By application of theorem 16, if Φ i = Φ A , there exists a state q ≥ r such that χ A ( n, m) ↓ q . By definition,

A q ( n, m) = χ A ( n, m)[q] = b
for some boolean b. Since t q ⊥ and t[q] = U (because t ↓ r and q ≥ r), we obtain by definition of realizability that b = True. Let q i n = l. We have two possibilities: 1. A( n, l) is false. We define the state

s ′ := λx N λy N . if x = i ∧ Bool y = n then m else q x (y)
Then, s ′ ≥ q, for A( n, l) is false. Moreover, since χ A ( n, m) ↓ q , for all q ′ ≥ q, χ A ( n, m)[q ′ ] = b; by Proposition 17, there exists q ′ ≥ q, such that χ A ( n, m)[q ′ ] = True if and only if A( n, m) is true. Since χ A ( n, m)[q ′ ] = b = True, we have that A( n, m) is true. By assumption on t, we have t s ′ ⊥ and t[s ′ ] = U , because s ′ ≥ r. Since s ′ i n = m, by definition of t s ′ ⊥ we would have both A s ′ ( n, m) = False and A s ′ ( n, m) = True, which is a contradiction.

A( n, l

) is true. By Proposition 17, there is a state s ′ ≥ q such that A s ′ ( n, l) = True. By assumption on t, we have t s ′ ⊥ and t[s ′ ] = U . But q i n = l, A( n, l) is true and s ′ ≥ q; therefore (i, n) ∈ def(q) and hence s ′ i n = l. By definition of t s ′ ⊥, we would have

A s ′ ( n, l) = False and A s ′ ( n, m) = True, which is in contradiction with A s ′ ( n, l) = True.
◭ Finally, we are in a position to prove in HA ω + EM that the realizability of a formula A implies its truth.

Theorem 19 (Soundness of Realizability). Let A be any →-free arithmetical formula and suppose t A. Then A is true.

Proof. We prove a stronger statement. Let s be a state and suppose that for all s ′ ≥ s, t s ′ A. We prove by induction on A, that A is true. A = P , with P atomic. Suppose, by the way of contradiction, that P is false. Then we have that for all s ′ ≥ s, t s ′ ⊥, which is impossible by Theorem 18. A = ∀x N B. Let n be any numeral. Then, for all s ′ ≥ s, tn s ′ B(n). By induction hypothesis B(n) is true. Therefore, ∀x N B is true, and we obtain the thesis. A = ∃x N B. By Theorem 16, there exists a state r ≥ s such that π 0 t ↓ r . Let π 0 t[r] = n with n numeral. Then, by definition, for every r ′ ≥ r, π 0 t[r ′ ] = n and therefore t r ′ B(n). By induction hypothesis B(n) is true, and we obtain the thesis.

◭

Since all the proofs given in this section are formalizable in HA ω + EM (see Section 5), we are able to prove the conservativity of HA ω + EM + SK over HA ω + EM for arithmetical formulas.

Theorem 20 (Conservativity of HA ω + EM + SK over HA ω + EM). Let A be a closed arithmetical formula, and suppose

HA ω + EM + SK ⊢ A Then:
HA ω + EM ⊢ A

(1)

HA + EM ⊢ A (2)
Proof.

1. We may assume that A is →-free. Otherwise,

HA ω + EM ⊢ A ↔ B
with B →-free and we consider B. Since Γ is arbitrary, we may assume that all the subformulas of the instances of EM and SK used in the derivation belong to Γ . By formalization of the Adequacy Theorem 12 in HA ω (see Section 5), we obtain that HA ω ⊢ t A for some term t of T Class . By formalization of the proof of Theorem 19 in HA ω + EM, we obtain that HA ω + EM ⊢ (t A) → A. We conclude HA ω + EM ⊢ A.

2.

There are at least two ways to obtain the thesis. On one hand, we may use (1) and the standard result about the conservativity of HA ω + EM over HA + EM for arithmetical formulas (see for example Troesltra [START_REF] Troelstra | Metamathematical Investigations of Intuitionistic Arithmetic and Analysis[END_REF]). On the other hand, we may code directly terms of system T Class into natural numbers and then express the proofs of point 1) in HA + EM (see Section 5). ◭ 5 Formalization of the Proofs in PA and in HA ω + EM

In this section we explain how to formalize in PA and HA ω + EM the proof of the Adequacy Theorem 12 of Section 3, the proofs of the Computability Theorem 16 and the Soundness Theorem 19 of Section 4. We start with the case of PA.

Formalization in PA

One can routinely code in PA all the concepts we have so far used. As in Tait [START_REF] Tait | Intensional Interpretations of Functional of Finite Type[END_REF], one may code the terms of T Class with natural numbers and successively the definition of the realizability and computability predicates with arithmetical formulas. Since neither settheoretic concepts nor Skolem axioms are employed in any of the given proofs, everything can be coded in PA. Theorem 22 allows us to replace in our conservativity proof the expression t A with the expression ∀s S . t[s] s A[s], which is a formula of HA ω . Moreover, the Adequacy Theorem for is formalizable in HA ω , since it is a special case of the Adequacy Theorem for modified realizability, which is formalizable in that system (see [START_REF] Troelstra | Realizability[END_REF]).

Formalization in

Secondly, we adapt the notion of computability to terms of type S → τ . For every pair of terms t, u ∈ T respectively of type S → (σ → τ ) and S → σ, we define the following notion of application: t • u := λs S .ts(us)

For every term t ∈ T of type S → (τ 0 × τ 1 ) and for i = 0, 1, we define the following notion of projection:

π i t := λs S .π i ts
Finally, for every constant term c / ∈ SC, we define c * := λs S c. We now adapt Definition 13 and Definition 14. Since there is no possibility of confusion, we maintain the same notations of Section 4 but with the new specified meaning.

Definition 23 (Definition of a term in a state s). For every state s term t : S → τ of T with τ atomic type, we define t ↓ s (and we say "t is defined in s") as the statement: for all states s ′ ≥ s, ts ′ = ts.

Definition 24 (Computable terms).

For every type τ of T , we define a set of closed terms of T of type S → τ as follows:

N ={t : S → N | for all states s there is a state s ′ ≥ s such that t ↓ s ′ } Bool ={t : S → Bool | for all states s there is a state s ′ ≥ s such that t ↓ s ′ } U ={t : S → U | for all states s there is a state s ′ ≥ s such that t

↓ s ′ } τ → σ ={t | ∀u ∈ τ t • u ∈ σ } τ × σ ={t | π 0 t ∈ τ and π 1 t ∈ σ }
The proof of Lemma 15 is easily adapted. Lemma 25. For every term t : S → ρ of T , if for every state s there exists a state s ′ ≥ s and u ∈ ρ such that for all states s ′′ ≥ s ′ , ts ′′ = us ′′ , then t ∈ ρ .

Proof. By induction on the type ρ. ρ = N. Let s be a state. We have to show that there exists a state r ≥ s such that t ↓ r . By assumption on t there exists a state s ′ ≥ s and u ∈ N such that for all s ′′ ≥ s ′ , ts ′′ = us ′′ . Thus, there exists s ′′ ≥ s ′ such that u ↓ s ′′ . Let r = s ′′ ; we prove t ↓ r . Let r ′ ≥ r. We have that ur ′ = ur, by u ↓ r , and tr ′ = ur ′ , since r ′ ≥ s ′ . Hence, tr ′ = ur = tr. We conclude t ↓ r and finally t ∈ ρ . ρ = Bool, U: as for the case ρ = N. ρ = τ → σ. Let v ∈ τ . We have to show that t • v ∈ σ . Let s be any state. By assumption on t there exists a state s ′ ≥ s and u ∈ τ → σ such that for all s ′′ ≥ s ′ , ts ′′ = us ′′ . Therefore for all s ′′ ≥ s ′ , (t • v)s ′′ = ts ′′ (vs ′′ ) = us ′′ (vs ′′ ) = (u • v)s ′′ and u • v ∈ σ . Hence, by induction hypothesis, t • v ∈ σ . 7. v is if τ : Bool → τ → τ → τ . Suppose that u ∈ Bool , u 1 ∈ τ , u 2 ∈ τ . Then, for all states s there exists s ′ ≥ s such that u ↓ s ′ . We have to prove that if * τ • u • u 1 • u 2 ∈ τ . Let s be a state and let s ′ ≥ s be such that u ↓ s ′ . If us ′ = True, then for all s ′′ ≥ s ′ , 10. v is ⋒ : U → U → U. Suppose that u 1 ∈ U and u 2 ∈ U . We have to prove that ⋒ * • u 1 • u 2 ∈ U . Let s be a state. Since u 1 ∈ U there exists s ′ ≥ s such that u 1 ↓ s ′ . Since u 2 ∈ U , there exists s ′′ ≥ s ′ such that u 2 ↓ s ′′ . Therefore, there exist two constants U 1 and U 2 such that for all s ′′′ ≥ s ′′ , u 1 s ′′′ = U 1 and u 2 s ′′′ = U 2 . Finally, for all s ′′′ ≥ s ′′ , (

(if * τ • u • u 1 • u 2 ) s ′′ = if τ (us ′′ )(u 1 s ′′ )(u 2 s ′′ ) = u 1 s ′′
⋒ * • u 1 • u 2 ) s ′′′ = ⋒(u 1 s ′′′ )(u 2 s ′′′ ) = ⋒ U 1 U 2 = U 3
for some update constant U 3 . By definition of U , ⋒ * • u 1 • u 2 ∈ U .

11. v is S, mkupd or get. The proof is similar to the one of the previous case.

12. v is a constant Φ i : N → N in SC. Suppose now, for a term u : N, that u ∈ N . We have to prove that Φ i = (λs S .s i ) • u ∈ N . Let s be a state. We must show that there exists a s ′ ≥ s such that (λs S .s i ) • u ↓ s ′ . Since u ∈ N , there exists a state s ′ ≥ s such that u ↓ s ′ .

Let n = us ′ , with n numeral, and m = s ′ i (n). Let Φ i = Φ A(x,y) . If A / ∈ Γ , then trivially (i, n) ∈ def(s ′ ) by Definition 8. Therefore for all s ′′ ≥ s ′ , ((λs S .s i ) • u)s ′′ = s ′′ i (n) = m and we are done. Hence, we may assume A ∈ Γ . There are two cases, and this is the only point of this proof in which we use EM. a. A(n, m) is true. Therefore, for all s ′′ ≥ s ′ , s ′′ i (n) = m because (i, n) ∈ def(s ′ ). Thus, for all s ′′ ≥ s ′ , ((λs S .s i ) • u)s ′′ = s ′′ i (n) = m, which is the thesis.

A

  = B ∧ C. Then, for all s ′ ≥ s, t s ′ A and t s ′ B. By induction hypothesis A and B are true, and we obtain the thesis. A = B ∨ C. By Theorem 16, there exists a state r ≥ s such that p 0 t ↓ r . Let p 0 t[r] = b with b boolean, say b = True. Then, by defintion, for every r ′ ≥ r, p 0 t[r ′ ] = True and therefore t r ′ A. By induction hypothesis A is true, and we obtain the thesis.

and u 1

 1 ∈ τ . If us ′ = False, then for all s ′′ ≥ s ′ ,(if * τ • u • u 1 • u 2 ) s ′′ = if τ (us ′′ )(u 1 s ′′ )(u 2 s ′′ ) = u 2 s ′′ and u 2 ∈ τ . By Lemma 25, we conclude if * τ • u • u 1 • u 2 ∈ τ . 8. v is R τ : τ → (N → (τ → τ )) → N → τ . Suppose that u ∈ τ , w ∈ N → (τ → τ ) , z ∈ N . We have to prove that R * τ • u • w • z ∈ τ . By a plain induction, it is possible to prove, for each numeral n, R * τ • u • w • n * ∈ τ .Let s be a state and let s ′ ≥ s be such that z ↓ s ′ . Let zs ′ = n with n numeral. Then for alls ′′ ≥ s ′ , (R * τ • u • w • z) s ′′ = R τ (us ′′ )(vs ′′ )(zs ′′ ) = R τ (us ′′ )(vs ′′ )n = (R * τ • u • w • n * )s ′′ By Lemma 25, we conclude R * τ • u • w • z ∈ τ . 9. v is min : U → N. Suppose that u ∈ U .Let s be a state. Since u ∈ U , there exists s ′ ≥ s such that u ↓ s ′ . We have to prove that min * • u ∈ N . Let be us ′ = U , with U update. For all s ′′ ≥ s ′ :(min * • u)s ′′ = min(us ′′ ) = min U = n for some numeral n. By definition of N , min * • u ∈ N .

Typing Rules for Composed Terms

	t : σ → τ tu : τ	u : σ	u : τ λx σ u : σ → τ	u : σ u, t : σ × τ t : τ	u : τ0 × τ1 i ∈ {0, 1} πiu : τi
	Reduction Rules All the usual reduction rules for simply typed lambda calculus (see Girard [14]) plus
	the rules for recursion, if-then-else and projections

  We define the realizability relation t F , where t ∈ T Class , F ∈ L Class and t : |F |.Definition 10 (Interactive Realizability). Assume s is a state, t is a closed term of T Class , F ∈ L Class is a closed formula, and t : |F |. We define first the relation t s F by induction and by cases according to the form of F :

1. t s Q for some atomic Q if and only if U = t[s] implies: for every (i, n, m) ∈ U , Φ i = Φ A for some A ∈ Γ , and A s ( n, s i n ) = False and A s ( n, m) = True. U = ∅ implies Q[s] = True 2. t s A ∧ B if and only if π 0 t s A and π 1 t s B 3. t s A ∨ B if and only if either p 0 t[s] = True and p 1 t s A, or p 0 t[s] = False and p 2 t s B 4. t s A → B if and only if for all u, if u s A, then tu s B 5. t s A B if and only if π 0 t s A and π 1 t s B ⊥ 6. t s ∀x τ A if and only if for all closed terms u : τ of T , tu s A[u/x] 7. t s ∃x τ A if and only for some closed term u : τ of T , π 0 t[s] = u and π 1 t s A[u/x] We define t F if and only if for all states s of T , t s F .

  HA ω + EM Instead of coding everything into natural numbers, which is of limited practical interest, it is more satisfying to formalize our proofs directly in HA ω + EM. There is no serious obstacle to this end, except for a small formalization issue: the notion t[s] of evaluation of a term t of T Class in a state s, which we have heavily used in the definitions of the realizability and computability predicates, is not directly representable in HA ω + EM. To begin with, terms of T Class may contain some constant Φ ∈ SC which does not belong to the language of HA ω . This problem is easily solved by considering terms of the form t[s] with s state variable. However, in the definition of Interactive realizability for implication and in the statement of the Computability Theorem one needs to define formulas x A and x ∈ N , where x is a variable. In these definitions it is necessary to speak about the substitution of an actual state s in the body of a variable x, which is impossible in HA ω (remember that x represents a term t[s] of T ). This last issue is overcome quite easily by considering in place of a term t : τ in T Class the term λs S .t[s] : S → τ , where S := N 2 → N is the type of states. In this way, one makes explicit the functional dependence of t from the state s and transforms t into an object having a semantical denotation. It is however necessary to slightly adapt the definitions of realizability and computability, which is what we are going to do.First, we give an alternative definition of Interactive realizability, which is shown in [4] to be equivalent to Kreisel's modified realizability for HA ω applied to some Friedman translation of formulas. We denote with L the restriction of the language L Class to the formulas not containing any Skolem function constant Φ ∈ SC.Definition 21 (Alternative Definition of Interactive Realizability). Assume s : S is a closed term of T , t is a closed term of T , D ∈ L is a closed formula of L, and t : |D|. We define by induction on D the relation t One can prove straightforwardly, as in[4], that our first Definition 10 of Interactive realizability is equivalent to this alternative one.

	Theorem 22 (Characterization of Interactive Realizability). Let t ∈ T Class and s be a state.
	Then, for every B ∈ L Class
	t s B ⇐⇒ t[s] s B[s]

s D: 1. t s Q if and only if t = U implies: for every (i, n, m) ∈ U , Φ i = Φ A for some A ∈ Γ , and A s ( n, s i n ) = False and A s ( n, m) = True. U = ∅ implies Q = True 2. t s A ∧ B if and only if π 0 t s A and π 1 t s B 3. t s A ∨ B if and only if either p 0 t = True and p 1 t mr A, or π 0 t = False and p 1 t mr B 4. t s A → B if and only if for all u, if u s A, then tu s B 5. t s ∀x τ A if and only if for all closed terms u : τ of T , tu s A[u/x] 6. t s ∃x τ A if and only for some closed term u : τ of T , π 0 t = u and π 1 t s A[u/x]

ρ = τ 0 × τ 1 . Let i ∈ {0, 1}, we have to show that π i t ∈ τ i . Let s be any state. By assumption on t there exists s ′ ≥ s and u ∈ τ 0 × τ 1 such that for all s ′′ ≥ s ′ , ts ′′ = us ′′ . Therefore for all s ′′ ≥ s ′ , (π i t)s ′′ = π i (ts ′′ ) = π i (us ′′ ) = (π i u)s ′′ and π i u ∈ τ i . Hence, by induction hypothesis π i t ∈ τ i .

◭

Also the proof of the Computability Theorem remains substantially the same.

Theorem 26 (Computability Theorem).

Let v : τ be a term of T Class and suppose that all the free variables of v are among x σ1 1 , . . . ,

Proof. We proceed by induction on v. 4. v is λx τ1 .u : τ 1 → τ 2 . Then, by means of typing rules, u : τ 2 . Suppose now, for a term t : S → τ 1 in T , that t ∈ τ 1 . We have to prove that v • t ∈ τ 2 . We have:

By induction hypothesis, this latter term is in τ 2 . By Lemma 25 we conclude v•t ∈ τ 2 .

5. v is u, w : τ 0 × τ 1 . By means of typing rules, u : τ 0 , w : τ 1 and by induction hypothesis

By Lemma 25, we obtain v ∈ τ i .

b. A(n, m) is false. If there exists l such that A(n, l) is true, then let

which is the thesis. If there is no l such that A(n, l) is true, then trivially (i, n) ∈ def(s ′ ). Thus for all s ′′ ≥ s ′ , ((λs S .s i ) • u)s ′′ = s ′′ i (n) = m and we are done.

◭

The proofs of Proposition 17 and Theorem 18 remain exactly the same, while the proof of Theorem 19 can be straightforwardly adapted. In particular, in the base case of the induction one needs to prove that a term t, possibly with free variables of type N, is computable. This follows from Theorem 26 and the fact that it is possible to prove by induction the statement ∀x N . λs S x ∈ N .