38679232
Short Definitions of the Ordinals
In this paper, a simple inductive characterization of the ordinal numbers is stated and developed. The characterization forms the basis for a set of axioms for ordinal theory and also for several short explicit definitions of the ordinals. The axioms are shown to be sufficient for ordinal theory, and, subject to suitable existence assumptions, each of the definitions is shown to imply the axioms. The present results apply to the familiar von Neumann version of the ordinals, but the methods used are easily adapted to other versions. ? 1. Axioms for ordinal theory. According to the usual interpretation, each ordinal is the set of all lesser ordinals. Thus zero is the empty set A, a successor ordinal x' is x U {x} for some ordinal x, and a limit ordinal is a set w of ordinals that is equal to its own sum set Zw. In fact, the class On of all ordinals might be characterized informally as the smallest class Z such that (1) AEZ, (2) (y) (yEZ D y'EZ), and (3) (w) (1w = w c Z D wEZ). More simply, On can be characterized as the smallest Z such that
1953614
Alternative Proof of a Theorem of Kleene
11313688
Existence of Classes and Value Specification of Variables
In mathematics, when we want to introduce classes which fulfill certain conditions, we usually prove beforehand that classes fulfilling such conditions do exist, and that such classes are uniquely determined by the conditions. The statements which state such unicity and existence of classes are in mathematical logic consequences of the principles of extensionality and class existence. In order to illustrate how these principles enable us to introduce classes into systems of mathematical logic, let us consider the manner in which Godel introduces classes in his book on set theory. For instance, before introducing the definition of the non-ordered pair of two classes Godel puts down as its justification the following two axioms: By A4, for every two classes y and z there exists at least one non-ordered pair w of them; and by A3, w is uniquely determined in A4.
29040872
A Variant to Turing's Theory of Computing Machines
The principal purpose of this paper is to offer a theory which is closely related to Turing's [1] but is more economical in the basic operations. I t will be proved that a theoretically simple basic machine can be imagined and specified such tha t all partial recursive functions (and hence all solvable computation problems) can be computed by it and tha t only four basic types of instruction are employed for the programs: shift left one space, shift right one space, mark a blank space, conditional transfer. In particular, erasing is dispensable, one symbol for marking is sufficient, and one kind of transfer is enough. The reduction is somewhat similar to the realization of, for instance, the definability of conjunction and implication in terms of negation and disjunction, or of the definability of all these in terms of Sheffer's stroke function. As a result, i t becomes less direct to prove that certain things can be done by the machines, but a little easier to prove that certain things cannot be done. This serf-contained theory will b e presented, as far as possible, in a language which is familiar to those who are engaged in the use and construction of largescale computers. Turing's theory of computable functions antedated but has not much influenced the extensive actual construction of digital computers. These two aspects of theory and practice have been developed almost entirely independently of each other. The main reason is undoubtedly that logicians are interested in questions radically different from those with which the applied mathematicians and electrical engineers are primarily concerned. I t cannot, however, fail to strike one as rather strange that often the same concepts are expressed by very different terms in the two developments. One is even inclined to ask whether a rapprochement might not produce some good effect. This paper wiU, it is believed, be of use to those who wish to compare and connect the two approaches. Extensive use of Turing [1] and Kleene [2] (Chapter XI I I ) will be made, although the exposition is sufficient in itself.
42852449
A Formal System of Logic
The main purpose of this paper is to present a formal system P in which we enjoy a smooth-running technique and which countenances a universe of classes which is symmetrical as between large and small. More exactly, P is a system which differs from the inconsistent system of [ 1 ] only in the introduction of a rather natural new restrictive condition on the defining formulas of the elements (sets, membership-eligible classes). It will be proved that if the weaker system of [ 2 ] is consistent, then P is also consistent. After the discovery of paradoxes, it may be recalled, Russell and Zermelo in the same year proposed two different ways of safeguarding logic against contradictions (see [ 3 ], [ 4 ]). Since then various simplifications and refinements of these systems have been made. However, in the resulting systems of Zermelo set theory, generation of classes still tends to be laborious and uncertain; and in the systems of Russell's theory of types, complications in the matter of reduplication of classes and meaningfulness of formulas remain. In [ 2 ], Quine introduced a system which seems to be free from all these complications. But later it was found out that in it there appears to be an unavoidable difficulty connected with mathematical induction. Indeed, we encounter the curious situation that although we can prove in it the existence of a class V of all classes, and we can also prove particular existence theorems for each of infinitely many classes, nobody has so far contrived to prove in it that V is an infinite class or that there exists an infinite class at all.
29402189
Non-Standard Models for Formal Logics
showed that there must be a model in which that portion of the model which is supposed to represent the positive integers of the formal logic is not in fact isomorphic to the positive integers; indeed it is not even well ordered by what is supposed to be the relation of <. For the purposes of the present paper, we do not need a precise definition of what is meant by a standard model of a formal logic. The non-standard models which we shall discuss will be flagrantly non-standard, as for instance a model of the sort whose existence is proved by Henkin. It will suffice if we and our readers are in agreement that a model of a formal logic is not a standard model if either: (a) The relation in the model which represents the equality relation in the formal logic is not the equality relation for objects of the model. (b) That portion of the model which is supposed to represent the positive integers of the formal logic is not well ordered by the relation <. (c) That portion of the model which is supposed to represent the ordinal numbers of the formal logic is not well ordered by the relation <. Our first result is that there is no standard model for the system known as "Quine's New Foundations" (see [2] and [3]). This is proved for the logic originally proposed by Quine (see [2]), which is a system of such apparent weakness that so far no one has succeeded in proving the axiom of infinity in the system. Clearly, if there is no standard model for this apparently weak system, there cannot be a standard model for any apparently stronger system which one might form by adding additional axioms, such as the axiom of infinity. A natural reaction to this result would be to suspect that there is no model of any sort for Quine's New Foundations; that is to suspect that it is inconsistent. An alternative (and much less likely) reaction would be to suspect that the property of not having a standard model is perhaps a not uncommon property of strong formal logics, and to suspect that perhaps several of the familiar strong formal logics have no standard model. Unlikely as this might appear at first sight, we will present considerable evidence in favor of the idea. In particular we shall show that it is a property of each of the familiar formal logics that if it is w-consistent then one cannot prove in the logic itself that if the logic is consistent it must have a standard model; in fact, one cannot prove this statement about the logic even in certain stronger logics if these stronger logics are simply consistent.
9869945
The Logic of Automata—Part II
The transition part of a net controls the passage of the net from state to state and is therefore the heart of the net. In this subsection we introduce "the transition matr ix," a table which describes a net by showing the various ways in which it may pass from one delay state to another. We use a characterizing table with M input (state) words I, N internalstate words S, and M X N rows, each of the form <<I, S > , S ' > , to define N 2 direct-transition expressions I~j as follows. I ~ is a disjunction of all those I~ such tha t <<Ik, S~>, S i > is a row of the characterizing table; if there are no such Ik , then I~s is ¢ ("the false"). Tha t is, I~i is a disjunction of all those input words (if any) which can cause the net to pass from state S~ at time t to state Sj at t ime t + 1; it is allowed that i equals j . I t is clear that each I~i is a disjunctive normal form expression of the input function variables. Note tha t the direct-transition expression "~b" is distinct from the directtransition expressions "0", "00", "000", etc.; the former means that no direct transition between the two states is possible, while the latter mean that such a transition is brought about by making all the inputs zero. A direct transition from S~ to S~ in a net is a passage from state S~ at t to state S~ at t + 1. Such a transition is possible only in the case where I~i ~ ¢. We say that < I k , S~> (or Ik S~) at time t directly produces Si at time t -~ 1 only in the case where the net makes a direct transition from S~ to Sy under the influence of input Ik at t. A transition from S~ to Si in a net is a passage from state S~ at t to state S~ at t ~ w (w > 0). Such a transition is possible only where there exists a sequence of direct-transition expressions, none of which are ¢, of the form I~o, , I,~o~, . . . , I ~ j . We say that I~S~(t) , I~,~(t -q1), . . . , I~s(t -k w 1) produces S j at t "-k w if and only if there is a transition from S~(t) to Si(t -k w) under the direction of the hsted inputs; this is a transition of w steps (or, alternatively, a transition of length w). I t is convenient to arrange the information in an M N characterizing table in a direct-transition matrix of order N by arranging the N * direct-transi-
15916460
An approach to security and privacy of RFID system for supply chain
Radio frequency identification (RFID) is expected to become pervasive and ubiquitous, as it can be embedded into everyday items as smart labels. A typical scenario of exploiting RFID is supply chain. The RFID based supply chain management yields convenience, efficiency and productivity gains. However, RFID systems create new risks to security and privacy. We briefly present the current solutions to RFID security and privacy. A new approach is then proposed, which exploits randomized read access control and thus prevents hostile tracking and man-in-the-middle attack. In addition, compared with current schemes that achieve the similar security level, the proposed approach dramatically decreases the computation load. Another benefit is that it is suitable for RFID systems with a large number of tags
18424476
Proving theorems by pattern recognition I
Certain preliminary results on doing mathematics by machines (“mechanical mathematics”) were reported in an earlier paper [20]. The writer suggested developing inferential analysis as a branch of applied logic and as a sister discipline of numerical analysis. This analogy rests on the basic distinction of pure existence proofs, elegant procedures which in theory always terminate, and efficient procedures which are more complex to describe but can more feasibly be carried out in practice. In contrast with pure logic, the chief emphasis of inferential analysis is on the efficiency of algorithms, which is usually attained by paying a great deal more attention to the detailed structures of the problems and their solutions, to take advantage of possible systematic short cuts. The possibilities of much more elaborate calculations by machines provide an incentive to studying a group of rather minute questions which were formerly regarded as of small theoretical interest. When the range of actual human computation was narrow, there seemed little point in obtaining faster procedures which were still far beyond what was feasible. Furthermore, on account of the versatility of machines, it now appears that as more progress is made, strategies in the search for proofs, or what are often called heuristic methods, will also gradually become part of the subject matter of inferential analysis. An analogous situation in numerical analysis would be, for example, to make the machine choose to apply different tricks such as taking the Fourier transform to obtain a solution of some differential equation.
7283306
A Fair Item-Item Exchange Protocol Satisfying Newly Introduced Requirements
Many protocols are designed to guarantee fairness in electronic exchange that is widely used in e-commerce and e-government systems. In spite of the cryptographic view, we tend to view the fairness problem in a more complete vision. First we present a renewed set of requirement definitions for fair protocols. Second we study the encrypted item validation problem and present a simple and effective solution. With these preliminary discussions, we present our new item-item exchange protocol that is the first one to satisfy those newly introduced requirements
17656556
A Non-repudiable Protocol for Secure Messaging
As Oppliger stated, secure messaging refers to the ability to provide data confidentiality, data integrity, data origin authentication, and non-repudiation of origin services for email. It is very important but poorly developed and has very limited application. We propose an email protocol assures non-repudiability which means that if the email is successfully sent, the sender cannot deny she/he has actually sent the mail and the recipient cannot deny she/he has actually received it. The protocol uses an efficient RSA-based convertible signature.