## SEARCH

#### Institution

##### ( see all 988)

- University of Leeds 23 (%)
- Baruch College of CUNY 20 (%)
- University of Helsinki 20 (%)
- Kobe University 18 (%)
- University of Notre Dame 18 (%)

#### Author

##### ( see all 1059)

- Shelah, Saharon 51 (%)
- Apter, Arthur W. 25 (%)
- Rathjen, Michael 16 (%)
- Hirst, Jeffry L. 11 (%)
- Montagna, Franco 11 (%)

#### Subject

- Mathematics 1187 (%)
- Algebra 1115 (%)
- Mathematical Logic and Foundations 1115 (%)
- Mathematics, general 1115 (%)

## CURRENTLY DISPLAYING:

Most articles

Fewest articles

Showing 1 to 10 of 1187 matching Articles
Results per page:

## External automorphisms of ultraproducts of finite models

### Archive for Mathematical Logic (2012-05-01) 51: 433-441 , May 01, 2012

Let
$${\fancyscript{L}}$$
be a finite first-order language and
$${\langle{\fancyscript{M}_n} \,|\, {n < \omega}\rangle}$$
be a sequence of finite
$${\fancyscript{L}}$$
-models containing models of arbitrarily large finite cardinality. If the intersection of less than continuum-many dense open subsets of Cantor Space ^{ω}2 is non-empty, then there is a non-principal ultrafilter
$${\fancyscript{U}}$$
over *ω* such that the corresponding ultraproduct
$${\prod_\fancyscript{U}\fancyscript{M}_n}$$
has an automorphism that is not induced by an element of
$${\prod_{n<\omega}{\rm Aut}(\fancyscript{M}_n)}$$
.

## Hechler’s theorem for the null ideal

### Archive for Mathematical Logic (2004-07-01) 43: 703-722 , July 01, 2004

### Abstract.

We prove the following theorem: For a partially ordered set *Q* such that every countable subset of *Q* has a strict upper bound, there is a forcing notion satisfying the countable chain condition such that, in the forcing extension, there is a basis of the null ideal of the real line which is order-isomorphic to *Q* with respect to set-inclusion. This is a variation of Hechler’s classical result in the theory of forcing. The corresponding theorem for the meager ideal was established by Bartoszyński and Kada.

## Forcing with quotients

### Archive for Mathematical Logic (2008-08-27) 47: 719-739 , August 27, 2008

We study an extensive connection between quotient forcings of Borel subsets of Polish spaces modulo a *σ*-ideal and quotient forcings of subsets of countable sets modulo an ideal.

## Subsystems of second-order arithmetic between RCA0 and WKL0

### Archive for Mathematical Logic (2008-07-01) 47: 205-210 , July 01, 2008

We study the Lindenbaum algebra
$${\fancyscript{A}}$$
(*WKL*_{o}, *RCA*_{o}) of sentences in the language of second-order arithmetic that imply *RCA*_{o} and are provable from *WKL*_{o}. We explore the relationship between
$${\Sigma^1_1}$$
sentences in
$${\fancyscript{A}}$$
(*WKL*_{o}, *RCA*_{o}) and
$${\Pi^0_1}$$
classes of subsets of ω. By applying a result of Binns and Simpson (*Arch. Math. Logic **43*(3), 399–414, 2004) about
$${\Pi^0_1}$$
classes, we give a specific embedding of the free distributive lattice with countably many generators into
$${\fancyscript{A}}$$
(*WKL*_{o}, *RCA*_{o}).

## On the bounded version of Hilbert's tenth problem

### Archive for Mathematical Logic (2003-07-01) 42: 469-488 , July 01, 2003

### Abstract.

