The papers are in PostScript format. Download by clicking on the paper name. Following the list of papers is a short description of the contents of each paper (including publishing date, journal, and co-authors).

- (with D. Butnariu an E. P. Klement) On Triangular Norm-Based Propositional Fuzzy Logics ,
- (with Ronny Nahum) Topological Complexity of Graphs and their Spanning Trees ,
- A Topological Linking Theorem in Simple Graphs
- Borel ideals vs. Borel sets of countable relations and trees The journal maintains a database. Click here to get more info.
- On analytic filters and prefilters. The journal maintains a database. Click here to get more info.
- On the Topological Strength of Boolean Set Operations

PAPER 1 Title: On Triangular Norm-Based Propositional Fuzzy Logics Authors: Dan Butnariu Department of Mathematics and Computer Science, University of Haifa, 31905 Haifa, Israel Erich Peter Klement Institut f\"ur Mathematik, Johannes Kepler Universit\"at, A-4040 Linz, Austria Samy Zafrany Department of Mathematics Technion city, 32000 Haifa, Israel samy@techunix.technion.ac.il Journal: Fuzzy Sets and Systems 69 (1995), 241-255. \begin{abstract} Fuzzy logics based on triangular norms and their corresponding conorms are investigated. An affirmative answer to the question whether in such logics a specific level of satisfiability of a set of formulas can be characterized by the same level of satisfiability of its finite subsets is given. Tautologies, contradictions and contingencies with respect to such fuzzy logics are studied, in particular for the important cases of min-max and Lukasiewicz logics. Finally, fundamental t-norm-based fuzzy logics are shown to provide a gradual transition between min-max and Lukasiewicz logics. \end{abstract} Key words: Fuzzy Logics, Min-max logic, Lukasiewicz Logic, Triangular Key words: Norms, Satisfiability. AMS-Classification: 03B52, 03B50, 03B05 ============================================================================== ============================================================================== PAPER 2 Title: Topological Complexity of Graphs and their Spanning Trees Authors: Ronny Nahum Department of Mathematics and Computer Science Haifa University, 31905 Haifa, Israel Samy Zafrany Department of Mathematics Technion city, 32000 Haifa, Israel e-mail:samy@techunix.technion.ac.il Journal: Acta Mathematica Hungarica 66 (1) (1995), 1-10. \begin{abstract} Let $X$ be a perfect separable complete metric space. Let $G=(V,E)$ be a simple graph such that $V\subseteq X$. Let $\vec{E}=\setn{(x,y)}{\{x,y\}\in E}$. We call $G$ {\em analytic} if $\vec{E}$ is an analytic subset of $X^2$. Similarly, $G$ is {\em $\sigma$-analytic} if $\vec{E}$ belongs to the $\sigma$-algebra generated by all the analytic subsets of $X^2$. We call $G$ a {\em weighted graph} if an ordinal is assigned to every edge. Let $G$ be an analytic connected weighted graph. We prove that under some restrictions $G$ has a $\sigma$-analytic minimal spanning tree $T$ (i.e, if we replace one edge in $T$ by a lighter edge, then $T$ stops being a spanning tree). We also give examples that show that this result is optimal. \end{abstract} Key words: weighted graphs, minimal spanning tree, analytic set, uniformization, projective hierarchy. AMS-Classification: 03B52, 03B50, 03B05 ============================================================================== ============================================================================== PAPER 3: A Topological Linking Theorem in Simple Graphs Ronny Nahum and Samy Zafrany Department of Mathematics and Computer Science Haifa University, 31905 Haifa, Israel e-mail:{samy@techunix.technion.ac.il} June 14, 1994 \begin{abstract} We prove a topological version of a combinatorial theorem due to R.~A.~Brualdi and J.~S.~Pym. Their theorem is a generalization of the well known Cantor-Bernstein Theorem as well as of other reformulations of it (Banach's mapping theorem and \Konig's matching theorem). Let $G=(V,E)$ be a simple graph such that $V$ is a perfect separable complete metric space. Let $A,B\subseteq V$ be disjoint, and let $A{*}B$ be the set of all paths $p=(x_1,x_2,\ldots,x_n)$ in $G$, such that $x_1\in A$ and $x_n\in B$. A {\em linking} $f:A\leadsto B$ is a subset $f\subseteq A{*}B$ such that for each $a\in A$ there exists exactly one path $p\in f$ whose initial vertex is $a$. We call $f$ {\em injective} if every distinct $p,q\in f$ are vertex-disjoint, and we call $f$ {\em bijective} if, in addition, for every $b\in B$ there is a path in $f$ that ends with $b$. The topological version states: if $f:A\leadsto B$ and $g:B\leadsto A$ are Borel injective linkings, then there exists a Borel bijective linking $h:A\leadsto B$. We also consider possible extensions of this result in various directions. \end{abstract} Key words: topological graph, Borel set, linking, perfect matching AMS-Classification: 04A15, 05C10, 03E15 ============================================================================== ============================================================================== PAPER 4 Title: Borel Ideals vs. Borel Sets of Countable Relations and Trees Author: Samy Zafrany Journal: Annals of Pure and Applied Logic 43 (1989) This paper is a revised version of Chapter 3 of the author's Ph.D. dissertation which was written in the University of California at Berkeley, under the supervision of Professor John W. Addison. \begin{abstract} For every $\mu<\w_1$, let $I_\mu$ be the ideal of all sets $S\subseteq\w^\mu$ whose order type is $<\w^\mu$. If $\mu=1$ then $I_1$ is simply the ideal of all finite subsets of $\w$, which is known to be $\BS{2}$-complete. We show that for every $\mu<\w_1$, $I_\mu$ is $\BS{2\mu}$-complete. As corollaries to this theorem, we prove that the set $\WO_{\w^\mu}$ of well orderings $R\subseteq\wxw$ of order type $<\w^\mu$ is $\BS{2\mu}$-complete, the set $\LP_\mu$ of linear orderings $R\subseteq\wxw$ that have a $\mu$-limit point is $\BS{2\mu+1}$-complete. Similarly, we determine the exact complexity of the set $\LT_\mu$ of trees $T\subseteq\wpwc$ of Luzin height $<\mu$, the set $\WR_\mu$ of well-founded partial orderings of height $<\mu$, the set $\LR_\mu$ of partial orderings of Luzin height $<\mu$, the set $\WF_\mu$ of well-founded trees $T\subseteq\wpwc$ of height $<\mu$ (the latter is an old theorem of Luzin). The proofs use the notions of Wadge reducibility and Wadge games. We also present a short proof to a theorem of Luzin and Garland about the relation between the height of ``the shortest tree'' representing a Borel set and the complexity of the set. \end{abstract} ================================================================== ================================================================== PAPER 5 Title: On Analytic Filters and Pre-filters Author: Samy Zafrany Department of Mathematics and Computer Science Ben Gurion University of the Negev Beer Sheva, Israel Journal: Journal of Symbolic Logic, Vol. 55, Num. 1 March 1990 \begin{abstract} We show that every analytic filter is generated by a $\BP{2}$ pre-filter, every $\BS{2}$ filter is generated by a $\BP{1}$ pre-filter, and if $P\subseteq\pw$ is a $\BS{2}$ pre-filter then the filter generated by it is also $\BS{2}$. The last result is unique for the Borel classes as there is a $\BP{2}$-complete pre-filter $P$ such that the filter generated by it is $\boldSigma^1_1$-complete. Also, every complete co-analytic filter does not have an analytic pre-filter. The proofs use \Konig's infinity Lemma, a normal form theorem for monotone analytic sets, and Wadge reductions. \end{abstract} ================================================================== ================================================================== PAPER 6 Title: On the Topological Strength of Boolean Set Operations This paper is an extended version of Chapter 1 of the author's Ph.D. dissertation which was written in the University of California at Berkeley, under the supervision of Professor John W. Addison. Author: Samy Zafrany July 30, 1989 Draft 1 \begin{abstract} We review the basic facts of the theory of Boolean set operations. A measure of strength is assigned to every Boolean set operation by relating it to a subset of the Cantor space and using the usual topological complexity of that set. Composition of two or countably many Boolean set operations is defined and its properties are studied. We focus our attention on the compositions of the $\liminf$ and $\limsup$ operations and generalize (in various directions) an old theorem of Sier\'pinski on the strength of those operations. \end{abstract}

Samy Zafrany School of Computer Science and Mathematics samy@netanya.ac.il Netanya Academic College Phones: 16 Kibutz-Galuyot Street 972-9-8607738 (Office) Kiriat Yizhack Rabin Netanya 42365, ISRAEL