6
votes
5answers
181 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
1
vote
2answers
58 views

Sigma hierarchy of logical formulae

In some papers on mathematical logic I've found references to hierarchy like $\Sigma_1^0$-sentence and so on. What does it mean? What is $\Sigma_n^m$, what is $n$ and $m$ here?
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
0
votes
0answers
29 views

Help with formulating a mathematical logic formula

I need to write a precise mathematical expression to formulate an algorithm that could be implemented in software. It has the following simple logic: An Internet user of the software in a ...
11
votes
1answer
308 views

What underlies formal logic (or math, generally)?

I read a useful definition of the word understanding. I can't recall it verbatim, but the notion was that understanding is 'data compression': understanding happens when we learn one thing that ...
0
votes
1answer
27 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
0
votes
2answers
94 views

Does current foundation of first order logic need a fundamental change?

Note the following (not too exact) correspondence between natural and formal languages. a. In a natural language we begin with a set of alphabets. a'. In a first order language we begin with a set ...
1
vote
3answers
397 views

Prove « If P(A) is a subset of P(B) => A is a subset of B » [duplicate]

I need to prove «If P(A) is a subset of P(B) => A is a subset of B», generally, I understand the main way I should prove it, but the problem is in formal, pedantic language I have to use to prove ...
2
votes
1answer
31 views

Undecidability of REGULAR_TM

In case you have Sipser's Introduction to the Theory of Computation 3rd edition, I am asking specifically about the proof of theorem 5.3, how the language REGULAR_TM is undecidable. \begin{equation} ...
1
vote
1answer
27 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
1
vote
2answers
106 views

$\beta$ - conversion and $\alpha$-reduction problem in $\lambda$-calculus

Here is an expression that I am trying to reduce and my operations so far: $$((\lambda x.(x (\lambda z.zy))) (\lambda z.\lambda y. zy) )= (x (\lambda z.zy))[x \to \lambda z.\lambda y. zy ] = ...
0
votes
1answer
51 views

Is this $\beta$-reduction well defined?

Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it ...
2
votes
2answers
108 views

Logic: building a sentence

Let $L$ be a language with a 1-place function symbol $f$. Give an $L$-sentence $\phi$ that is true in every $L$-structure $M$ if the following holds: if $M \models \phi$, then $M$ is infinite. My ...
3
votes
2answers
135 views

Object language and meta-language

I'm reading a Mathematical Logic book (A course in mathematical logic, Bell.M ) and the author is saying that the symbols of a formal language don't have a well-defined shape, he's claiming that they ...
-2
votes
3answers
246 views

What is truth? A puzzle of ZFC and CH [closed]

Given a enough strong formal theory capable to form Continuum hypothesis. from law of excluded middle and Noncontradiction, one and only one of CH and negative CH should be true. but the consistent ...
-2
votes
1answer
150 views

Do all true number thesis with universal form allways has a proof? [closed]

true number thesis with universal form: Goldbach conjecture, twin primes, every normal number thesis with a form ∀x∈N.P(x). As a comment from André Nicolas, Matiyasevich's theorem(Hilbert's tenth ...
5
votes
1answer
353 views

First-order logic without equality

Can we do without equality in first order logic? I looked at some cases in which equality is essential and found that it seems enough to have inequality implicit in the variables. Let $\phi(x,y)$ be a ...
2
votes
2answers
110 views

Finite-state machine.

I have a problem with the transition function of a finite-state machine. I understand that can be represented by transition table or state diagram but unfortunately in some exercises I do not ...
1
vote
1answer
71 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
1
vote
2answers
112 views

Finding a grammar that generates a language.

Given a string w over an alphabet $\Sigma$ we define symmetric string the string $w^R$ defined as follows: if $w=\epsilon$ ($\epsilon$ is empty string) if $w=\sigma x$ with $\sigma\in\Sigma$ and ...
1
vote
2answers
331 views

Converting each formula into Conjunctive Normal Form?

How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee ...
2
votes
1answer
172 views

Function problem vs. decision problem

Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
4
votes
3answers
196 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
0
votes
1answer
100 views

Clarification for the definition of “a term is free for a variable in some wf. of a first order language”

Definition 1 Let $A$ be any wf. of a first order language L and $x$ be any variable. We say $x$ occurs free in $A$ if there is at least one occurrence of $x$ in $A$ which is not the scope of ...
1
vote
1answer
241 views

Differences between the formal grammar, formation rules and automaton for a formal language

Added: A formal grammar is a set of formation rules for strings in a formal language. Formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language ...
1
vote
2answers
480 views

LTL is a star-free language but it can describe $a^*b^\omega$. Contradiction?

Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following ...
4
votes
2answers
305 views

Different standards for writing down expressions in a formal way

What are standard ways to write mathematical expressions in a (semi)formal way ? In different posts of mine concerning similar question I have encountered for a generic expression of the type "for all ...