The paper establishes lower bounds on the provability of 𝒟=NP and the MRDP theorem in weak fragments of arithmetic. The theory *I*^{5}*E*_{1} is shown to be unable to prove 𝒟=NP. This non-provability result is used to show that *I*^{5}*E*_{1} cannot prove the MRDP theorem. On the other hand it is shown that *I*^{1}*E*_{1} proves 𝒟 contains all predicates of the form (∀*i*≤|*b*|)*P*(*i*,*x*)^*Q*(*i*,*x*) where ^ is =, <, or ≤, and *I*^{0}*E*_{1} proves 𝒟 contains all predicates of the form (∀*i*≤*b*)*P*(*i*,*x*)=*Q*(*i*,*x*). Here *P* and *Q* are polynomials. A conjecture is made that 𝒟 contains NLOGTIME. However, it is shown that this conjecture would not be sufficient to imply 𝒟=*N P*. Weak reductions to equality are then considered as a way of showing 𝒟=NP. It is shown that the bit-wise less than predicate, ≤_{2}, and equality are both co-NLOGTIME complete under FDLOGTIME reductions. This is used to show that if the FDLOGTIME functions are definable in 𝒟 then 𝒟=*N P*.

## Extracting Herbrand disjunctions by functional interpretation

### Archive for Mathematical Logic (2005-07-01) 44: 633-644 , July 01, 2005

### Abstract.

Carrying out a suggestion by Kreisel, we adapt Gödel’s functional interpretation to ordinary first-order predicate logic(PL) and thus devise an algorithm to extract Herbrand terms from PL-proofs. The extraction is carried out in an extension of PL to higher types. The algorithm consists of two main steps: first we extract a functional realizer, next we compute the *β*-normal-form of the realizer from which the Herbrand terms can be read off. Even though the extraction is carried out in the extended language, the terms are ordinary PL-terms. In contrast to approaches to Herbrand’s theorem based on cut elimination or*ɛ*-elimination this extraction technique is, except for the normalization step, of low polynomial complexity, fully modular and furthermore allows an analysis of the structure of the Herbrand terms, in the spirit of Kreisel ([13]), already prior to the normalization step. It is expected that the implementation of functional interpretation in Schwichtenberg’s MINLOG system can be adapted to yield an efficient Herbrand-term extraction tool.

## Generalized quantifier and a bounded arithmetic theory for LOGCFL

### Archive for Mathematical Logic (2007-07-01) 46: 489-516 , July 01, 2007

We define a theory of two-sort bounded arithmetic whose provably total functions are exactly those in
$${\mathcal{F}_{LOGCFL}}$$
by way of a generalized quantifier that expresses computations of *SAC*^{1} circuits. The proof depends on Kolokolova’s conditions for the connection between the provable capture in two-sort theories and descriptive complexity.

## Subvarieties of BL-algebras generated by single-component chains

### Archive for Mathematical Logic (2002-10-01) 41: 673-685 , October 01, 2002

### Abstract.

In this paper we study and equationally characterize the subvarieties of *BL*, the variety of BL-algebras, which are generated by families of single-component BL-chains, i.e. MV-chains, Product-chain or Gödel-chains. Moreover, it is proved that they form a segment of the lattice of subvarieties of *BL* which is bounded by the Boolean variety and the variety generated by all single-component chains, called ŁΠG.

## More fine structural global square sequences

### Archive for Mathematical Logic (2009-10-13) 48: 825-835 , October 13, 2009

We extend the construction of a global square sequence in extender models from Zeman [8] to a construction of coherent non-threadable sequences and give a characterization of stationary reflection at inaccessibles similar to Jensen’s characterization in *L*.

## Pairs, sets and sequences in first-order theories

### Archive for Mathematical Logic (2008-08-01) 47: 299-326 , August 01, 2008

In this paper we study the idea of theories with containers, like sets, pairs, sequences. We provide a modest framework to study such theories. We prove two concrete results. First, we show that first-order theories of finite signature that have functional non-surjective ordered pairing are definitionally equivalent to extensions in the same language of the basic theory of non-surjective ordered pairing. Second, we show that a first-order theory of finite signature is sequential (is a theory of sequences) iff it is definitionally equivalent to an extension in the same language of a system of weak set theory called *WS*.