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)

4
votes
1answer
93 views

Show that the theory of the $Th(\mathbb N)$ in first order logic with the finiteness quantifier is categorical

Suppose that a finiteness quantifier $\mathbf Fx$ is added to first order logic. Its semantics are: $\mathbf Fx\Phi(x)$ is true in a model just in case there a finitely many things in the domain of ...
8
votes
3answers
215 views

How to deduce that something does not follow?

Assume I have formulas $H$, $P$ and $Q$. Assume further that I can show in classical logic that $P$ follows from $H$: $$H \vdash P$$ And that the negation of $Q$ follows from $H$: $$H \vdash \neg ...
0
votes
2answers
156 views

Show that there is a hyperreal number system of the same size as the real numbers?

The hyperreal number system is defined as one that contains the real numbers, satisfies the first order properties of real numbers, and contain infinitesimals. It can't be as simple as stating the ...
2
votes
1answer
106 views

Logic - finding most general statement

Let A and B be sets. For each statement below, please write down the most general statements you can make about A and B. Make sure you justify your answer. a. A ∪ B = A? b. A ∩ B = A? c. A ∪ B = A ...
0
votes
3answers
400 views

Restricted quantifiers - Logic

Let $P(x),Q(x),R(x)$ be the statements $x$ is a clear explanation,$x$ is satisfactory,$x$ is an excuse,respectively. Suppose that the domain for $x$ consists of all the English text. Express each of ...
0
votes
2answers
105 views

Arithmetic functions

This may be a slightly vague question but if one defines a function (of some arity) recursively on the natural numbers, the "simplest" examples are things like addition, multiplication, or factorial. ...
0
votes
1answer
431 views

Logic Puzzle from “101 Puzzles in Thought and Logic”

The following is a puzzle from "101 Puzzles in Thought and Logic" By C R Wylie, Jr. Jane, Janice, Jack ,Jasper and Jim are the names of five high schools chums. Their last names in one order or ...
4
votes
3answers
198 views

$\langle \Bbb Q,<\rangle$ is an elementary submodel of $ \langle \Bbb R,< \rangle$

I am trying to show that $\langle\Bbb Q,<\rangle$ is an elementary submodel of $\langle\Bbb R,<\rangle$. I first believed that this problem is quite trivial $-$ I thought all I needed to do was ...
1
vote
4answers
532 views

