Skip to main content

# Questions tagged [logic]

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

28,327 questions
Filter by
Sorted by
Tagged with
-2 votes
0 answers
21 views

### Why does universal generalization not prove $\forall x \in X \vdash P(x) \implies \vdash \forall x \in X P(x)$?

I have learnt that if $X$ is any set and $P(x)$ is any proposition defined for any $x \in X$, $\forall x \in X \vdash P(x)$ doesn't necessarily imply that $\vdash \forall x \in X P(x)$. However, I ...
• 3,037
0 votes
0 answers
25 views

### Questions on Effectively Denumerable Sets and Universal Programs in Computability Theory

I'm currently reading the book Computability: An Introduction to Recursive Function Theory by Nigel Cutland. I find this book very good, but I have two unresolved questions about it: Definition of &...
• 297
-1 votes
0 answers
45 views

### Circular definition in propositional logic?

Please excuse me if this question has been raised before - I have absolutely no idea how phrase an appropriately detailed query, perhaps due to how philosophical this is. Consider the definition of a ...
• 129
0 votes
1 answer
46 views

### Can we conclude $\forall x \in X Q(x)$ from $\forall x \in X P(x)$ and $\forall x \in X P(x) \implies Q(x)$ here?

Let $X$ be any set, and let $P(x)$ and $Q(x)$ be propositions which are defined for any $x\in X$. Say that we know that $\forall x \in X P(x)$ and that $\forall x \in X P(x) \implies Q(x)$. I want to ...
• 3,037
1 vote
1 answer
32 views

• 1
1 vote
1 answer
63 views

### Is My Proof of This Set's Property Rigorous?

I have a set $A$ which is a non-empty set of real numbers, and it does not contain zero. The set $A$ satisfies the following properties: Property $P_1$: For any $x, y \in A, xy \in A$. Property $P_2$:...
• 393
0 votes
0 answers
67 views

### Why do we need to show $\lnot \lnot P \implies P$ when justifying proof by contradiction here? Does my proof work without doing this?

I am confused of the justifications I hear for why proof by contradiction works, including the one on wikipedia. I am confused why people say we need the law of the excluded middle, and why Wikipedia ...
• 3,037
0 votes
0 answers
60 views

### Did Gödel use the term "mathematical logic" to mean the same thing it means today? [closed]

Today the term mathematical logic usually refers to a part of mathematics that includes proof theory, model theory, set theory and recursion theory, some of which originated with Godel's famous ...
• 51
0 votes
1 answer
93 views

### Let $P,Q$ be statements. If $P$ is a false statement, then $P\implies Q$ is true. This convention works perfectly anytime. Why? [duplicate]

I learned the following convention. Convention 1: Let $P,Q$ be statements. If $P$ is a false statement, then $P\implies Q$ is true. Convention 1 works perfectly anytime. Why? For example, ...
• 1,260
2 votes
2 answers
160 views

### Intuition behind Gödel's diagonal lemma?

I'm trying to develop a good intuition for how Gödel's first incompleteness theorem works. I think I've got most of it, but there's one step involving a lemma I haven't been able to really get. Here's ...
2 votes
0 answers
59 views

1 vote
1 answer
54 views

### To what extent can Primitive Recursion perform wellfounded recursion?

Ordinarily, primitive recursive functions are such that each value is recursively defined from the value immediately prior. It's not hard to improve that to several values, by a clever encoding of ...
• 2,191
0 votes
2 answers
60 views

### Difficulties with an existence and uniqueness proof

Have been trying to prove this for 2 hours straight. I'm asked to prove that there is a unique $A \in P(U)$ such that for every $B \in P (U)$, $A \cap B = A$. I understand that $A=\emptyset$ satisfies ...
• 33
2 votes
0 answers
113 views
+50

### Formalizing a Theory in a Universe and Model vs Universe question

A basic question about a terminology on fondation of set theory: What does it mean to "formalize a formal theory (ie a collection of syntactically welldefined sentences with resp. to some ...
• 7,851
0 votes
0 answers
108 views

### Are there any deep series Involving $\pi^e$ , $e^e$ , $\pi^\pi$ that are derived from Jacobi theta functions that resulting to close integers [closed]

I have developed a interest in the topic of almost integers. I have reviewed materials on Wikipedia and Wolfram, and I have been conducting experiments at home, discovering some interesting findings. ...
1 vote
1 answer
99 views

### How do I calculate the points within in a polygon that changes height and width to create a hollow frame shape?

I am using JavaScript to create a shape using clip-path. I have no issues with the code but my issue lies with the math. I can get close to my goal but it fails once the shape's height or width is ...
• 45
2 votes
1 answer
167 views

### Metalanguage Integers

In context on set theory & model theory of set theory what does exactly mean "metalanguage integer(s)"? Recall a metalanguage ( where one reasons about object theory phrased in object ...
• 7,851
1 vote
3 answers
108 views

### Is my proof correct? Suppose $A \cap B \subseteq C \setminus D$. Prove that if $x \in A$, then if $x \in D$, then $x \notin B$

I'm a high school student studying Velleman's How To Prove It without any help from a professional mathematician. I came across this problem in chapter 3 problem 9 and I am not really sure if my proof ...
• 41
0 votes
0 answers
23 views

• 119
8 votes
1 answer
97 views

### Analytic sets vs recursively enumerable sets

I have long thought (due to my limited knowledge in both subjects) that analytic sets of reals are analogous to recursively enumerable sets of natural numbers: Analytic sets are images of continuous ...
• 562
2 votes
2 answers
73 views

### $( A \subseteq B \land B\subset C ) \implies (A \subset C)$ [ proof by quantification theory]

I had a problem to find out the proper quantified sentence to prove this theorem. I saw an answer in this platform and here's the link. But I want to prove the theorem using only logic (I mean ...
5 votes
1 answer
180 views

### External Integers and First-Order Formulas in Set Theory

So far I know it is not possible to express the natural numbers $\Bbb N$ in terms of a first order sentence in language from ZFC. More precisely, one can in ZFC prove only it's existence as "...
• 7,851
0 votes
0 answers
44 views

### What is the "Godel ordering of algorithms"?

I was reading this paper, and in example 3.8 appeared the ideia of "Godel ordering of algorithm". Does anyone know what is this ordering? I've seen some things about Godel ordering, but ...
• 41
2 votes
1 answer
161 views

-1 votes
2 answers
121 views

### If $A\Rightarrow B$, how does $\bar{A}$ say nothing about B? [closed]

I'm reading Probability Theory by E.T. Jaynes and in the first chapter on plausible reasoning, he states The proposition $A\Rightarrow B$ does not assert that either A or B is true; it means only ...
• 107
0 votes
1 answer
64 views

### Deduction construction examples in Kleene's "Introduction to Metamathematics"

The deductions for construction proposed to readers seem to be pretty easy, but I'm not quite sure of my solution. I'm talking about the example 2 in §20. The first one is to construct $A\&B$ from ...
2 votes
0 answers
51 views

### Can the consistency of a complete recursively axiomatizable be decided?

It's known that the theorems of a complete, recursively axiomatizable theory $T$ must be decidable. Enderton proved this in his Corollary 25G by considering whether $T$ is consistent (Enderton's ...