Questions about 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)

12
votes
1answer
661 views

Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Math people: It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. ...
11
votes
7answers
1k views

Is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$?

is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$? I read in the book that the order of quantifiers make a big difference so I was wondering if these two expressions ...
2
votes
2answers
647 views

What does $\forall x \exists y(x + y = 0)$ mean?

What does $\forall x \exists y(x + y = 0)$ mean? Does it mean "For all x there exists a y for which x + y equals zero"? Thanks.
1
vote
2answers
574 views

common knowledge and concept of coarsening partition

Here is a proof of the equivalence between my definition and Aumann's for "common knowledge". I'm assuming some familiarity with set partitions. Aumann's definition is in terms of the ...
1
vote
2answers
297 views

How to prove that the following language is not regular?

This is the following problem that I've been having difficulty on: For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
1
vote
1answer
679 views

consider the two statements “all rhombi are squares” and “no rhombi are squares” are these two statements negations of each other?

Explain your reasoning I think their negations but do not know how to explain it. I need help But I do know that: Every square is a rhombus, but every rhombus is not a square. A square must have all ...
3
votes
1answer
65 views

Prove that A $\equiv B$

Suppose, I have to prove that $A\equiv B$. I started out by proving that $¬B \implies ¬A$. This proves $A\implies B$. Next I proved that suppose B is true and A is not and this turns out to be ...
2
votes
3answers
461 views

What exactly do truth tables mean?

I'm struggling understanding truth tables. Let's denote a true proposition by 1 and a false proposition by 0. We will be considering the propositional operation, $\Rightarrow$ (implies). The truth ...
0
votes
3answers
50 views

Identifying Proof Method and Implementing It

The question I am working on is: Prove that if $m+n$ and $n+p$ are even integers, where $m$, $n$,and $p$ are integers, then $m+p$ is even. What kind of proof did you use? I was thinking--and ...
7
votes
4answers
1k views

meaning of infinitely many. Is it same as $\forall$?

As the title stated , what is the meaning of infinitely many ? When we say a set contains infinitely many elements, does this mean we cannot finish counting all the elements in the set ? Does ...
2
votes
5answers
233 views

Is there an axiom that prevents other axioms from contradicting each other?

i.e. Does an axiom already exist, which prevents the addition of those new axioms which can contradict already existing axioms? Also, who decides that something is an axiom?
1
vote
1answer
96 views

Uniform continuity on empty set.

Let $\langle X,\rho \rangle$ be a metric space and $f:\emptyset\to X$ a function. Since $\emptyset$ is compact, I know that $f$ is uniformly continuous. But can it be proven by vacuous truth? It's the ...
7
votes
1answer
223 views

What are the formal properties of Godel numbering that are required to make it 'work'?

Godel numbering assigns a number to every formula. It appears to me that any encoding will do. However its also apparent, though I'm not sure how, that certain properties of the encoding used in Godel ...
6
votes
3answers
273 views

Formal definition of equation and unknowns

I was just wondering about the formal definition of equation, I mean in terms of logic and the theory of sets. Suppose for example I wanted to define an equation on $\mathbb{R}$, of course it might be ...
3
votes
2answers
146 views

Category-Theory and the modelling of $n$-ary functions (especially the $0$-ary functions)

Hi have a questioning regarding the modelling of $n$-ary functions and constants. First in the category of sets I know that the empty set $\emptyset$ is initial because for every other set $X$ there ...
2
votes
1answer
5k views

Boolean Algebra - Product of Sums

I converted from a truth table to sum of products and simplified that easily. What I am having problems with is simplifying the product of sums for that same truth table. I have: NOTE: $A' = ...
0
votes
1answer
52 views

Coding normalization

Working on a program that handles CNF (conjunctive normal form). If I have a formula like (a iff b) where iff is if and only if. I'd like to know which one of the following options is the correct ...
1
vote
2answers
2k views

Negating Quantified statements

The problem I am working on is: Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express ...
2
votes
1answer
610 views

Determining The Truth Value Of Quantified Statements

The problem I am working on is: Determine the truth value of each of these statements if the domain consists of all integers. a) $∀n(n+1>n)$ b) $∃n(2n=3n)$ c) $∃n(n=−n)$ ...
0
votes
1answer
104 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
3
votes
3answers
953 views

Determining Whether Arguments Are Valid

The question is, "Determine whether each of these arguments is valid. If an argument is correct, what rule of inference is being used? If it is not, what logical error occurs? a) If $n$ is a real ...
2
votes
4answers
854 views

Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $

I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
1
vote
2answers
443 views

Logic gates analyses

How to write the output of the gates not, and, or, xor, nand and nor in terms of their inputs, expressed as zeros and ones, using base 10 addition and multiplication. Thanks much in advance!!!
0
votes
1answer
57 views

Does adjoining an induction schema to a theory of arithmetic interact nicely with adjoining its consistency statement?

I'm struggling to articulate this question, but here it goes. For any first order theory $T$ involving a unary function symbol $S$ (intuitively, the successor function), let $I(T)$ denote the theory ...
0
votes
2answers
143 views

Church's Thesis

If we let $f$ be a computable function and define $h(x) = 1$, if $x$ is an element of $\operatorname{dom}(f)$ and undefined otherwise. I am trying to prove that h is computable via Church's Thesis. ...
0
votes
1answer
403 views

URM computable indicating RAM computability

How can we show that every URM computable function is RAM computable? I can see that that from Church's thesis, URM Computability iff p.r., but now sure how to get this claim above. Taking the hint ...
0
votes
1answer
600 views

