Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

7
votes
1answer
192 views

Non-Isomorphic Ultrapowers

It is clear that given a family $(\mathfrak{A}_i)_{i\in I}$ of $L$-structures their ultraproduct may depend on the choice of the ultrafilter (for this question I am only considering non-principal ...
2
votes
4answers
3k views

How do I prove the transitivity of a set of implications?

If I have a set of implications, how can I prove the transitivity? In other words: I know the transitivity law, but I need to show on paper for an assignment whether the argument is valid or not. $$ ...
1
vote
1answer
108 views

Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$ is a tautology

Prove that $((p\lor q)\land(p\lor(\lnot q)))\rightarrow p$ Please could someone give me some feed back on this proof? Does it look correct? = $\lnot ((p\lor q)\land(p\lor(\lnot q)))\lor p$ = $ ...
2
votes
1answer
88 views

Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
4
votes
2answers
209 views

Sequent calculus and first incompletness theorem

Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
1
vote
1answer
122 views

Unintelligible statement in a text of Logic

re-reading some of the Shoenfield's book, "Mathematical logic", I noticed a statement incomprehensible. The offending statement is on page 89, where it says: With the result mentioned in (iv), this ...
1
vote
2answers
51 views

if F , G are two formulas , h[f] is the height of the formula f ,then h[ G a F ] is less or equal to sup( h[F] , h[G] ) + 1

if F , G are two propostional formulas , h[f] is the height of the formula f , then h[ G a F ] is less or equal to sup( h[F] , h[G] ) + 1 , a is one of the connectives , my question is , what is sup ...
0
votes
2answers
92 views

why are these words not formulas?

these words here : A^B ( A implies B v C ) ( A implies B,c ) ( A^B^C) for all A ( A v not A ) (( A^(B implies C )) v ( not A implies ( B^C)) ^ ( not A v B )) not (A) why these words are ...
2
votes
1answer
72 views

CNF Rule hierarchy discovery

This is bothering me for some time. Consider that I have a set of CNF formulae: $F_1 = \left( A \lor B \lor C \right) \land \left( C \lor D \lor E \right) \land \left( B \lor F \lor G \right)$ $F_2 ...
13
votes
5answers
714 views

Notation Question: What does $\vdash$ mean in logic?

In a "math structures" class at the community college I'm attending (uses the book Discrete Math by Epp, and is basically a discrete math "light" edition), we've been covering some basic logic. I've ...
1
vote
1answer
162 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ ...
5
votes
3answers
227 views

Logic - how to prove $\;[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r) \equiv T\;$?

That's what I have so far... It seems like a bad approach. I've tried others and end up in the same spot.
1
vote
2answers
555 views

Propositional Logic - Associative Property question

$p \land \lnot q \lor q \land \lnot r \lor \lnot p \lor r $ $\equiv$$(p \lor \lnot p) \land (\lnot q \lor q) \land (\lnot r \lor r)$ Is this move "legal"? Or can you only apply the associative ...
5
votes
3answers
597 views

Counting Rows of a Truth Table that Satisfy a Condition

How can I mathematically count the number of rows in a truth table of n-inputs that will satisfy a certain boolean condition? For example, say I have a 4-input truth table that will in turn have 16 ...
7
votes
2answers
508 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) ...
2
votes
2answers
3k views

How to prove that a set of logical connectives is functionally complete(incomplete)?

