Questions tagged [elementary-set-theory]
This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, relations and functions, countability and uncountability, etc. More advanced topics should use (set-theory) instead.
27,475
questions
-6
votes
0
answers
28
views
Кто может помочь доказать тождество? A ∪ В = (А \ C) ∪ (В \ А) ∪ (А ⋂ В) [closed]
A ∪ В = (А \ C) ∪ (В \ А) ∪ (А ⋂ В)
- 1
0
votes
0
answers
28
views
$f:\mathbb{R}\to\mathbb{R}$ is increasing. $\{y\in\mathbb{R}:\#f^{-1}(\{y\})\geq 2\}$ can contain at most countably many points. Why?
I am reading "Measure, Integration & Real Analysis" by Sheldon Axler.
The following exercise is Exercise 24 on p.40 in Exercises 2B in this book.
Exercise 24
Suppose $B\subset\mathbb{R}$...
- 7,456
0
votes
0
answers
13
views
Is there a proof showing that all (absolutely) normal numbers are disjunctive?
I was reading the Wikipedia pages for normal numbers and disjunctive sequences (hadn't come across either of these terms before so I'm not an expert or anything, pls be nice. Just going on a tangent ...
1
vote
0
answers
16
views
If I can find two limits of a set relation, what effect does that have on set relationships?
I'm a bit new to set theory, so forgive me if I'm missing some formalisms here.
Let x be some finite set of actions, and y be some finite set of actions, and $\omega$ be a scalar s.t. $0 \leq \omega \...
- 111
-3
votes
0
answers
11
views
How to prove A△(A△B)=B and (A|B|C)&(A|not B|C)¬(A|C)=∅ [closed]
Problem : Prove the following properties of the symmetric difference:
1)A△(A△B)=B
2)(A|B|C)&(A|not B|C)¬(A|C)=∅
0
votes
0
answers
19
views
Handbook of Categorical Algebra Definition 1.1.2
In the definition mentioned in the title, an universe $\mathcal U$ is defined as a set satisfying some properties. One of this properties is that if $x\in \mathcal U$ and $f: x\to y$ is surjective ...
- 149
-1
votes
0
answers
50
views
Why doesn't Cantor's diagonal argument also work for rational numbers? [duplicate]
Let's suppose that we don't know how to arrange all the rational numbers in such a way that easily shows that they're countably infinite. I present to you the following list which claims to include ...
- 117
3
votes
1
answer
124
views
Can superset and subset be used interchangeably?
Is it true that $A \subset B \iff B \supset A$? I have been using both interchangeably in order to save time when Latexing some notes, but this question gave me some pause.
- 661
1
vote
1
answer
62
views
Injection from $\omega$ to set of finite tuples plus one element
Let $U$ be an infinite set and write $\omega$ for $\mathbb{N}$:
$$ A=\bigcup_{n>0}\{f:n\to U \ f \text{ is injective}\}$$
That is, $f\in A$ is of the form $(i_0,...,i_n)$ for $i_j\in U,j\leq n$ and ...
- 75
1
vote
0
answers
32
views
Existence and uniqueness of the equivalence closure
Given a relation $R \subseteq B \times B $, show the existence and uniqueness of the closure of R under the properties that define an equivalence relation. Does the order in which the closures of ...
3
votes
1
answer
35
views
Banach Decomposition Theorem from Fixpoint Theorem
Let $A$ be a set. Knowing that every monotone set function $F: \mathcal{P}(A)\to\mathcal{P}(A)$ (in the sense that $X\subseteq Y\subseteq A\implies F(X)\subseteq F(Y)$) has a fixpoint, prove the ...
- 75
0
votes
0
answers
45
views
Monotone set function in a set [closed]
Let $A$ be a set and let $F:\mathcal{P}(A)\to \mathcal{P}(A)$ a monotone function, i.e. if $X\subseteq Y\subseteq A$, then $F(X)\subseteq F(Y)$. Let
$$\mathcal Z:=\{X\subseteq A\mid X\subseteq F(X)\}\...
- 75
0
votes
1
answer
47
views
Understanding the Union Axiom. Proving $x \cup y := \{z: z\in x \lor z\in y\}$ is a set.
Hi guys I'm really new to set theory and I'm trying to well understand the Union Axiom.
First of all, the Union Axiom state the following (at least this is the definition I have):
$$\forall \,x\ \...
- 191
0
votes
1
answer
61
views
Is there a set of functions that span all "nice" functions?
I have been reading as to why there are elementary functions that have non-elementary antiderivatives and I have come to the conclusion that our notion of "elementary" functions is somewhat ...
- 521
1
vote
1
answer
37
views
If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$.
Question:
If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$.
My Working:
If $A\cup B=A$, then we have $B \subset A$.
If $B = \varnothing$, $ax-1\...
- 923
-2
votes
0
answers
75
views
+50
order property vs. antisymmetric property
The definition of order property is well known:for a first-order theory $T$ the order property means that for some first-order formula $\phi(\bar{x},\bar{y})$ linearly orders in $M$ some infinite $\...
- 3,889
0
votes
1
answer
46
views
Image and preimage definition
I got the following very basic question:
Why is an image - in contrast to a preimage - defined by using the existential quantifier?
Let $f\colon A \to B$ be a mapping and $M$ a subset of $A$ and $N$ ...
- 3
1
vote
2
answers
100
views
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ [closed]
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$
Confused on how to do this, any help would be great.
Correction: Accidentally ...
- 37
0
votes
1
answer
69
views
Indexed sets Prove $(\bigcap_iA_i)^c=\bigcup_i A_i^c $
Here i my approach. I stuggle to get the curly brackets in.
Attempt:
$\bigcup_i A_i^c=({x: \exists i \in I, x \in A_i})^c $
$={x: \exists i \in I, x \not \in A_i}$
How can I proceed here? I dont see ...
- 235
1
vote
0
answers
55
views
Show that a monotone function has a fixpoint
Let $F:\mathcal{P}(A)\to\mathcal{P}(A)$ be a monotone function, i.e. $X\subseteq Y\subseteq A$ implies $F(X)\subseteq F(Y)$. Show that it has a greatest fixpoint (i.e. a fixpoint $X$ such that for ...
- 75
2
votes
1
answer
28
views
Set notation iterating two variables over different lengths
How does one interpret the following set notation:
$$
\{(x_i,y_j): i=1,...,4,j=1,...,6\}
$$
- 23
3
votes
1
answer
94
views
Why is there no negative infinity in the extended complex plane?
I'm reading Ravi Agarwal's "Introduction to Complex Analysis". He says this:
It is often convenient to add the element $\infty$ to $\mathbb{C}$. The enlarged set
$\mathbb{C} \cup \{\infty\}$...
- 155
0
votes
0
answers
26
views
Real Analysis Set Theory Related Question
I have no idea what this set would be $$-A = \{ t \in \mathbb{R}: -t \in A \}$$. I'm thinking that it means it's all negative real numbers in the set $-A$. Furthermore, I don't know what $A$ would be.
1
vote
1
answer
31
views
Symmetric difference of a set and its n-th preimage
I have a question about the following statement:
Let $X$ be a set and $f:X\to X$ a map, then for any subset $A\subset X$ and all $n\in\mathbb{N}$
$$A\triangle f^{-n}(A)\subseteq\bigcup_{i=0}^{n-1}f^{-...
- 11
1
vote
0
answers
67
views
Possible Bijection Between Natural and Real Numbers [duplicate]
I'm studying the Cantor diagonal argument showing that there isn't any function $f:\mathbb N \to \mathbb R$ in one-to-one with each other and accepted it.
But, thinking about it for awhile, I thought ...
0
votes
1
answer
86
views
I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… [closed]
enter image description here
I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… as this would not be the case right? As only relations ...
0
votes
0
answers
30
views
List all the elements of $\{C \in \mathcal{P}(\{0,1,2\}) : \{0,1\} \nsubseteq C\}$.
I'm just really confused about what {0,1} not being contained in C would mean. Does it mean that the answer is all the elements of the powerset except for {0,1}, or does it mean the answer is all the ...
- 1
-3
votes
0
answers
79
views
I dont understand the writers confusing use of "Set" as opposed to a "Relation". [closed]
enter image description hereenter image description hereenter image description here
I dont understand the writers confusing use of "Set" as opposed to a "Relation". My only guess ...
- 1
0
votes
1
answer
35
views
Question about a proof that addition from the left preserves the order of ordinals
I found the following proof that ordinal addition from the left preserves strict inequalities (see b)).
I am having trouble understanding the limit stage. The proof uses the inequality
$\gamma + \...
- 975
-4
votes
0
answers
27
views
I have tried proving this but I still couldn't get it [closed]
I was given two distinct sets, A and B. If A is a subset of B, prove that B is not a subset of A and that A is not equal to B.
1
vote
0
answers
38
views
Confusion on Authors use of the word into as opposed to onto
The function G, which is a mapping of B -> A by the definition in the screenshot should be a mapping from B onto A because all members of B would always mapped to A Right?
- 21
0
votes
1
answer
17
views
What type of relation wrt arbitrary elements of a generic set exists between particular (distinct, not-nec unique) elements of that set?
What type of relation wrt ane arbitrary element of a generic (ostensibly non‑ordered) set exists between particular (distinct, not necessarily unique) elements of that set? I.e.(e.g.): $𝑥∈\{𝚡₁,…,𝚡...
1
vote
2
answers
24
views
Proving by induction how many elements are in the $n$-ary cartesian product between the two same sets.
Here's a question that has been bugging me for a while.
Let $A$ be a set such that $A = \{a, b\}$. Then, $A_1 = A$, $\;A_2 = A \times A$, and for $n \in \mathbb{N}$, $A_n = A_{n-1} \times A$. How ...
- 33
1
vote
0
answers
42
views
Prove $A^c \setminus B^c=B \setminus A$ [duplicate]
Prove $A^c \setminus B^c=B \setminus A$
Attempt:
let $A^c = \{ x:x \in U, x \not \in A\}$ and let $B^c = \{ x:x \in U, x \not \in B\}$ and $ B \setminus A =\{x:x \in B, x \not \in A\}$
Dont know how ...
- 235
0
votes
1
answer
54
views
What are the basics for notation used in cardinal arithmetic?
If $S$ and $T$ are sets, which of the following would you say is $T^{S}$?
$T^{S}$ is the set of all functions from $S$ to $T$.
$T^{S}$ is the Cartesian product of $T$ taken $\begin{vmatrix} S \end{...
- 917
1
vote
0
answers
17
views
Possible errors in a proof concerned with irreflexivity and asymmetry
I'm trying to prove that asymmetric relation R would also be irreflexive. My proof is as follows:
Suppose R is not irreflexive. Then a is related to a by R for some a. Then either a is not related to ...
- 43
1
vote
1
answer
39
views
$S$ is any non empty set and $2^S$ is the power set of $S$. True or False for the following
$S$ is any non empty set and $2^S$ is the power set of $S$.
let $S = \{ 1,2 \}$. Then the power set $P(S) = \{\{1,2\}, \{1\}, \{2\}, \emptyset \}$ where P(S) contains $2^2=4$ elements.
True or False ...
- 235
3
votes
2
answers
55
views
Prove or disprove. $\bigcup_{i\in I} \bigcap_{j\in J} C_{i,j} = \bigcap_{j\in J} \bigcup_{i\in I} C_{i,j}.$ [duplicate]
Let $\{ C_{i,j} : i\in I \text{ and } j\in J \}$ be a family of sets. Assume the set $I$ (of indices $i$) is arbitrary, non-empty, and non-enumerable. Similarly, assume the set $J$ (of indices $j$) is ...
- 13.9k
0
votes
0
answers
22
views
Notation regarding a set with two disjoint properties
I'm trying to write the solution to the following equation in set builder notation
$$\max\{|x_1|,|x_2| \}=1$$ So far, I've come up with:
$$\big\{ (x_1,x_2) \in \mathbb{R}^2: \big(|x_1|=1, -1\le x_2 \...
1
vote
0
answers
29
views
How to think about distence or closeness between various intersecting and non-intersecting sets?
Edit: I want to add more context. I'm interested in toying around with mathematical modeling of something, where it is helpful to represent the things I'm modeling with sets whose elements are points. ...
- 87
1
vote
1
answer
26
views
Give an example of a relation $R$ on the given set $A$ that has the properties described: $A=\mathbb Q$, $R$ is both symmetric and anti-symmetric
$A=\mathbb Q$, $R$ is both symmetric and anti-symmetric
What I have is "$R = \{(a, b)~ |~ a, b \in \mathbb Q~ ,~ a = b\}$". I just want to double check if my logic is correct and if not, ...
- 13
1
vote
0
answers
38
views
For any three relations prove the $ (T \circ S) \circ R = T \circ (S \circ R) $ [duplicate]
Prove: For any three relations $R \subset W \times X$, $S \subset X \times Y$, and $T \subset Y \times Z$, $(T \circ S) \circ R = T \circ (S \circ R)$.
(image link)
Attempted Proof: suppose $ (a,b) ...
- 235
0
votes
0
answers
37
views
Notation: x randomly chosen with weights from set S
I have implemented $\epsilon$-greedy policy in the context of reinforcement learning in Python code:
...
- 1
0
votes
1
answer
54
views
composition relations in Set Theory
I have provided my solution and I see there are subtle differences to those provide in picture. Is my solution equivalent? Which is more rigorously correct?
\begin{align}
(S \circ R)^{-1} & = \...
- 235
1
vote
0
answers
46
views
Kuratowski's definition of ordered pairs: proving $(x,y) = (u,v) \iff x=u \text{ and } y=v$
I'm new to set theory and I need to prove the following:
$(x,y) = (u,v) \iff x=u,y=v$ where $(x,y) = \{\{x\},\{x,y\}\}$ as in Kuratowski's definition of ordered pairs.
Now, I think I got the right to ...
- 191
0
votes
0
answers
23
views
$\overline{F}:A/R\to A/R$ such that $\overline{F}([x]_R)=[F(x)]_R$ uniqueness extremely trivial im confused?
Assume that $R$ is an equivalence relation on $A$ and that $F:A\to A$. If $F$ is compatible with $R$, then there exists a unique $\overline{F}:A/R\to A/R$ such that $$\overline{F}([x]_R)=[F(x)]_R$$
...
- 170
3
votes
1
answer
299
views
Is this exercise from Tao's Analysis 1 erroneous?
On page 68 of the fourth edition of Tao's Analysis 1, is Exercise $3.5.12$, the first part of which I believe is erroneous. The exercise is stated as follows:
(Note: $n++$ refers to the successor of $...
- 435
0
votes
0
answers
39
views
Injective function from N (naturals) to Q?
In this video (https://www.youtube.com/watch?v=Vp570S6Plt8) at 11:17, the speaker says that their argument proves that the size of infinity of Q is less than the size of infinity of N. This makes ...
- 1
1
vote
1
answer
38
views
Resources for "Bell Machover"
Recently, I've been reading through A Course In Mathematical Logic by John Bell and Moshé Machover. However, it's not always the easiest book to understand. What might be some good supplements to have ...
- 91
0
votes
1
answer
30
views
Proving $C = \{ x \in \mathbb R^n\colon Ax = b\}$is closed, for some $A \in \mathbb R^{m \times n}$ and $b \in \mathbb R^m$ s.t. system is feasible.
Consider the set
$$ C = \{ x \in \mathbb R^n\colon Ax = b \}, $$
where $A$ is some matrix in $\mathbb R^{m \times n}$ and $b \in \mathbb R^m$ such that the system is feasible. I aim to prove such set ...
- 1,171