circuit in Conway’s Game of Life

Let's assume that the bits in the Moore neighborhood are numbere as follows: $$\begin{array}{lll} a_4 & a_3 & a_2 & a_{11}\\ a_5 & {\large a_0} & a_1 & a_{10} \\ a_6 & ...
1
vote
1answer
138 views

Moore neighborhood on a two-dimensional Cartesian lattice

How many distinct cellular automata rules are there that use the Moore neighborhood on a two-dimensional Cartesian lattice if we allow three bits (eight states) per site?
1
vote
1answer
756 views

Understanding common knowledge in logic and game theory

For $k = 2$, it is merely "first-order" knowledge. Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does ''not'' know that the other blue-eyed person ...
2
votes
3answers
123 views

Are PA and ZFC examples of logical systems?

Wikipedia says A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to ...
1
vote
2answers
49 views

For arbitrary theories T and S, is it meaningful to say “T proves the consistency of S”?

For arbitrary (first-order) theories T and S (where T needn't be a theory of arithmetic), is it meaningful to say "T proves the consistency of S"?
1
vote
2answers
375 views

Negate the following statements

1) For every shape A, there is a circle D, such that D surrounds A 2) There is a circle C, such that for every line l, l intersects C This is what I got are my answers correct 1) There is at least ...
4
votes
6answers
2k views

Does law of excluded middle prove itself?

Law of excluded middle says that for any proposition ($A$) either it is true or it's negation ($\bar{A}$) is true: $A\veebar\bar{A}$. When I was taught math logic, this was given as an axiom, but I ...
5
votes
2answers
152 views

Is it possible that two theories be equiconsistent, with Peano Arithmetic not able to prove this?

Do there exist first-order theories that are are equiconsistent, but which cannot be proven to be equiconsistent using Peano Arithmetic? (I hope not.)
1
vote
2answers
138 views

How can I prove the majority of three languages is also regular if the three languages are regular?

This is a question I've been stuck on recently: Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
3
votes
2answers
151 views

How bad is this analogy for logical independence?

It is an amazing and well-known fact that the Continuum Hypothesis is logically independent of Zermelo-Frankel set theory with the Axiom of Choice (ZFC), assuming it is consistent. In a similar vein, ...
4
votes
1answer
305 views

Gödel Completeness theorem

I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems. What I understand now (and you will see my understanding ...
4
votes
2answers
409 views

Is “reflexive transitive closure of relation $R$” a first-order property?

Suppose I have a language with two binary relation symbols $R$ and $R^\ast$. Suppose I have a first-order theory $T$ which says some things about $R$, but nothing about $R^\ast$. Is there a set of ...
2
votes
1answer
115 views

Are the brackets in formal box notation of recursive functions omittable?

So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
3
votes
1answer
107 views

Is first-order logic a sufficiently powerful metatheory to prove the “conditional independence” of CH from ZFC?

Lets define independence and conditional independence as follows. Define that an axiom $X$ is independent from a system $Y$ if and only if $Y$ can be used to prove neither $X$, nor its (syntactical) ...
4
votes
2answers
2k views

How to use the Rules of Inference to a statement from two premises

The problem is as follows: Given the premise ∀x(P (x) ∨ Q(x)) and ∀x((¬P (x) ∧ Q(x)) → R(x)) is true, use the rules of inference to show that ∀x(¬R(x) → P(x)) is also true. (The domains of all ...
3
votes
4answers
838 views

Quantified Statements To English

The problem I am working on is: Translate these statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) $∀x(C(x)→F(x))$ ...
1
vote
4answers
175 views

Would it also be useful to include an ordered pair function in first order logic?

Typically, first-order logic is assumed to include an equality relation $=$, even though this is "non-logical," together with some postulates about equality. Would it also be useful to include an ...
4
votes
1answer
135 views

Reference request - is there an axiomatic theory of consistency?

Is there an axiomatic theory whose domain of discourse can be interpreted as a collection of first order theories, which has a predicate $\mathrm{Con}$ such that $\mathrm{Con}(T)$ can be interpreted ...
2
votes
3answers
172 views

How to prove this with induction

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$ is the same as $$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$ Do I ...
2
votes
1answer
104 views

Successor axiom systems and sequences of axiom systems

Let $A$ denote a system of first-order axioms. Is there a canonical way to form a successor system $A'$ extending the ontology of $A$ to include all definable collections? Edit: Importantly we want ...
2
votes
2answers
3k views

Simplifying the following expression using Boolean Algebra

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR a'.b'.c' + a.b'.c' + a.b.c' This is what I have so far. a'.b'.c' + ...
2
votes
2answers
59 views

Definabilty of two functions on natural numbers

Is there a first order logic arithmetic ($0,+,\cdot$) formula $f(n,m)$ such that $f(n,m)$ is true in $\mathbb{N}$ iff $m$ is the $n$th prime number? Similarly, is there $g(k,n,m)$ which is equivalent ...
4
votes
3answers
664 views

Is A∨¬A a tautology when there is a proof (by contradiction)?

$A \lor \neg A$ is stated as a "tautology", but is it really a tautology? It can be proven by counterposition. And therefore it is not a tautology when it can be proven(?) Update Here's the proof ...
3
votes
1answer
762 views

Correct Path To Castle Riddle [duplicate]

I'm working on the following riddle that I found to be kind of interesting, but I can't figure it out. The problem is as follows: A prince visits an island inhabited by two tribes. Members of one ...