How to prove that a set of logical connectives is functionally complete(incomplete)? For example, we are given this set: $ \left\{\begin{matrix} f = (01101001) \\ g = (1010) \\ h = (01110110) \\ ...
39
votes
2answers
1k views

Is it possible to prove a mathematical statement by proving that a proof exists?

I'm sure there are easy ways of proving things using, well... any other method besides this! But still, I'm curious to know whether it would be acceptable/if it has been done before?
1
vote
2answers
79 views

negation of the quantification of a constant function

I got the constant function $\mathbb{R}->\mathbb{R}$ $f(x) = c$ which could be expressed as $\forall x \in \mathbb{R} \exists!c \in \mathbb{R}:f(x) = c $ But after I negated this term, therefore ...
2
votes
1answer
50 views

Expressing “uncountable” in $L_{\omega_1\omega}$

Given a countable signature $\tau$ I'm trying to find a uncountable $\tau$-Structure $\mathfrak{A}$ which does not satisfy the same infinitary logic $L_{\omega_1\omega}$-sentences as a countable ...
1
vote
1answer
60 views

All classes of finite structures are axiomatizable in $L_{\infty\omega}$

We want to proof that every class of finite structures is axiomatizable in the infinitary logic $L_{\infty\omega}$. We fix the signature $\tau$ (is okay to do so?). Thus, we can assume that for every ...
2
votes
1answer
99 views

When and why does the Lindenbaum extension construction fail for second order theories?

From any consistent set of first order sentences $\Gamma$, one may generate by an inductive process a unique set of sentences $\Delta(\Gamma)$ such that $\forall A, \Gamma \models A \implies A \in ...
1
vote
2answers
203 views

Definable relations of $(\mathbb R; <)$ in first-order language

On page 101, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), What subsets of the real line $\mathbb R$ are definable in $(\mathbb R; <)$? What subsets of the plane $\mathbb R ...
3
votes
1answer
399 views

Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive. Let $E$ be the set of even natural numbers. The function $f$ defined ...
3
votes
2answers
80 views

Class of structures isomorphic to $(\mathbb{Z},<)$ in infinitary logic $L_{\omega_1 \omega}$