Prove equivalence $(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$

Prove equivalence $$(P \Rightarrow Q) \land (P \Rightarrow R) \Leftrightarrow P\Rightarrow(Q\land R)$$ What is the step by step for the equivalence of these equations. I can first break down the ...
2
votes
3answers
413 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...
1
vote
1answer
153 views

Different Negations of Self-referential Propositions

On Page 33, The Liar: an Essay on Truth and Circularity, (Barwise and Etchemendy, 1987) Exercise 6 Explain how the claims made by the following sentences ...
0
votes
2answers
104 views

Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7. So i'm not completely sure how to use strong induction, but the base case is ...
0
votes
2answers
693 views

Contrapositive of an Implication

Why is the contrapostive of an implication equivalent to its normal truth table? i.e. why is this the case: $$ \begin{array}{c|l|c} p & q & \text~p \implies \text~q \\ \hline 1 & 0 ...
2
votes
1answer
372 views

Transcribing Propositions In English To The Language Of Logic

The question I am working on is: Let $p$ and$q$ be the propositions $p$:It is below freezing. $q$:It is snowing. Write these propositions using $p$ and $q$ and logical connectives (including ...
1
vote
1answer
704 views

Determine Consistency Of System Specifications

I am looking at an example problem in my text: "Determine whether these system specifications are consistent: 'The diagnostic message is stored in the buffer or it is re-transmitted.' 'The ...
6
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
3
votes
1answer
88 views

If $X=\bigcup_{n\in{\mathbb{N}}}\kappa^n$, is it provable from $ZF$ that $|X|=\kappa$?

My question is the following, if $\kappa$ is an aleph and $F$ is the set of all finite sequences in $\kappa$, then the fact that $|F|=\kappa$ is provable from $ZF$?. This can be proven from $ZF$ for ...
3
votes
3answers
302 views

Proving that the theorems of one logistic system are also theorems of another logistic system

Question: I am developing the proof for the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1102. Let $\mathscr{M}$ be ...
5
votes
3answers
223 views

Negating “Zach blocks e-mails and texts from Jennifer”

I am reviewing some basic propositional logic. The question that I have come across that has given some confusion is Zach blocks e-mails and texts from Jennifer where I am asked to find the negation ...
3
votes
1answer
137 views

Automorphism of an elementary extension of a structure that moves an undefinable element

I know that the easiest way to show a point is not definable is to find an automorphism of the structure that moves the given point. I've also seen many examples undefinable points that couldn't be ...
0
votes
2answers
103 views

Is the halting of a program that checks for duplicates in an infinite multiset decidable?

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset. Let $\Phi$ be an empty multiset. Take any element $\sigma$ from $\Sigma$. If $\sigma \in \Phi$, return true. Otherwise, ...
1
vote
2answers
813 views

Example of decidable & undecidable in First Order Logic

What would be an example of decidable & undecidable in First Order Logic? Edit: With first order formulas
2
votes
2answers
173 views

What is a Complex Name?

On Page 38, Elementary Set Theory with a Universal Set, Randall Holmes(2012), which can be found here. We give a semi-formal definition of complex names (this is a variation on Bertrand ...
1
vote
3answers
247 views

Given an Inconsistent Set, find a Consistent Subset

I'm a student learning first-order logic, so forgive me if this is elementary. If I'm given an inconsistent set (that is, a set $\Sigma$ that can be used to show $\phi$ and $\lnot\phi$), is it ...
4
votes
2answers
2k views

How do you make a universal quantifier a existential quantifier in a multiple-quantifier statement?

So I'm studying for a final- and one of the study questions is "Express (as simply as you can) each of the following sentences without the use of universal quantification:" a) (∀x)(∃y)(∀z)[P(x,y,z)] ...
0
votes
1answer
365 views

The Definition of Consistency and Compactness in FOL

First order logic: "consistency," "compactness"? Consistency: A set $\Sigma\subseteq\text{WFF}$ is consistent iff there is no $\varphi\in\text{WFF}$ such that $\Sigma\vdash\varphi$ and ...
1
vote
2answers
51 views

Logic - Will a second parameter value inherit negation if the first parameter is false?

Will a second parameter value inherit negation if the first parameter is false? Like: (~A & B) → X Is B false? Would it ...
3
votes
1answer
234 views

Consequences of axioms of Dense linear order without endpoints is complete

I've been musing over this problem over the past few days, and believe I have an answer. However, I am still a bit shaky with some of the definitions I am using, and would appreciate if anyone could ...
2
votes
2answers
77 views

In unification, what cannot be unified?

Looking at various examples online, some seem concrete, but some seem to not be explained properly. Can $f(x)$ be substituted with $g(x)$? I know that $x$ cannot be substituted with $f(x)$, but $x$ ...
5
votes
7answers
693 views

What are some examples of subtle logical pitfalls?

Here's an example: Demonstrating that the assumption $A=B$ leads to a true statement is a vacuous truth. In order the show that $A=B$, prove that the difference $\Delta =A-B$ is zero. The subtle ...
22
votes
1answer
554 views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...
4
votes
3answers
1k views

De Morgan's Second law

De Morgan's second law makes sense: not p and q is the same as not p or not q. However, when I tried to construct a sentence as an example of the law, it seemed not true. For example: Sequa does not ...
1
vote
1answer
103 views

What is/How to do Unification

I'm reviewing for a final exam on Monday, and I have a question I was unable to answer on a previous test. The professor's notes were horrendous, and I can't find anything better online. They all seem ...
0
votes
1answer
273 views

First Order Logic Example of Halting Problem

I am trying to understand the halting problem better. What would be a few examples of some first order formulas that express a halting problem? Any responses would be appreciated! Thank you!
8
votes
2answers
315 views

Does negation of Axiom of Choice imply symmetry?

It seems that every construction of a model in which the Axiom of Choice fails involves some kind of symmetry. Is there an example of a construction of a model where AC fails but no argument involving ...
1
vote
0answers
328 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
9
votes
5answers
4k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
2
votes
1answer
215 views

Does elementary embedding exist between two elementary equivalent structures?

By previous question, if there is a elementary embedding from $\mathfrak A$ into $\mathfrak B$, then $\mathfrak A \equiv \mathfrak B$. Now it is naturally to ask conversely, if $\mathfrak A \equiv ...
1
vote
1answer
327 views

Is one structure elementary equivalent to its elementary extension?

Let $\mathfrak A,\mathfrak A^*$ be $\mathcal L$-structures and $\mathfrak A \preceq \mathfrak A^*$. That implies forall n-ary formula $\varphi(\bar{v})$ in $\mathcal L$ and $\bar{a} \in \mathfrak A^n$ ...
1
vote
2answers
882 views

What is definability in First-Order Logic?

Can someone explain to me the definition of definability in first-order logic in simple terms and with an example? I would appreciate this. I just want to really understand this. Thank you. Here is ...
3
votes
2answers
364 views

Automorphisms of saturated models

This is basically Exercise 10.1.5(c) in Hodges's Model theory. First, a reminder of some definitions: Let $\lambda$ be a cardinal, and let $\Sigma$ be a finitary first-order signature. A ...
0
votes
2answers
76 views

Number mapping function

I can't find out a function f(x)=y that would map my x's to required y's. It is OK to write it in a programming language. Notation in mathematics is also OK. It ...
2
votes
3answers
150 views

Are these two statement equivalent?

$\forall x \exists y P(x,y)$ $\exists x \forall y P(x,y)$ where P(x,y) means x is smaller than y. I believe that they mean the same thing.
1
vote
3answers
208 views

Are these statements equivalent (quantifiers)?

$\neg \forall x \exists y \neg P(x,y)$ is equal to $\exists x \exists y \neg P(x,y)$ I had to make sure, because I wasn't sure at all.
4
votes
3answers
197 views

Want to show Quantifier elimination and completeness of this set of axioms…

Let $\Sigma_\infty$ be a set of axioms in the language $\{\sim\}$ (where $\sim$ is a binary relation symbol) that states: (i) $\sim$ is an equivalence relation; (ii) every equivalence ...
0
votes
2answers
240 views

Discrete Math Logic Homework

Consider the following statement: $$\forall \epsilon > 0,\space\exists\delta>0:(|x-a|\lt\delta\implies|f(x)-L|\lt\epsilon).$$ (a) Write the converse of the statement.(b) Write the ...
1
vote
1answer
218 views

Stuck on simple relations between sets

Find the relations between A, B and C when $[(A\cap B)\cup C]-A=(A\cap B)-C$ So we can write it as: $[(A\cup C)\cap(B\cup C)]-A=(A\cap B)-C$. Here comes the problem, though. Can I just assume ...
1
vote
4answers
146 views

How to prove this logic?

How to prove $\exists x (P(x) \lor Q(x)) \equiv \exists x P(x) \lor \exists x Q(x)$ I know it is tautology... but how to solve...? Please help.
3
votes
1answer
125 views

Feferman-Vaught theorem and Term Powers

In an example of usage of quantifier elimination in wikipedia, it briefly mentions Feferman-Vaught theorem and Term Powers, but I am finding little information on what these are. Can anyone explain ...
0
votes
1answer
198 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...