We want to define the class of all structures isomorphic to $(\mathbb{Z},<)$ in the infinitary logic $L_{\omega_1 \omega}$. Therefor we define strict order as usual: $\forall x,y,z ~~ (x<y ...
1
vote
1answer
181 views

Representing Recursion and Primitive Recursion diagrammatically

I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
2
votes
3answers
413 views

Annoying logical deduction

I'm trying to show that $\vdash \neg\neg A \to A$. I can't seem to figure out the deduction. Mendelson proves this in his book, but I'm trying to use a different set of axioms. These are $A\to (B\to ...
3
votes
1answer
151 views

Members of (lightface) Borel sets

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
1
vote
2answers
177 views

Sentence such that the universe of a structure has exactly two members

On page 100, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Assume that the language has equality and a two-place predicate symbol $P$. For each of the following conditions, ...
3
votes
2answers
220 views

Antique handling of consequentia mirabilis?

Would Aristotele deem the following classically valid (*) conclusion $$\lnot A \rightarrow A \vdash A$$ a petitio principii? How would he go about showing it? (*) ...
3
votes
1answer
230 views

Strictly decreasing function $f(n)>f(n+1)$ is not definable in $\mathbb{N}$ (Set Theoretic (Neumann's) construction of $\mathbb{N}$).

I'm studying some Set Theory now and I oppose to a problem which I guess it is related to well ordering of Natural numbers. The problem is: Prove that there is no function ...
3
votes
3answers
204 views

$(p \land q)\implies(p \lor q)$, how to make a truth table with $p$ twice?

I thought I understood truth tables, until I saw repeats of $p$. I guessed on this one: $p \implies \neg p$. This is what I have: $$ \begin{array}{c||c||c} p & \neg p & p \implies \neg p\\ ...
3
votes
3answers
431 views

Why is axiomatic system needed in propositional logic?

I am trying to learn propositional logic. I have read that axiomatic system is defined since there are some problems which can not be solved using truth tables. I have found such a problem in ...
2
votes
1answer
76 views

Equivalence of two limit point statements

In my homework it is asked to prove the following statement: Let $X \subseteq \mathbb{R}^m$, let $y$ be a limit point of $X$, and let $f:X\setminus\{y\} \to \mathbb{R}$ be a function.There is a ...
10
votes
4answers
476 views

Clarification of a remark of J. Steel on the independence of Goldbach from ZFC

On page 424 of the following paper: S. Feferman, Harvey M. Friedman, P. Maddy and John R. Steel, ``Does Mathematics Need New Axioms?'' The Bulletin of Symbolic Logic, Vol. 6, No. 4 (Dec., 2000), pp. ...
5
votes
4answers
153 views

Example of a question that would seem not to have enough information for an answer

Looking for an example of a question that would seem not to have sufficient information for an answer, or a question that the solution would not require (or maybe even maybe hindered ) by the extra ...
5
votes
2answers
121 views

How does Fraenkel's urelement proof show choice is independent of ZF?

I understand the actual proof Fraenkel gives but I can't see how it proves choice independent of the full ZF because he works in a very restricted universe. Can anyone show how to connect one to the ...
1
vote
2answers
219 views

Show that if $x$ does not occur free in $α$, then $α \vDash ∀ x α$.

On page 99, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that if $x$ does not occur free in $α$, then $α \vDash ∀ x α$. Added:This could be seen as a follow-up problem of ...
3
votes
2answers
206 views

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence?

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence? $Q$ is a unitary relation. I suppose that $\vDash Q x \to \forall x Qx$ , which is equivalent to $\vDash Q x \to \forall y Qy$ is ...
10
votes
4answers
484 views

which texts do you recommend to study mathematical logic?

I want to study Godel's incompleteness theorem's and I look for a text whoch provide mathematical logic with a nice way to make me able to study Godel's incompleteness theorems I didn't study ...
3
votes
1answer
92 views

What does Equational Theorem Prover do?

http://www.cs.unm.edu/~mccune/eqp/ What does EQP do? Is there any paper that explains what it does? README and other read files do not provide such information - it only talks of how to use it and ...
5
votes
0answers
128 views

Interpretation of impure set theory within pure set theory?

I recently came across this paper, where the author (in section 3.1) gives an interpretation of ZFU within ZF. The author of the paper goes on to show what he calls the "synonymy" (i.e., that ZF and ...
2
votes
2answers
243 views

multiple xor (sum of parities)

If we have: $b_1 \oplus b_2 = b_1 (1 - b_2) + b_2 (1 - b_1)$ what is (or are, if there are different versions) the compact general formula for a multiple "summation": $b_1 \oplus b_2 \oplus \dotsb ...
2
votes
1answer
587 views

Spivak Chapter 2, problems 27 (and 28)

To be honest, I have no idea how to even start this problem. I'm sorry I don't have any work to show, but I'm just at a blank. Help? Chapter 2: Problem 27: "University B, once boasted 17 tenured ...
2
votes
2answers
187 views

Are all models of peano arithmetics descibed using first order logic non standard?

It is known that there are non-standard models of Peano Arithmetics when it is described using first order logic. My question is if there is standard model (one which does not contains non-standard ...
3
votes
4answers
343 views

some question about logic that the premise is false.

Is it just for convenience that define false statements imply anything? if yes, why it would be defined like this?
6
votes
0answers
246 views

Foundation for category theory

Before a little premise: It's well known that we can internalize the notion of category, functor and natural transformation in any category with enough structure: for instance we can define what an ...
1
vote
1answer
71 views

Why a formula must be closed in order to prove decidability?

Based on this from http://www.encyclopediaofmath.org/index.php/Decidable_formula A decidable formula is a formula A of a given formal system that is either provable in this system (that is, is a ...
3
votes
3answers
161 views

Definition of computability of real numbers?

What exactly does it mean to say that a real number $x$ is computable? I can think of two reasonable definitions but I am not sure whether or not they are equivalent: 1) There is an algorithm which ...
0
votes
1answer
51 views

Are these steps correct?

Let: $f, x, u, y, v : \mathbb{C} \to \mathbb{R}$ be functions in the complex variable $s$. I made this claim If $f(s)≠0 \,\pmod{2\pi}$, then $x(s)=0,u(s)=0, y(s)=0,v(s)=0$, (this first implication ...
1
vote
2answers
301 views

Example of unsatisfiable set of wffs, with each pair is satisfiable

On page 66, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), For each of the following conditions, give an example of an unsatisfiable set $\Gamma$of formulas that meets the ...